PDF de programación - Algoritmos y Estructuras de Datos

Imágen de pdf Algoritmos y Estructuras de Datos

Algoritmos y Estructuras de Datosgráfica de visualizaciones

Publicado el 5 de Abril del 2020
2.471 visualizaciones desde el 5 de Abril del 2020
2,0 MB
383 paginas
Creado hace 1a (26/10/2019)
Algoritmos y Estructuras de Datos

Bottazzi, Cristian. [email protected],
Costarelli, Santiago. [email protected],

D’Elía, Jorge. [email protected],

Dalcin, Lisandro. [email protected],
Galizzi, Diego. [email protected],

Giménez, Juan Marcelo. [email protected],

Olivera, José. [email protected],
Novara, Pablo. zaskar [email protected],
Paz, Rodrigo. [email protected],
Prigioni, Juan. [email protected],

Pucheta, Martín. [email protected],

Rojas Fredini, Pablo Sebastián. [email protected],

Romeo, Lautaro. [email protected] ,
Storti, Mario. [email protected],

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 de Investigación de Métodos Computacionales

http://www.cimec.org.ar

Indice

1. Dise ño y análisis de algoritmos

13
1.1. Conceptos básicos de algoritmos . . . . . . . . . . . . . . . . 13

1.1.1. Ejemplo: Sincronización de acceso a objetos en cálculo

distribuido . . . . . . . . . . . . . . . . . . . . . . . . 14
Introducción básica a grafos . . . . . . . . . . . . . . . 16
1.1.2.
1.1.3. Planteo del problema mediante grafos
. . . . . . . . . 17
1.1.4. Algoritmo de búsqueda exhaustiva . . . . . . . . . . . 18
1.1.5. Generación de las coloraciones . . . . . . . . . . . . . 19
1.1.6. Crecimiento del tiempo de ejecución . . . . . . . . . . 22
1.1.7. Búsqueda exhaustiva mejorada . . . . . . . . . . . . . 23
1.1.8. Algoritmo heurístico ávido . . . . . . . . . . . . . . . . 26
1.1.9. Descripción del algoritmo heurístico en seudo-código . 29
1.1.10. Crecimiento del tiempo de ejecución para el algoritmo

ávido . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.1.11. Conclusión del ejemplo . . . . . . . . . . . . . . . . . 36
1.2. Tipos abstractos de datos . . . . . . . . . . . . . . . . . . . . 37

1.2.1. Operaciones abstractas y características del TAD

1.2.2.
1.2.3.

CONJUNTO . . . . . . . . . . . . . . . . . . . . . . . 38
Interfaz del TAD CONJUNTO . . . . . . . . . . . . . . 38
Implementación del TAD CONJUNTO . . . . . . . . . . 40
1.3. Tiempo de ejecución de un programa . . . . . . . . . . . . . . 41
1.3.1. Notación asintótica . . . . . . . . . . . . . . . . . . . . 43
Invariancia ante constantes multiplicativas . . . . . . . 45
1.3.2.
Invariancia de la tasa de crecimiento ante valores en
1.3.3.
un conjunto finito de puntos . . . . . . . . . . . . . . . 45
1.3.4. Transitividad . . . . . . . . . . . . . . . . . . . . . . . 45
1.3.5. Regla de la suma . . . . . . . . . . . . . . . . . . . . . 46
1.3.6. Regla del producto . . . . . . . . . . . . . . . . . . . . 46

3

1.3.7. Funciones típicas utilizadas en la notación asintótica . . 46
1.3.8. Equivalencia . . . . . . . . . . . . . . . . . . . . . . . 48
1.3.9. La función factorial . . . . . . . . . . . . . . . . . . . . 48
1.3.10. Determinación experimental de la tasa de crecimiento . 50
1.3.11. Otros recursos computacionales . . . . . . . . . . . . . 51
1.3.12. Tiempos de ejecución no-polinomiales . . . . . . . . . 52
1.3.13. Problemas P y NP . . . . . . . . . . . . . . . . . . . . 52
1.3.14. Varios parámetros en el problema . . . . . . . . . . . . 53
1.4. Conteo de operaciones para el cálculo del tiempo de ejecución 54
1.4.1. Bloques if . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.4.2. Lazos . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.4.3. Suma de potencias . . . . . . . . . . . . . . . . . . . . 60
1.4.4. Llamadas a rutinas . . . . . . . . . . . . . . . . . . . . 60
1.4.5. Llamadas recursivas . . . . . . . . . . . . . . . . . . . 60

