27

Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Embed Size (px)

Citation preview

Page 1: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 2: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 3: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 4: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 5: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 6: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 7: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 8: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 9: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 10: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 11: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 12: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 13: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 14: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 15: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 16: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 17: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 18: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 19: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 20: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos
Page 21: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Técnicas de diseño de algoritmos

•Algoritmos voraces: •Algoritmos paralelos:•Algoritmos probabilísticos:•Algoritmos determinísticos:•Algoritmos no determinísticos •Divide y vencerás:•Metaheurísticas:•Programación dinámica:•Ramificación y acotación:•Vuelta Atrás:

Page 22: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Representación de Algoritmos: 

Sintaxis y Semántica:El termino sintaxis se refiere a la representación, en tanto que semántica se refiere al concepto que se representa.

Primitivas: Una primitiva, viene a ser una estructura semántica bien definida junto con una sintaxis no ambigua para representarla.

Pseudocódigo: Es un sistema de notación en el que podemos expresar información ideas durante el proceso de creación de algoritmos. 

Diseño Modular:Hasta aquí, hemos estado analizado el papel de las interrelaciones sintáctico- semánticas en referencia al objetivo de producir programas no ambiguos.

Page 23: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

 

Descubrimiento del AlgoritmoEl descubrimiento de algoritmos suele ser el paso mas difícil en el proceso de creación de software; es decir descubrir un algoritmo es equivalente a encontrar un método para resolver el problema.

Teoría de la resolución de problemasLas técnicas de resolución de problemas no son solo de los ciencia de la computación , sino de cualquier otro campo. La capacidad de resolver problemas sigue siendo mas una aptitud artística que debe desarrollarse. Las fases para resolver problema son: Fase1. Entender el problema.Fase2. Idear un plan para resolver el problema.Fase3. Llevar a cabo el plan.Fase4. Evaluar la solución en cuanto a su exactitud y a su potencial como herramienta para resolver otros problemas.

 Traducidas al contexto de creación de programa. Esa fase se convierten en: Fase1. Entender el problema.Fase2. Pensar cómo un procedimiento algoritmo podría resolver el problema.Fase3. Formular el algoritmo y representarlo en forma de programa.Fase4. Evaluar el programa en cuanto a su exactitud y a su potencial como herramienta para resolver otros problemas.

 

Cómo dar el primer pasodesglosar el problema original en subproblemas, podemos acercarnos a la solución global paso a paso, cada uno de los cuales es mas fácil de resolver que el problema original.

Page 24: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Estructuras iterativasPresentaremos varios algoritmos muy utilizados para buscar y ordenar (la búsqueda secuencial y binaria , y las ordenaciones por inserción y rápida). Las estructuras iterativas permiten la repetición de una serie de sentencias n veces, determinándose n.

El algoritmo de búsqueda secuencialAl algoritmo de ordenación por

inserción

Estructuras RecursivasLas estructuras recursivas son una alternativa al paradigma cíclico en las estructuras

repetitivas.Como introducción a la técnica, consideremos el algoritmo de búsqueda binaria que aplica una metodología de “divide y vencerás” al proceso de búsqueda. 

El algoritmo de búsqueda binaria

Control Recursivo

El algoritmo de ordenación rápida

Page 25: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

 

Eficiencia y Corrección

Eficiencia de AlgoritmosEl problema de la eficiencia es bastante importante. De hecho , la búsqueda de soluciones eficientes a los problemas y de técnicas para medir la eficiencia es un tema primario del área de la teoría de la complejidad.

Verificación del SoftwareEn la actualidad la comunidad de quienes se ocupan de procesos de datos se apoya entre otros enfoques de verificación de programas .

 

Page 26: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Clasificación de los algoritmosComo se mencionó antes, la mayoría de los algoritmos tienen un parámetro primario N, normalmente el número de datos a procesar, que afecta muy significativamente al tiempo de ejecución. El parámetro N podría el grado de un polinomio, el tamaño de un archivo a ordenar o en el que se va a realizar una búsqueda, el número de nodos en un grafo, etc. 

LogN: Tiempo de ejecución de un programa es logarítmico, este será ligeramente más lento a

medida que crezca N. 

NlogN: Tiempo de ejecución es el de los algoritmos, que resuelven un problema dividiéndolo en

pequeños subproblemas, resolviéndolos independientemente, y combinando después las soluciones. 

N2 : Tiempo de ejecución de un algoritmo es cuadrático, solo es practico para problemas relativamente

pequeño.  

N3 : Un algoritmo que procesa tríos de elementos de datos tiene un tiempo de ejecución cúbico y no

es útil mas que en problemas pequeños. 

2N : Pocos algoritmos con un tiempo de ejecución exponencial son susceptibles de poder ser útiles en

la practica, aunque aparecen de forma natural al aplicar el método de la fuerza bruta en la resolución de problemas.

Page 27: Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Implementación de algoritmosLa implementación de un algoritmo es desarrollar una versión inicial en su forma más simple.  

Selección de un AlgoritmoLa primera regla es que se debe implementar primero el algoritmo más simple que resuelva un problema dado. Si el problema particular con el que se tropieza se resuelve fácilmente, entonces el algoritmo sencillo podría resolver el problema y no seria necesario hacer nada mas 

Análisis EmpíricoEl principal peligro que se corre al comparar empíricamente programas es que una implementación puede ser más optimizada que otra.  

Optimización de un ProgramaLa mejor forma de perfeccionar el rendimiento de un algoritmo es mediante un proceso gradual de transformación en mejores programas y mejores implementaciones. 

Algoritmos y SistemasLa mejora del rendimiento de un algoritmo en particular y también se aplican para mejorar el rendimiento de un sistema grande. Al construir sistemas realas está justificado un estilo de programación más «defensivo»: los programas deben implementarse de modo que puedan modificarse fácilmente, leerse con rapidez y, entenderse por otros programadores, y que además realicen una buena interfaz con otras partes del sistema.