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 15 de Febrero del 2019
1.402 visualizaciones desde el 15 de Febrero del 2019
1,9 MB
303 paginas
Creado hace 2a (21/11/2017)
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
  • Links de descarga
http://lwp-l.com/pdf15215

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