2. Tipos de datos abstractos fundamentales

65
2.1. El TAD Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.1.1. Descripción matemática de las listas . . . . . . . . . . 66
2.1.2. Operaciones abstractas sobre listas . . . . . . . . . . . 67
2.1.3. Una interfaz simple para listas . . . . . . . . . . . . . . 68
2.1.4. Funciones que retornan referencias . . . . . . . . . . . 71
2.1.5. Ejemplos de uso de la interfaz básica . . . . . . . . . . 73
Implementación de listas por arreglos . . . . . . . . . . 78
2.1.6.
2.1.6.1. Eficiencia de la implementación por arreglos . 84
Implementación mediante celdas enlazadas por punteros 85
2.1.7.1. El tipo posición . . . . . . . . . . . . . . . . . 87
2.1.7.2. Celda de encabezamiento . . . . . . . . . . . 88
2.1.7.3. Las posiciones begin() y end() . . . . . . . 91
2.1.7.4. Detalles de implementación . . . . . . . . . . 91
Implementación mediante celdas enlazadas por cursores 93
2.1.8.1. Cómo conviven varias celdas en un mismo

2.1.7.

2.1.8.

espacio . . . . . . . . . . . . . . . . . . . . . 95
2.1.8.2. Gestión de celdas . . . . . . . . . . . . . . . 96
2.1.8.3. Analogía entre punteros y cursores . . . . . . 97

2.1.9. Tiempos de ejecución de los métodos en las diferentes

implementaciones.

. . . . . . . . . . . . . . . . . . . . 100
2.1.10. Interfaz STL . . . . . . . . . . . . . . . . . . . . . . . 102
2.1.10.1. Ventajas de la interfaz STL . . . . . . . . . . . 102
2.1.10.2. Ejemplo de uso . . . . . . . . . . . . . . . . . 103

2.1.10.2.1. Uso de templates y clases anidadas . 104
2.1.10.2.2. Operadores de incremento prefijo y

postfijo:

. . . . . . . . . . . . . . . . 104
2.1.10.3. Detalles de implementación . . . . . . . . . . 105
2.1.10.4. Listas doblemente enlazadas . . . . . . . . . 108
2.2. El TAD pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.2.1. Una calculadora RPN con una pila . . . . . . . . . . . 110
2.2.2. Operaciones abstractas sobre pilas . . . . . . . . . . . 111
2.2.3.
Interfaz para pila . . . . . . . . . . . . . . . . . . . . . 111
Implementación de una calculadora RPN . . . . . . . . 112
2.2.4.
Implementación de pilas mediante listas
2.2.5.
. . . . . . . . 116
2.2.6. La pila como un adaptador . . . . . . . . . . . . . . . . 118
2.2.7.
Interfaz STL . . . . . . . . . . . . . . . . . . . . . . . 118
2.3. El TAD cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Intercalación de vectores ordenados
. . . . . . . . . . 120
2.3.1.1. Ordenamiento por inserción . . . . . . . . . . 120
2.3.1.2. Tiempo de ejecución . . . . . . . . . . . . . . 123
2.3.1.3. Particularidades al estar las secuencias pares

2.3.1.

e impares ordenadas . . . . . . . . . . . . . . 123
2.3.1.4. Algoritmo de intercalación con una cola auxiliar 124
2.3.2. Operaciones abstractas sobre colas . . . . . . . . . . . 126
Interfaz para cola . . . . . . . . . . . . . . . . . . . . . 126
2.3.3.
Implementación del algoritmo de intercalación de vec-
2.3.4.
tores . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
2.3.4.1. Tiempo de ejecución . . . . . . . . . . . . . . 128
2.4. El TAD correspondencia . . . . . . . . . . . . . . . . . . . . . 129
. . . . . . . . . 131

