PDF de programación - Algoritmos y Estructuras de Datos

Algoritmos y Estructuras de Datos

Mario Storti, Jorge D’Elía, Rodrigo Paz, Lisandro Dalcín, y Martín Pucheta

<{jdelia,mpucheta}@intec.unl.edu.ar>,

<{mario.storti,dalcinl,rodrigo.r.paz}@gmail.com>

www: http://www.cimec.org.ar/aed

Facultad de Ingeniería y Ciencias Hídricas

Universidad Nacional del Litoral http://fich.unl.edu.ar
Centro Internacional de Métodos Computacionales en Ingeniería

http://www.cimec.org.ar

(Document version: aed-2.0.4-102-g184c1cd ’clean)

(Date: Sat Feb 25 15:25:54 2012 -0300)

Indice

1. Diseño y análisis de algoritmos

1.1. Conceptos básicos de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Ejemplo: Sincronización de acceso a objetos en cálculo distribuido . . . . . . . . . . .
Introducción básica a grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2.
1.1.3. Planteo del problema mediante grafos
. . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4. Algoritmo de búsqueda exhaustiva . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.5. Generación de las coloraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.6. Crecimiento del tiempo de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.7. Búsqueda exhaustiva mejorada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.8. Algoritmo heurístico ávido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.9. Descripción del algoritmo heurístico en seudo-código . . . . . . . . . . . . . . . . . .
1.1.10. Crecimiento del tiempo de ejecución para el algoritmo ávido . . . . . . . . . . . . . . .
1.1.11. Conclusión del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Tipos abstractos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Operaciones abstractas y características del TAD CONJUNTO . . . . . . . . . . . . .
Interfase del TAD CONJUNTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2.
1.2.3.
Implementación del TAD CONJUNTO . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Tiempo de ejecución de un programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1. Notación asintótica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2.
Invariancia ante constantes multiplicativas . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3.
. . .
Invariancia de la tasa de crecimiento ante valores en un conjunto finito de puntos
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 . . . . . . . . . . . . . . . . . . .
1.3.8. Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.9. La función factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.10. Determinación experimental de la tasa de crecimiento . . . . . . . . . . . . . . . . . .
1.3.11. Otros recursos computacionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.12. Tiempos de ejecución no-polinomiales . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.13. Problemas P y NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.14. Varios parámetros en el problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Conteo de operaciones para el cálculo del tiempo de ejecución . . . . . . . . . . . . . . . . .

1

9
9
10
11
11
12
13
15
16
19
21
26
27
27
28
28
30
30
32
33
33
34
34
34
34
36
36
37
38
39
39
40
40

INDICE
INDICE

1.4.1. Bloques if . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2. Lazos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3. Suma de potencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.4. Llamadas a rutinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.5. Llamadas recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Tipos de datos abstractos fundamentales

2.1.7.

2.1.8.

2.1. El TAD Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Descripción matemática de las listas . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Operaciones abstractas sobre listas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3. Una interfase simple para listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4. Funciones que retornan referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5. Ejemplos de uso de la interfase básica . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación de listas por arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.6.
2.1.6.1. Eficiencia de la implementación por arreglos . . . . . . . . . . . . . . . . . .
Implementación mediante celdas enlazadas por punteros . . . . . . . . . . . . . . . .
2.1.7.1. El tipo posición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.7.2. Celda de encabezamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.7.3. Las posiciones begin() y end() . . . . . . . . . . . . . . . . . . . . . . .
2.1.7.4. Detalles de implementación . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación mediante celdas enlazadas por cursores . . . . . . . . . . . . . . . .
2.1.8.1. Cómo conviven varias celdas en un mismo espacio . . . . . . . . . . . . . .
2.1.8.2. Gestión de celdas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.8.3. Analogía entre punteros y cursores . . . . . . . . . . . . . . . . . . . . . . .
2.1.9. Tiempos de ejecución de los métodos en las diferentes implementaciones. . . . . . . .
2.1.10. Interfase STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.10.1. Ventajas de la interfase STL . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.10.2. Ejemplo de uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.10.2.1. Uso de templates y clases anidadas . . . . . . . . . . . . . . . . . .
2.1.10.2.2. Operadores de incremento prefijo y postfijo: . . . . . . . . . . . . . .
2.1.10.3. Detalles de implementación . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.10.4. Listas doblemente enlazadas . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. El TAD pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Una calculadora RPN con una pila . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2. Operaciones abstractas sobre pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interfase para pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3.
Implementación de una calculadora RPN . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4.
2.2.5.
Implementación de pilas mediante listas
. . . . . . . . . . . . . . . . . . . . . . . . .
2.2.6. La pila como un adaptador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interfase STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.7.
2.3. El TAD cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
Intercalación de vectores ordenados
2.3.1.1. Ordenamiento por inserción . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1.2. Tiempo de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1.

((version aed-2.0.4-102-g184c1cd ’clean) (date Sat Feb 25 15:25:54 2012 -0300) (proc-date Sat Feb 25 15:26:39 2012 -0300))

40
41
45
45
46

48
48
49
49
50
52
54
58
63
64
65
66
68
69
70
72
73
73
76
77
77
78
78
79
79
82
82
83
84
84
85
88
89
90
90
91
91
93

2

INDICE
INDICE

. . . . .
2.3.1.3. Particularidades al estar las secuencias pares e impares ordenadas
2.3.1.4. Algoritmo de intercalación con una cola auxiliar . . . . . . . . . . . . . . . . .
2.3.2. Operaciones abstractas sobre colas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interfase para cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3.
2.3.4.
Implementación del algoritmo de intercalación de vectores . . . . . . . . . . . . . . . .
2.3.4.1. Tiempo de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4. El TAD correspondencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93
94
95
95
96
97
97
Interfase simple para correspondencias . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Implementación de correspondencias mediante contenedores lineales . . . . . . . . . 102
Implementación mediante contenedores lineales ordenados . . . . . . . . . . . . . . . 103
Implementación mediante listas ordenadas . . . . . . . . . . . . . . . . . . . 105
2.4.3.1.
2.4.3.2.
Interfase compatible con STL . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.4.3.3. Tiempos de ejecución para listas ordenadas . . . . . . . . . . . . . . . . . . 109
2.4.3.4.
Implementación mediante vectores ordenados . . . . . . . . . . . . . . . . . 110
2.4.3.5. Tiempos de ejecución para vectores ordenados . . . . . . . . . . . . . . . . 112
2.4.4. Definición de una relación de orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

2.4.1.
2.4.2.
2.4.3.

3. Arboles

3.1. Nomenclatura básica de árboles

114
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
. . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.1.0.0.1. Altura de un nodo.
3.1.0.0.2. Profundidad de un nodo. Nivel. . . . . . . . . . . . . . . . . . . . . . 1