Source: https://es.scribd.com/doc/81863611/1-1-1-Conceptos-basicos-Algoritmos-y-aproximaciones
Timestamp: 2017-01-21 19:43:49+00:00

Document:
NavegarInteresesBiography & MemoirBusiness & LeadershipFiction & LiteraturePolitics & EconomyHealth & WellnessSociety & CultureHappiness & Self-HelpMystery, Thriller & CrimeHistoryYoung AdultNavegar porLibrosAudio librosArtículosPartiturasExplorar todoSubirIniciar sesiónRegistrarseConceptos básicos: Algoritmos y aproximacionesEn 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. 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. 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. 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. ).
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. Generalidades El programador de computadoras es ante que nada una personaque 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 alKhowarizmi, 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ónal 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 computadoraque 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 cienciade 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 mediospara 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 creatividady
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. 2. 3. 4. 5. inicio leer el pedido examinar la ficha del cliente si el cliente es solvente aceptar pedido; en caso contrario, rechazar pedido 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.
? Sabemos que cada ejecución lleva un tiempo constante. 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. ¿Cuánto tiempo. :=... T(6)= 0. Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir. Orden de complejidad de f(n): O(f)
. externos no aportan información sobre el algoritmo. Notaciones asintóticas: Indican como crece T. T(8)= 3.. T(4)= 0. Podemos hacer previsiones. Instrucciones ejecutadas por el algoritmo. IF y CASE: Estudiar lo que puede ocurrir. para el conteo de instrucciones. si el algoritmo es poco eficiente. 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. *. Mejor caso y peor caso según la condición. cuántas instrucciones. ¿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.5 min ¿Qué conclusiones podemos extraer? Análisis a priori: Evitamos la implementación. o alguna constante. de forma aproximada (y parametrizada).1 ms N= 5.): Una unidad de tiempo. O(T): Orden de complejidad de T.. pero ¿qué significa T(N)? Tiempo de ejecución en segundos. ¿Tardarán todas lo mismo? Ejecuciones del bucle principal. T(N) = bN + c. T(N) = 2N + 4. Bucles FOR: Se pueden expresar como una sumatoria. ¿Se puede predecir cuándo se cumplirán las condiciones? Llamadas a procedimientos: Calcular primero los procedimientos que no llaman a otros. Suponiendo que b y c son constantes. Programa "cifras.Los factores externos no aportan información sobre el algoritmo. Algunas reglas básicas.exe": N= 4. con los segundos que tardan las operaciones básicas correspondientes. T(N) = N+1. u omega de T. Nos interesa un análisis que sea independiente de esos factores. Operaciones básicas (+.. T(7)= 10 s N= 8. Asignación de tiempos.2 s N= 7. para valores suficientemente grandes (asintóticamente) sin considerar constantes.. -. Podemos comparar con otros algoritmos. o una constante diferente. Q (T): Orden exacto de T. luego se diferencia en una constante con los anteriores.. Normalmente usaremos la notación T(N)=. con los límites del FOR. Operaciones de entrada salida: Otra unidad de tiempo. Ejemplo. T(5)= 5 ms N= 6. W (T): Orden inferior de T...
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(. W (f)=W (g).Dada una función f: N ® R+. W (f+g) = W (max(f+g)) ¿Y para los Q (f+g)? ¿Es cierto que O(f . " n ³ n0: t(n) £ c·f(n) } Nota: O(f) es un conjunto de funciones. llamamos orden de f al conjunto de todas las funciones de N en R+ acotadas superiormente por un múltiplo real positivo de f. Memoria en una tabla hash..n. . llamamos orden de f al conjunto de todas las funciones de Nm en R+ acotadas superiormente por un múltiplo real positivo de f. n2. "Funciones acotadas superiormente por un múltiplo de f. -g))? P5. n Î O(n2) Þ 2n+1 Î O(n2) P2. Ej. el tiempo y la memoria consumidos pueden depender de muchos parámetros.
. ¿Qué relación hay entre O(log2 n) y O(log10 n)? P6. . de N en R+. Dadas f y g de N en R+. g)). Q (f)=Q (g) g(n) ii) limn¥ ® f(n) = 0 Þ O(f) Í O(g). k) = kB+l+n+2kn Orden de complejidad de f(n1.... Propiedades P1.. Dadas f y g de N en R+. ¿se cumple O(f)Í O(g) ó O(g)Í O(f)? P4. Si f Î O(g) entonces O(f) Í O(g). ¿Cómo es la relación para los W ? P3. O(f)=O(g) Û Q (f)=Q (g) Û f Î Q (g) Û W (f)=W (g) P7. nm) suficientemente grandes. 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. Grandes. 2n+1 Î O(n).) es completa? Dadas f y g. Dadas f y g... O(f)= { t: N ® R+ / $ c Î R+... "Valores de n sufic. M(B. W (g) Í W (f) g(n) P5. nm): O(f) Dada una función f: Nm ® R+..xN ® R+) Ej.. l..": nos quitamos las constantes. se cumple: i) limn¥ ® f(n) Î R+ Þ O(f)=O(g). O(f+g) = O(max(f. f: Nm ® R+ (f: Nx. La definición es aplicable a cualquier función de N en R.g) = O(max(f. para valores de (n1. para valores de n suficientemente grandes.m. Si f Î O(g) y g Î O(h) entonces f Î O(h). Dadas f y g de N en R+.. Dadas f y g de N en R+. $ n0 Î N. Si f Î W (g) y g Î W (h) entonces f Î W (h) Ej..": no nos importa lo que pase para valores pequeños. no sólo tiempos de ejec. no una función.
O(c) Ì O(n) O(cn + b) = O(dn + e) O(p) = O(q). Orden inferior u omega de f(n): W (f): Dada una función f: N ® R+. k2 ³ n2 ." km ³ nm : t(k1. llamamos orden de f según P (o condicionado a P) al conjunto: O(f | P)= { t: N ® R+ / $ c Î R+.. encontrar la función f más simple tal que t Î O(f). Orden exacto de f(n): Q (f): Dada una función f: N ® R+. .. . O(nm) O(n2). $ n0 Î N. y P: N ® B. Las propiedades se siguen cumpliendo ® Demostrarlo. tenemos W (f | P) y Q (f | P). Relación de orden entre O(. km) £ c·f(k1. km) } De la misma forma. Ejemplo. nm Î N. O(f) = O(f | true). ±O(f) £ O(g) Û O(f) Í O(g) Û Para toda t Î O(f). t(n) Î O(n2).
. " n ³ n0: t(n) ³ c·f(n) } La notación omega se usa para establecer cotas inferiores del tiempo de ejecución. " n ³ n0: P(n) Þ t(n) £ c·f(n) } De igual forma. y que más se aproxime asintóticamente. k2. llamamos orden exacto de f al conjunto de todas las funciones de N en R+ que crecen igual que f. y del tiempo de inicialización b y de ejecución de un paso a.. O(n+2m) Notaciones condicionales: En algunos casos interesa estudiar el tiempo sólo para ciertos tamaños de entrada. t(n) = 2n2/5 + 3p /2. a. llamamos omega de f al conjunto de todas las funciones de N en R+ acotadas inferiormente por un múltiplo real positivo de f. $ n1.a.. ¿Qué relación hay entre los siguientes órdenes? O(n+m). asintóticamente y salvo constantes... siendo c y d constantes positivas. $ n0 Î N. podemos extender los conceptos de W (f) y Q (f). T(N) = T(N. k2. Ejemplo. ¿O(f) « O(f | P)? Ordenes De Complejidad Uso de los órdenes de complejidad: Dado un tiempo t(n).. n2... Orden condicionado de f(n): O(f | P) Dada una función f: N ® R+. si p y q son polinomios del mismo grado. f Î O(g | false). para funciones con varios parámetros. Algoritmo de búsqueda binaria: Si N es potencia de 2 el estudio se simplifica. para valores de n suficientemente grandes.) = Relación de inclusión entre conjuntos..O(f)= { t: Nm ® R+ / $ c Î R+. si p es un polinomio de menor grado que q.b). W (f)= { t: N ® R+ / $ c Î R+. O(p) Ì O(q). . Ejemplo.. Podemos suponerlos constantes T(N). t Î O(g) Se cumple que: O(c) = O(d). Para cualquier f y g. Relación de orden: igual que antes. " k1 ³ n1 . b) = a·N + b El tiempo depende del tamaño del problema N. o variables T(N..
algunos resultan inmediatos de resolver.. El diseño de un algoritmo que resuelva un problema es.. a esquemas muy generales que pueden adaptarse a un problema particular al detallar las partes generales del esquema. El esquema mas sencillo quizás sea el llamado divide y vencerás. otra para n/2.. Ì O(2n) Ì O(n!) Ì O(nn) ¿Qué pasa con las omegas? ¿Y con los órdenes exactos? El orden de un polinomio anxn+. en general. 5. independientemente de la base. llamado de fuerza bruta. Una forma de facilitar esta labor consiste en recurrir a técnicas conocidas de diseño de algoritmos.+a1x+a0 es O(xn). 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 . No obstante. Ejemplo. basado en la descomposición de un problema en
.. nnn å 1 = n Î O(n). otros son bastante complejos.. El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá ser del todo automatizada. t(n) = amnm + am-1nm-1 + . d Î R+. " 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+. Todo problema algorítmico es un reto para su diseñador.. å i = n(n+1)/2 Î O(n2). $ n0 Î N...Es necesario en este momento mencionar algo sobre como hacerlo. n/4. pero con un poco de análisis puede encontrarse algoritmos más eficientes. +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. idear un algoritmo continua siendo una labor bastante creativa donde los conocimientos y la experiencia del propio diseñador tiene un papel fundamental. .. La investigaciónen 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.. 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. Los logaritmos son del mismo orden.001. Este método. y a pesar de que resulta mas adecuado en bastantes casos utilizar alguno de estos esquemas que realizar un diseño desde cero. puede ser muy directo. Muchos problemas pueden resolverse buscando una solución fácil y directa pero.) Ì O(n2) Ì O(n3) Ì . aparecerá un orden logarítmico O(log2 n). una tarea difícil. a la vez bastante ineficiente. å im Î O(nm+1) i=1 i=1 i=1 Si hacemos una operación para n. se decir..Q (f) = O(f) Ç W (f) = { t: N ® R+ / $ c.
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. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado. puesto que existe un número reducido de esquema y técnicas de diseño. la fuerza bruta. En principio. Se programa un computador de manera que parta de un conjunto de axioma matemáticos y los que use para reducir aleatoriamente teoremas validos. a pesar de lo complejas que son las operaciones de búsqueda. El conocimiento de técnicas de diseño es solo un primer paso para el diseñador. el uso de parámetros de acumulación al resolver problemas utilizando divide y vencerás. y quizás el mejor. sobre todo. si no mas bien calificativo Para una forma de diseñar algoritmos: tomar una solución directa. Una solución por fuerza bruta también puede resultar adecuada como primera aproximación a la solución final. la solución es dinámica. Este método de trabajo es practicable. 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. completa y consistente del problema a resolver y queremos obtener un algoritmo en el que. con la experiencia. su tarea se simplifica.subproblemas. 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. Otro algoritmo realizaba un búsqueda dicotomica o binaria. no es un esquema algorítmico. siendo dicha solución finalmente adaptada al dominio original. El mas entendido. Si no nos importa la eficiencia del algoritmo. poco reflexionada. se produzca cierto resultado. con complejidad
. si la decisión en una etapa. que debe completarse con otros conocimientos y. hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda. solo puede tomarse tras considerar varias solucionesde otras etapas mas simples. y a métodos basados en transformaciones del dominio para encontrar una solución mas fácilmente a un problema en un dominio transformado. dad su ineficacia. y el empleode tablas como estructura auxiliar para la resolución eficiente de problemas donde se aplica programación dinámica). Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Supongamos que disponemos de una especificación precisa. En realidad. esto no es malo. dados uno datos de entrada valido. tenemos una solución voraz. Por ejemplos: Algunos algoritmos de búsqueda de un elemento en un vector. Aprender los principiosbásicos del diseño de algoritmos podemos preguntarnos por un método aceptable. Método de fuerza bruta Comenzamos el estudio de esquemas algorítmicos con un método sencillo. Aun así. Nos estamos refiriendo a métodos basados en la mejora de la eficiencia (por ejemplo. Consideraciones generales Si el hábil programador dispone de un recetario de algoritmos de donde poder seleccionar el más adecuado para cada problema. podríamos utilizar un algoritmo general llamado algoritmo del museo británico. pero dado que no se ha analizado apenas el problema. Uno de ellos realizaba una búsqueda secuencial con complejidad lineal sobre el tamaño del vector y podía usarse con cualquier vector. es muy probable que no se hayan aprovechado propiedades deducibles del problema y que la solución sea terriblemente ineficiente. pero que debe evitarse siempre que se pueda. conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica.
Hay dos participantes (deportistas o equipos.logarítmica. La función principal usa una función auxiliar que tiene los parámetros de aquellas más algunos adicionales. pero poco reflexionada. pero no todos: hay algunos fácilmente formulables. Los parámetros adicionales tienen como misión ir acumulando resultados principales durante el proceso recursivo. 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. pero debe mejorar su rendimiento para que sea práctico. Esta es la solución de fuerza bruta: una solución directa. De todas formas. Otra técnica útil es el uso de tablas. En estos casos. en combinación con otras contrucciones. Parámetros Acumuladores Veamos primero una solución ineficiente que intentaremos mejorar. la modificación para incorporar probabilidades diferentes es evidente y no complica el problema. se almacena en una tabla. Divide y vencerás: Consiste en descomponer un problema en un subproblema. Veremos dos parámetros para la mejora de eficiencia de algoritmos recursivos: el uso de parámetros acumuladores y el uso de tablas. Esta técnica también se suele emplear con la programación dinámica. El algoritmo primero responde a un razonamiento más sencillo. La intención es que la primera vez que se realiza un cálculo. que juegan una competición que es ganada por el primero que venza en n partidos. en caso positivo. cuya idea básica se expone a continuación. A. resolver independientemente los
. donde puede consultarse otras veces que se necesite. De forma que cada uno tiene un 50% de posibilidades de ganar cada partido. Ejemplo: Sea el problema de la competición. y solo se podía usar cuando el vector estuviese ordenado. una solución funcional a muchos problemas. 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 . Muchos algoritmos recursivos resultan eficientes. aprovechar esta circunstancia para usar el algoritmo más eficiente: el de búsqueda binaria.B. Un modo de evitar problema lo proporciona la técnica de los parámetros acumuladores. Cada una se ilustra con un ejemplo distinto. se supone que ambos participantes tienen cualidades y preparación similar . Lo más razonable es comprobar si el vector esta ordenado y. pero muy ineficientes. Técnicas de los Parámetros Acumuladores y de Tabulacion La recurcion es un mecanismo que permite obtener. Por sencillez . siendo ( n ) mayor que( 0 ). dichos algoritmos pueden servir como una primera aproximación al algoritmo definitivo. no importa que). por lo que uno puede sentirse tentado a usar siempre. Tabulacion No todos los algoritmos recursivos ineficientes pueden optimizarse con la técnica de los parámetros acumuladores.
en una maquina expendedora de tabaco). Ejemplo. en la búsqueda de caminos mínimos sobre grafos. el algoritmo debe funcionar.. cuando se pueda. Los criterios de estilo pueden reflejarse en un conjunto de normas de estilo de codificación. las siguientes respuestas reflejan. la tipografía seguida ala hora de escribir nombres de variables. etc. la búsqueda en estructuras ordenadas.Para ello. Generalmente. La estrategia voraz aplicada comienza devolviendo. si es posterior.etc. mientras el valor de dicha moneda sea mayor o igual al cambio que resta por dar).etc. Dar un cambioutilizando el menor número de monedas Considérese ahora el problema de la devolución del cambio al realizar una compra (por ejemplo. 1. El procedimiento se repite sucesivamente hasta encontrar la palabra o decidir que no aparece. cierta medida. subprogramas. y así sucesivamente. la planificación en el orden de la ejecución de unos programas en un computador. El modo de encolumnar las distintas partes de un algoritmo para facilitar su lectura y comprensión. se trata de dar como cambio la menor cantidad posible usando estos tipos de monedas.subproblemas para luego combinar sus soluciones y obtener la solución del problema original. Nunca se debe olvidar que la característica más simple e importante de un algoritmo es que funcione. la moneda de mayor valor ( es decir. Consideraciones y Criterios para Diseñar Algoritmos Algunas consideraciones estilísticas pueden contribuir a mejor la calidadde los algoritmos (y programas ) mediante la reducción del numero de errores que aparecen al desarrollar los. Corrección. Ejemplo. Ello asegura que tanto algoritmos como programa resulten legibles y puedan modificarse fácilmente en caso de necesidad. Puede emplearse en problemas de optimización. Si no ha encontrado y es anterior se procede a buscarla en la primera mitad. También influyen haciendo que nuestro algoritmo resulten más fáciles de leer y entender para otras personas. como el conocido de la mochila. Ante la pregunta ¿Cuáles son las característica de un buen algoritmo?.
. y la normas sobre como y donde deben de introducirse los comentarios. Esta técnica se puede aplicar con éxito a problemas como la multiplicación de matrices. 2. la ordenación de vectores. 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. 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 diccionariode acuerdo con el siguiente criterio. estas normas de estilo se dirigen hacia aspectos como la forma de construir los nombres de variables o tipo de datos que aparezcan.. palabras claves. los factores que identifican la calidad en ellos . Pude aparecer obvio. se buscara en la segunda mitad. Estilo y calidad de los programas van fuertemente unidos. El proceso finaliza cuando se ha devuelto todo el cambio. pero resulta difícil de asegurar en algoritmos complejos. continua aplicándose el mismo criterio para la segunda moneda mas valiosa. 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. Método voraz: Este método trata de producir tipo de mejor resultado a partir de conjunto de opciones candidatas . Suponiendo que se disponga de cantidad suficiente de ciertos tipos diferentes de monedas de curso legal.
Un algoritmo voraz sigue el esquema anterior. ésta es la función por optimizar. Si el algoritmo voraz se ha diseñado correctamente. 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. 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. Esta característica hace que aunque el análisis del problema sea arduo. Eficiencia. lo ideal es que nuestro algoritmo resulte correcto. no hay que desperdiciar estos recursos y tratar de desarrollar algoritmos más eficientes. Si este conjunto ampliado sigue siendo válido. La documentación ayuda a comprender el funcionamiento de los algoritmos. fiable y fácil de mantener. A menudo. permite formar una solución del problema. en cuyo caso no importa cual se elija. el algoritmo debe estar bien documentación. Según esta descripción. Inicialmente. Otro ejemplo se da cuando. Puede haber varias soluciones optimas. 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. En particular. se habla de la memoria y del tiempo de ejecución . Ciertos detalles o algunas partes especiales de los mismos pueden olvidarse fácilmente o quedar oscura si no están adecuadamente comentadas. Por ejemplo. Resumiendo. el candidato se incorpora definitivamente. la calidad de un algoritmo tiene muchas facetas y todas ellas importantes. estos problemas no se intentan resolver "de golpe ". éste es un proceso repetitivo sencillo que trata sucesivamente los diferentes elementos del problema. claro. es decir. Por tanto. En realidad. por tanto. Se supone que un problema de esta clasetiene al menos una solución. si dicho conjunto no es válido. sea el problema de encontrar un subconjunto de los arcos de un grafo. 4. puede llamarse candidato al elemento tratado en cada paso. Es más frecuente que el subconjunto de la solución se vaya formando paso a paso. el problema incluye restricciones adicionales que limitan el número posible de soluciones. En cada paso se intenta añadir el mejor de los candidatos restantes a dicha solución parcial. La eficiencia de un algoritmo se mide por los recursos que este consume. la primera solución encontrada es óptima. el conjunto de candidatos que forman la solución está vacío. 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. Obviamente.3. el problema parte de:
Una función objetivo que da el valor de una solución. 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. la solución voraz siempre resulte sencilla. Normalmente. eficiente. y de acuerdo con los puntos de vista anteriores. La única complicación es comprobar que se siguen satisfaciendo las restricciones del problema. si satisface las restricciones del problema y. dados unos ficheros almacenados en una cinta de que el tiempo de recuperación de un fichero cualquiera sea el mínimo en promedio. se desecha el candidato. Al contrario. el algoritmo no debe desaprovechar recursos. encontrando de una sola vez la solución completa y óptima.
. analizando durante cada etapa que elemento conviene añadir a la solución parcial ya existente. Por lo que se ha descrito del esquema voraz. Para facilitar la descripción de este proceso. Claridad.
solución v (siguiente)) VorazAcumulador (candidatos ± (siguiente).
Obsérvese que las funciones de validez y completitud no se preocupan de la optimalidad del la solución. Cada fila resultante puede tener una complejidad de o (n2).n).n) -> Cadidatos = ( ) v EsSolución ( solución)-> Value siguiente -> seleccionar ( candidatos ) IN EsVálida (solución v ( siguiente)) => VorazAcumulador (candidatos ± (solución). la decisión. la tabla de competición se va completando por filas. tales que sumados sus valores equivalgan al importe. el mejor candidato. Para ello. es decir. La función objetivo no suele aparecer en el algoritmo final.
A su vez.n) -> FUNCTION VorazAcumulador ( candidatos : (1. De todas formas. Es fácil encontrar una solución si en cada etapa se genera el subcalendario correspondiente a un equipo. el lector puede intentar encontrar una solución voraz del problema del calendario. es definitiva.. Desglose en monedas Como primer ejemplo introductorio sencillo al que puede aplicarse la técnica voraz. si permite formar alguna solución del problema. utilizar el menor número de monedas.y
Un conjunto de restricciones sobre el valor de los datos de entrada y sobre la solución final del problema. Como fila primera se toma la secuencia de los índices de los participantes en cualquier orden. Una función que determine si cierto conjunto de candidatos es válido. sino que se utiliza durante el análisis del problema y es determinante en la elección de la función de selección. cada solución válida y completa es optima. y de un importe. se parte de un conjunto de tipos de monedas válidas. nunca cambian de opinión: una vez que un candidato es aceptado o rechazado en la solución. Se trata de indicar la cantidad (menor) de monedas de los tipos considerados. en este caso. es decir. Hay que desglosar una cantidad en un conjunto de monedas tratando de cumplir alguna condición. de las que se supone que hay cantidad suficiente para realizar el desglose.n) : (1. 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. 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.. solución) VorazAcumulador (candidatos. es decir. Además. pero si la función de selección es la adecuada. Podemos representar el esquema voraz de la siguiente forma funcional: FUNCTION Voraz ( candidatos: ( 1...n ) : ( 1. Solución : (1. ( ) ) Puede verse por qué estos algoritmos se llaman " voraces " : en cada paso toman el mejor trozo de la solución.. 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. se considera el problema de un cambio o desglose en monedas.
Esta restricción permite una formulación y resolución recursiva de los subproblemas. 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. Estos subproblemas se resuelven independientemente y después se combinan sus soluciones parciales para obtener la solución del problema original. mientras sea posible. Una solución viene dad por un conjunto de monedas devuelto tras el desglose. Por supuesto. Veamos el esquema de divide y vencerás para dos subproblemas. dado un problema al resolver planteando en términos de una entrada de tamaño n. y cuyo valor total es igual al importe a desglosar. El caso más frecuente es cuando el número de subproblemas es dos.Para simplificar. se descompone en varias partes más fáciles de resolver. 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. en particular. Mas formalmente. éste no será nunca excluido de él. 100. 1<k<=n. el proceso recursivo nunca terminaría. 25.
Con esta información se puede comprobar que en este problema están presentes los distintos elementos de la técnica voraz. la moneda de mayor valor de entre las candidatas. Estos valores se definen por medio de un tipo enumerado MONEDAS. Su formación funcional es como sigue. 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. Asimismo. 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. considerado el problema como de tipo dato y la solución. Su declaración es la siguiente: TYPE Monedas -> M500 I M100 I M50 I M25 I M5 I M1.M1 Se supone inicialmente asignados los valores a cada uno de los tipos de monedas. 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. La función objetivo cosiste en minimizar la cantidad total de monedas utilizadas en el desglose. deben existir algunos pasos sencillos cuya solución pueda calcularse fácil y directamente. es fácil su generalización a k subproblemas 2<k<=n. 50. de tipo resultado: TYPEVAR
. Esquema de Divide y vencerás. La función de selección establece que hay que elegir. 5 y 1 pesetas para el desglose. Después se resuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original. podemos utilizar sólo monedas de 500. en caso contrario. suponemos que manejamos dineroespañol y. cuando un candidato (moneda) se incorpora al conjunto solución. Además. Valores -> Integer M500 M1 Cantidades -> Integer M500 . la técnica de divide y vencerás parte la entrada en k subproblemas. 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.
escribiremos una formulación más restrictiva pero bastante usual. el tiempo de cómputo de la función DivideYVecneras se describe con la siguiente relación de recurrencia: g(n). inferior. IN inferior. superior. subsolucion1). superior) THEN ResolverDirectamente (problema. DyVAux (problema. subsolucion2.. DivideYVenceras (subproblema2)) Se puede hacer una formulación imperativa similar.N subsolucion1. TYPEVAR dato. Por concreció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. en la que se utiliza un vector de tamaño N. Partir y Combinar por funciones o procedimientos concretos. olución) ELSE Medio := Partir (inferior. Sin embargo. Elaboración de un Calendario Deportivo: Sea un campeonato deportivo. Nótese que. subsolucion2). solución) DyVAux (problema.n.Dato. OUT solución : resultado) -> PROCEDURE DyVAux (IN problema : dato1..N. y sin perdida de generalidad. en caso contrario donde T(n) es la función de tiempo de DivideYVenceras para entradas de tamaño n. puede suponerse que las competiciones se celebran en días sucesivos y
. resultado FUNCTION DivideYVenceras (problema : dato) : resultado -> EsPequeño (problema) }=> ResolverDirectamente (problema) | VALUE subproblemas -> Partir (problema) IN subproblemas == (subproblema1.. OUT solución : resultado) -> VAR medio: 1. inferior. ResolverDirectamente. solución) El esquema general se adapta a un problema concreto al sustituir los metasimbolos EsPequeño. subsolucion2 : resultado IF EsPequeño (inferior. para nuestros propósitos resulta indiferente el deporteobjeto de la competición.si n es pequeño T(n) = 2 T(n/2) + f(n). La eficiencia final del algoritmo depende de la función f(n) concreta que aparezca durante el análisis.n.. subproblema2) => Combinar (DivideYVenceras (subproblema1) . superior : 1. superior. 1. N. es general. para que esta técnica resulte eficiente todos los subproblemas deben ser de tamaño parecido. resultado PROCEDURE DivideYVenceras (IN problema : dato1. 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. superior). así que hablaremos de participantes en vez de deportistas o equipos. medio+1. Combinar (subsolucion1. medio. DyVAux (problema. Si el tamaño de los dos subproblemas es el mismo (o casi).
1<= i<=n. La siguiente figura describe visualmente parte de la elaboración de 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. Solo sirve como solución aquellas combinaciones de fila que cumplan las restricciones enunciadas en el párrafoanterior sobre las columnas de la tabla (las restricciones sobre las filas están garantizadas por el modo de generar los conjuntos P(i)).n}-{i} ahora se completan las filas de la tabla de todas las formas posibles.j)±esimo de la tabla. el conjunto de permutaciones de los números {1. Se necesitan elaborar n-1 competiciones por participantes. 1<=i<=n. Primero se obtiene para cada participante i. Se supone también que cada participante tiene asignado un número comprendido entre 1 y N. Cada conjunto P(i) consta de (n-1)! Elementos. Para simplificar el problema. la solución del problema puede representarse en una tabla de dimensión nx(n-1). A su vez. El método de fuerza bruta resulta sencillo.
días 1 participantes 1 2 2 1 1 2 3 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 8 5 6 7 3 4 1 2 7 8 5 6 4 3 2 1 6 7 8 5 5 6 7 8 1 2 3 4 6 5 8 7 4 1 2 3 7 8 5 6 3 4 1 2
. el conjunto P(i) de todas las permutaciones posibles del resto de los participantes con los que debe competir. Se dispone de una solución inmediata aplicando fuerza bruta. la columna j también contiene números distintos. El elemento (i. hay n = 2k participantes para algún entero positivo k. 1<=j<n. Dado que el numero de participantes de n.. Si hay varios calendarios validos. 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. incluyendo en cada fila i algún ejemplo de P(i). se elige uno cualquiera. pero es terriblemente ineficiente. contiene el numero del participante contra el que el participante i-esimo compite el día j-esimo. es decir. se supone que el numero de participantes es una potencia de dos. resultan nx(n-1)!=n! formas de rellenar la tabla. Por tanto. porque el día j-esimo cada participante solo puede competir con otro participante. es decir.que cada participante compite una vez por día.
N.8 7 6 5 2 3 4 1
Se distinguen dos casos. sucesivamente con los participantes 2k-1 +1. medio+1. rotando dicha secuencia a la derecha. es decir. El algoritmo descrito se expresa a continuación.1. de numeración comprendida entre 1 y 2k-1 y otro para los participantes comprendidos entre 2k-1 +1 y 2k .. Completemos primero la parte de los participantes de numeración inferior.N)1. el resto del calendario se puede construir fácilmente. CompletarTabla (inf.sup-1.1 := inf ELSE medio := (inf + sup) Div 2. FormarTabla (inf. ya que a unión de los dos calendarios tiene un tamaño 2k x(2k-1 -1).1.N-1) -> VAR medio : 1. Este proceso se repite para el resto de los participantes de numeración inferior. El caso recursivo.. .2n . Si el numero de participantes es 2k . El subcalendario del primer participante es sencillo porque basta con que compita en días sucesivos con los participantes de numeración. la mitad izquierda de la tabla. para k>1. sup. es más complejo. tabla). PROCEDURE Calendario ( INOUT tabla : (1.N. Finalmente se completa la mitad derecha de la tabla (correspondiente al cruce de los dos
.. 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.1 : = sup.. CompletarTabla (medio+1. sup.. inf. El caso básico se da cuando solo hay dos participantes... Después se genera. superior en orden creciente de numeración. La idea consiste en añadir inicialmente a la tabla una columna "ficticia" de índice j=0. 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). mediante divide y vencerás. OUT tabla : (1. también de orden de complejidad cuadrática. FormarTabla (medio+1. tablasup. 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. que almacena los índices de las filas.N-1) -> PROCEDURE FormaTabla (IN inf : 1. tabla). medio. medio. En efecto. tabla). cuando hay más de dos participantes.N. tabla) Este sistema de ecuacionesdefina una función de tiempo del orden de O(n2).. Veamos otra estrategia.N IF inf = sup-1 THEN tablainf. por ejemplo..N) 1. La solución es directa porque se celebra una sola competición entre ambos. medio. IN sup :1. Sin embargo. faltando 2k x2k-1 celdas para completar el calendario total.. sup-1. donde se aplica divide y vencerás para resolver el problema y que se aprovecha de la simetría de la solución.N. Por fortuna. que es mucho mas eficiente que la solución de fuerza bruta. la unión de estos subcalendarios no forma un calendario completo para el campeonato de 2k participantes. medio. faltan por elaborar las competiciones cruzadas entre los participantes de numeración inferior y los de numeración superior. 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.
inf. IN inf. los componentes tablai. siendo 1<=k<=n y 0<=l<=(n/2)-1.. Para el caso general.. medio)..m y vm+1. medio.N. es decir.s un vector de índice inferior i e índice superior s. N) El procedimiento para realizar la mezcla de los subvectores ordenados es: PROCEDURE Mezclar ( IN inf : INTEGER.grupos de equipos cuyos subcalendarios se han generado por divide y vencerás).N IF inf < sup THEN medio := (inf+sup) Div 2. medio+1.. 1. inf. El algoritmo resultante es: PROCEDURE Ordenar (INOUT v : INTEGER1. WHILE (i1<=medio) ^ (i2<=sup) DO IF vectori1 << vectori2 THEN vectorAuxj :=vectori1. mediante comparaciones de sus elementos sucesivos. OrdenarAux (vector.N.= vectori2.. índice : INTEGER i1 := inf. La partición puede hacerse por la mitad si se toma un índice m=[(i+s)/2] y dos subvectores vi.s . Mezclar (vector. 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. En esta última etapa. sup) OrdenarAux (v. Este proceso de mezcla es realizado por un procedimiento auxiliar. El caso básico corresponde a un subvector de un solo elemento. j := inf.N. la combinación de los dos subvectores ya ordenados es fácil.1. i2 := i2 + 1
. j : INTEGER. sup : 1.l).. basta con mezclar los dos subvectores. los valores de las casillas (k. i2 := medio + 1.. que obviamente ya esta ordenado. sup).. IN sup : INTEGER. sea vi. i1 :=i1 + 1 ELSE vectorAuxj . INOUT vector : INTEGER1. IN medio: INTEGER. i2. para obtener un único vector ordenado..l ya completadas.N) -> VAR Medio : 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. OrdenarAux (vector.j a partir de las casillas tablak. i1.N) -> VAR vectorAux : INTEGER1.N) -> (* ordenación por mezcla *) PROCEDURE OrdenarAux (INOUT Vector : INTEGER1..
j := j + FOR índice IN i1. de forma que las ecuaciones de recurrencia de la función de tiempo son: T(n) = a. Puede diseñarse un algoritmo de mezcla más complejo que mejore ambos aspectos. 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
. 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. b=cte Si n es una potencia de 2. que podemos llamar algoritmo convencional de multiplicación de matrices. Es fácil analizar la complejidad del algoritmo para un vector de longitud n. El cálculo de cada elemento Cij requiere n multiplicaciones.. J := j + 1 FOR índice IN i2. que existe un entero no negativo k tal que n=2k.sup DO vectorindice := vectorAuxindice El algoritmo resultante es sencillo conceptualmente. Los únicos inconvenientes que presenta es que el procedimiento de mezcla necesita gran capacidad de almacenamiento (para dos copias del vector) y que. las ecuaciones anteriores se resuelven por sustituciones sucesivas. Supongamos. pero mantenga la complejidad asintótica calculada. La matriz C tiene n2 elementos.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. J := j + 1 FOR índice In inf. así que el tiempo total del algoritmo de multiplicación es de orden O(n3).. por sencillez. proviene directamente de la definición matemática del producto de matrices. La matriz productoC=AxB también es una matriz de nxn cuyo elemento (i. n>1.sup DO vectorAuxj := vectorindice .medio DO vectorAuxj := vectorindice. que n es una potencia de dos. A y B. n=1. Multiplicación de Matrices: Sean dos matrices. además de mezclar. (Si n no es un potencia de dos. Sin embargo. es decir. La operación de mezcla es proporcional a n.) las submatrices A y B pueden partirse en cuatro submatrices de dimensión (n/2)x(n/2). pueden añadirse las filas y columnas de ceros necesarias para formar una dimensión que sea potencia de dos. a=cte 2T(n/2) + bn. n =2k para algún k.. la técnica de divide y vencerás sugiere un algoritmo distinto. necesita copiar el vector auxiliar completo en el principal. es decir. de dimensión nxn. El algoritmo anterior.
Sin embargo. 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 ". pero de una manera menos directa que en el caso voraz. Usando una técnica de fuerza bruta. interesa encontrar algoritmos mas eficientes. de forma que no se ha conseguido ningún ahorro sustancial de tiempo. porque si hay d opciones para cada una de las n decisiones. 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. todo problema resoluble con esta técnica debe de satisfacer el principio de optimalidad. resultará un total de d secuencias posibles de decisión.. Además. 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. pero para n>2 las submatrices Cij se calculan mediante multiplicaciones (recursivas) y sumas de submatrices de dimensión (n/2)x(n/2). siendo b alguna constante. no todos los problemas pueden resolverse de esta manera. conduciendo de forma directa a la solución. dado que la complejidad respectiva de estas operaciones es O(n3)n y o(n2). No es fácil establecer una definición de la programación dinámica. Supongamos que tenemos un problema que satisface el principio de optimalidad. Dos submatrices de (n/2)x(n/2) pueden sumarse en un tiempo bn2. Sea D = { v1 . Sin embargo. La resolución de este sistema de ecuaciones nos dice que O(T(n))=OT(n3).vn} el conjunto de valores de decisión posibles para la decisión d1. El algoritmo de Strassen calcula las cuatro submatrices Cij empleando 7 multiplicaciones y 18 sumas o restas de matrices. asimismo. Esta vez se necesita producir varias secuencias de decisiones.Para n=2. el número de secuencias de decisión es exponencial sobre el número de decisiones. Entonces. 1<i<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. sea. una secuencia óptima de decisiones respecto a E0 es la mejor secuencias de decisión { Vli Sli }. Podría conseguirse mas eficiencia si lográramos realizar menos multiplicaciones de matrices. tal que Eo es el estado inicial del problema y deben tomarse n decisiones d. una característica es que el programa "aprende "dinámicamente de las decisiones que toma. los elementos Cij se calculan mediante algunas multiplicaciones y sumas de números. El método es eficiente porque una vez que se toma una decisión en un paso. De esta forma se reduce al número total de subsecuencias generadas. Podemos formalizar algo más la idea básica. como inversión de una matriz o hallar su determinante. aunque fuera a costa de un mayor numero de sumas de matrices.
. Solamente al final se sabe cuál es la mejor de todas. 1<i<N1. no se reconsidera en el futuro. para cualquier operación de las anteriores) significaría la existencia de un algoritmo similar para las demás. 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. 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. La existencia de un algoritmo eficiente para la multiplicación (en realidad. porque la multiplicación esta relacionada con otras operaciones sobre matrices mas usuales. asegurando que la secuencia de decisiones es la mejor de las posibles.
.. a partir de la secuencia de decisiones Xi+1 Xn ( es la clase de formulación adoptada hasta ahora ). los candidatos para la posición i+1 del vector desolucion x1. La ecuación de recurrencia puede formularse de dos formas: delantera o trasera.. 1<i<n .n son aquellos valores generados por G que satisfacen A.n )..... La formulación delantera expresa la decisión de Xl . 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.. a partir de la recurrentes con formulación trasera es igual que e la formulación delantera. En algunos problemas de optimización se conoce un criterio óptimo de selección que puede usarse de forma voraz.l).. hay un caso en que la decisión d1 no va seguida por ninguna secuencia de decisiones.xi+1) es falso si el camino (xi.. Por lo tanto. la ecuación de base establece el valor para la etapa n+1 en que no queda ninguna decisión Xi. La formulación trasera expresa la decisión de Xi. que es problema ( n. todavía hay otros problemas peores que no queda mas remedio que realizar una búsqueda de la solución. Tiene sentido centrarse en un subproblema del problema inicial porque éste satisface el principio de optimalidad pero.. 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.. si este subproblema de simboliza como problema (k.dl..n ).. Sin embargo. pudiéndose aplicar la técnica de programación dinámica..1 ) debe expresarse en términos de los valores de decisión existente para decisiones d1 y el subproblema problema ( k+1. 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... del gusto del programador.. Por supuesto..xi+1) termina en un nodo de respuesta.) Una solución dinámica para problema ( k. cada solución es el resultado de una secuencia de decisiones.xi) el conjunto de todos los valores posibles de xi+1 tales que (x1.xi+1) es un camino hasta el estado del problema.xi+1) no puede extenderse para alcanzar un nodo de respuesta.. sencillamente. Además. La elección de una formulación delantera o trasera depende del problema considerado o. INOUT solucion : elemento1.. Esquema de Algoritmos de Vuelta Atrás: Sea (x1. sólo que en orden contrario. entonces el problema completo es problema ( l.Xn la secuencia de decisiones necesaria para resolver el problema. a tomar.... 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. Supongamos que también existe algún predicado R que determina si un camino (x1. Otros problemas satisfacen el principio de optimalidad.. puede generalizarse la formulación del problema a cualquier subsecuencia de decisiones dk . Supongamos que existe algún predicado acotador A tal que A(x1.xi) el camino desde la raíz hasta un nodo de un árbol del espacio de estado. además.1 ) resultante de aplicar cada valor de decisión.El razonamiento anterior se refiere a la primera decisión d1 tomada desde el estado inicial E0 sin embargo. 1<i<n. El Algoritmo de Vuelta Atrás se especifica de la forma siguiente: PROCEDURE Retroceso (IN k : INTEGER. Sea G(x1. partiendo como estado inicial de Ek-1. 1<i<n. 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 expresión inicial de la ecuación de recurrencia..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. En resumen. Sea X1 . 1<k<n.
solucion). 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). 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. IF R(solucion. 1. Normalmente.VAR nodo : elemento FOR noso IN G(solucion. 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. Después simplemente se llama recursivamente al algoritmo para generar los estados descendientes. 1. encontrar un ciclo simple de costo mínimo que pase por todos los nodos. Algoritmos Heuristicos Existen muchos problemas para los cuales no se conocen algoritmos que puedan encontrar la solución de forma eficiente: problemas NP-completos. Es un problema NP. Retroceso (k+1. pero necesitamos una solución eficiente. k-1) DO Solucion k := nodo. donde la solución está formada por un grupo de elementos en cierto orden: podemos aplicar el esquema voraz. Este mismo proceso se repite en el resto de nodos del árbol. A). En este punto podemos retroceder (y no seguir avanzando por mas ramas). se basa en un conocimiento intuitivo del programador sobre un determinado problema. Posibilidades:
. Así. 1. completo y ponderado G = (V.k) THEN << guardar µsolucion¶ >>. Objetivo: obtener buenas soluciones en un tiempo de ejecución corto. pues tenemos ya una solucion mayor. 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. El problema del viajante Problema: Dado un grafo no dirigido. k sirve de cota inferior al retroceso. Se sale del bucle FOR cuando no quedan mas valores para solución terminando la llamada actual al algoritmo. 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. Problema de optimización. evitando así la exploración de gran parte de al estructura. La estructura de algoritmo voraz se puede utilizar para construir procedimientos heurísticos: hablamos de heurísticas voraces. La solución exacta puede requerir un orden factorial o exponencial: el problema de la explosión combinatoria. k) THEN IF R(solucion. solucion) La llamada inicial del algoritmo es Retroceso(1. se comprueba si se ha encontrado una solucion.
2) Coste: 30+15+25+10+45=125 Empezando en el nodo 3. 5)) Coste = 10+15+20+45+50 = 140 Conclusiones: Ninguno de los dos algoritmos garantiza una solución óptima.. Selección: seleccionar la arista candidata de menor coste. 1) Coste: 15+20+10+45+50=140 Heurística voraz 2 ± Una solución será un conjunto de aristas (a1. c2. próximas a la óptima. Sin embargo. Solución: ((2. Empezando en el nodo 1. Se trata de calcular un subconjunto A¶ de aristas tal que dos aristas
. En cada paso moverse al nodo no visitado más próximo al último nodo seleccionado. 4. normalmente ambos dan soluciones buenas. repetir la heurística 1 con varios orígenes. 3). Hacer igual que en el algoritmo de Kruskal. 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.
Los nodos son los candidatos. 3. ca). . sin importar el orden. pero garantizando que se forme un ciclo. Las aristas son los candidatos. Heurística voraz 1 ± Una solución será un cierto orden en el conjunto de nodos (c1. Acabamos cuando tengamos n nodos. 5). Solución: (5. (1. . 2.. Ejemplo. 2). a2.. Sin embargo. resulta parcialmente interesante que estos garanticen una cota en el margen de imprecisión. ó bien. 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. (3. A continuación se ilustra este tipo de tratamiento de problemas al problema de recubrimiento de un grafico: Dado un grafo G=(V. an-1) que formen un ciclo hamiltoniano.1. .. c2. Algoritmos De Aproximación Dado un problema NP completo. 2.A). Para este tipo de problemas. 4). 4.. Ejemplo. los algoritmos que no conducen a una solución óptima se llaman algoritmos de aproximación. (1... 5. como es calcular el ajuste maximizal del grafo G. Solución: (1. 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. es probable que no sepamos resolverlo de manera precisa y completa utilizando un algoritmo polimico en tiempo. Empezar en un nodo cualquiera.. cn). a partir de la solución del algoritmo intentar hacer modificaciones locales para mejorar esa solución. Empezar con un grafo sin aristas. Inicialización: seleccionar un nodo cualquiera. el orden de visita de los nodos. 3. Este problema se puede resolver a través de otro aproximado.. (4. Posibles mejoras: buscar heurísticas mejores.
En el siguiente trabajopretendemos presentar una serie de conceptoy definiciones propios del estudio de los Algoritmos. su análisis y diseño. 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. divide y vencerás.análisis y diseño. entre otros. Esto es evidente. también por la propia definición. los diseños de estos últimos. la recursividad e iteración.
. de una en una y en cualquier orden e ir eliminando las incidentes al conjunto que se esta construyendo hasta recubrir todo en grafo. 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. De igual forma podremos ver las definiciones y algunas características. ya que por la definición de ajuste maximal. tipos de algoritmos de búsqueda y ordenación así como sus aplicaciones. programación dinámica. su importancia en el mundo de las aplicaciones para computadoras y el manejo de lógica de programación. ningún vértice perteneciente a M puede recubrir a mas de una arista en M. normas. En el mismo podremos encontrar los conceptos de algoritmo y algunos de sus componentes. que desde su aparición hasta nuestros días es. vital para el desarrollo de aplicaciones para computadorasy el manejo y dominio de la lógica de programación para resolver problemas. En consecuencia. y seguirá siendo.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¶. Objetivos General : Posibilitar la estudiante alcanzar una visión sistemática de lo que conocemos sobre Los Algoritmos Computacionales. El procedimiento para construir un ajuste maximizal de un grafo G consistiría en ir tomando aristas de G. donde daremos los conceptos básicos de semánticay sus tipos haciendo mayor énfasis en la semántica axiomática. Justificacion Es importante el estudio y conocimiento de lo que hoy conocemos como Algoritmos Computacionales. En ese mismo orden encontraremos las diferentes técnicaspara diseñarlos como son el método de la fuerza bruta. Finalmente veremos los que es la verificación y derivación de programas. el voraz. Específicos : Introducir los conceptos propios sobre Algoritmo. los vértices incidentes a las aristas de M son un recubrimiento de G. de vuelta atrás. 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. Con el objetivoinmediato de aprobar con los mejores meritos la asignatura de Algoritmos Computacionales. Este nuevo problema garantiza conseguir un recubrimiento que contiene no más de dos vértices del recubrimiento mínimo. Para poder aplicar el nuevo problema aproximado. reglas. 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. por lo menos la mitad de los vértices de M deben pertenecer a un recubrimiento.
se considera con Al-Khowarizmi el otro gran padre de la algoritmia ( ciencia que trata de los algoritmos). El lenguajealgorí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.) 3. 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. Aunque la popularización del término ha llegado con el advenimiento de la era informática. Un algoritmo es un método para resolver un problema. El profesor Niklaus Wirth. inventor de Pascal. Esta ecuación será de una de las hipótesis fundamentales consideradas en esta obra. de algoritmo. búsqueda. Proporcionar concepto sobre las técnicas de diseño. (Fase de codificación. Desglosar sus variantes (ordenación. multiplicar y dividir números decimales. Modula-2 y Oberon. Visualizar sus ventajas e importancia. El eje central de esta metodología es el concepto. Algoritmos + Estructuras de Datos = Programas. ). 3. el cual escribió sobre los años 800 y 825 su obra Quitad Al Mugabala. Es un método para resolver un problema mediante una serie de datos precisos. la traducciónal latín del apellido de la palabra algorismus derivo posteriormente en algoritmo. donde se recogía el sistema de numeración hindú y el concepto del cero. Fue Fibinacci. Definir sus tipos y variantes. restar.
. que describe la secuencia ordenada de pasos que conducen a la solución de un problema dado. matemático persa que vivió durante el siglo IX y alcanzo gran reputación por el enunciado de las reglas para sumar. titulo uno de sus mas famosos libros. Proporcionar conceptos sobre su análisis y diseño. Generalidades El programador de computadoras es ante que nada una personaque resuelve problemas. Marco Historico Un algoritmo es un conjunto de operaciones y procedimientosque deben seguirse para resolver un problema. por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto.y y y y y y
Proporcionar una idea de su uso. algoritmo proviene de Mohammed alKhowarizmi. Los pasos para la resolución de un problema son: 1. 2. ya tratado.
2. 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. Euclides. se le denomina algoritmo. definidos y finitos. Ejecución y validación del programa por la computadora. La palabra algoritmo se deriva del nombre latinizado del gran Matemático Árabe Mohamed Ibn Al Kow Rizmi. A la metodología necesaria para resolver problemas mediante programas se denomina Metodología de la Programación. etc. (Análisis del problema y desarrollo del algoritmo). el que tradujo la obra al latín y el inicio con la palabra: Algoritmi Dicit. El conjunto de todas las operaciones a realizar y e orden en que se deben efectuarse. Expresar el algoritmo como un programa de lenguaje de programación adecuado. Diseño de algoritmo.
Los métodos mas eficaces para el proceso de diseño se basan en el conocido por Divide y Vencerás. Redactar el algoritmo correspondiente.Para llegar a la realización de un programa es necesario el diseño previo de algoritmo. ingles o francés. 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. En la etapa de diseño se determina como hace el programa la tarea solicitada. En la cienciade la computación y en la programación. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta. Si se sigue un algoritmo dos veces. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Proceso y Salida. En esencia. Salida: terminación del plato (por ejemplo. 5. Un algoritmo debe ser finito. inicio leer el pedido examinar la ficha del cliente si el cliente es solvente aceptar pedido. Tanto el lenguaje de programación como la computadora son los mediospara obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente. Esta examina en su banco de datos la ficha del cliente. Los pasos del algoritmo son: 1. el algoritmo será siempre el mismo. la
. sin embargo. 2. Ejemplo de Algoritmo: Un cliente ejecuta un pedido a una fábrica. los algoritmos son más importantes que los lenguajes de programación o las computadoras. por ejemplo. El diseño de la mayoría de los algoritmos requiere creatividady conocimientos profundos de la técnica de la programación. Dada la importancia del algoritmo en la ciencia de la computación. 4. los pasos para la elaboración del plato se realizaran sin importar el idioma del cocinero. cordero). o sea.
La definición de un algoritmo debe definir tres partes: Entrada. una receta de un plato de cocina se puede expresar en español. Así. rechazar pedido fin
Diseño del Algoritmo: En la etapa de análisis del proceso de programación se determina que hace el programa. Un algoritmo debe estar definido. debe tener un numero finito de pasos. la solución de un problema se puede expresar mediante un algoritmo. Proceso: elaboración de la receta en la cocina. Si se sigue un algoritmo se debe terminar en algún momento. es decir. un aspecto muy importante será el diseño de algoritmos. se debe obtener el mismo resultado cada vez. 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 computadoraque lo ejecuta. 3. en caso contrario. En el algoritmo de receta de cocina citado anteriormente se tendrá: Entrada: ingrediente y utensilios empleados. en caso contrario rechazara el pedido. pero cualquiera que sea el lenguaje. si el cliente es solvente entonces la empresa acepta el pedido. en una analogía con la vida diaria.
El proceso de romper el problema en cada etapa y expresar cada paso en forma más detallada se denomina refinamiento sucesivo. Un algoritmo es mejor cuantos menos recursos consuma. fácil de entender. comprobados y depurados independientemente (incluso por diferentes programadores) y a continuación combinarlos entre si. robusto. su facilidad de programarlo. Comunicaciones. El diseño del algoritmo es independiente del lenguaje de programación en el que se vaya a codificar posteriormente.
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. Recursos consumidos: Ejemplo. Análisis De Algoritmos Recursos De Computadores Y Complejidad Algoritmo: Conjunto de reglas para resolver un problema. Comprobar el modulo. Los módulos pueden ser planeados. etc. Cada sub programa es resuelto mediante un modulo (sub programa) que tiene un solo punto de entrada y un solo punto de salida. Este método se conoce técnicamente como diseño descendente (Top Down) o modular. Memoria principal: Entradas/salidas a disco. ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo sencillo? i:= 0 a[n+1]:= x repetir i:= i + 1
. El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:
programar modulo. Combinar el modulo con los módulos anteriores. Su ejecución requiere unos recursos. forma aproximada o algunos casos. etc. 4. Si es necesario. 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. Recursos consumidos: Tiempo de ejecución. Eficiencia: Relación entre los recursos consumidos y los productos conseguidos. 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. depurar el modulo. codificados. Lo que se consigue: Resolver un problema de forma exacta. Criterio empresarial: Maximizar la eficiencia. procesadores. corto.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.
? Sabemos que cada ejecución lleva un tiempo constante.. Operaciones básicas (+. :=.2 s
.. T(4)= 0. ¿Se puede predecir cuándo se cumplirán las condiciones? Llamadas a procedimientos: Calcular primero los procedimientos que no llaman a otros. 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. Contenido de los datos de entrada.. o alguna constante. IF y CASE: Estudiar lo que puede ocurrir. Cray. ¿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. ¿Cuánto tiempo. externos no aportan información sobre el algoritmo. o una constante diferente. Programa "cifras. La implementación que haga el programador del algoritmo. Tamaño de los datos de entrada. de la máquina. de lo que haya en a. de forma aproximada (y parametrizada).. Instrucciones ejecutadas por el algoritmo. luego se diferencia en una constante con los anteriores. Caso promedio. Media de todos los posibles contenidos. La ejecución más lenta posible. T(6)= 0.. de las estructuras de datos utilizadas. Mejor caso. Los factores externos no aportan información sobre el algoritmo. Pentium III. Operaciones de entrada salida: Otra unidad de tiempo.. Ejemplo. El contenido favorece una rápida ejecución. El ordenador donde lo ejecutemos: 286. T(N) = bN + c. Algunas reglas básicas.hasta a[i] = x Respuesta: Depende. T(N) = N+1.exe": N= 4. de los tipos de datos.): Una unidad de tiempo. Asignación de tiempos... ¿Tardarán todas lo mismo? Ejecuciones del bucle principal. T(5)= 5 ms N= 6. pero ¿qué significa T(N)? Tiempo de ejecución en segundos. T(N) = 2N + 4. ¿De qué depende? De lo que valga n y x.. *. Suponiendo que b y c son constantes.. Calcular la media de una matriz de NxM. con los segundos que tardan las operaciones básicas correspondientes. -. Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir. cuántas instrucciones.. En particular.. con los límites del FOR.1 ms N= 5. En general los recursos dependen de: Factores externos. El lenguaje de programación y el compilador usado. Normalmente usaremos la notación T(N)=.. para el conteo de instrucciones. Bucles FOR: Se pueden expresar como una sumatoria. Mejor caso y peor caso según la condición. Peor caso. Ejemplo..
W (f+g) = W (max(f+g)) ¿Y para los Q (f+g)? ¿Es cierto que O(f . T(8)= 3. -g))? P5.. 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(. Dadas f y g de N en R+. se cumple: i) limn¥ ® f(n) Î R+ Þ O(f)=O(g). W (g) Í W (f) g(n)
. Nos interesa un análisis que sea independiente de esos factores.. Dadas f y g de N en R+. W (T): Orden inferior de T. Podemos comparar con otros algoritmos. Si f Î W (g) y g Î W (h) entonces f Î W (h) Ej. " n ³ n0: t(n) £ c·f(n) } Nota: O(f) es un conjunto de funciones. ¿Cómo es la relación para los W ? P3. no sólo tiempos de ejec. ¿se cumple O(f)Í O(g) ó O(g)Í O(f)? P4. Orden de complejidad de f(n): O(f) Dada una función f: N ® R+. si el algoritmo es poco eficiente.) es completa? Dadas f y g.g) = O(max(f.": nos quitamos las constantes. Q (T): Orden exacto de T. Podemos hacer previsiones.. Grandes.. Propiedades P1. para valores de n suficientemente grandes. La definición es aplicable a cualquier función de N en 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. O(f)= { t: N ® R+ / $ c Î R+. O(f+g) = O(max(f. de N en R+. g)). "Funciones acotadas superiormente por un múltiplo de f. para valores suficientemente grandes (asintóticamente) sin considerar constantes. n Î O(n2) Þ 2n+1 Î O(n2) P2. O(T): Orden de complejidad de T. Q (f)=Q (g) g(n) ii) limn¥ ® f(n) = 0 Þ O(f) Í O(g).": no nos importa lo que pase para valores pequeños. Dadas f y g.5 min ¿Qué conclusiones podemos extraer? Análisis a priori: Evitamos la implementación. "Valores de n sufic. u omega de T. Si f Î O(g) entonces O(f) Í O(g). $ n0 Î N. T(7)= 10 s N= 8. Si f Î O(g) y g Î O(h) entonces f Î O(h). no una función. 2n+1 Î O(n).. 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. Notaciones asintóticas: Indican como crece T.N= 7. W (f)=W (g).
Para cualquier f y g.. podemos extender los conceptos de W (f) y Q (f). km) £ c·f(k1. k2 ³ n2 . . . o variables T(N. nm): O(f) Dada una función f: Nm ® R+.. f: Nm ® R+ (f: Nx.) = Relación de inclusión entre conjuntos.. $ n0 Î N.. el tiempo y la memoria consumidos pueden depender de muchos parámetros.a. y del tiempo de inicialización b y de ejecución de un paso a.
... O(f) = O(f | true).n. para funciones con varios parámetros.. " k1 ³ n1 . tenemos W (f | P) y Q (f | P). ¿Qué relación hay entre O(log2 n) y O(log10 n)? P6. Orden condicionado de f(n): O(f | P) Dada una función f: N ® R+..." km ³ nm : t(k1. ¿Qué relación hay entre los siguientes órdenes? O(n+m). t(n) Î O(n2). n2. para valores de (n1. k) = kB+l+n+2kn Orden de complejidad de f(n1.b).. O(n+2m) Notaciones condicionales: En algunos casos interesa estudiar el tiempo sólo para ciertos tamaños de entrada. ¿O(f) « O(f | P)? Ordenes De Complejidad Uso de los órdenes de complejidad: Dado un tiempo t(n).xN ® R+) Ej. k2. llamamos orden de f al conjunto de todas las funciones de Nm en R+ acotadas superiormente por un múltiplo real positivo de f. Ejemplo.m. Ej. Relación de orden entre O(. Algoritmo de búsqueda binaria: Si N es potencia de 2 el estudio se simplifica. .. O(f)= { t: Nm ® R+ / $ c Î R+. " n ³ n0: P(n) Þ t(n) £ c·f(n) } De igual forma.. 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. M(B.... k2. llamamos orden de f según P (o condicionado a P) al conjunto: O(f | P)= { t: N ® R+ / $ c Î R+. .. t(n) = 2n2/5 + 3p /2. Las propiedades se siguen cumpliendo ® Demostrarlo. y P: N ® B. a. Ejemplo. nm Î N... O(nm) O(n2). . encontrar la función f más simple tal que t Î O(f). T(N) = T(N. f Î O(g | false). l. b) = a·N + b El tiempo depende del tamaño del problema N. Dadas f y g de N en R+. Dadas f y g de N en R+.P5.. km) } De la misma forma. $ n1. Memoria en una tabla hash. y que más se aproxime asintóticamente. n2. O(f)=O(g) Û Q (f)=Q (g) Û f Î Q (g) Û W (f)=W (g) P7.. Podemos suponerlos constantes T(N). Ejemplo. nm) suficientemente grandes..
aparecerá un orden logarítmico O(log2 n). t Î O(g) Se cumple que: O(c) = O(d). nnn å 1 = n Î O(n). n/4. independientemente de la base. para valores de n suficientemente grandes. 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. W (f)= { t: N ® R+ / $ c Î R+.±O(f) £ O(g) Û O(f) Í O(g) Û Para toda t Î O(f). Ì O(2n) Ì O(n!) Ì O(nn) ¿Qué pasa con las omegas? ¿Y con los órdenes exactos? El orden de un polinomio anxn+.. å im Î O(nm+1) i=1 i=1 i=1 Si hacemos una operación para 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+. .. d Î R+. 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 .. " n ³ n0: t(n) ³ c·f(n) } La notación omega se usa para establecer cotas inferiores del tiempo de ejecución. Q (f) = O(f) Ç W (f) = { t: N ® R+ / $ c. 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.) Ì O(n2) Ì O(n3) Ì . O(c) Ì O(n) O(cn + b) = O(dn + e) O(p) = O(q).. si p y q son polinomios del mismo grado. Ejemplo. Los logaritmos son del mismo orden.. asintóticamente y salvo constantes. El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá ser del todo
. 5.. siendo c y d constantes positivas. t(n) = amnm + am-1nm-1 + .001... $ n0 Î N. si p es un polinomio de menor grado que q. otra para n/2. +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. Orden exacto de f(n): Q (f): Dada una función f: N ® R+.. O(p) Ì O(q). Relación de orden: igual que antes. llamamos orden exacto de f al conjunto de todas las funciones de N en R+ que crecen igual que f..+a1x+a0 es O(xn). å i = n(n+1)/2 Î O(n2).Es necesario en este momento mencionar algo sobre como hacerlo. $ n0 Î N.
Por ultimo. puesto que existe un número reducido de esquema y técnicas de diseño. y el empleode tablas como estructura auxiliar para la resolución eficiente de problemas donde se aplica programación dinámica). No obstante. Muchos problemas pueden resolverse buscando una solución fácil y directa pero. el uso de parámetros de acumulación al resolver problemas utilizando divide y vencerás. La investigaciónen 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. 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 principiosbásicos del diseño de algoritmos podemos preguntarnos por un método aceptable. a la vez bastante ineficiente. siendo dicha solución finalmente adaptada al dominio original. se decir. El esquema mas sencillo quizás sea el llamado divide y vencerás. idear un algoritmo continua siendo una labor bastante creativa donde los conocimientos y la experiencia del propio diseñador tiene un papel fundamental. una tarea difícil. pero con un poco de análisis puede encontrarse algoritmos más eficientes. Supongamos que disponemos de una especificación precisa. podríamos utilizar un algoritmo general llamado algoritmo del museo británico. puede ser muy directo. su tarea se simplifica. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado. basado en la descomposición de un problema en subproblemas. Aun así. y a pesar de que resulta mas adecuado en bastantes casos utilizar alguno de estos esquemas que realizar un diseño desde cero. en general. conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica. El diseño de un algoritmo que resuelva un problema es. Nos estamos refiriendo a métodos basados en la mejora de la eficiencia (por ejemplo. que debe
. Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Si no nos importa la eficiencia del algoritmo. Consideraciones generales Si el hábil programador dispone de un recetario de algoritmos de donde poder seleccionar el más adecuado para cada problema. a pesar de lo complejas que son las operaciones de búsqueda. 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. y quizás el mejor. El conocimiento de técnicas de diseño es solo un primer paso para el diseñador. El mas entendido. solo puede tomarse tras considerar varias solucionesde otras etapas mas simples. su uso adecuado mediante el esquema de búsqueda con retroceso (o backtracking) permite ganar gran eficiencia respecto a soluciones de fuerza bruta. Este método. y a métodos basados en transformaciones del dominio para encontrar una solución mas fácilmente a un problema en un dominio transformado. tenemos una solución voraz. Todo problema algorítmico es un reto para su diseñador. la solución es dinámica. hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda. Una forma de facilitar esta labor consiste en recurrir a técnicas conocidas de diseño de algoritmos. completa y consistente del problema a resolver y queremos obtener un algoritmo en el que. Este método de trabajo es practicable. llamado de fuerza bruta. si la decisión en una etapa. dados uno datos de entrada valido. se produzca cierto resultado. a esquemas muy generales que pueden adaptarse a un problema particular al detallar las partes generales del esquema. otros son bastante complejos.automatizada. algunos resultan inmediatos de resolver.
Los parámetros adicionales tienen como misión ir acumulando resultados principales durante el proceso recursivo. sobre todo. pero dado que no se ha analizado apenas el problema. no es un esquema algorítmico. La función principal usa una función auxiliar que tiene los parámetros de aquellas más algunos adicionales. en combinación con otras contrucciones. es muy probable que no se hayan aprovechado propiedades deducibles del problema y que la solución sea terriblemente ineficiente. con la experiencia. poco reflexionada. pero poco reflexionada. esto no es malo. Método de fuerza bruta Comenzamos el estudio de esquemas algorítmicos con un método sencillo. En principio. pero debe mejorar su rendimiento para que sea práctico. 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. dichos algoritmos pueden servir como una primera aproximación al algoritmo definitivo. si no mas bien calificativo Para una forma de diseñar algoritmos: tomar una solución directa. 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.
. Otro algoritmo realizaba un búsqueda dicotomica o binaria. Técnicas de los Parámetros Acumuladores y de Tabulacion La recurcion es un mecanismo que permite obtener. Muchos algoritmos recursivos resultan eficientes. Parámetros Acumuladores Veamos primero una solución ineficiente que intentaremos mejorar.completarse con otros conocimientos y. pero que debe evitarse siempre que se pueda. dad su ineficacia. 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. aprovechar esta circunstancia para usar el algoritmo más eficiente: el de búsqueda binaria. Esta es la solución de fuerza bruta: una solución directa. una solución funcional a muchos problemas. En estos casos. Cada una se ilustra con un ejemplo distinto. Un modo de evitar problema lo proporciona la técnica de los parámetros acumuladores. y solo se podía usar cuando el vector estuviese ordenado. 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 . cuya idea básica se expone a continuación. la fuerza bruta. en caso positivo. Lo más razonable es comprobar si el vector esta ordenado y. pero muy ineficientes. Veremos dos parámetros para la mejora de eficiencia de algoritmos recursivos: el uso de parámetros acumuladores y el uso de tablas. El algoritmo primero responde a un razonamiento más sencillo. por lo que uno puede sentirse tentado a usar siempre. con complejidad logarítmica. En realidad. Una solución por fuerza bruta también puede resultar adecuada como primera aproximación a la solución final. pero no todos: hay algunos fácilmente formulables.
continua aplicándose el mismo criterio para la segunda moneda mas valiosa. la planificación en el orden de la ejecución de unos programas en un computador. que juegan una competición que es ganada por el primero que venza en n partidos. El proceso finaliza cuando se ha devuelto todo el cambio. la búsqueda en estructuras ordenadas. A.Para ello. si es posterior. Ejemplo. no importa que). Ejemplo: Sea el problema de la competición. se supone que ambos participantes tienen cualidades y preparación similar . Si no ha encontrado y es anterior se procede a buscarla en la primera mitad. Hay dos participantes (deportistas o equipos. Puede emplearse en problemas de optimización. se trata de dar como cambio la menor cantidad posible usando estos tipos de monedas. donde puede consultarse otras veces que se necesite. la ordenación de vectores. Consideraciones y Criterios para Diseñar Algoritmos Algunas consideraciones estilísticas pueden contribuir a mejor la calidadde los algoritmos (y programas ) mediante la reducción del numero de errores que aparecen al desarrollar los.
. 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 diccionariode acuerdo con el siguiente criterio. Esta técnica también se suele emplear con la programación dinámica. Método voraz: Este método trata de producir tipo de mejor resultado a partir de conjunto de opciones candidatas .Tabulacion No todos los algoritmos recursivos ineficientes pueden optimizarse con la técnica de los parámetros acumuladores. cuando se pueda. Por sencillez . como el conocido de la mochila. se almacena en una tabla. resolver independientemente los subproblemas para luego combinar sus soluciones y obtener la solución del problema original. Dar un cambioutilizando el menor número de monedas Considérese ahora el problema de la devolución del cambio al realizar una compra (por ejemplo. la moneda de mayor valor ( es decir. la modificación para incorporar probabilidades diferentes es evidente y no complica el problema.etc. El procedimiento se repite sucesivamente hasta encontrar la palabra o decidir que no aparece.B.. De todas formas. en la búsqueda de caminos mínimos sobre grafos. y así sucesivamente.etc. 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. siendo ( n ) mayor que( 0 ). en una maquina expendedora de tabaco). mientras el valor de dicha moneda sea mayor o igual al cambio que resta por dar). La intención es que la primera vez que se realiza un cálculo. se buscara en la segunda mitad. Otra técnica útil es el uso de tablas. 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. De forma que cada uno tiene un 50% de posibilidades de ganar cada partido. Divide y vencerás: Consiste en descomponer un problema en un subproblema. Esta técnica se puede aplicar con éxito a problemas como la multiplicación de matrices. La estrategia voraz aplicada comienza devolviendo. Suponiendo que se disponga de cantidad suficiente de ciertos tipos diferentes de monedas de curso legal.
Claridad. la calidad de un algoritmo tiene muchas facetas y todas ellas importantes. Esta característica hace que aunque el análisis del problema sea arduo. Estilo y calidad de los programas van fuertemente unidos. 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. estas normas de estilo se dirigen hacia aspectos como la forma de construir los nombres de variables o tipo de datos que aparezcan. 4. Un algoritmo voraz sigue el esquema anterior. cierta medida. Pude aparecer obvio. eficiente. fiable y fácil de mantener. Es más frecuente que el subconjunto de la solución se vaya formando paso a paso. 1. Eficiencia. 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. En realidad. el problema incluye restricciones adicionales que limitan el número posible de soluciones. estos problemas no se intentan resolver "de golpe ". lo ideal es que nuestro algoritmo resulte correcto. Ante la pregunta ¿Cuáles son las característica de un buen algoritmo?. Normalmente.También influyen haciendo que nuestro algoritmo resulten más fáciles de leer y entender para otras personas. los factores que identifican la calidad en ellos . El modo de encolumnar las distintas partes de un algoritmo para facilitar su lectura y comprensión. la solución voraz siempre
. Resumiendo. dados unos ficheros almacenados en una cinta de que el tiempo de recuperación de un fichero cualquiera sea el mínimo en promedio.. En particular. y la normas sobre como y donde deben de introducirse los comentarios. Puede haber varias soluciones optimas. sea el problema de encontrar un subconjunto de los arcos de un grafo. Se supone que un problema de esta clasetiene al menos una solución. palabras claves. se habla de la memoria y del tiempo de ejecución . 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. la tipografía seguida ala hora de escribir nombres de variables. las siguientes respuestas reflejan. subprogramas. Generalmente. el algoritmo no debe desaprovechar recursos. en cuyo caso no importa cual se elija. el algoritmo debe estar bien documentación. 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. y de acuerdo con los puntos de vista anteriores. 3. encontrando de una sola vez la solución completa y óptima. Ello asegura que tanto algoritmos como programa resulten legibles y puedan modificarse fácilmente en caso de necesidad. etc. Corrección. el algoritmo debe funcionar. Otro ejemplo se da cuando. 2. claro. Los criterios de estilo pueden reflejarse en un conjunto de normas de estilo de codificación. analizando durante cada etapa que elemento conviene añadir a la solución parcial ya existente. La eficiencia de un algoritmo se mide por los recursos que este consume. Por ejemplo. Ciertos detalles o algunas partes especiales de los mismos pueden olvidarse fácilmente o quedar oscura si no están adecuadamente comentadas. pero resulta difícil de asegurar en algoritmos complejos. Nunca se debe olvidar que la característica más simple e importante de un algoritmo es que funcione. A menudo. La documentación ayuda a comprender el funcionamiento de los algoritmos.
el candidato se incorpora definitivamente. el mejor candidato. Al contrario. la decisión..n) : (1. 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. pero si la función de selección es la adecuada. ( ) ) Puede verse por qué estos algoritmos se llaman " voraces " : en cada paso toman el mejor trozo de la solución. si permite formar alguna solución del problema. Una función que determine si cierto conjunto de candidatos es válido.resulte sencilla. es decir. solución v (siguiente)) VorazAcumulador (candidatos ± (siguiente). permite formar una solución del problema. Si este conjunto ampliado sigue siendo válido. Además.n ) : ( 1. por tanto.n). Para facilitar la descripción de este proceso. cada solución válida y completa es optima. puede llamarse candidato al elemento tratado en cada paso. Podemos representar el esquema voraz de la siguiente forma funcional: FUNCTION Voraz ( candidatos: ( 1.n) -> FUNCTION VorazAcumulador ( candidatos : (1. si satisface las restricciones del problema y. nunca cambian de opinión: una vez que un candidato es aceptado o rechazado en la solución. La función objetivo no suele aparecer en el algoritmo final. Solución : (1.
A su vez. La única complicación es comprobar que se siguen satisfaciendo las restricciones del problema. En cada paso se intenta añadir el mejor de los candidatos restantes a dicha solución parcial. Inicialmente.. Un conjunto de restricciones sobre el valor de los datos de entrada y sobre la solución final del problema. la primera solución encontrada es óptima. solución) VorazAcumulador (candidatos. el conjunto de candidatos que forman la solución está vacío. Según esta descripción. el problema parte de:
Una función objetivo que da el valor de una solución.. Por tanto. debe recordarse que puede haber varios criterios alternativos de selección y que de su
. si dicho conjunto no es válido. es decir. Si el algoritmo voraz se ha diseñado correctamente. es definitiva.n) -> Cadidatos = ( ) v EsSolución ( solución)-> Value siguiente -> seleccionar ( candidatos ) IN EsVálida (solución v ( siguiente)) => VorazAcumulador (candidatos ± (solución).
Obsérvese que las funciones de validez y completitud no se preocupan de la optimalidad del la solución. se desecha el candidato. 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. éste es un proceso repetitivo sencillo que trata sucesivamente los diferentes elementos del problema. es decir. sino que se utiliza durante el análisis del problema y es determinante en la elección de la función de selección.. ésta es la función por optimizar.. De todas formas. Por lo que se ha descrito del esquema voraz. Obviamente.
es decir. y de un importe. se considera el problema de un cambio o desglose en monedas. Se trata de indicar la cantidad (menor) de monedas de los tipos considerados. Hay que desglosar una cantidad en un conjunto de monedas tratando de cumplir alguna condición. Su declaración es la siguiente: TYPE Monedas -> M500 I M100 I M50 I M25 I M5 I M1. 25. en particular. La función de selección establece que hay que elegir. utilizar el menor número de monedas. Para simplificar. Para ello. Una solución viene dad por un conjunto de monedas devuelto tras el desglose. Asimismo. Estos valores se definen por medio de un tipo enumerado MONEDAS.correcta elección depende que la solución calculada por el algoritmo sea optima. 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. y cuyo valor total es igual al importe a desglosar. 100. Cada fila resultante puede tener una complejidad de o (n2). podemos utilizar sólo monedas de 500. 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. Como ejercicio. tales que sumados sus valores equivalgan al importe. Después se resuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original. Es fácil encontrar una solución si en cada etapa se genera el subcalendario correspondiente a un equipo. Además. 50. se parte de un conjunto de tipos de monedas válidas. de las que se supone que hay cantidad suficiente para realizar el desglose. 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. mientras sea posible. Desglose en monedas Como primer ejemplo introductorio sencillo al que puede aplicarse la técnica voraz. éste no será nunca excluido de él.
. 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.M1 Se supone inicialmente asignados los valores a cada uno de los tipos de monedas. Además. 5 y 1 pesetas para el desglose. el lector puede intentar encontrar una solución voraz del problema del calendario. cuando un candidato (moneda) se incorpora al conjunto solución. Como fila primera se toma la secuencia de los índices de los participantes en cualquier orden. suponemos que manejamos dineroespañol y. Valores -> Integer M500 M1 Cantidades -> Integer M500 .
Con esta información se puede comprobar que en este problema están presentes los distintos elementos de la técnica voraz. la tabla de competición se va completando por filas. La función objetivo cosiste en minimizar la cantidad total de monedas utilizadas en el desglose. este algoritmo tiene la ventaja de valer para las situaciones en que el número de participantes no es una potencia de dos. en este caso. la moneda de mayor valor de entre las candidatas.
OUT solución : resultado) -> PROCEDURE DyVAux (IN problema : dato1. subproblema2) => Combinar (DivideYVenceras (subproblema1) . el proceso recursivo nunca terminaría.. superior : 1. considerado el problema como de tipo dato y la solución. superior). Sin embargo. es fácil su generalización a k subproblemas 2<k<=n. Mas formalmente. la técnica de divide y vencerás parte la entrada en k subproblemas.n.N subsolucion1. superior. Su formación funcional es como sigue. solución) DyVAux (problema. medio. DyVAux (problema. escribiremos una formulación más restrictiva pero bastante usual. en caso contrario. DivideYVenceras (subproblema2)) Se puede hacer una formulación imperativa similar.Esquema de Divide y vencerás.N. 1<k<=n. se descompone en varias partes más fáciles de resolver. N. inferior. subsolucion2). Veamos el esquema de divide y vencerás para dos subproblemas. TYPEVAR dato. El caso más frecuente es cuando el número de subproblemas es dos. medio+1... DyVAux (problema. Estos subproblemas se resuelven independientemente y después se combinan sus soluciones parciales para obtener la solución del problema original. Esta restricción permite una formulación y resolución recursiva de los subproblemas. IN inferior. Por supuesto. dado un problema al resolver planteando en términos de una entrada de tamaño n. solución)
. de tipo resultado: TYPEVAR Dato. subsolucion2. 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. subsolucion1). 1.n. resultado PROCEDURE DivideYVenceras (IN problema : dato1. resultado FUNCTION DivideYVenceras (problema : dato) : resultado -> EsPequeño (problema) }=> ResolverDirectamente (problema) | VALUE subproblemas -> Partir (problema) IN subproblemas == (subproblema1. olución) ELSE Medio := Partir (inferior. deben existir algunos pasos sencillos cuya solución pueda calcularse fácil y directamente.. 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. subsolucion2 : resultado IF EsPequeño (inferior. superior. OUT solución : resultado) -> VAR medio: 1. en la que se utiliza un vector de tamaño N. Combinar (subsolucion1. superior) THEN ResolverDirectamente (problema. inferior.
1<=j<n. hay n = 2k participantes para algún entero positivo k. Para simplificar el problema. la columna j también contiene números distintos. se supone que el numero de participantes es una potencia de dos. incluyendo en cada fila i algún ejemplo de P(i). se elige uno cualquiera. resultan nx(n-1)!=n! formas de rellenar la tabla. para que esta técnica resulte eficiente todos los subproblemas deben ser de tamaño parecido. Dado que el numero de participantes de n. Elaboración de un Calendario Deportivo: Sea un campeonato deportivo. La eficiencia final del algoritmo depende de la función f(n) concreta que aparezca durante el análisis.. Si el tamaño de los dos subproblemas es el mismo (o casi).j)±esimo de 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. El método de fuerza bruta resulta sencillo. Si hay varios calendarios validos. 1<=i<=n. Por tanto. Cada conjunto P(i) consta de (n-1)! Elementos.
. puede suponerse que las competiciones se celebran en días sucesivos y que cada participante compite una vez por día. el conjunto P(i) de todas las permutaciones posibles del resto de los participantes con los que debe competir.El esquema general se adapta a un problema concreto al sustituir los metasimbolos EsPequeño. en caso contrario donde T(n) es la función de tiempo de DivideYVenceras para entradas de tamaño n. La siguiente figura describe visualmente parte de la elaboración de la tabla. Primero se obtiene para cada participante i. 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. Se supone también que cada participante tiene asignado un número comprendido entre 1 y N. Nótese que. A su vez.n}-{i} ahora se completan las filas de la tabla de todas las formas posibles.si n es pequeño T(n) = 2 T(n/2) + f(n). pero es terriblemente ineficiente. para nuestros propósitos resulta indiferente el deporteobjeto de la competición. ResolverDirectamente. es general. Por concreción. es decir. el tiempo de cómputo de la función DivideYVecneras se describe con la siguiente relación de recurrencia: g(n). Partir y Combinar por funciones o procedimientos concretos. es decir. así que hablaremos de participantes en vez de deportistas o equipos. El elemento (i. contiene el numero del participante contra el que el participante i-esimo compite el día j-esimo. 1<= i<=n. Se dispone de una solución inmediata aplicando fuerza bruta. Solo sirve como solución aquellas combinaciones de fila que cumplan las restricciones enunciadas en el párrafoanterior sobre las columnas de la tabla (las restricciones sobre las filas están garantizadas por el modo de generar los conjuntos P(i)). porque el día j-esimo cada participante solo puede competir con otro participante. 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. la solución del problema puede representarse en una tabla de dimensión nx(n-1). 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. el conjunto de permutaciones de los números {1. y sin perdida de generalidad. Se necesitan elaborar n-1 competiciones por participantes.
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.1 participantes 1 2 2 1
1 2 3 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 8 5 6 7 3 4 1 2 7 8 5 6 4 3 2 1 6 7 8 5 5 6 7 8 1 2 3 4 6 5 8 7 4 1 2 3 7 8 5 6 3 4 1 2 8 7 6 5 2 3 4 1
Se distinguen dos casos..N-1) -> PROCEDURE FormaTabla (IN inf : 1. Completemos primero la parte de los participantes de numeración inferior. PROCEDURE Calendario ( INOUT tabla : (1.N) 1. es decir. ya que a unión de los dos calendarios tiene un tamaño 2k x(2k-1 -1).N)1. por ejemplo. sucesivamente con los participantes 2k-1 +1. En efecto. Este proceso se repite para el resto de los participantes de numeración inferior. es más complejo..1. IN sup :1.. . el resto del calendario se puede construir fácilmente. El caso básico se da cuando solo hay dos participantes.. OUT tabla : (1. El algoritmo descrito se expresa a continuación. cuando hay más de dos participantes. superior en orden creciente de numeración. La solución es directa porque se celebra una sola competición entre ambos.2n .N. El caso recursivo. rotando dicha secuencia a la derecha. para k>1. la unión de estos subcalendarios no forma un calendario completo para el campeonato de 2k participantes.N.. El subcalendario del primer participante es sencillo porque basta con que compita en días sucesivos con los participantes de numeración. faltando 2k x2k-1 celdas para completar el calendario total.N-1) -> VAR
. 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. Sin embargo. 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).. de numeración comprendida entre 1 y 2k-1 y otro para los participantes comprendidos entre 2k-1 +1 y 2k ..1.N.. Si el numero de participantes es 2k . 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. faltan por elaborar las competiciones cruzadas entre los participantes de numeración inferior y los de numeración superior. Por fortuna.N..
CompletarTabla (medio+1. mediante comparaciones de sus elementos sucesivos. siendo 1<=k<=n y 0<=l<=(n/2)-1. tabla). medio... CompletarTabla (inf. tablasup. medio. medio.N. medio+1. que es mucho mas eficiente que la solución de fuerza bruta. 1.m y vm+1. que almacena los índices de las filas. sea vi. tabla).1 := inf ELSE medio := (inf + sup) Div 2. Este proceso de mezcla es realizado por un procedimiento auxiliar. donde se aplica divide y vencerás para resolver el problema y que se aprovecha de la simetría de la solución. tabla) Este sistema de ecuacionesdefina una función de tiempo del orden de O(n2). 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. La idea consiste en añadir inicialmente a la tabla una columna "ficticia" de índice j=0.N.N IF inf < sup THEN medio := (inf+sup) Div 2.1.N) -> (* ordenación por mezcla *) PROCEDURE OrdenarAux (INOUT Vector : INTEGER1. es decir.. la mitad izquierda de la tabla.s . inf. sup.N) -> VAR Medio : 1. El caso básico corresponde a un subvector de un solo elemento... sup). también de orden de complejidad cuadrática. sup) OrdenarAux (v.sup-1. FormarTabla (inf..j a partir de las casillas tablak. En esta última etapa. mediante divide y vencerás. sup. OrdenarAux (vector. sup : 1.l ya completadas. IN inf.. inf. basta con mezclar los dos subvectores. la combinación de los dos subvectores ya ordenados es fácil. N)
. El algoritmo resultante es: PROCEDURE Ordenar (INOUT v : INTEGER1. para obtener un único vector ordenado.N IF inf = sup-1 THEN tablainf.. Para el caso general. los componentes tablai. Mezclar (vector..medio : 1.1 : = sup. OrdenarAux (vector. Veamos otra estrategia. sup-1. FormarTabla (medio+1. que obviamente ya esta ordenado. inf.s un vector de índice inferior i e índice superior s. 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.l). tabla). La partición puede hacerse por la mitad si se toma un índice m=[(i+s)/2] y dos subvectores vi. medio+1. medio. Después se genera. 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). los valores de las casillas (k. medio). medio.
. pero mantenga la complejidad asintótica calculada. n =2k para algún k. J := j + 1 FOR índice IN i2.. n=1..sup DO vectorindice := vectorAuxindice El algoritmo resultante es sencillo conceptualmente. n>1.sup DO vectorAuxj := vectorindice .N) -> VAR vectorAux : INTEGER1. La matriz productoC=AxB también es una matriz de nxn cuyo elemento (i. Puede diseñarse un algoritmo de mezcla más complejo que mejore ambos aspectos. INOUT vector : INTEGER1. de dimensión nxn. j := inf. de forma que las ecuaciones de recurrencia de la función de tiempo son: T(n) = a. Multiplicación de Matrices: Sean dos matrices. necesita copiar el vector auxiliar completo en el principal. además de mezclar. a=cte 2T(n/2) + bn. i2 := i2 + 1 j := j + FOR índice IN i1.= vectori2. IN sup : INTEGER. b=cte Si n es una potencia de 2. las ecuaciones anteriores se resuelven por sustituciones sucesivas. i2 := medio + 1.medio DO vectorAuxj := vectorindice. IN medio: INTEGER. i1 :=i1 + 1 ELSE vectorAuxj . 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.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
.El procedimiento para realizar la mezcla de los subvectores ordenados es: PROCEDURE Mezclar ( IN inf : INTEGER. i1. A y B. J := j + 1 FOR índice In inf. índice : INTEGER i1 := inf. La operación de mezcla es proporcional a n.. Los únicos inconvenientes que presenta es que el procedimiento de mezcla necesita gran capacidad de almacenamiento (para dos copias del vector) y que. j : INTEGER. Es fácil analizar la complejidad del algoritmo para un vector de longitud n. WHILE (i1<=medio) ^ (i2<=sup) DO IF vectori1 << vectori2 THEN vectorAuxj :=vectori1.. es decir. i2.N.
parciales. asegurando que la secuencia de decisiones es la mejor de las posibles. Además.) las submatrices A y B pueden partirse en cuatro submatrices de dimensión (n/2)x(n/2). Sin embargo. interesa encontrar algoritmos mas eficientes. una característica es que el programa "aprende "dinámicamente de las decisiones que toma. Supongamos. (Si n no es un potencia de dos. conduciendo de forma directa a la solución. porque la multiplicación esta relacionada con otras operaciones sobre matrices mas usuales. por sencillez. Dos submatrices de (n/2)x(n/2) pueden sumarse en un tiempo bn2. dado que la complejidad respectiva de estas operaciones es O(n3)n y o(n2). proviene directamente de la definición matemática del producto de matrices. Podría conseguirse mas eficiencia si lográramos realizar menos multiplicaciones de matrices. Este principio establece que "una secuencia óptima de decisiones que resuelve un problema debe cumplir la
. Sin embargo. El cálculo de cada elemento Cij requiere n multiplicaciones. siendo b alguna constante. aunque fuera a costa de un mayor numero de sumas de matrices. de forma que no se ha conseguido ningún ahorro sustancial de tiempo. pueden añadirse las filas y columnas de ceros necesarias para formar una dimensión que sea potencia de dos. pero de una manera menos directa que en el caso voraz. Esta vez se necesita producir varias secuencias 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. la técnica de divide y vencerás sugiere un algoritmo distinto. Solamente al final se sabe cuál es la mejor de todas. como inversión de una matriz o hallar su determinante. El algoritmo anterior. 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. todo problema resoluble con esta técnica debe de satisfacer el principio de optimalidad. es decir. 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. pero para n>2 las submatrices Cij se calculan mediante multiplicaciones (recursivas) y sumas de submatrices de dimensión (n/2)x(n/2). La resolución de este sistema de ecuaciones nos dice que O(T(n))=OT(n3). La existencia de un algoritmo eficiente para la multiplicación (en realidad. que podemos llamar algoritmo convencional de multiplicación de matrices. así que el tiempo total del algoritmo de multiplicación es de orden O(n3). que existe un entero no negativo k tal que n=2k. para cualquier operación de las anteriores) significaría la existencia de un algoritmo similar para las demás. La matriz C tiene n2 elementos. los elementos Cij se calculan mediante algunas multiplicaciones y sumas de números. No es fácil establecer una definición de la programación dinámica. que n es una potencia de dos. no todos los problemas pueden resolverse de esta manera. Sin embargo. 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.
la ecuación de base establece el valor para la etapa n+1 en que no queda ninguna decisión Xi.dl. 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. La ecuación de recurrencia puede formularse de dos formas: delantera o trasera. del gusto del programador. además. partiendo como estado inicial de Ek-1. sencillamente.1 ) resultante de aplicar cada valor de decisión..
. 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. El razonamiento anterior se refiere a la primera decisión d1 tomada desde el estado inicial E0 sin embargo. 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. La formulación trasera expresa la decisión de Xi.n ). La elección de una formulación delantera o trasera depende del problema considerado o. Sea X1 . Tiene sentido centrarse en un subproblema del problema inicial porque éste satisface el principio de optimalidad pero. 1<i<n. asimismo. Podemos formalizar algo más la idea básica.1 ) debe expresarse en términos de los valores de decisión existente para decisiones d1 y el subproblema problema ( k+1. De esta forma se reduce al número total de subsecuencias generadas. a tomar. Entonces. a partir de la recurrentes con formulación trasera es igual que e la formulación delantera. 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.) Una solución dinámica para problema ( k.n ). sólo que en orden contrario. 1<k<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. resultará un total de d secuencias posibles de decisió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. En resumen. 1<i<n . que es problema ( n. tal que Eo es el estado inicial del problema y deben tomarse n decisiones d.vn} el conjunto de valores de decisión posibles para la decisión d1. si este subproblema de simboliza como problema (k. La expresión inicial de la ecuación de recurrencia.. entonces el problema completo es problema ( l. 1<i<N1.l). 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. 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). 1<i<n. puede generalizarse la formulación del problema a cualquier subsecuencia de decisiones dk . Sea D = { v1 .. Supongamos que tenemos un problema que satisface el principio de optimalidad.propiedad de que cualquier subsecuencia de decisiones también debe ser óptima respecto al subproblema que resuelva ". hay un caso en que la decisión d1 no va seguida por ninguna secuencia de decisiones.. sea. Usando una técnica de fuerza bruta. el número de secuencias de decisión es exponencial sobre el número de decisiones.Xn la secuencia de decisiones necesaria para resolver el problema. 1<i<n. La formulación delantera expresa la decisión de Xl . una secuencia óptima de decisiones respecto a E0 es la mejor secuencias de decisión { Vli Sli }. a partir de la secuencia de decisiones Xi+1 Xn ( es la clase de formulación adoptada hasta ahora ). porque si hay d opciones para cada una de las n decisiones.
. 1.... Sea G(x1.n son aquellos valores generados por G que satisfacen A.cada solución es el resultado de una secuencia de decisiones.n) -> VAR nodo : elemento FOR noso IN G(solucion. IF R(solucion.. solucion). 1.... pues tenemos ya una solucion mayor.. Después simplemente se llama recursivamente al algoritmo para generar los estados descendientes. Este mismo proceso se repite en el resto de nodos del árbol. k) THEN IF R(solucion. Supongamos que existe algún predicado acotador A tal que A(x1...xi) el camino desde la raíz hasta un nodo de un árbol del espacio de estado.. Así.. Retroceso (k+1. k sirve de cota inferior al retroceso. k-1) DO Solucion k := nodo. Otros problemas satisfacen el principio de optimalidad. El Algoritmo de Vuelta Atrás se especifica de la forma siguiente: PROCEDURE Retroceso (IN k : INTEGER.. Por lo tanto. 1. pudiéndose aplicar la técnica de programación dinámica. Por supuesto. 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. Se sale del bucle FOR cuando no quedan mas valores para solución terminando la llamada actual al algoritmo.. Algoritmos Heuristicos Existen muchos problemas para los cuales no se conocen algoritmos que puedan encontrar la solución de forma eficiente: problemas NP-completos... Esquema de Algoritmos de Vuelta Atrás: Sea (x1.xi+1) termina en un nodo de respuesta. 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.xi+1) es falso si el camino (xi. 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).. solucion) La llamada inicial del algoritmo es Retroceso(1.k) THEN << guardar µsolucion¶ >>.. En este punto podemos retroceder (y no seguir avanzando por mas ramas). los candidatos para la posición i+1 del vector desolucion x1. se comprueba si se ha encontrado una solucion.xi+1) no puede extenderse para alcanzar un nodo de respuesta... 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. evitando así la exploración de gran parte de al estructura. 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..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 también existe algún predicado R que determina si un camino (x1.
.. Sin embargo. INOUT solucion : elemento1.. En algunos problemas de optimización se conoce un criterio óptimo de selección que puede usarse de forma voraz. todavía hay otros problemas peores que no queda mas remedio que realizar una búsqueda de la solución..
5. Solución: (1. . Posibilidades: 1.La solución exacta puede requerir un orden factorial o exponencial: el problema de la explosión combinatoria.. (4. El problema del viajante Problema: Dado un grafo no dirigido. c2. Solución: (5. 2) Coste: 30+15+25+10+45=125 Empezando en el nodo 3.. ca). Normalmente. sin importar el orden. (3. 2). Problema de optimización. 5)) Coste = 10+15+20+45+50 = 140
... (1. cn). Empezar con un grafo sin aristas. completo y ponderado G = (V. . Hacer igual que en el algoritmo de Kruskal. Es un problema NP. an-1) que formen un ciclo hamiltoniano. Solución: ((2. 5). Ejemplo. 3. Los nodos son los candidatos. 2. donde la solución está formada por un grupo de elementos en cierto orden: podemos aplicar el esquema voraz. 3. En cada paso moverse al nodo no visitado más próximo al último nodo seleccionado. 4. Heurística voraz 1 ± Una solución será un cierto orden en el conjunto de nodos (c1.. 4). Empezando en el nodo 1. 3). 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. a2. el orden de visita de los nodos. se basa en un conocimiento intuitivo del programador sobre un determinado problema. pero garantizando que se forme un ciclo. Ejemplo. encontrar un ciclo simple de costo mínimo que pase por todos los nodos. A). c2. 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. 2. Acabamos cuando tengamos n nodos.. Objetivo: obtener buenas soluciones en un tiempo de ejecución corto. 4. 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. (1. .. Empezar en un nodo cualquiera. Las aristas son los candidatos. 1) Coste: 15+20+10+45+50=140 Heurística voraz 2 ± Una solución será un conjunto de aristas (a1. La estructura de algoritmo voraz se puede utilizar para construir procedimientos heurísticos: hablamos de heurísticas voraces... pero necesitamos una solución eficiente. Selección: seleccionar la arista candidata de menor coste. Inicialización: seleccionar un nodo cualquiera.
Para este tipo de problemas. Sin embargo. 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. como es calcular el ajuste maximizal del grafo G. a partir de la solución del algoritmo intentar hacer modificaciones locales para mejorar esa solución.A). Este nuevo problema garantiza conseguir un recubrimiento que contiene no más de dos vértices del recubrimiento mínimo. normalmente ambos dan soluciones buenas. ó bien. 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. también por la propia definición. El procedimiento para construir un ajuste maximizal de un grafo G consistiría en ir tomando aristas de G.Conclusiones: Ninguno de los dos algoritmos garantiza una solución óptima. 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¶. resulta parcialmente interesante que estos garanticen una cota en el margen de imprecisión. ningún vértice perteneciente a M puede recubrir a mas de una arista en M. Para poder aplicar el nuevo problema aproximado. los algoritmos que no conducen a una solución óptima se llaman algoritmos de aproximación. es probable que no sepamos resolverlo de manera precisa y completa utilizando un algoritmo polimico en tiempo. por lo menos la mitad de los vértices de M deben pertenecer a un recubrimiento. Algoritmos De Aproximación Dado un problema NP completo. de una en una y en cualquier orden e ir eliminando las incidentes al conjunto que se esta construyendo hasta recubrir todo en grafo. ya que por la definición de ajuste maximal. Este problema se puede resolver a través de otro aproximado. Esto es evidente. próximas a la óptima. A continuación se ilustra este tipo de tratamiento de problemas al problema de recubrimiento de un grafico: Dado un grafo G=(V.
. repetir la heurística 1 con varios orígenes. los vértices incidentes a las aristas de M son un recubrimiento de G. En consecuencia. Sin embargo. Posibles mejoras: buscar heurísticas mejores.
Leer más sobre este usuarioCOMPONENTES ELECTRICOS.docx01_fundamentos electricidad.pdfagenda del ing. químico.pdf1.3 movimiento de varias particulas dependientes y relacionales.pdfConsideraciones Generales de Un Estudio de MercadoAdmon Prog DatosAprendizaje Colaborativo a Travs de Las Tic 28801.2 Bases de Datos Multidimencionales (BDM).Abrir Puerto Firewall22224605 2 Tipos de AuditoriaAlgebra - Tomo13_CCNA2Código de conducta reuniones
Sign up to vote on this titleUsefulNot useful1.1.1. Conceptos básicos Algoritmos y aproximaciones por Karina Mumentey RegaladoInsertarDescargaLeer en Scribd móvil: iPhone, iPad y Android.Copyright: Attribution Non-Commercial (BY-NC)Precio de lista: $0.00Download as DOCX, PDF, TXT or read online from ScribdFlag for inappropriate contentMás informaciónMostrar menos
RelacionadoMétodos numericos unidad 1por Gusstavoo Trejo Bahena3.1 apoyos redundantespor Cesar Alexander Jmz ArandaSesión 7 Medición con calibradorpor Hugo Aguerotarea manufacturapor Armando Bueno VelazquezNANOTECNOLOGIA,Sobre Polimeros Catenanos y Rotaxanospor angelkick42¿Qué es DFMApor Carlos Aguilar GomesProceso de manufactura para polímerospor Miguel Morales VelascoUnidad 5.- Proceso de Union de Materialespor Iesus Da Vincis SalomonSimilar to 1.1.1. Conceptos básicos Algoritmos y aproximacionesMétodos numericos unidad 13.1 apoyos redundantesSesión 7 Medición con calibradortarea manufacturaNANOTECNOLOGIA,Sobre Polimeros Catenanos y Rotaxanos¿Qué es DFMAProceso de manufactura para polímerosUnidad 5.- Proceso de Union de Materiales1.1.1. Conceptos básicos Algoritmos y aproximaciones

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución