6. Algoritmos de búsqueda y ordenación
En muchas situaciones de programación es necesario repetir ciertos procedimientos hasta alcanzar un punto en que no se puede o no se desea continuar. Esta repetición de tareas puede llevarse a cabo básicamente de dos maneras diferentes: la iteración y la recursión. Como se supone que en cada repetición se procesa un estado diferente de cosas -sin lo cual el proceso tendería al infinito-, ambos métodos presentan también alguna forma de control de fin de tarea. La idea básica en un algoritmo iterativo es que la repetición de la tarea se controla desde afuera. Se ejecuta un conjunto de acciones en forma completa, se verifica la condición de salida y si es necesario se vuelve a ejecutar el conjunto de acciones en forma completa. El orden en que se ejecuta y evalúa determina que el algoritmo sea de evaluación previa (primero se evalúa la condición de salida y luego se ejecutan las acciones) o de evaluación posterior (primero se ejecutan las acciones y luego se evalúa el resultado). En ambos casos, sin embargo, el control de las repeticiones es exterior al grupo principal de acciones. En un algoritmo recursivo, en cambio, la tarea se controla desde adentro. Se comienza a ejecutar un conjunto de acciones, pero antes de finalizar se evalúa si se ha llegado a la condición de salida; si no es así, se continúa ordenando una nueva ejecución del mismo conjunto de acciones. Finalmente se concluye con la tarea iniciada. Dicho en otros términos, el procedimiento se llama repetidas veces a sí mismo, y el control de esas llamadas forma parte del grupo principal de acciones. Por otra parte, si bien hay problemas que se resuelven más directamente en forma iterativa y otros que son más naturalmente recursivos, ambas técnicas son compatibles e intercambiables, por lo que todo algoritmo recursivo puede transformarse en iterativo y viceversa.
Algoritmos De Búsqueda Cuando se trata de buscar un valor en un arreglo ordenado de datos, el algoritmo de búsqueda binaria es el más frecuentemente utilizado. La idea central de este algoritmo es comparar el elemento ubicado en el lugar central del arreglo con el valor buscado. Si el elemento central es igual al valor buscado la búsqueda finaliza con éxito. Si no es así, puede ocurrir o bien que el elemento central sea mayor que el buscado -en cuyo caso el elemento coincidente debe estar en la mitad inferior del arreglo- o bien que sea menor -y el elemento coincidente se encuentra en la mitad superior. En ambos casos se prosigue la búsqueda en la mitad que corresponde, si es que quedan elementos en esa dirección, o bien se finaliza la búsqueda sin éxito, en caso contrario. Existe naturalmente una solución recursiva, ya que si el valor buscado no es hallado en la posición del centro se repite el mismo procedimiento con una de las mitades del arreglo, y así hasta que se encuentre el valor o no queden más "mitades". Compárese esto con el problema de las bolillas dentro de las cajas, en el cual la "bolilla blanca" sería el valor buscado y la "caja interior" sería la mitad que se debe seguir examinando. En ocasiones es necesario determinar no sólo si el valor buscado se halla en el arreglo, sino además saber en qué posición está (o debería estar, si es que no existe). Por ejemplo, si se desea insertar un nuevo valor en un arreglo ordenado, una solución eficaz es "buscar" el valor en el arreglo (aunque se sepa de antemano que no se encuentra) para determinar la posición correcta en la que debe ser insertado. En esos casos se debe informar por algún medio (generalmente un puntero pasado como parámetro o una variable global) cuál es la posición lógica del elemento buscado dentro del arreglo.
Ejemplo de un Algoritmo de Búsqueda A modo de ejemplo se presenta una versión de la función int busbin (int *vec, unsigned tam, int val, unsigned *ord); Ésta realiza una búsqueda binaria del elemento val en el vector de enteros apuntado por vec de tam elementos y deja en la memoria apuntada por ord la posición lógica que tiene (o debería tener) el elemento buscado. Retorna 1 si el elemento es hallado o 0 en caso contrario. Para calcular el elemento mitad del vector se desplaza tam un bit a la derecha, lo que equivale a dividirlo en dos, pero resulta mucho más rápido para el procesador que la operación de división. int busbin (int *vec, unsigned tam, int val, unsigned *ord) {if (!(vec && tam && ord)) return 0; unsigned mitad = tam >> 1; // Divide tam en 2 desplazando un bit a la// derecha. Es más rápido que tam / 2. if (vec [mitad] == valor) { *ord += mitad; return 1; } if (vec [mitad] < valor) { mitad++; *ord += mitad; vec += mitad; tam -= mitad; } else tam = mitad; return tam? busbin (vec, tam, va, ord): 0;}
Algoritmos De Ordenacion Se presentan aquí dos métodos muy utilizados para obtener el ordenamiento de un conjunto de datos: el algoritmo de ordenamiento por inserción y el algoritmo conocido como quick sort (ordenamiento rápido). Estos dos algoritmos son ilustrativos, además, porque el algoritmo de ordenamiento por inserción es esencialmente iterativo, mientras que el algoritmo de quick sort es esencialmente recursivo. A continuación se comentan las características de ambos algoritmos para ordenar en forma ascendente los valores dentro de un vector en memoria. Siguiendo este ejemplo, para obtener ordenamientos descendentes basta cambiar el sentido de las comparaciones por desigualdad, y para otro tipo de soporte de datos (archivos en disco, por ejemplo) los cambios se referirán principalmente al modo de leer y escribir los datos.
Ordenación por Inserción: La idea central de este algoritmo es recorrer secuencialmente y hacia delante el conjunto de datos comparando cada elemento con el anterior. Si el elemento actual es igual o mayor que el anterior entonces ese par de datos se encuentra en la secuencia correcta, por lo que no hay que modificar nada. Si, en cambio, el actual es menor que el anterior, significa que el actual está fuera de secuencia, por lo que debe ser insertado en el lugar correcto entre los valores que han quedado atrás. Una vez resuelta esta cuestión, se repite el proceso con el elemento siguiente del conjunto hasta que no haya más elementos. Dos características surgen directamente de esta descripción:
- Si hay que comparar cada valor con el anterior, entonces se debe comenzar el proceso por el segundo elemento, ya que es el primero en tener uno anterior.
- Si se van reinsertando correctamente "hacia atrás" los valores a medida que se avanza (o si se avanza sin reinsertar porque no es necesario), entonces los elementos anteriores al actual ya están ordenados.
La tarea de reinsertar un elemento "hacia atrás" cuando se descubre que está fuera de secuencia es accesoria y puede ser realizada por una función auxiliar. Esta función auxiliar se puede implementar de varias maneras, pero todas ellas deben partir de la certeza de que ese subconjunto de elementos ya está ordenado. A continuación se presentan una implementación de la función principal int *ordins (int *vec, unsigned tam); y dos implementaciones alternativas de la función auxiliar void insertar (int *ult, unsigned tam); La función ordins () ordena por inserción el vector de enteros apuntado por vec de tamaño tam y retorna vec, mientras que ambas versiones de insertar (), ubican el valor contenido en el elemento apuntado por ult entre los tam elementos ordenados que han quedado atrás. Ambas funciones auxiliares son estáticas -esto es, de uso "privado" dentro del módulo donde están insertas- ya que la tarea que realizan es subsidiaria y dependiente de la función ordins (). int *ordenar (int *vec, unsigned tam) {int *ant = vec, *act = vec + 1;unsigned i;for (i = 1; i < tam; i++, ant++, act++) if (*act < *ant) insertar (act, i);return vec;}
La primera versión de insertar () es típicamente iterativa y efectúa una especie de rotación de los valores de los elementos. Primeramente resguarda en la variable local auxiliar aux el valor del ítem a reinsertar -que se encuentra en *ult- y a continuación procede a mover una posición hacia delante cada uno de los elementos anteriores a aux retrocediendo en el vector hasta que no hay más elementos o encuentra uno que no es mayor que aux. Finalmente reinserta el valor de aux en el lugar donde se encontraba el último elemento removido. static void insertar (int *ult, unsigned tam) {int *ant = ult – 1; // ant apunta siempre al ítem anterior a ult. int aux = *ult; // aux contiene el valor a reinsertar. do *(ult–) = *(ant–); // Evaluación posterior porque ya se sabe que el while (–tam && aux < *ant); // primer ítem anterior a ult es mayor que *ult. *ult = aux; // Restituye el valor de aux en la última} // posición vacante.
La segunda versión de insertar () recurre a su vez a la función auxiliar de búsqueda binaria busbin (), con el fin de determinar la posición que debe ocupar el elemento *ult entre los anteriores a ult. Para ello inicializa las variables globales estáticas valor y orden, que son utilizadas por busbin () para conocer el elemento buscado e informar su posición. Obsérvese que para que esta versión de insertar () pueda acceder a otras funciones y variables globales estáticas, debe estar incluida a su vez en el mismo módulo de código que ellas. Luego de obtener a través de busbin () el lugar que debe ocupar el nuevo ítem, calcula la cantidad de elementos a desplazar y -como la primera versión- mueve una posición hacia delante cada uno de los elementos anteriores a ult retrocediendo en el vector hasta llegar a la posición correcta. Ya no necesita comparar y contar puesto que, al conocer la cantidad de elementos a desplazar, sólo necesita contar. Finalmente reinserta el valor de aux en el lugar donde estaba el último elemento removido. static void insertar (int *ult, unsigned tam) {unsigned _ord = 0; // _ord contendrá la posición correcta de *ult. int *ant = ult – 1; // ant apunta al ítem anterior a ult. valor = *ult; // Inicializa las variables globales estáticas orden = &_ord; // que utilizará busbin (). if (–tam) // Si hay más de un elemento llama a busbin () busbin (ant – tam, tam); // con la dirección inicial del vector. tam -= _ord; // Descuenta de tam la posición del nuevo ítem. do *(ult–) = *(ant–); // Desplaza la cantidad necesaria de elementos while (tam–); // hacia delante y restituye el valor de valor *ult = valor; // en la última posición vacante.}
La ventaja de la primera versión es que es autónoma, ya que no depende de otras funciones ni variables globales estáticas, por lo que puede ser incluida en cualquier módulo de código. Presenta sin embargo el inconveniente de que tiene que comparar una y otra vez cada elemento del arreglo para encontrar su posición correcta. En vectores de gran tamaño esto puede resentir en forma notable la eficiencia. La segunda versión, en cambio, soluciona el problema de las comparaciones sucesivas utilizando un algoritmo de búsqueda más eficiente, aunque esto la obliga a convivir en el mismo módulo con otras funciones y variables globales estáticas de las cuales depende.
Algoritmo de Quick Sort: La idea central de este algoritmo es la siguiente: si se toma un conjunto de elementos desordenados y se ubica uno cualquiera de ellos -llamado pivote- en una posición tal que todos los que estén antes sean menores o iguales y todos los que estén después sean mayores, entonces esa posición particular sería la correcta para ese elemento si el conjunto estuviera ordenado. Asimismo se verifica que el conjunto ha quedado dividido en dos partes: en la primera están todos los elementos menores o iguales al pivote y en la segunda todos los mayores. Esto permite aplicar recursivamente el mismo procedimiento en ambas partes del conjunto hasta que éste quede completamente ordenado. La tarea de dividir el conjunto de datos en dos grupos en torno al pivote es accesoria y puede ser realizada por una función auxiliar. Esta función auxiliar se puede implementar de varias maneras, pero todas ellas deben informar de algún modo en qué posición ha quedado ubicado el pivote. Al igual que busbin (), la función qsort () es recursiva, y cada llamada provocará que la función se llame "internamente" a sí misma varias veces. Los valores de los parámetros vec y tam seguramente variarán entre una llamada y otra, ya que son los que definen la parte del arreglo que se ordenará cada vez. Sin embargo, tanto los controles de que los parámetros sean legales como el retorno de la función con la dirección original del vector deben hacerse sólo una vez. Para evitar tener que hacer estos controles redundantes en cada llamada recursiva, la tarea se divide entre dos funciones. La primera está declarada públicamente como int *qsort (int *vec, unsigned tam); No es recursiva y sólo realiza las tareas que deben ser ejecutadas una sola vez: verifica que vec y tam sean legales y llama a la segunda función, que es la que completa la tarea. Si vec o tam son ilegales la función retorna vec sin hacer nada más. La segunda función, definida como void _qsort (int *vec, unsigned tam); Es estática (por lo tanto inaccesible desde fuera del módulo), y es la que realmente lleva a cabo la tarea recursiva de ordenamiento. Recibe los parámetros vec y tam, que varían entre una llamada y otra, pero que tienen siempre valores legales. A continuación se presentan dos pequeños módulos de librería con una versión optimizada de la función: el módulo qsort.h contiene simplemente la declaración, mientras que el módulo qsort.cpp incluye la implementación de la función principal int *qsort (int *vec, unsigned tam); y una implementación de las dos funciones auxiliares int dividir (int *vec, unsigned tam); void _qsort (int *vec, unsigned tam); La función qsort () verifica la validez de los parámetros vec y tam y llama a _qsort () antes de retornar vec. La función _qsort () ordena por el algoritmo de quick sort el vector de enteros apuntado por vec de tamaño tam, llamando a su vez a la función dividir (). Ésta divide los tam elementos del vector apuntado por vec en dos grupos alrededor de un pivote y retorna la cantidad de elementos del primer grupo -que incluye al pivote. Ambas funciones auxiliares son estáticas -esto es, de uso "privado" dentro del módulo donde están insertas- ya que la tarea que realizan es subsidiaria y dependiente de la función qsort ().
7. Verificación y derivación de programas
Conceptos Basicos La definición del significado de un elemento del lenguaje se puede realizar de distintas formas, cada una de las cuales define una semántica diferente del lenguaje. En esta lección se van a introducir los conceptos más importantes de algunas de estas formas semánticas, y se van a tratar más extensamente los conceptos de corrección, verificación y prueba, ya mencionados en la lección.
Semántica: Ahondando en la situación de la introducción anterior sobre la definición del lenguaje pascal, se puede conjeturar que la manera informar de definir el significado de las construcciones del lenguaje es insatisfactoria. El motivo es la falta de precisión con la que se define el significado de dichos conceptos, lo cual deja abierta como posibilidad que dicho significado dependa de la maquina donde se utilice el lenguaje. Otro problema importante es la ambigüedad del lenguaje natural, que permite que distintos implementadotes o programadores entiendan de modo distintos una definición. Acerca de este tema, el lenguaje pascal vuelve a servirnos de ejemplos. Hasta hace no mucho tiempo existía una gran variedad de versiones del mismo, cada una realizada específicamente. Dependiendo del objetivo prioritario que se presenta cubrir al dar el significado de un lenguaje podemos encontrar diversas aproximaciones. Entre todas ellas, las más frecuentemente utilizadas son la sematica operacional, la sematica declarativa y la sematica axiomatica. Veamos a continuación una peque son la sematica operacional, la sematica declarativa y la sematica axiomatica. Veamos a continuación una pequeña introducción a cada una de estas aproximaciones.
Semántica operacional: La semántica operacional define el significado de un lenguaje de programación en términos de los cambios de estado que producen las instrucciones primitivas del lenguaje. Estos cambios no se reflejan directamente en la maquina real, sino en una maquina (virtual) abstracta asociada que sirve como instrumento de conexión con aquella. Expresado de otra forma, podemos decir que la semántica operacional define el significado de un programa en términos del efecto producido por la ejecución paso a paso del mismo, de tal modo que la especificación de las instrucciones del lenguaje mediante instrucciones primitivas de la maquina abstracta es, precisamente, la definición semántica del mismo. A pesar de la aparente simplicidad de este formalismo, este tipo de semántica no describe con igual claridad todo tipo de lenguaje de programación. El motivo es que el mecanismo que emplean los distintos lenguajes de programación para realizar un cómputo no siempre puede expresarse de una manera clara, comprensible y concisa.
Semántica denotacional: La semántica denotacional define unas aplicaciones (funciones) de valoración semántica que asignan a cada construcción denotada tal objeto matemático que modela su significado. Se dice que la construcción denota tal objeto o que este objeto es la denotación de dicha construcción. En otras palabras, la semántica denotacional indica que función matemática se obtiene a la salida ante unas entradas del programa, sin preocuparse de la ejecución paso a paso del programa. Existe una variante de esta semántica que es la semántica algebraica, en la que se utiliza conceptos algebraicos a la hora de modelar el significado de las construcciones. El primer paso a realizar en la definición de la semántica denotacional de un determinado lenguaje es el establecimiento de un dominio semantico al que pertenecerán los resultados obtenidos de la evaluación de las construcciones del lenguaje. Esta evaluación es proporcionada por un conjunto de funciones de significado cuyo dominio esta constituido por el conjunto de construcciones del lenguaje y cuyo rango (o imajen) viene dado por el dominio semantico. Este tipo de semántica dotan de significado a los elementos del lenguaje de una manera mas formal y abstracta, pero sin embargo también necesitan un mayor conocimiento de conceptos matemáticos, que no tienen por que ser básicos ni elementales.
Recursividad: Una función recursiva es una función que se define en términos de si misma., es decir, en su cuerpo aparece alguna aplicación suya. La recursividad es un mecanismo que se usa cuando hay que repetir cierto tratamiento o cálculo pero el número de repeticiones es variable. De hecho ya se han visto definiciones recursivas, el tipo suma permite definir tipos de datos recursivos, como el tipo de lista. La definición del tipo lista permite repetir la adición de elementos a una lista. el numero de adicciones es variable y determina el numero final de elementos de lista.
Iteración: Una instrucción iterativa engloba una secuencia de instrucciones que se escribe una sola vez, pero permite que se ejecute varias veces. Una instrucción iterativa también se llama Bucle. Las instrucciones englobadas suelen denominarse cuerpo del bucle; cada ejecución del cuerpo de un bucle se llama iteración del mismo. Hay varios formatos de bucles que vemos a continuación. Una instrucción LOOP tiene el siguiente formato: LOOP <Instrucción> Su efecto es ejecutar eternamente la instrucción englobada. Sin embargo, puede terminarse la ejecución del bucle si se ejecuta una instrucción especial, formada por la palabra clave EXIT. Obsérvese que la instrucción EXIT debe ir incluida dentro de una instrucción condicional; en caso contrario, el bucle LOOP terminaría su ejecución al llegar a ella, realizando una iteración como mucho. Pero esto no tiene mucho sentido, porque si se hubiera querido realizar una sola ejecución de dichas instrucciones, no se hubieran incluido en una instrucción iterativa. La instrucción EXIT no puede usarse en ninguna de las dos clases de bucles que se exponen a continuación. Una instrucción WHILE tiene el siguiente formato: WHILE <condición>DO <Instrucción> La ejecución de una instrucción WHILE comienza evaluando la condición booleana. Si es cierta, se ejecuta la secuencia de instrucciones y se comienza de nuevo. Si la condición es falsa, la ejecución del WHILE termina y el algoritmo continúa por la instrucción siguiente al bucle. La instrucción FOR tiene el siguiente formato: FOR <variable> IN <subrango>BY<expresión entera>DO <Instrucción> La instrucción FOR usa una variable, llamada variable de índice, que toma distintos valores en las sucesivas ejecuciones del cuerpo. La variable de índice debe ser entera, enumerada o subrango. Los valores que toma la variable de índice se indica mediante un subrango del mismo tipo y un incremento. El subrango se expresa de la manera usual: un valor inicial y un valor final separados por dos puntos. El incremento viene dado por una expresión entera; puede suprimirse, en cuyo caso se supone que es igual a uno. Al comenzar la ejecución del bucle, la variable índice toma el valor inicial del subrango y se evalúa la expresión entera para determinar el incremento. Veamos el resto del comportamiento del bucle cuando el tipo de la variable índice es un subrango entero. Tras cada iteración, el valor del índice se actualiza, sumándose a su valor el incremento. Si el incremento es positivo, solo se realiza la siguiente iteración si el valor de la variable índice es menor o igual que el valor final del subrango; por el contrario, si el incremento es negativo, solo se itera de nuevo cuando su valor es mayor o igual que el valor del final del subrango. Si la variable es enumerada o de un subrango enumerado, el comportamiento del bucle es parecido. Un valor es menor que otro si tiene un ordinal menor. El incremento de un valor enumerado produce otro valor cuyo ordinal es mayor que el inicial en la cantidad expresada por el incremento.
Semantica Axiomatica La semántica axiomatica asociada a cada construcción del lenguaje un axioma lógico que relaciona el estado del computo (valores que tienen las variables utilizadas) antes y después de ejecutar esta construcción. Existen distintas semánticas, axiomatica, de la que la mas conocida es la introducida por el sistema formal de hoare y que es utilizada para definir el significado de lenguaje imperativos (por ejemplo, pascal). El método axiomatico expresa la semántica de un lenguaje de programación asociado al lenguaje una teoría matemática o sistema formal que permita demostrar propiedades de los programas escritos en ese lenguaje. Esta aproximación formal contrasta con el método denotacional mostrando anteriormente, que asocia a cada construcción del lenguaje una denotación (significado) en un intento de encontrar un modelo matemático (colección abstracta de objetos matemáticos) del lenguaje. Un sistema formal puede entenderse como un metalenguaje que pose su propia sintaxis y semántica. Desde el punto de vista sintáctico, es necesario definir una gramática en la que se reflejen las contrucciones validas del sistema formal, normalmente se suele emplear la sintaxis sde la lógica de predicado de primer orden ampliada com. expresiones aritméticas y de teoría de conjuntos. Una vez fijada la sintaxis a emplear, un sistema formal se define mediante un conjunto de axiomas (propiedades ciertas escritas en forma de sentencias logicas) que expresen las propiedades de las construcciones básicas y un conjuntos de reglas de inferencias (forma de deducir una propiedades de otras) que permitan deducir las propiedades de construcciones mas complejas. Las definiciones de sistemas formales para lenguajes funcionales suele hacerse fundamentalmente para demostrar propiedades que tiene que ver con el tipo de una expresión y de las subexpresiones que la componen.
Diseño De Algoritmos Recursivos Las definiciones recursivas pueden resultar sorprendentes a primera vista.Incluso puede dar lugar a funciones que nunca terminen (inútiles como algoritmos), Sin embargo, usadas juiciosamente son un instrumento potentisimo de diseño de algoritmos. En primer lugar, hay que identificar el proceso repetitivo por realizar. En segundo lugar, hay que considerar que una función recursiva solo es útil si su evaluación termina.
Clasificación Según el número de llamadas recursivas realizadas, se distinguen tres clases: Recursividad lineal: El cuerpo de la función contiene una llamada recursiva. Son las funciones recursivas. Son las funciones recursivas más sencillas. Todas las funciones especificadas en este capitulo son recursivas lineales. Un caso importante de recursividad lineal aparece cuando la expresión más externa del caso recursivo de la función es la misma llamada recursiva. Esta clase de recursividad se llama recursividad de cola.
Recursividad no lineal. El cuerpo de la función contiene varias llamadas recursivas. Lo mas frecuente que contenga dos llamadas recursivas, en cuyo caso se habla de recursividad binaria. Recursividad mutua: Es un caso curioso de recurcion, una función no contienen ninguna llamada recursiva, pero durante la evaluación de su aplicación surgen llamadas recursivas. Auque a primera vista parezca imposible obtenérsete comportamiento, la recursividad puede conseguirse indirectamente si hay dos funciones que se llaman entre si. Otra clasificación basada en el formato de los parámetros de las llamadas recursivas. Recursividad estructural: Las sucesivas llamadas recursivas sobre un dato se hacen siguiendo la estructura recursiva del mismo. En el caso de los elementos enteros, una recurcion estructurar significa que el valor se vaya decrementando en uno. Recurcion bien fundada: Aunque hablando con propiedad, cualquier recursividad esta bien fundada, suele utilizarse este término para aquellas recursividades que no son estructurales. Un ejemplo de función recursiva bien es invertir Entero, donde el parámetro entero se divide entre diez. La primera clasificación dada es útil para decidir si es conveniente usar una definición recursiva o iterativa en los algoritmos imperactivo. La segunda clasificación es útil para decidir el principio de inducción necesaria para necesaria para verificar el algoritmo.
Diseño De Algoritmos Iterativos Cada clase de bucle resulta útil en situaciones diferentes. El bucle FOR se utiliza cuando se conoce el número de iteraciones que se quiere realizar. El bucle WHILE es usado en las otras situaciones en que no se conoce el número de iteraciones. El bucle LOOP es útil cuando puede haber varias condiciones de salida del bucle, situadas en diferentes partes del cuerpo, o cuando la condición de salida no esta al comienzo del bucle. Sin embargo, conocer la instrucción iterativa que mas conviene para un algoritmo es solo el comienzo de la construcción de la instrucción. Es conveniente tener algunas guías para el diseño de algoritmos iterativos. El diseño de un algoritmo iterativo se hace sobre una base distinta de la de uno recursivo. En los algoritmos imperativos se tiene disponible toda la información del problema en las variables. Por esta razón, es útil partir los datos del problema en dos:
- La parte que representa el problema aun no resuelto.
- La parte que representa el problema ya resuelto; es decir, el resultado ya calculado.
Una vez que se han distinguido estas dos partes, el bucle se construye a partir de tres decisiones hechas sobre dicha partición:
- Fijar la situación inicial. El problema a resolver se encuentra en los parámetros de entrada o de entrada/salida; si estos datos quieren modificarse durante el algoritmo, deben copiarse en variables auxiliares. también hay que dar un valor inicial a las variables que representan la solución vacía.
- Formar el cuerpo del bucle. Para ello puede usarse un razonamiento parecido al recursivo. Se supone, por generalidad, que la iteración se encuentra en un estado intermedio. Debe entonces determinarse que hacer en una iteración para avanzar en la resolución del problema.
- Determinar la condición de terminación. Corresponde a la situación en que se ha hallado la solución completa. Esta parte esta totalmente relacionada con la elección de la instrucción iterativa. Según la forma de la iteración, se elige un bucle FOR, WHILE o LOOP, como se describió antes.
Normalmente, la terminación del bucle puede especificarse de forma sencilla, incluso en casos relativamente complicados. Por ejemplo, cuando se tiene un bucle WHILE con una condición compuesta es posible que pueda usarse la técnica del centinela para obtener una especificación más sencilla. Algo con lo que hay que tener especial cuidado es la terminación de los bucles. Esta es fácil de determinar en un algoritmo recursivo porque basta con tomar una medida de los parámetros y comprobar que disminuye en cada llamada recursiva, de forma que se acerca al tamaño de los casos básicos. En una solución iterativa se razona igual, pero la tarea es algo mas complicada porque el control del proceso repetitivo no tiene parámetros, sino que se hace a partir de la información contenida en las variables.
8. Análisis Foda
Introducción: El análisis FODA es una herramienta que permite conformar un cuadro de la situación actual de la empresa u organización, permitiendo de esta manera obtener un diagnóstico preciso que permita en función de ello tomar decisiones acordes con los objetivos y políticas formulados. El término FODA es una sigla conformada por las primeras letras de las palabras Fortalezas, Oportunidades, Debilidades y Amenazas (en inglés SWOT: Strenghts, Weaknesses, Oportunities, Threats). De entre estas cuatro variables, tanto fortalezas como debilidades son internas de la organización, por lo que es posible actuar directamente sobre ellas. En cambio las oportunidades y las amenazas son externas, por lo que en general resulta muy difícil poder modificarlas.
- Fortalezas: son las capacidades especiales con que cuenta la empresa, y por los que cuenta con una posición privilegiada frente a la competencia. Recursos que se controlan, capacidades y habilidades que se poseen, actividades que se desarrollan positivamente, etc.
- Oportunidades: son aquellos factores que resultan positivos, favorables, explotables, que se deben descubrir en el entorno en el que actúa la empresa, y que permiten obtener ventajas competitivas.
- Debilidades: son aquellos factores que provocan una posición desfavorable frente a la competencia. recursos de los que se carece, habilidades que no se poseen, actividades que no se desarrollan positivamente, etc.
- Amenazas: son aquellas situaciones que provienen del entorno y que pueden llegar a atentar incluso contra la permanencia de la organización.
Análisis: El Análisis FODA es un concepto muy simple y claro, pero detrás de su simpleza residen conceptos fundamentales de la Administración. Intentaré desguazar el FODA para exponer sus partes fundamentales. Tenemos un objetivo: convertir los datos del universo (según lo percibimos) en información, procesada y lista para la toma de decisiones (estratégicas en este caso). En términos de sistemas, tenemos un conjunto inicial de datos (universo a analizar), un proceso (análisis FODA) y un producto, que es la información para la toma de decisiones (el informe FODA que resulta del análisis FODA). Sostengo que casi cualquier persona puede hacer un análisis FODA. Digo casi porque esa persona tiene que tener la capacidad de distinguir en un sistema:
- Lo relevante de lo irrelevante
- Lo externo de lo interno
- Lo bueno de lo malo
Parece fácil, ¿verdad? Pongámoslo en otras palabras: el FODA nos va a ayudar a analizar nuestra empresa siempre y cuando podamos responder tres preguntas: Lo que estoy analizando, ¿es relevante? ¿Está fuera o dentro de la empresa? ¿Es bueno o malo para mi empresa? Estas tres preguntas no son otra cosa que los tres subprocesos que se ven en el proceso central del dibujo de arriba. Pasemos a explicar: La relevancia es el primer proceso y funciona como filtro: no todo merece ser elevado a componente del análisis estratégico. Es sentido común ya que en todos los órdenes de la vida es fundamental distinguir lo relevante de lo irrelevante. En FODA este filtro reduce nuestro universo de análisis disminuyendo nuestra necesidad de procesamiento (que no es poca cosa). Ejemplos: dudosamente sea una ventaja comparativa el sistema de limpieza de baños de una petroquímica, o el color de los monitores, o si el papel que se usa es carta o A4. Parece tonto, pero es increíble la cantidad de veces que a los seres humanos nos cuesta distinguir lo principal de lo accesorio, ya sea en una discusión, una decisión o donde sea. Claro que la relevancia de algo depende de dónde estemos parados, y este concepto de relatividad es importante. La higiene de los baños puede ser clave en un Hospital o un Hotel. El orden en el que se hacen los pasos al efectuar una compraventa no es tan importante como los pasos que toman los bomberos para apagar un incendio. La disciplina y la autoridad formal son dejadas de lado en muchas empresas de la "Nueva Economía"… pero a un ejército en batalla eso puede costarle la vida. Es por eso que quien hace un análisis FODA debe conocer el negocio (ni más ni menos que saber de lo que está hablando). Filtrados los datos sólo nos queda clasificarlos. Aplicando el sentido común, podemos construir una matriz con dos dimensiones (dentro/fuera, bueno/malo):
Positivas | Negativas | |
Exterior | Oportunidades | Amenazas |
Interior | Fortalezas | Debilidades |
Quien haya inventado el Análisis FODA eligió para cada intersección una palabra: así la intersección de "bueno" y "exterior" es una oportunidad, mientras que las cuestiones "positivas" del "interior" de nuestra empresa son una fortaleza, y así sucesivamente. Distinguir entre el adentro y el afuera de la empresa a veces no es tan fácil como parece. Es fácil decir que desde el punto de vista de la Ferrari, M. Schumager es una fortaleza (interna), y que si M. Hakkinen se queda sin empleo en su escudería, será una Oportunidad (externa) para la Ferrari. Pero el control de un recurso escaso (petróleo) o un proveedor exclusivo están físicamente fuera de mi empresa… y sin embargo son Fortalezas. La clave está en adoptar una visión de sistemas y saber distinguir los límites del mismo. Para esto hay que tener en cuenta, no la disposición física de los factores, sino el control que yo tenga sobre ellos. Recordando una vieja definición de límite: lo que me afecta y controlo, es interno al sistema. Lo que me afecta pero está fuera de mi control, es ambiente (externo). Sólo nos queda la dimensión positivo/negativo, que aparentemente no debería ofrecer dificultad, pero hay que tener cuidado. El competitivo ambiente de los negocios está lleno de maniobras, engaños, etc. En la Segunda Guerra Mundial, el Eje estaba feliz de que el desembarco de los Aliados fuera en Calais, porque tenía muchas fortalezas en ese caso. Pero el día D fue en Normandía y por eso hoy el mundo es lo que es. Las circunstancias pueden cambiar de un día para el otro también en el interior de la empresa: la Fortaleza de tener a ese joven y sagaz empleado puede convertirse en grave Debilidad si se marcha (y peor si se va con la competencia). Y la Debilidad de tener a un empleado próximo a jubilarse y a quien le cuesta adaptarse a las nuevas tecnologías puede revelarse como Fortaleza demasiado tarde… cuando se retira y nos damos cuenta de que dependíamos de él porque era el único que sabía "dónde estaba todo" y "cómo se hacen las cosas". La sagacidad del empresario debe convertir las Amenazas en Oportunidades y las Debilidades en Fortalezas. Ejemplos: Asociarnos con nuestra competencia de toda la vida para enfrentar a un enemigo más pesado; pasar a un empleado desestructurado y extrovertido de una tarea organizativa que hace mal, a la línea de fuego de atención al público. Las posibilidades son muchas. Y esos son los tres pasos necesarios para analizar la situación actual de la organización mediante el Análisis FODA.
El Análisis FODA de este trabajo: Fortaleza: Los conceptos que se nos encomendaron investigar, están desarrollados de forma amplia y lógica. Tiene un contenido y una presentación al nivel de los que significa ser estudiante universitario de un 7mo cuatrimestre de Ing. En Sistemas. Continuidad y constancia de la estructura, calidad y cantidad de contenido que los demás trabajos entregados, a demás de mejoras considerables, lo cual nos garantiza obtener calificaciones similares o superiores a las ya obtenidazas de referidos trabajos.
Oportunidades: Debido a las mejoras realizadas al mismo y una mejor coordinación y participación de los integrantes del grupo este se concluirá en menor tiempo y así podremos completar el procedimiento correcto de entrega de trabajos de esta materia.
Debilidades: A causa de la dificultad para conseguir la información solicitada algunos de los conceptos relacionados con los problemas, tipos, etc. No se encuentran en nuestro trabajo.
Amenazas: Que las debilites de nuestro trabajo influyan considerablemente en la evaluación del mismo provocando que las expectativas y el esfuerzo realizados por los que participamos en el mismo no lleguen a cumplirse.
Luego de realizar este trabajo hemos visto como los algoritmos son una de las herramientas más complejas y aplicables en el área de la informática y el mundo de los computadores. Pudimos comprobar que mientras más potente, completo y eficiente es el computador o la aplicación que corre sobre el mismo mas grande, complejo y exacto es el algoritmo que utiliza. Las técnicas de desarrollo de algoritmos nos permiten encontrar la mejor solucion a los problemas que se nos presentan y deben ser solucionados por el computador, estas técnicas están orientadas para utilizarse en cada uno de los niveles de complejidad y variedad o alternativas para las cuales se aplican los algoritmos. Un algoritmo es el conjunto de operaciones y procedimientos que deben seguirse para resolver un problema, es por ellos que debemos estudiarlos y conocerlos.
Correa Uribe, Guillermo. "Desarrollo de Algoritmos y sus aplicaciones", Editora MacGraw – Hill Inc. USA, III Edición. Abril/1992, Colombia. pp. 251. Gálvez, Javier. Gonzáles, Juan. "Algorítmica, Análisis y Diseño de Algoritmos", Editora RA-MA (Addison-Wesley Iberiamericana), II Edición. Septiembre/1993, USA. pp 502. Matías, Cristian "Manual de Informática Educativa", Editora Taller. 2da. Edición. Julio/1999. Sto. Dgo. R.D. pp 260. Sean, James A. "Análisis y Diseño de Sistemas de Información", Editora MacGraw – Hill Inc. USA, 2 ta. Edición. Diciembre/1998, México. pp 941. World Wide Wed: www.altavista.com www.elrincondelvago.com www.aulaclick.com
Autor:
Ing. Domingo de los Santos.
Ingeniero en Sistemas.
| Página siguiente |