2.4.1.
2.4.2.

Interfaz simple para correspondencias
Implementación de correspondencias mediante conte-
nedores lineales . . . . . . . . . . . . . . . . . . . . . 134
Implementación mediante contenedores lineales orde-
nados . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Implementación mediante listas ordenadas . . 138
2.4.3.1.
2.4.3.2.
Interfaz compatible con STL . . . . . . . . . . 140
2.4.3.3. Tiempos de ejecución para listas ordenadas . 144
Implementación mediante vectores ordenados 144
2.4.3.4.
2.4.3.5. Tiempos de ejecución para vectores ordenados148
2.4.4. Definición de una relación de orden . . . . . . . . . . . 148

2.4.3.

3. Arboles

3.1. Nomenclatura básica de árboles

151
. . . . . . . . . . . . . . . . 151
3.1.0.0.1. Altura de un nodo.
. . . . . . . . . . 154
3.1.0.0.2. Profundidad de un nodo. Nivel. . . . . 154
3.1.0.0.3. Nodos hermanos . . . . . . . . . . . 154
3.2. Orden de los nodos . . . . . . . . . . . . . . . . . . . . . . . 154
3.2.1. Particionamiento del conjunto de nodos . . . . . . . . . 156
3.2.2. Listado de los nodos de un árbol
. . . . . . . . . . . . 157
3.2.2.1. Orden previo . . . . . . . . . . . . . . . . . . 157
3.2.2.2. Orden posterior . . . . . . . . . . . . . . . . . 158
3.2.2.3. Orden posterior y la notación polaca invertida 159
3.2.3. Notación Lisp para árboles . . . . . . . . . . . . . . . . 160
3.2.4. Reconstrucción del árbol a partir de sus órdenes . . . . 161
3.3. Operaciones con árboles . . . . . . . . . . . . . . . . . . . . 164
3.3.1. Algoritmos para listar nodos . . . . . . . . . . . . . . . 164
Inserción en árboles . . . . . . . . . . . . . . . . . . . 165
3.3.2.
3.3.2.1. Algoritmo para copiar árboles . . . . . . . . . 166
3.3.3. Supresión en árboles
. . . . . . . . . . . . . . . . . . 169
3.3.4. Operaciones básicas sobre el tipo árbol . . . . . . . . . 170
Interfaz básica para árboles . . . . . . . . . . . . . . . . . . . 170
3.4.1. Listados en orden previo y posterior y notación Lisp . . 174
3.4.2. Funciones auxiliares para recursión y sobrecarga de

3.4.

3.5.

3.6.

funciones . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.4.3. Algoritmos de copia . . . . . . . . . . . . . . . . . . . 176
3.4.4. Algoritmo de poda . . . . . . . . . . . . . . . . . . . . 176
Implementación de la interfaz básica por punteros . . . . . . . 176
. . . . . . . . . . . . . . . . . . . . . . 177
3.5.1. El tipo iterator
3.5.2. Las clases cell e iterator t
. . . . . . . . . . . . . . . . 179
3.5.3. La clase tree . . . . . . . . . . . . . . . . . . . . . . . 183
Interfaz avanzada . . . . . . . . . . . . . . . . . . . . . . . . 186
3.6.1. Ejemplo de uso de la interfaz avanzada . . . . . . . . . 191
3.7. Tiempos de ejecución . . . . . . . . . . . . . . . . . . . . . . 194
3.8. Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . 194
3.8.1. Listados en orden simétrico . . . . . . . . . . . . . . . 195
3.8.2. Notación Lisp . . . . . . . . . . . . . . . . . . . . . . . 195
Árbol binario lleno . . . . . . . . . . . . . . . . . . . . 196
3.8.3.
3.8.4. Operaciones b´
  • Links de descarga
http://lwp-l.com/pdf17497

Comentarios de: Algoritmos y Estructuras de Datos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad