Algoritmos y estructura de datos

Algoritmos y Estructuras de Datos
Mario Storti, Jorge D’El´ Rodrigo Paz, Lisandro Dalc´ y Mart´ Pucheta ıa, ın, ın , www: http: // www. cimec. org. ar/ aed Facultad de Ingenier´ y Ciencias H´ ıa ıdricas Universidad Nacional del Litoral http: // fich. unl. edu. ar Centro Internacional de M´todos Computacionales en Ingenier´ e ıa http: // www. cimec. org. ar

(Document version:aed-2.0.3-142-g80f46c8 ’clean) (Date: Sat Oct 31 11:09:55 2009 -0300)

Indice
1. Dise˜ o y an´lisis de algoritmos n a 1.1. Conceptos b´sicos de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . a 1.1.1. Ejemplo: Sincronizaci´n de acceso a objetos en c´lculo distribuido . . o a 1.1.2. Introducci´n b´sica a grafos . . . . . . . . . . . . . . . . . . . . . . . . o a 1.1.3. Planteo del problemamediante grafos . . . . . . . . . . . . . . . . . . 1.1.4. Algoritmo de b´squeda exhaustiva . . . . . . . . . . . . . . . . . . . . u 1.1.5. Generaci´n de las coloraciones . . . . . . . . . . . . . . . . . . . . . . o 1.1.6. Crecimiento del tiempo de ejecuci´n . . . . . . . . . . . . . . . . . . . o 1.1.7. B´squeda exhaustiva mejorada . . . . . . . . . . . . . . . . . . . . . . u 1.1.8. Algoritmo heur´ıstico ´vido . . . . . . . . . . . . . . . . . . . . . . . . a 1.1.9. Descripci´n del algoritmo heur´ o ıstico en seudo-c´digo . . . . . . . . . . o 1.1.10. Crecimiento del tiempo de ejecuci´n para el algoritmo ´vido . . . . . . o a 1.1.11. Conclusi´n del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . o 1.2. Tipos abstractos de datos . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 1.2.1. Operaciones abstractas y caracter´ ısticas del TAD CONJUNTO . . . . 1.2.2. Interfase del TAD CONJUNTO . . . . . . . . . . . . . . . . . . . . . . 1.2.3. Implementaci´n del TAD CONJUNTO . . . . . . . . . . . . . . . . . o 1.3. Tiempo de ejecuci´n de un programa . . . . . . . . . . . . . . . . . . . . . . . o 1.3.1. Notaci´n asint´tica . . . . . . . . . . . . . . . . . . . . . . . . .. . . . o o 1.3.2. Invariancia ante constantes multiplicativas . . . . . . . . . . . . . . . . 1.3.3. Invariancia de la tasa de crecimiento ante valores en un conjunto finito 1.3.4. Transitividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.5. Regla de la suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.6. Regla del producto . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 1.3.7. Funciones t´ ıpicas utilizadas en la notaci´n asint´tica . . . . . . . . . . o o 1.3.8. Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.9. La funci´n factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 1.3.10. Determinaci´n experimental de la tasa de crecimiento . . . . . . . . . o 1.3.11. Otros recursoscomputacionales . . . . . . . . . . . . . . . . . . . . . . 1.3.12. Tiempos de ejecuci´n no-polinomiales . . . . . . . . . . . . . . . . . . o 1.3.13. Problemas P y NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.14. Varios par´metros en el problema . . . . . . . . . . . . . . . . . . . . . a 1.4. Conteo de operaciones para el c´lculo del tiempo de ejecuci´n . . . . . . . . . a o 1 9 . . . .. 9 . . . . . 10 . . . . . 11 . . . . . 11 . . . . . 13 . . . . . 13 . . . . . 16 . . . . . 17 . . . . . 19 . . . . . 22 . . . . . 27 . . . . . 27 . . . . . 27 . . . . . 28 . . . . . 29 . . . . . 30 . . . . . 31 . . . . . 32 . . . . . 34 de puntos 34 . . . . . 34 . . . . . 34 . . . . . 35 . . . . . 35 . . . . . 36 . . . . . 36 . . . . . 38 . . . . . 39 . . . . . 39 . . . . . 39 . . . . . 40 . . .. . 40

INDICE

INDICE

1.4.1. 1.4.2. 1.4.3. 1.4.4. 1.4.5.

Bloques if . . . . . . Lazos . . . . . . . . Suma de potencias . Llamadas a rutinas . Llamadas recursivas

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . ....