Algoritmos computacionales

Indice1. Introducción 2. Marco Historico 3. Generalidades 4. Análisis De Algoritmos 5. Técnica de diseño de algoritmos 6. Algoritmos de búsqueda y ordenación 7. Verificación y derivación de programas 8. Análisis Foda 9. Conclusión 10. Bibliografía

1. Introducción

En el siguiente trabajo pretendemos presentar una serie de concepto y definiciones propios del estudio de los Algoritmos, su análisis y diseño. En el mismo podremos encontrar los conceptos de algoritmo y algunos de sus componentes, análisis y diseño. También veremos los diferentes tipos de formas y tamaños o medidas en que se pueden almacenar y representar los datos y estructuras en un algoritmo o programa. En ese mismo orden encontraremos las diferentes técnicas para diseñarlos como son el método de la fuerza bruta, el voraz, divide y vencerás, programación dinámica, de vuelta atrás, entre otros. De igual forma podremos ver las definiciones y algunas características, reglas, normas, tipos de algoritmos de búsqueda y ordenación así como sus aplicaciones. Finalmente veremos los que es la verificación y derivación de programas, donde daremos los conceptos básicos de semántica y sus tipos haciendo mayor énfasis en la semántica axiomática, la recursividad e iteración, los diseños de estos últimos, así como los típicos ciclos utilizados en algoritmos y programas y los paso a tener en cuenta al momento de desarrollar un algoritmo iterativo o recursivo.

Justificacion Es importante el estudio y conocimiento de lo que hoy conocemos como Algoritmos Computacionales, que desde su aparición hasta nuestros días es, y seguirá siendo; vital para el desarrollo de aplicaciones para computadoras y el manejo y dominio de la lógica de programación para resolver problemas.

Motivación Como estudiantes de la Facultad de Ciencias y Tecnología " Escuela de Informática y Computación " de la Universidad Dominicana Organización y Métodos O&M con aspiraciones de iniciarnos como Ingeniero en Sistemas y Computación. Con el objetivo inmediato de aprobar con los mejores meritos la asignatura de Algoritmos Computacionales.

Objetivos General : Posibilitar la estudiante alcanzar una visión sistemática de lo que conocemos sobre Los Algoritmos Computacionales. Específicos : Introducir los conceptos propios sobre Algoritmo, su importancia en el mundo de las aplicaciones para computadoras y el manejo de lógica de programación.

• Proporcionar una idea de su uso.
• Visualizar sus ventajas e importancia.
• Definir sus tipos y variantes.
• Proporcionar conceptos sobre su análisis y diseño.
• Proporcionar concepto sobre las técnicas de diseño.
• Desglosar sus variantes (ordenación, búsqueda, etc. ).

2. Marco Historico

Un algoritmo es un conjunto de operaciones y procedimientos que deben seguirse para resolver un problema. La palabra algoritmo se deriva del nombre latinizado del gran Matemático Árabe Mohamed Ibn Al Kow Rizmi, el cual escribió sobre los años 800 y 825 su obra Quitad Al Mugabala, donde se recogía el sistema de numeración hindú y el concepto del cero. Fue Fibinacci, el que tradujo la obra al latín y el inicio con la palabra: Algoritmi Dicit. El lenguaje algorítmico es aquel por medio al cual se realiza un análisis previo del problema a resolver y encontrar un método que permita resolverlo. El conjunto de todas las operaciones a realizar y e orden en que se deben efectuarse, se le denomina algoritmo. Es un método para resolver un problema mediante una serie de datos precisos, definidos y finitos.

3. Generalidades

El programador de computadoras es ante que nada una persona que resuelve problemas, por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. A la metodología necesaria para resolver problemas mediante programas se denomina Metodología de la Programación. El eje central de esta metodología es el concepto, ya tratado, de algoritmo. Un algoritmo es un método para resolver un problema. Aunque la popularización del término ha llegado con el advenimiento de la era informática, algoritmo proviene de Mohammed al-Khowarizmi, matemático persa que vivió durante el siglo IX y alcanzo gran reputación por el enunciado de las reglas para sumar, restar, multiplicar y dividir números decimales; la traducción al latín del apellido de la palabra algorismus derivo posteriormente en algoritmo. Euclides, el gran matemático griego (del siglo IV antes de Cristo) que invento un método para encontrar el máximo común divisor de dos números, se considera con Al-Khowarizmi el otro gran padre de la algoritmia (ciencia que trata de los algoritmos). El profesor Niklaus Wirth, inventor de Pascal, Modula-2 y Oberon, titulo uno de sus mas famosos libros, Algoritmos + Estructuras de Datos = Programas, significándonos que solo se puede llegar a realizar un buen programa con el diseño de un algoritmo y una correcta estructura de datos. Esta ecuación será de una de las hipótesis fundamentales consideradas en esta obra. La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto. Los pasos para la resolución de un problema son:

1. Diseño de algoritmo, que describe la secuencia ordenada de pasos que conducen a la solución de un problema dado. (Análisis del problema y desarrollo del algoritmo).
2. Expresar el algoritmo como un programa de lenguaje de programación adecuado. (Fase de codificación.)
3. Ejecución y validación del programa por la computadora.

Para llegar a la realización de un programa es necesario el diseño previo de algoritmo, de modo que sin algoritmo no puede existir un programa. Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que lo ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo. Así, por ejemplo, en una analogía con la vida diaria, una receta de un plato de cocina se puede expresar en español, ingles o francés, pero cualquiera que sea el lenguaje, los pasos para la elaboración del plato se realizaran sin importar el idioma del cocinero. En la ciencia de la computación y en la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente. Dada la importancia del algoritmo en la ciencia de la computación, un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. En esencia, la solución de un problema se puede expresar mediante un algoritmo.

Características de los Algoritmos: Las características fundamentales que debe cumplir todo algoritmo son:

• Un algoritmo debe ser preciso e indicar el orden de realización de cada paso.
• Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.
• Un algoritmo debe ser finito. Si se sigue un algoritmo se debe terminar en algún momento; o sea, debe tener un numero finito de pasos.

La definición de un algoritmo debe definir tres partes: Entrada, Proceso y Salida. En el algoritmo de receta de cocina citado anteriormente se tendrá: Entrada: ingrediente y utensilios empleados. Proceso: elaboración de la receta en la cocina. Salida: terminación del plato (por ejemplo, cordero).

Ejemplo de Algoritmo: Un cliente ejecuta un pedido a una fábrica. Esta examina en su banco de datos la ficha del cliente; si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario rechazara el pedido. Redactar el algoritmo correspondiente. Los pasos del algoritmo son:

1. inicio
2. leer el pedido
3. examinar la ficha del cliente
4. si el cliente es solvente aceptar pedido; en caso contrario, rechazar pedido
5. fin

Diseño del Algoritmo: En la etapa de análisis del proceso de programación se determina que hace el programa. En la etapa de diseño se determina como hace el programa la tarea solicitada. Los métodos mas eficaces para el proceso de diseño se basan en el conocido por Divide y Vencerás, es decir, la resolución de un problema complejo se realiza dividiendo el problema en sub problemas y a continuación dividir estos sub problemas en otros de nivel mas bajo, hasta que pueda ser implementada una solución en la computadora. Este método se conoce técnicamente como diseño descendente (Top Down) o modular. El proceso de romper el problema en cada etapa y expresar cada paso en forma más detallada se denomina refinamiento sucesivo. Cada sub programa es resuelto mediante un modulo (sub programa) que tiene un solo punto de entrada y un solo punto de salida. Cualquier programa bien diseñado consta de un programa principal (el modulo de nivel mas alto) que llama a sub programas (módulos de nivel mas bajo) que a su vez pueden llamar a otros sub programas. Los programas estructurados de esta forma se dice que tienen un diseño modular y el método de romper el programa en módulos más pequeño se llama Programación Modular. Los módulos pueden ser planeados, codificados, comprobados y depurados independientemente (incluso por diferentes programadores) y a continuación combinarlos entre si. El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:

• programar modulo.
• Comprobar el modulo.
• Si es necesario, depurar el modulo.
• Combinar el modulo con los módulos anteriores.

