Comunidad de Programadores
Iniciar sesión
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Recordar contraseña?
Iniciar sesión
Crear cuenta
Documentación y Recursos
Cursos y Manuales
Biblioteca de Temas
Código Fuente
Noticias/Artículos
PDFs de programación
Foros y Consultas
Foros de Consulta
Chats de prog.
Tablón de Notas
Diccionario informático
Programadores
Programadores
Ofertas de Trabajo
Programas
Programas/Utilidades
Nuestros Programas
Iconos y Cursores
Preguntas/Respuestas
Otros
Utilidades
Colaboradores
Encuestas/Estadísticas
Contactar
LWP
»
PDFs de programación
»
oscommerce
» Algoritmos y Estructuras de Datos
PDF de programación - Algoritmos y Estructuras de Datos
Volver
Filtrado por el tag: oscommerce
<<
>>
Algoritmos y Estructuras de Datos
Publicado el 15 de Febrero del 2019
2.633 visualizaciones desde el 15 de Febrero del 2019
1,9 MB
303 paginas
Creado hace 7a (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...
Cerrar
Cerrar
Cerrar
Cerrar
Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.
Puedes registrarte o validarte desde
aquí
.
Es necesario revisar y aceptar las políticas de privacidad
Acepto las
políticas de privacidad
Tags:
3d
abstracción
access
algoritmo
algoritmos
base
bases de datos
bd
burbuja
c++
calc
clústers
computación
cpu
estructura de datos
estructuras de datos
exchange
fedora
git
gnu
gnu/linux
herencia
hp
html
informática
ingeniería informática
internet
juego
juegos
latex
lenguaje c
lenguajes de programación
lisp
lógica
matemáticas
perl
postfix
programación
programación funcional
programación orientada a objetos
project
publisher
página web
quicksort
red hat
rest
scheme
seguridad
sgml
software
software libre
swap
tk
unix
utilidades
vb
word
xml
Comentarios de: Algoritmos y Estructuras de Datos (0)
No hay comentarios