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

Actualizado el 21 de Marzo del 2018 (Publicado el 23 de Enero del 2018)
652 visualizaciones desde el 23 de Enero del 2018
1,5 MB
306 paginas
Creado hace 3a (03/08/2016)
Algoritmos y Estructuras de Datos

Bottazzi, Cristian. cristian.bottazzi@gmail.com,
Costarelli, Santiago. santi.costarelli@gmail.com,

D’Elía, Jorge. jdelia@intec.unl.edu.ar,

Dalcin, Lisandro. dalcinl@gmail.com,
Galizzi, Diego. dgalizzi@gmail.com,

Giménez, Juan Marcelo. jmarcelogimenez@gmail.com,

Olivera, José. joseolivera123@gmail.com,
Novara, Pablo. zaskar_84@yahoo.com.ar,
Paz, Rodrigo. rodrigo.r.paz@gmail.com,
Prigioni, Juan. jdprigioni@gmail.com,

Pucheta, Martín. martinpucheta@gmail.com,

Rojas Fredini, Pablo Sebastián. floyd.the.rabbit@gmail.com,

Storti, Mario. mario.storti@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 de Investigación de Métodos Computacionales

http://www.cimec.org.ar

(Document version: aed-3.0-1-g02fa845)
(Date: Wed Aug 3 17:32:23 2016 -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 . . . . . . . . . . . . .
Interfaz 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 . . . . . . . . . . . . . . . . .

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

1

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.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 interfaz simple para listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4. Funciones que retornan referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5. Ejemplos de uso de la interfaz 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. Interfaz STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.10.1. Ventajas de la interfaz 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interfaz 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interfaz 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.1.7.

2.3.1.

((version aed-3.0-1-g02fa845) (date Wed Aug 3 17:32:23 2016 -0300) (proc-date Wed Aug 3 17:32:44 2016 -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
89
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Interfaz 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
Interfaz 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.
Interfaz compatible con STL . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.4.3.3. Tiempos de ejecución para listas ordenadas . . . . . . . . . . . . . . . . . . 109
Implementación mediante vectores ordenados . . . . . . . . . . . . . . . . . 109
2.4.3.4.
2.4.3.5. Tiempos de ejecución para vectores ordenados
. . . . . . . . . . . . . . . . 112
2.4.4. Definición de una relación de orden . . . .
  • Links de descarga
http://lwp-l.com/pdf8439

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