El proceso que convierte los resultados del análisis del problema en un diseño modular con refinamiento sucesivo que permitan una posterior traducción al lenguaje se denomina diseño de algoritmo. El diseño del algoritmo es independiente del lenguaje de programación en el que se vaya a codificar posteriormente.

4. Análisis De Algoritmos

Recursos De Computadores Y Complejidad Algoritmo: Conjunto de reglas para resolver un problema. Su ejecución requiere unos recursos. Un algoritmo es mejor cuantos menos recursos consuma, su facilidad de programarlo, corto, fácil de entender, robusto, etc. Criterio empresarial: Maximizar la eficiencia. Eficiencia: Relación entre los recursos consumidos y los productos conseguidos. Recursos consumidos: Tiempo de ejecución. Memoria principal: Entradas/salidas a disco. Comunicaciones, procesadores, etc. Lo que se consigue: Resolver un problema de forma exacta, forma aproximada o algunos casos. Recursos consumidos: Ejemplo. ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo sencillo? i:= 0 a[n+1]:= x repetir i:= i + 1 hasta a[i] = x Respuesta: Depende.

¿De qué depende? De lo que valga n y x, de lo que haya en a, de los tipos de datos, de la máquina… En general los recursos dependen de: Factores externos.El ordenador donde lo ejecutemos: 286, Pentium III, Cray,… El lenguaje de programación y el compilador usado. La implementación que haga el programador del algoritmo. En particular, de las estructuras de datos utilizadas. Tamaño de los datos de entrada. Ejemplo. Calcular la media de una matriz de NxM.

Contenido de los datos de entrada. Mejor caso. El contenido favorece una rápida ejecución. Peor caso. La ejecución más lenta posible. Caso promedio. Media de todos los posibles contenidos. Los factores externos no aportan información sobre el algoritmo. Conclusión: Estudiar la variación del tiempo y la memoria necesitada por un algoritmo respecto al tamaño de la entrada y a los posibles casos, de forma aproximada (y parametrizada). externos no aportan información sobre el algoritmo. Normalmente usaremos la notación T(N)=…, pero ¿qué significa T(N)? Tiempo de ejecución en segundos. T(N) = bN + c. Suponiendo que b y c son constantes, con los segundos que tardan las operaciones básicas correspondientes. Instrucciones ejecutadas por el algoritmo. T(N) = 2N + 4. ¿Tardarán todas lo mismo? Ejecuciones del bucle principal. T(N) = N+1. ¿Cuánto tiempo, cuántas instrucciones,…? Sabemos que cada ejecución lleva un tiempo constante, luego se diferencia en una constante con los anteriores. Asignación de tiempos, para el conteo de instrucciones. Algunas reglas básicas. Operaciones básicas (+, -, *, :=,…): Una unidad de tiempo, o alguna constante. Operaciones de entrada salida: Otra unidad de tiempo, o una constante diferente. Bucles FOR: Se pueden expresar como una sumatoria, con los límites del FOR. IF y CASE: Estudiar lo que puede ocurrir. Mejor caso y peor caso según la condición. ¿Se puede predecir cuándo se cumplirán las condiciones? Llamadas a procedimientos: Calcular primero los procedimientos que no llaman a otros. Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir. ¿Existe una cota inferior y superior del número de ejecuciones? ¿Se puede convertir en un FOR? El análisis de algoritmos también puede ser a posteriori: implementar el algoritmo y contar lo que tarda para distintas entradas. Ejemplo. Programa "cifras.exe": N= 4, T(4)= 0.1 ms N= 5, T(5)= 5 ms N= 6, T(6)= 0.2 s N= 7, T(7)= 10 s N= 8, T(8)= 3.5 min

¿Qué conclusiones podemos extraer? Análisis a priori: Evitamos la implementación, si el algoritmo es poco eficiente. Podemos hacer previsiones. Podemos comparar con otros algoritmos. Medidas Asintoticas Notación asintótica: El tiempo de ejecución T(n) está dado en base a unas constantes que dependen de factores externos. Nos interesa un análisis que sea independiente de esos factores. Notaciones asintóticas: Indican como crece T, para valores suficientemente grandes (asintóticamente) sin considerar constantes. O(T): Orden de complejidad de T.W (T): Orden inferior de T, u omega de T.Q (T): Orden exacto de T. Orden de complejidad de f(n): O(f) Dada una función f: N ® R+, llamamos orden de f al conjunto de todas las funciones de N en R+ acotadas superiormente por un múltiplo real positivo de f, para valores de n suficientemente grandes. O(f)= { t: N ® R+ / $ c Î R+, $ n0 Î N, " n ³ n0: t(n) £ c·f(n) } Nota: O(f) es un conjunto de funciones, no una función. "Valores de n sufic. Grandes…": no nos importa lo que pase para valores pequeños. "Funciones acotadas superiormente por un múltiplo de f…": nos quitamos las constantes. La definición es aplicable a cualquier función de N en R, no sólo tiempos de ejec.

Propiedades P1. Si f Î O(g) y g Î O(h) entonces f Î O(h). Si f Î W (g) y g Î W (h) entonces f Î W (h) Ej. 2n+1 Î O(n), n Î O(n2) Þ 2n+1 Î O(n2) P2. Si f Î O(g) entonces O(f) Í O(g).

¿Cómo es la relación para los W ? P3. Dadas f y g de N en R+, se cumple: i) O(f) = O(g) Û f Î O(g) y g Î O(f) ii) O(f) Í O(g) Û f Î O(g)

¿La relación de orden entre O(..) es completa? Dadas f y g, ¿se cumple O(f)Í O(g) ó O(g)Í O(f)? P4. Dadas f y g, de N en R+, O(f+g) = O(max(f, g)).W (f+g) = W (max(f+g))

¿Y para los Q (f+g)? ¿Es cierto que O(f – g) = O(max(f, -g))? P5. Dadas f y g de N en R+, se cumple: i) limn¥ ® f(n) Î R+ Þ O(f)=O(g), W (f)=W (g), Q (f)=Q (g) g(n) ii) limn¥ ® f(n) = 0 Þ O(f) Í O(g), W (g) Í W (f) g(n) P5. Ej. ¿Qué relación hay entre O(log2 n) y O(log10 n)? P6. Dadas f y g de N en R+, O(f)=O(g) Û Q (f)=Q (g) Û f Î Q (g) Û W (f)=W (g) P7. Dadas f y g de N en R+, se cumple: i) limn¥ ® f(n) Î R+ Þ O(f) = O(g) g(n) ii) limn¥ ® f(n) = 0 Þ O(f) Ì O(g) g(n) iii) limn¥ ® f(n) = +¥ Þ O(f) É O(g) g(n)

Notación con varios parámetros: En general, el tiempo y la memoria consumidos pueden depender de muchos parámetros. f: Nm ® R+ (f: Nx…m..xN ® R+) Ej. Memoria en una tabla hash. M(B,n, l, k) = kB+l+n+2kn Orden de complejidad de f(n1, n2, …, nm): O(f) Dada una función f: Nm ® R+, llamamos orden de f al conjunto de todas las funciones de Nm en R+ acotadas superiormente por un múltiplo real positivo de f, para valores de (n1, …, nm) suficientemente grandes. O(f)= { t: Nm ® R+ / $ c Î R+, $ n1, n2, .., nm Î N, " k1 ³ n1 , k2 ³ n2 ,..," km ³ nm : t(k1, k2, …, km) £ c·f(k1, k2, …, km) }

De la misma forma, podemos extender los conceptos de W (f) y Q (f), para funciones con varios parámetros. Las propiedades se siguen cumpliendo ® Demostrarlo. Ejemplo. T(N) = T(N, a, b) = a·N + b El tiempo depende del tamaño del problema N, y del tiempo de inicialización b y de ejecución de un paso a. Podemos suponerlos constantes T(N), o variables T(N,a,b). ¿Qué relación hay entre los siguientes órdenes? O(n+m), O(nm) O(n2), O(n+2m)

Notaciones condicionales: En algunos casos interesa estudiar el tiempo sólo para ciertos tamaños de entrada. Ejemplo. Algoritmo de búsqueda binaria: Si N es potencia de 2 el estudio se simplifica.

