aednotes

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,
Olivera, José. joseolivera123@gmail.com,
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-2.0.6-13-ga4e5fe8)
(Date: Mon Nov 10 19:54:58 2014 -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 . . . . . . . .
1.1.2. Introducción básica a grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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 . . . . . . . . . .
1.2.2. Interfaz del TAD CONJUNTO . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....