Orden condicionado de f(n): O(f | P) Dada una función f: N ® R+, y P: N ® B, llamamos orden de f según P (o condicionado a P) al conjunto: O(f | P)= { t: N ® R+ / $ c Î R+, $ n0 Î N, " n ³ n0: P(n) Þ t(n) £ c·f(n) } De igual forma, tenemos W (f | P) y Q (f | P). O(f) = O(f | true). Para cualquier f y g, f Î O(g | false). ¿O(f) « O(f | P)?

Ordenes De Complejidad Uso de los órdenes de complejidad: Dado un tiempo t(n), encontrar la función f más simple tal que t Î O(f), y que más se aproxime asintóticamente. Ejemplo. t(n) = 2n2/5 + 3p /2; t(n) Î O(n2). •Relación de orden entre O(..) = Relación de inclusión entre conjuntos. –O(f) £ O(g) Û O(f) Í O(g) Û Para toda t Î O(f), t Î O(g) •Se cumple que: O(c) = O(d), siendo c y d constantes positivas. O(c) Ì O(n) O(cn + b) = O(dn + e) O(p) = O(q), si p y q son polinomios del mismo grado. O(p) Ì O(q), si p es un polinomio de menor grado que q.

Orden inferior u omega de f(n): W (f): Dada una función f: N ® R+, llamamos omega de f al conjunto de todas las funciones de N en R+ acotadas inferiormente por un múltiplo real positivo de f, para valores de n suficientemente grandes.W (f)= { t: N ® R+ / $ c Î R+, $ n0 Î N, " n ³ n0: t(n) ³ c·f(n) } La notación omega se usa para establecer cotas inferiores del tiempo de ejecución. Relación de orden: igual que antes. Orden exacto de f(n): Q (f): Dada una función f: N ® R+, llamamos orden exacto de f al conjunto de todas las funciones de N en R+ que crecen igual que f, asintóticamente y salvo constantes.Q (f) = O(f) Ç W (f) = { t: N ® R+ / $ c, d Î R+, $ n0 Î N, " n ³ n0: c·f(n) ³ t(n) ³ d·f(n) }

Notación o pequeña de f(n): o(f): Dada una función f: N ® R+, llamamos o pequeña de f al conjunto de todas las funciones de N en R+ que crecen igual que f asintóticamente: o(f)= { t: N ® R+ / lim t(n)/f(n) = 1}n¥ ®

Esta notación conserva las constantes multiplicativas para el término de mayor orden. Ejemplo. t(n) = amnm + am-1nm-1 + … +a1n + a0 t(n) Î o(amnm) ¹ o(nm) ¿o(amnm) Í O(amnm)? ¿o(t) Í O(t)?

Costa de complejidad con frecuencia Algunas relaciones entre órdenes frecuentes: O(1) Ì O(log n) Ì O(n) Ì O(n·log n) Ì O(n·(log n)2) Ì O(n1.001…) Ì O(n2) Ì O(n3) Ì … Ì O(2n) Ì O(n!) Ì O(nn)

¿Qué pasa con las omegas? ¿Y con los órdenes exactos? El orden de un polinomio anxn+…+a1x+a0 es O(xn). n n nå 1 = n Î O(n); å i = n(n+1)/2 Î O(n2); å im Î O(nm+1) i=1 i=1 i=1

Si hacemos una operación para n, otra para n/2, n/4, …, aparecerá un orden logarítmico O(log2 n). Los logaritmos son del mismo orden, independientemente de la base.

5. Técnica de diseño de algoritmos

Diseño de Algoritmos: Hasta ahora se han realizado algunos comentarios respecto a la necesidad de diseñar algoritmos correctos y eficientes utilizando los elementos de un lenguaje de programación .Es necesario en este momento mencionar algo sobre como hacerlo. El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá ser del todo automatizada. Todo problema algorítmico es un reto para su diseñador, algunos resultan inmediatos de resolver, otros son bastante complejos. La investigación en esta área ha permitido descubrir un conjunto de métodos o esquemas de diseño hacia los cuales puede orientarse la realización de muchos algoritmos. No obstante, y a pesar de que resulta mas adecuado en bastantes casos utilizar alguno de estos esquemas que realizar un diseño desde cero, idear un algoritmo continua siendo una labor bastante creativa donde los conocimientos y la experiencia del propio diseñador tiene un papel fundamental. El diseño de un algoritmo que resuelva un problema es, en general, una tarea difícil. Una forma de facilitar esta labor consiste en recurrir a técnicas conocidas de diseño de algoritmos, se decir, a esquemas muy generales que pueden adaptarse a un problema particular al detallar las partes generales del esquema. Muchos problemas pueden resolverse buscando una solución fácil y directa pero, a la vez bastante ineficiente. Este método, llamado de fuerza bruta, puede ser muy directo, pero con un poco de análisis puede encontrarse algoritmos más eficientes. El esquema mas sencillo quizás sea el llamado divide y vencerás, basado en la descomposición de un problema en subproblemas. Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado, tenemos una solución voraz, si la decisión en una etapa, solo puede tomarse tras considerar varias soluciones de otras etapas mas simples, la solución es dinámica. Aun así, hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda, a pesar de lo complejas que son las operaciones de búsqueda, su uso adecuado mediante el esquema de búsqueda con retroceso (o backtracking) permite ganar gran eficiencia respecto a soluciones de fuerza bruta. Por ultimo, conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica. Nos estamos refiriendo a métodos basados en la mejora de la eficiencia (por ejemplo, el uso de parámetros de acumulación al resolver problemas utilizando divide y vencerás, y el empleo de tablas como estructura auxiliar para la resolución eficiente de problemas donde se aplica programación dinámica), y a métodos basados en transformaciones del dominio para encontrar una solución mas fácilmente a un problema en un dominio transformado, siendo dicha solución finalmente adaptada al dominio original.

Consideraciones generales Si el hábil programador dispone de un recetario de algoritmos de donde poder seleccionar el más adecuado para cada problema, su tarea se simplifica. Supongamos que disponemos de una especificación precisa, completa y consistente del problema a resolver y queremos obtener un algoritmo en el que, dados uno datos de entrada valido, se produzca cierto resultado. Si no nos importa la eficiencia del algoritmo, podríamos utilizar un algoritmo general llamado algoritmo del museo británico. Se programa un computador de manera que parta de un conjunto de axioma matemáticos y los que use para reducir aleatoriamente teoremas validos. Aprender los principios básicos del diseño de algoritmos podemos preguntarnos por un método aceptable. El mas entendido, y quizás el mejor, es organizar el diseño sobre un esquema de algoritmo o una técnica de diseño que haya demostrado su utilidad para otros problemas. Este método de trabajo es practicable, puesto que existe un número reducido de esquema y técnicas de diseño. El conocimiento de técnicas de diseño es solo un primer paso para el diseñador, que debe completarse con otros conocimientos y, sobre todo, con la experiencia. Método de fuerza bruta Comenzamos el estudio de esquemas algorítmicos con un método sencillo, pero que debe evitarse siempre que se pueda, dad su ineficacia; la fuerza bruta. En realidad, no es un esquema algorítmico, si no mas bien calificativo Para una forma de diseñar algoritmos: tomar una solución directa, poco reflexionada. En principio, esto no es malo, pero dado que no se ha analizado apenas el problema, es muy probable que no se hayan aprovechado propiedades deducibles del problema y que la solución sea terriblemente ineficiente. Una solución por fuerza bruta también puede resultar adecuada como primera aproximación a la solución final, porque su desarrollo puede permitir profundizar más sobre el problema y conocer propiedades que sean utilizadas para obtener otra versión más eficiente. Por ejemplos: Algunos algoritmos de búsqueda de un elemento en un vector. Uno de ellos realizaba una búsqueda secuencial con complejidad lineal sobre el tamaño del vector y podía usarse con cualquier vector. Otro algoritmo realizaba un búsqueda dicotomica o binaria, con complejidad logarítmica, y solo se podía usar cuando el vector estuviese ordenado. El algoritmo primero responde a un razonamiento más sencillo, por lo que uno puede sentirse tentado a usar siempre. Esta es la solución de fuerza bruta: una solución directa, pero poco reflexionada. Lo más razonable es comprobar si el vector esta ordenado y, en caso positivo, aprovechar esta circunstancia para usar el algoritmo más eficiente: el de búsqueda binaria.

Técnicas de los Parámetros Acumuladores y de Tabulacion La recurcion es un mecanismo que permite obtener, en combinación con otras contrucciones, una solución funcional a muchos problemas. Muchos algoritmos recursivos resultan eficientes, pero no todos: hay algunos fácilmente formulables, pero muy ineficientes. En estos casos, dichos algoritmos pueden servir como una primera aproximación al algoritmo definitivo, pero debe mejorar su rendimiento para que sea práctico. Veremos dos parámetros para la mejora de eficiencia de algoritmos recursivos: el uso de parámetros acumuladores y el uso de tablas. Cada una se ilustra con un ejemplo distinto.

Parámetros Acumuladores Veamos primero una solución ineficiente que intentaremos mejorar. Ejemplo: Números de Fibonacci Los números de fibonacci suele especificarse como: Fib(0)=1 Fib(1)1 Fib(n+2)=fib(n)+fib(n+1)

Esta especificación de los números de fibonacci tienen una formulación recursiva inmediata en estilo funcional. Un modo de evitar problema lo proporciona la técnica de los parámetros acumuladores, cuya idea básica se expone a continuación. La función principal usa una función auxiliar que tiene los parámetros de aquellas más algunos adicionales. La función principal simplemente realiza una llamada a esta función auxiliar en los que los parámetros de aquellas se modifican y los parámetros nuevos toman un valor inicial adecuado . Los parámetros adicionales tienen como misión ir acumulando resultados principales durante el proceso recursivo.

Tabulacion No todos los algoritmos recursivos ineficientes pueden optimizarse con la técnica de los parámetros acumuladores. Otra técnica útil es el uso de tablas. La intención es que la primera vez que se realiza un cálculo, se almacena en una tabla, donde puede consultarse otras veces que se necesite. Esta técnica también se suele emplear con la programación dinámica. Ejemplo: Sea el problema de la competición. Hay dos participantes (deportistas o equipos, no importa que), A,B, que juegan una competición que es ganada por el primero que venza en n partidos, siendo ( n ) mayor que( 0 ). Por sencillez , se supone que ambos participantes tienen cualidades y preparación similar . De forma que cada uno tiene un 50% de posibilidades de ganar cada partido. De todas formas, la modificación para incorporar probabilidades diferentes es evidente y no complica el problema.

Divide y vencerás: Consiste en descomponer un problema en un subproblema, resolver independientemente los subproblemas para luego combinar sus soluciones y obtener la solución del problema original. Esta técnica se puede aplicar con éxito a problemas como la multiplicación de matrices, la ordenación de vectores, la búsqueda en estructuras ordenadas,etc. Ejemplo. Búsqueda de una palabra en un diccionario Como ejemplo sencillo de aplicación de esta estrategia puede considerarse la búsqueda de una palabra en un diccionario de acuerdo con el siguiente criterio. Se abre el diccionario por la pagina centrar(quedando dividido en dos mitades) y se comprueba si la palabra aparece allí o si es léxico gráficamente anterior o posterior. Si no ha encontrado y es anterior se procede a buscarla en la primera mitad., si es posterior, se buscara en la segunda mitad. El procedimiento se repite sucesivamente hasta encontrar la palabra o decidir que no aparece.

Método voraz: Este método trata de producir tipo de mejor resultado a partir de conjunto de opciones candidatas .Para ello, se va procedimiento paso a paso realizándose la mejor elección (usando una función objetivo que respeta un conjunto de restricciones ) de entre las posibles. Puede emplearse en problemas de optimización, como el conocido de la mochila, en la búsqueda de caminos mínimos sobre grafos, la planificación en el orden de la ejecución de unos programas en un computador,etc. Ejemplo. Dar un cambio utilizando el menor número de monedas Considérese ahora el problema de la devolución del cambio al realizar una compra (por ejemplo, en una maquina expendedora de tabaco). Suponiendo que se disponga de cantidad suficiente de ciertos tipos diferentes de monedas de curso legal, se trata de dar como cambio la menor cantidad posible usando estos tipos de monedas. La estrategia voraz aplicada comienza devolviendo, cuando se pueda, la moneda de mayor valor ( es decir, mientras el valor de dicha moneda sea mayor o igual al cambio que resta por dar), continua aplicándose el mismo criterio para la segunda moneda mas valiosa, y así sucesivamente. El proceso finaliza cuando se ha devuelto todo el cambio.

Consideraciones y Criterios para Diseñar Algoritmos Algunas consideraciones estilísticas pueden contribuir a mejor la calidad de los algoritmos (y programas ) mediante la reducción del numero de errores que aparecen al desarrollar los. También influyen haciendo que nuestro algoritmo resulten más fáciles de leer y entender para otras personas. Los criterios de estilo pueden reflejarse en un conjunto de normas de estilo de codificación. Ello asegura que tanto algoritmos como programa resulten legibles y puedan modificarse fácilmente en caso de necesidad. Generalmente, estas normas de estilo se dirigen hacia aspectos como la forma de construir los nombres de variables o tipo de datos que aparezcan., la tipografía seguida ala hora de escribir nombres de variables, subprogramas, palabras claves, etc. El modo de encolumnar las distintas partes de un algoritmo para facilitar su lectura y comprensión, y la normas sobre como y donde deben de introducirse los comentarios. Estilo y calidad de los programas van fuertemente unidos. Ante la pregunta ¿Cuáles son las característica de un buen algoritmo?, las siguientes respuestas reflejan, cierta medida, los factores que identifican la calidad en ellos .

1. Corrección, el algoritmo debe funcionar.
2. Nunca se debe olvidar que la característica más simple e importante de un algoritmo es que funcione. Pude aparecer obvio, pero resulta difícil de asegurar en algoritmos complejos.
3. Eficiencia, el algoritmo no debe desaprovechar recursos. La eficiencia de un algoritmo se mide por los recursos que este consume. En particular, se habla de la memoria y del tiempo de ejecución . A pesar de que con la reducción de los costes del hardware es posible diseñar computadores más rápidos y con más memoria, no hay que desperdiciar estos recursos y tratar de desarrollar algoritmos más eficientes.
4. Claridad, el algoritmo debe estar bien documentación. La documentación ayuda a comprender el funcionamiento de los algoritmos. Ciertos detalles o algunas partes especiales de los mismos pueden olvidarse fácilmente o quedar oscura si no están adecuadamente comentadas.

En realidad, y de acuerdo con los puntos de vista anteriores, la calidad de un algoritmo tiene muchas facetas y todas ellas importantes. Resumiendo, lo ideal es que nuestro algoritmo resulte correcto, eficiente, claro, fiable y fácil de mantener.

Algoritmos voraces Esquema voraz Hay muchos problemas en los que se pretende obtener un subconjunto de n elementos que satisfaga ciertas restricciones y que optimice alguna medida. Se supone que un problema de esta clase tiene al menos una solución. Puede haber varias soluciones optimas, en cuyo caso no importa cual se elija. Por ejemplo, sea el problema de encontrar un subconjunto de los arcos de un grafo. Otro ejemplo se da cuando, dados unos ficheros almacenados en una cinta de que el tiempo de recuperación de un fichero cualquiera sea el mínimo en promedio. A menudo, el problema incluye restricciones adicionales que limitan el número posible de soluciones. Normalmente, estos problemas no se intentan resolver "de golpe ", encontrando de una sola vez la solución completa y óptima. Es más frecuente que el subconjunto de la solución se vaya formando paso a paso, analizando durante cada etapa que elemento conviene añadir a la solución parcial ya existente. La dificultad principal para resolver esta clase de problemas estriba en el análisis necesario para poder formular un algoritmo que halle la solución en varios pasos. Un algoritmo voraz sigue el esquema anterior, pero con la fortuna de que cada vez que añade un elemento a la solución se tiene la certeza de haber realizado la mejor elección posible. Esta característica hace que aunque el análisis del problema sea arduo, la solución voraz siempre resulte sencilla. La única complicación es comprobar que se siguen satisfaciendo las restricciones del problema. Por lo que se ha descrito del esquema voraz, éste es un proceso repetitivo sencillo que trata sucesivamente los diferentes elementos del problema. Para facilitar la descripción de este proceso, puede llamarse candidato al elemento tratado en cada paso. Inicialmente, el conjunto de candidatos que forman la solución está vacío. En cada paso se intenta añadir el mejor de los candidatos restantes a dicha solución parcial. Si este conjunto ampliado sigue siendo válido, es decir, si satisface las restricciones del problema y, por tanto, permite formar una solución del problema, el candidato se incorpora definitivamente. Al contrario, si dicho conjunto no es válido, se desecha el candidato. Si el algoritmo voraz se ha diseñado correctamente, la primera solución encontrada es óptima. Por tanto, la dificultad principal al diseñar un algoritmo voraz reside en encontrar un criterio en encontrar un criterio de selección que garantice la optimalidad de la solución. Según esta descripción, el problema parte de:

• Una función objetivo que da el valor de una solución. Obviamente, ésta es la función por optimizar.
• Un conjunto de restricciones sobre el valor de los datos de entrada y sobre la solución final del problema.

A su vez, la solución consta de:

• Un conjunto de candidatos
• Una función de selección que en cada momento determine que candidato de los aún no usados parece ser el mejor.
• Una función que determine si cierto conjunto de candidatos es válido; es decir, si permite formar alguna solución del problema.

Obsérvese que las funciones de validez y completitud no se preocupan de la optimalidad del la solución, pero si la función de selección es la adecuada, cada solución válida y completa es optima. Podemos representar el esquema voraz de la siguiente forma funcional: FUNCTION Voraz ( candidatos: ( 1..n ) : ( 1..n) -> FUNCTION VorazAcumulador ( candidatos : (1..n), Solución : (1..n) : (1..n) -> Cadidatos = ( ) v EsSolución ( solución)-> Value siguiente -> seleccionar ( candidatos ) IN EsVálida (solución v ( siguiente)) => VorazAcumulador (candidatos – (solución), solución v (siguiente)) VorazAcumulador (candidatos – (siguiente), solución) VorazAcumulador (candidatos, ( ) )

Puede verse por qué estos algoritmos se llaman " voraces " : en cada paso toman el mejor trozo de la solución; es decir, el mejor candidato. Además, nunca cambian de opinión: una vez que un candidato es aceptado o rechazado en la solución, la decisión, es definitiva. La función objetivo no suele aparecer en el algoritmo final, sino que se utiliza durante el análisis del problema y es determinante en la elección de la función de selección. De todas formas, debe recordarse que puede haber varios criterios alternativos de selección y que de su correcta elección depende que la solución calculada por el algoritmo sea optima. Como ejercicio, el lector puede intentar encontrar una solución voraz del problema del calendario. Es fácil encontrar una solución si en cada etapa se genera el subcalendario correspondiente a un equipo; es decir, la tabla de competición se va completando por filas. Como fila primera se toma la secuencia de los índices de los participantes en cualquier orden. Cada fila resultante puede tener una complejidad de o (n2). Además, este algoritmo tiene la ventaja de valer para las situaciones en que el número de participantes no es una potencia de dos.

Desglose en monedas Como primer ejemplo introductorio sencillo al que puede aplicarse la técnica voraz, se considera el problema de un cambio o desglose en monedas. Hay que desglosar una cantidad en un conjunto de monedas tratando de cumplir alguna condición; en este caso, utilizar el menor número de monedas. Para ello, se parte de un conjunto de tipos de monedas válidas, de las que se supone que hay cantidad suficiente para realizar el desglose, y de un importe. Se trata de indicar la cantidad (menor) de monedas de los tipos considerados, tales que sumados sus valores equivalgan al importe. Para simplificar, suponemos que manejamos dinero español y, en particular, podemos utilizar sólo monedas de 500, 100, 50, 25, 5 y 1 pesetas para el desglose. Estos valores se definen por medio de un tipo enumerado MONEDAS. Asimismo, se declaran los tipos VALORES y CANTIDADES para representar el valor asignado a cada unidad monetaria y la cantidad de cada tipo de moneda que se devolverá en el desglose. Su declaración es la siguiente: TYPE Monedas -> M500 I M100 I M50 I M25 I M5 I M1, Valores -> Integer M500…M1 Cantidades -> Integer M500….M1

Se supone inicialmente asignados los valores a cada uno de los tipos de monedas. Los elementos de la técnica voraz están presentes en este problema de la siguiente forma:

• El conjunto de candidatos está constituido por cada una de las monedas de los diferentes tipos que se pueden usar para realizar el desglose del importe dado.
• Una solución viene dad por un conjunto de monedas devuelto tras el desglose, y cuyo valor total es igual al importe a desglosar.
• La condición de factibilidad de la solución siendo construida establece en el desglose debe ser menor o igual que el importe a desglosar.
• La función de selección establece que hay que elegir, mientras sea posible, la moneda de mayor valor de entre las candidatas.
• La función objetivo cosiste en minimizar la cantidad total de monedas utilizadas en el desglose.

Con esta información se puede comprobar que en este problema están presentes los distintos elementos de la técnica voraz. Además, cuando un candidato (moneda) se incorpora al conjunto solución, éste no será nunca excluido de él.

Divide Y Vencerás La técnica divide y vencerás consiste en descomponer el problema en un conjunto de subproblemas más pequeños. Después se resuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original.

Esquema de Divide y vencerás. La técnica de divide y vencerás es quizás una de las utilizadas debido a su sencillez: si un problema es demasiado grande para resolverlo de una vez, se descompone en varias partes más fáciles de resolver. Mas formalmente, dado un problema al resolver planteando en términos de una entrada de tamaño n, la técnica de divide y vencerás parte la entrada en k subproblemas, 1<k<=n. Estos subproblemas se resuelven independientemente y después se combinan sus soluciones parciales para obtener la solución del problema original. Este esquema de partición de problemas se denomina esquema de divide y vencerás solo en el caso en que los problemas sean de la misma clase del problema original. Esta restricción permite una formulación y resolución recursiva de los subproblemas. Por supuesto, deben existir algunos pasos sencillos cuya solución pueda calcularse fácil y directamente; en caso contrario, el proceso recursivo nunca terminaría. El caso más frecuente es cuando el número de subproblemas es dos. Veamos el esquema de divide y vencerás para dos subproblemas; es fácil su generalización a k subproblemas 2<k<=n. Su formación funcional es como sigue, considerado el problema como de tipo dato y la solución, de tipo resultado: TYPEVAR Dato, resultado FUNCTION DivideYVenceras (problema : dato) : resultado -> EsPequeño (problema) }=> ResolverDirectamente (problema) | VALUE subproblemas -> Partir (problema) IN subproblemas == (subproblema1, subproblema2) => Combinar (DivideYVenceras (subproblema1) , DivideYVenceras (subproblema2)) Se puede hacer una formulación imperativa similar. Sin embargo, escribiremos una formulación más restrictiva pero bastante usual, en la que se utiliza un vector de tamaño N. TYPEVAR dato, resultado PROCEDURE DivideYVenceras (IN problema : dato1..n,OUT solución : resultado) -> PROCEDURE DyVAux (IN problema : dato1..n,IN inferior, superior : 1..N, OUT solución : resultado) -> VAR medio: 1..N subsolucion1, subsolucion2 : resultado IF EsPequeño (inferior, superior) THEN ResolverDirectamente (problema, inferior, superior, olución) ELSE Medio := Partir (inferior, superior); DyVAux (problema, inferior, medio, subsolucion1); DyVAux (problema, medio+1, superior, subsolucion2); Combinar (subsolucion1, subsolucion2, solución) DyVAux (problema, 1, N, solución)

El esquema general se adapta a un problema concreto al sustituir los metasimbolos EsPequeño, ResolverDirectamente, Partir y Combinar por funciones o procedimientos concretos. Si el tamaño de los dos subproblemas es el mismo (o casi), el tiempo de cómputo de la función DivideYVecneras se describe con la siguiente relación de recurrencia: g(n),si n es pequeño T(n) = 2 T(n/2) + f(n), en caso contrario donde T(n) es la función de tiempo de DivideYVenceras para entradas de tamaño n, g(n) es el tiempo que tarda la función ResolverDirectamente en resolver problemas de pequeño tamaño (normalmente una constante) y f(n) es el tiempo necesario para partir el problema y combinar las subsoluciones. La eficiencia final del algoritmo depende de la función f(n) concreta que aparezca durante el análisis. Nótese que, es general, para que esta técnica resulte eficiente todos los subproblemas deben ser de tamaño parecido.

Elaboración de un Calendario Deportivo: Sea un campeonato deportivo; para nuestros propósitos resulta indiferente el deporte objeto de la competición, así que hablaremos de participantes en vez de deportistas o equipos. El problema consiste en elaborar un calendario de competición de forma que cada participante compita exactamente una vez con cada uno de los demás participantes. Por concreción, y sin perdida de generalidad, puede suponerse que las competiciones se celebran en días sucesivos y que cada participante compite una vez por día. Para simplificar el problema, se supone que el numero de participantes es una potencia de dos; es decir, hay n = 2k participantes para algún entero positivo k. Se supone también que cada participante tiene asignado un número comprendido entre 1 y N. Se necesitan elaborar n-1 competiciones por participantes. Por tanto, la solución del problema puede representarse en una tabla de dimensión nx(n-1). El elemento (i,j)–esimo de la tabla, 1<= i<=n, 1<=j<n, contiene el numero del participante contra el que el participante i-esimo compite el día j-esimo. Obsérvese que los números de participantes incluidos en la fila i de la tabla son distintos porque el participante i-esimo solo debe competir una vez con cada participante restante. A su vez, la columna j también contiene números distintos, porque el día j-esimo cada participante solo puede competir con otro participante. Se dispone de una solución inmediata aplicando fuerza bruta. Primero se obtiene para cada participante i, 1<=i<=n, el conjunto P(i) de todas las permutaciones posibles del resto de los participantes con los que debe competir, es decir, el conjunto de permutaciones de los números {1..n}-{i} ahora se completan las filas de la tabla de todas las formas posibles, incluyendo en cada fila i algún ejemplo de P(i). Solo sirve como solución aquellas combinaciones de fila que cumplan las restricciones enunciadas en el párrafo anterior sobre las columnas de la tabla (las restricciones sobre las filas están garantizadas por el modo de generar los conjuntos P(i)). Si hay varios calendarios validos, se elige uno cualquiera. El método de fuerza bruta resulta sencillo, pero es terriblemente ineficiente. Cada conjunto P(i) consta de (n-1)! Elementos. Dado que el numero de participantes de n, resultan nx(n-1)!=n! formas de rellenar la tabla. Sin embargo la aplicación de la técnica de divide y vencerás produce una solución mas sencillas aun pero muy eficientes. La siguiente figura describe visualmente parte de la elaboración de la tabla.

Se distinguen dos casos. El caso básico se da cuando solo hay dos participantes. La solución es directa porque se celebra una sola competición entre ambos. El caso recursivo, cuando hay más de dos participantes, es más complejo. Si el numero de participantes es 2k , para k>1, puede decirse que el "tamaño" del problema es 2k (sabemos que el calendario tendrá un tamaño de 2k x(2k-1 -1) posiciones). El problema puede reducirse a dos sub problemas de tamaño 2k-1 si se elaboran independientemente dos subcalendarios de tamaño 2k x(2k-1 -1): uno para los participantes, de numeración comprendida entre 1 y 2k-1 y otro para los participantes comprendidos entre 2k-1 +1 y 2k . Sin embargo, la unión de estos subcalendarios no forma un calendario completo para el campeonato de 2k participantes, ya que a unión de los dos calendarios tiene un tamaño 2k x(2k-1 -1), faltando 2k x2k-1 celdas para completar el calendario total. En efecto, faltan por elaborar las competiciones cruzadas entre los participantes de numeración inferior y los de numeración superior. Por fortuna, el resto del calendario se puede construir fácilmente. Completemos primero la parte de los participantes de numeración inferior. El subcalendario del primer participante es sencillo porque basta con que compita en días sucesivos con los participantes de numeración, superior en orden creciente de numeración; es decir, sucesivamente con los participantes 2k-1 +1,….,2n . El siguiente participante toma esta secuencia y realiza una fácil permutación de la misma que le garantiza el respeto de las restricciones de la solución; por ejemplo, rotando dicha secuencia a la derecha. Este proceso se repite para el resto de los participantes de numeración inferior. El calendario de los participantes de numeración superior se completa de forma similar con los números de los participantes de numeración inferior.

El algoritmo descrito se expresa a continuación. PROCEDURE Calendario ( INOUT tabla : (1..N)1..N,1..N-1) -> PROCEDURE FormaTabla (IN inf : 1..N, IN sup :1..N, OUT tabla : (1..N) 1..N,1..N-1) -> VAR medio : 1..N IF inf = sup-1 THEN tablainf.1 : = sup; tablasup.1 := inf ELSE medio := (inf + sup) Div 2; FormarTabla (inf, medio, tabla); FormarTabla (medio+1, sup, tabla); CompletarTabla (inf, medio, medio,sup-1, medio+1, tabla); CompletarTabla (medio+1, sup, medio, sup-1, inf, tabla)

Este sistema de ecuaciones defina una función de tiempo del orden de O(n2), que es mucho mas eficiente que la solución de fuerza bruta. Veamos otra estrategia, también de orden de complejidad cuadrática, donde se aplica divide y vencerás para resolver el problema y que se aprovecha de la simetría de la solución. La idea consiste en añadir inicialmente a la tabla una columna "ficticia" de índice j=0, que almacena los índices de las filas. Después se genera, mediante divide y vencerás, la mitad izquierda de la tabla. Finalmente se completa la mitad derecha de la tabla (correspondiente al cruce de los dos grupos de equipos cuyos subcalendarios se han generado por divide y vencerás). En esta última etapa, los valores de las casillas (k,l), siendo 1<=k<=n y 0<=l<=(n/2)-1, de acuerdo con las siguientes expresiones de los índices: i = (k + n/2) Mod (n+1) j = (1 + n/2) Mod n De esta forma se rellenan las casillas aun vacías, es decir, los componentes tablai,j a partir de las casillas tablak,l ya completadas.

Ordenación de un Vector por Mezcla: La ordenación de un vector es un problema que se presta fácilmente a la aplicación de la técnica de divide y vencerás. El caso básico corresponde a un subvector de un solo elemento, que obviamente ya esta ordenado. Para el caso general, sea vi..s un vector de índice inferior i e índice superior s. La partición puede hacerse por la mitad si se toma un índice m=[(i+s)/2] y dos subvectores vi..m y vm+1..s . la combinación de los dos subvectores ya ordenados es fácil. basta con mezclar los dos subvectores, mediante comparaciones de sus elementos sucesivos, para obtener un único vector ordenado. Este proceso de mezcla es realizado por un procedimiento auxiliar. El algoritmo resultante es: PROCEDURE Ordenar (INOUT v : INTEGER1..N) -> (* ordenación por mezcla *) PROCEDURE OrdenarAux (INOUT Vector : INTEGER1..N,1..N, IN inf, sup : 1..N) -> VAR Medio : 1..N IF inf < sup THEN medio := (inf+sup) Div 2; OrdenarAux (vector, inf, medio); OrdenarAux (vector, medio+1, sup); Mezclar (vector, inf, medio, sup) OrdenarAux (v, 1, N)

El procedimiento para realizar la mezcla de los subvectores ordenados es: PROCEDURE Mezclar ( IN inf : INTEGER, IN medio: INTEGER, IN sup : INTEGER, INOUT vector : INTEGER1..N) -> VAR vectorAux : INTEGER1..N, i1, i2, j : INTEGER, índice : INTEGER i1 := inf; i2 := medio + 1; j := inf; WHILE (i1<=medio) ^ (i2<=sup) DO IF vectori1 << vectori2 THEN vectorAuxj :=vectori1; i1 :=i1 + 1 ELSE vectorAuxj ;= vectori2; i2 := i2 + 1 j := j + FOR índice IN i1..medio DO vectorAuxj := vectorindice; J := j + 1 FOR índice IN i2..sup DO vectorAuxj := vectorindice ; J := j + 1 FOR índice In inf..sup DO vectorindice := vectorAuxindice

El algoritmo resultante es sencillo conceptualmente. Es fácil analizar la complejidad del algoritmo para un vector de longitud n. La operación de mezcla es proporcional a n, de forma que las ecuaciones de recurrencia de la función de tiempo son: T(n) = a, n=1, a=cte 2T(n/2) + bn, n>1, b=cte

Si n es una potencia de 2; es decir, n =2k para algún k, las ecuaciones anteriores se resuelven por sustituciones sucesivas, resultando: T(n) = 2T(n/2) + bn=…=2K T(n/2K) + kbn = an + bn log2 n El algoritmo de ordenación por mezcla es óptimo en tiempo de ejecución. Los únicos inconvenientes que presenta es que el procedimiento de mezcla necesita gran capacidad de almacenamiento (para dos copias del vector) y que, además de mezclar, necesita copiar el vector auxiliar completo en el principal. Puede diseñarse un algoritmo de mezcla más complejo que mejore ambos aspectos, pero mantenga la complejidad asintótica calculada.

Multiplicación de Matrices: Sean dos matrices, A y B, de dimensión nxn. La matriz producto C=AxB también es una matriz de nxn cuyo elemento (i,j)-esimo se forma multiplicando cada elemento de la final i-esima de A por el elemento correspondiente de la columna j-esima de B y sumando los productos parciales. El cálculo de cada elemento Cij requiere n multiplicaciones. La matriz C tiene n2 elementos, así que el tiempo total del algoritmo de multiplicación es de orden O(n3). El algoritmo anterior, que podemos llamar algoritmo convencional de multiplicación de matrices, proviene directamente de la definición matemática del producto de matrices. Sin embargo, la técnica de divide y vencerás sugiere un algoritmo distinto. Supongamos, por sencillez, que n es una potencia de dos; es decir, que existe un entero no negativo k tal que n=2k. (Si n no es un potencia de dos, pueden añadirse las filas y columnas de ceros necesarias para formar una dimensión que sea potencia de dos.) las submatrices A y B pueden partirse en cuatro submatrices de dimensión (n/2)x(n/2). Si el producto AxB tiene la forma: A11 A12 B11 B12 C11 C12 A21 A22 B21 B22 C21 C22 Entonces: C11 = A11*B11 + A12*B21 C12 = A11*B12 + A12*B22 C21 = A21*B11 + A22*B21 C22 = A21*B12 + A22*B22

Para n=2, los elementos Cij se calculan mediante algunas multiplicaciones y sumas de números, pero para n>2 las submatrices Cij se calculan mediante multiplicaciones (recursivas) y sumas de submatrices de dimensión (n/2)x(n/2). Dos submatrices de (n/2)x(n/2) pueden sumarse en un tiempo bn2, siendo b alguna constante. La resolución de este sistema de ecuaciones nos dice que O(T(n))=OT(n3), de forma que no se ha conseguido ningún ahorro sustancial de tiempo. Sin embargo, interesa encontrar algoritmos mas eficientes, porque la multiplicación esta relacionada con otras operaciones sobre matrices mas usuales, como inversión de una matriz o hallar su determinante. La existencia de un algoritmo eficiente para la multiplicación (en realidad, para cualquier operación de las anteriores) significaría la existencia de un algoritmo similar para las demás. Podría conseguirse mas eficiencia si lográramos realizar menos multiplicaciones de matrices, aunque fuera a costa de un mayor numero de sumas de matrices, dado que la complejidad respectiva de estas operaciones es O(n3)n y o(n2). El algoritmo de Strassen calcula las cuatro submatrices Cij empleando 7 multiplicaciones y 18 sumas o restas de matrices.

Programación Dinámica Principios de programación dinámica Se ha visto que la técnica voraz se aplica a problemas cuya solución puede formularse como el resultado de una secuencia de decisiones. El método es eficiente porque una vez que se toma una decisión en un paso, no se reconsidera en el futuro, conduciendo de forma directa a la solución. Sin embargo, no todos los problemas pueden resolverse de esta manera, asegurando que la secuencia de decisiones es la mejor de las posibles. La programación dinámica (también llamada planificación dinámica) es una técnica de programación que también permite resolver problemas mediante una secuencia de decisiones, pero de una manera menos directa que en el caso voraz. Esta vez se necesita producir varias secuencias de decisiones. Solamente al final se sabe cuál es la mejor de todas. No es fácil establecer una definición de la programación dinámica; una característica es que el programa "aprende "dinámicamente de las decisiones que toma. Además, todo problema resoluble con esta técnica debe de satisfacer el principio de optimalidad. Este principio establece que "una secuencia óptima de decisiones que resuelve un problema debe cumplir la propiedad de que cualquier subsecuencia de decisiones también debe ser óptima respecto al subproblema que resuelva ". Usando una técnica de fuerza bruta, el número de secuencias de decisión es exponencial sobre el número de decisiones, porque si hay d opciones para cada una de las n decisiones, resultará un total de d secuencias posibles de decisión. En la programación dinámica todos los subproblemas se resuelven de acuerdo con criterio de tamaño creciente y los resultados de subproblemas más pequeños se almacenan en algún tipo de estructura de datos (normalmente tablas) para facilitar la solución de los problemas más grandes. De esta forma se reduce al número total de subsecuencias generadas, evitándose una explosión combinatoria en la producción de las secuencias y consiguiéndose soluciones más eficientes en cuanto a tiempo de ejecución. Podemos formalizar algo más la idea básica. Supongamos que tenemos un problema que satisface el principio de optimalidad, tal que Eo es el estado inicial del problema y deben tomarse n decisiones d, 1<i<n. Sea D = { v1…..vn} el conjunto de valores de decisión posibles para la decisión d1. sea, asimismo, Eli el estado del problema tras la elección del valor vli 1<i<n1 y Sli una secuencia óptima de decisiones respecto al estao Eli. Entonces, una secuencia óptima de decisiones respecto a E0 es la mejor secuencias de decisión { Vli Sli }, 1<i<N1. El razonamiento anterior se refiere a la primera decisión d1 tomada desde el estado inicial E0 sin embargo, puede generalizarse la formulación del problema a cualquier subsecuencia de decisiones dk…..,dl, 1<k<n, partiendo como estado inicial de Ek-1. si este subproblema de simboliza como problema (k,l), entonces el problema completo es problema ( l,n ). Tiene sentido centrarse en un subproblema del problema inicial porque éste satisface el principio de optimalidad pero, además, tiene la ventaja ( quizás paradójica al tratar de un problema más pequeño ) de que proporciona una visión más general del problema en cuestión. ( Obsérvese que vamos a usar la técnica de resolución de problemas por generalización para después poder realizar una particularización de la solución obtenida.) Una solución dinámica para problema ( k,1 ) debe expresarse en términos de los valores de decisión existente para decisiones d1 y el subproblema problema ( k+1,1 ) resultante de aplicar cada valor de decisión. La expresión inicial de la ecuación de recurrencia, hay un caso en que la decisión d1 no va seguida por ninguna secuencia de decisiones, que es problema ( n,n ). En resumen, la aplicación de la técnica de programación dinámica a un problema significa comprobar primero el principio de optimalidad y desarrollar después unas ecuaciones recurrentes del estilo de (1) y (2). La ecuación general relaciona la secuencia óptima en una etapa i con la decisión tomada en la etapa i y la subsecuencia óptima en la etapa posterior i+1. la ecuación de base establece el valor para la etapa n+1 en que no queda ninguna decisión Xi, 1<i<n, a tomar. La ecuación de recurrencia puede formularse de dos formas: delantera o trasera. Sea X1…..Xn la secuencia de decisiones necesaria para resolver el problema. La formulación delantera expresa la decisión de Xl , 1<i<n, a partir de la secuencia de decisiones Xi+1……Xn ( es la clase de formulación adoptada hasta ahora ). La formulación trasera expresa la decisión de Xi, 1<i<n , a partir de la recurrentes con formulación trasera es igual que e la formulación delantera, sólo que en orden contrario. La elección de una formulación delantera o trasera depende del problema considerado o, sencillamente, del gusto del programador.

Algoritmos De Vuelta Atrás Existen un alto número de problemas que pueden formularse como la búsqueda de la mejor solución o del conjunto de todas las soluciones que satisfacen ciertas condiciones. Además, cada solución es el resultado de una secuencia de decisiones. Por supuesto, debe existir una función de criterios que debe ser satisfecha por cada secuencia solución u optimizada por dichas secuencias solución si solo queremos la mejor. En algunos problemas de optimización se conoce un criterio óptimo de selección que puede usarse de forma voraz. Otros problemas satisfacen el principio de optimalidad, pudiéndose aplicar la técnica de programación dinámica. Sin embargo, todavía hay otros problemas peores que no queda mas remedio que realizar una búsqueda de la solución.

Esquema de Algoritmos de Vuelta Atrás:

Sea (x1,…,xi) el camino desde la raíz hasta un nodo de un árbol del espacio de estado. Sea G(x1…xi) el conjunto de todos los valores posibles de xi+1 tales que (x1,…,xi+1) es un camino hasta el estado del problema. Supongamos que existe algún predicado acotador A tal que A(x1,…,xi+1) es falso si el camino (xi,…,xi+1) no puede extenderse para alcanzar un nodo de respuesta. Por lo tanto, los candidatos para la posición i+1 del vector desolucion x1..n son aquellos valores generados por G que satisfacen A. Supongamos que también existe algún predicado R que determina si un camino (x1,…,xi+1) termina en un nodo de respuesta. El Algoritmo de Vuelta Atrás se especifica de la forma siguiente: PROCEDURE Retroceso (IN k : INTEGER, INOUT solucion : elemento1…n) -> VAR nodo : elemento FOR noso IN G(solucion, 1, k-1) DO Solucion k := nodo; IF R(solucion, 1, k) THEN IF R(solucion, 1,k) THEN << guardar ‘solucion’ >>; Retroceso (k+1, solucion) La llamada inicial del algoritmo es Retroceso(1, solucion). El procedimiento no hace ninguna llamada recursiva cuando k = N+1 o cuando ningún nodo generado por G satisface el elemento posible que satisfacen A se añade una solución particular, se comprueba si se ha encontrado una solucion. Después simplemente se llama recursivamente al algoritmo para generar los estados descendientes. Se sale del bucle FOR cuando no quedan mas valores para solución terminando la llamada actual al algoritmo.

Ramificación (Bifurcacion) Y Acotación Los métodos de Ramificación y Acotación constituyen un a variante de las técnicas de retroceso para problemas donde se trata de encontrar el valor máximo o mínimo de cierta función objeto (esto suele suceder en los problemas de programación lineal entera).

La técnica de ramificación y acotacotacion aplica de la siguiente manera: Supóngase que al recorrer un árbol y alcanza una hoja se tiene una solucion con k colores, y que al seguir avanzando en el árbol (mediante la aplicación de varios pasos de retrocesos) se alcanza un nodo que requiere k+1 colores. En este punto podemos retroceder (y no seguir avanzando por mas ramas), pues tenemos ya una solucion mayor. Así, k sirve de cota inferior al retroceso. Este mismo proceso se repite en el resto de nodos del árbol, evitando así la exploración de gran parte de al estructura.

Algoritmos Heuristicos Existen muchos problemas para los cuales no se conocen algoritmos que puedan encontrar la solución de forma eficiente: problemas NP-completos. La solución exacta puede requerir un orden factorial o exponencial: el problema de la explosión combinatoria. Se hace necesario utilizar algoritmos heurísticos: Un algoritmo heurístico (o simplemente heurística) puede producir una buena solución (puede que la óptima) pero también puede que no produzca ninguna solución o dar una solución no muy buena. Normalmente, se basa en un conocimiento intuitivo del programador sobre un determinado problema. La estructura de algoritmo voraz se puede utilizar para construir procedimientos heurísticos: hablamos de heurísticas voraces. Objetivo: obtener buenas soluciones en un tiempo de ejecución corto. El problema del viajante Problema: Dado un grafo no dirigido, completo y ponderado G = (V, A), encontrar un ciclo simple de costo mínimo que pase por todos los nodos. Es un problema NP, pero necesitamos una solución eficiente. Problema de optimización, donde la solución está formada por un grupo de elementos en cierto orden: podemos aplicar el esquema voraz. Posibilidades:

1. Los nodos son los candidatos. Empezar en un nodo cualquiera. En cada paso moverse al nodo no visitado más próximo al último nodo seleccionado.
2. Las aristas son los candidatos. Hacer igual que en el algoritmo de Kruskal, pero garantizando que se forme un ciclo.

Heurística voraz 1 – Una solución será un cierto orden en el conjunto de nodos (c1, c2, …, cn), el orden de visita de los nodos. Inicialización: seleccionar un nodo cualquiera. Función de selección: de los nodos candidatos seleccionar el más próximo al último (o al primero) de la secuencia actual (c1, c2, …, ca). Acabamos cuando tengamos n nodos. Ejemplo. Empezando en el nodo 1. Solución: (1, 4, 5, 3, 2) Coste: 30+15+25+10+45=125 Empezando en el nodo 3. Solución: (5, 4, 3, 2, 1) Coste: 15+20+10+45+50=140 Heurística voraz 2 – Una solución será un conjunto de aristas (a1, a2, …, an-1) que formen un ciclo hamiltoniano, sin importar el orden. Empezar con un grafo sin aristas. Selección: seleccionar la arista candidata de menor coste. Factible: una arista se puede añadir a la solución actual si no se forma un ciclo (excepto para la última arista añadida) y si los nodos unidos no tienen grado mayor que 2. •Ejemplo. Solución: ((2, 3), (4, 5), (3, 4), (1, 2), (1, 5)) Coste = 10+15+20+45+50 = 140

Conclusiones: Ninguno de los dos algoritmos garantiza una solución óptima. Sin embargo, normalmente ambos dan soluciones buenas, próximas a la óptima. Posibles mejoras: buscar heurísticas mejores; repetir la heurística 1 con varios orígenes; ó bien, a partir de la solución del algoritmo intentar hacer modificaciones locales para mejorar esa solución.

Algoritmos De Aproximación Dado un problema NP completo, es probable que no sepamos resolverlo de manera precisa y completa utilizando un algoritmo polimico en tiempo. Para este tipo de problemas, los algoritmos que no conducen a una solución óptima se llaman algoritmos de aproximación. Sin embargo, resulta parcialmente interesante que estos garanticen una cota en el margen de imprecisión. A continuación se ilustra este tipo de tratamiento de problemas al problema de recubrimiento de un grafico: Dado un grafo G=(V,A), se trata de encontrar un conjunto con el menor numero de vértices tal que toda arista sea incidente por lo menos de un vértice de V. Este problema se puede resolver a través de otro aproximado, como es calcular el ajuste maximizal del grafo G. Se trata de calcular un subconjunto A’ de aristas tal que dos aristas cualquiera de A’ no tengan ningún vértice común y toda arista de A-A’ comparta algún vértice común con una arista de A’. Este nuevo problema garantiza conseguir un recubrimiento que contiene no más de dos vértices del recubrimiento mínimo. El procedimiento para construir un ajuste maximizal de un grafo G consistiría en ir tomando aristas de G, de una en una y en cualquier orden e ir eliminando las incidentes al conjunto que se esta construyendo hasta recubrir todo en grafo. Para poder aplicar el nuevo problema aproximado, seria necesario demostrar que el conjunto de todos los vértices inciden a las aristas de un ajuste maximal M para un grafo G es un recubrimiento con no mas de dos veces el numero de veces el recubrimiento de tamaño mínimo. Esto es evidente, ya que por la definición de ajuste maximal, los vértices incidentes a las aristas de M son un recubrimiento de G. también por la propia definición, ningún vértice perteneciente a M puede recubrir a mas de una arista en M. En consecuencia, por lo menos la mitad de los vértices de M deben pertenecer a un recubrimiento.