 | |  | | | Conectados:
Actualmente hay 6 invitados, 1 miembro(s) conectado(s).
Es un usuario anónimo. Puede registrarse aquí | |  | |  |
|  |
 |
|
 |
| |
Patiperros del DCC
CC40A: Diseño y Análisis de Algoritmos
CC40A: Diseño y Análisis de Algoritmos
Prof: Gonzalo Navarro
Prof. Aux: Julio Aracena
Más información del curso
Motivación
Analizar la eficiencia de diversos algoritmos para resolver una variedad
de problemas, principalmente no numéricos. Enseñar al alumno a
diseñar y analizar nuevos algoritmos.
Reglas del Juego
- 3 controles. 2/3 de la nota y debe ser >= 4. Recuperativo para notas
>= 3.7.
- 3 o 4 tareas. 1/3 de la nota y debe ser >= 4. Recuperativa para notas
>= 3.5.
Castigo por atraso: 1 punto por día hábil o fin de semana.
- 1 examen final, con derecho a recuperativo. Se exime del examen con 5.5 en
controles.
-
Los items indicados entre corchetes son temas no centrales que se darán
si el tiempo lo permite, y sobre los que se evaluará sólo
nociones generales.
Programa
Introducción (3 horas)
Algoritmos y su complejidad. ?`Como se mide la eficiencia de un algoritmo?
Tiempo y Espacio. Peor caso, caso promedio. Modelo de un computador y sus
medidas de complejidad.
Fundamentos Matemáticos (6 horas)
Notación. Medidas de Orden.
Solución de Recurrencias. Funciones Generatrices.
Cálculos asintóticos. Manipulación de big-O.
Paradigmas (6 horas)
Técnicas para el diseño de algoritmos:
Búsqueda exhaustiva, heurísticas, algoritmos probabilísticos,
avaricia (greedy), dividir para reinar, programación dinámica, inducción.
En cada caso, revisión de problemas característicos y de un mismo
problema resuelto con cada técnica.
Ordenamiento y Selección (6 horas)
Algoritmos de ordenamiento: Quicksort, Mergesort, Heapsort,
[Bucket sort, Radix sort]. Algoritmos de selección: Max-Min, k-ésimo.
Colas de Prioridad: heaps clásicas, [heaps binomiales].
Manipulación de Conjuntos (12 horas)
Operaciones usuales: buscar, insertar, eliminar, modificar, unir, recorrer,
etc.
Implementaciones. Vectores de bits. Arreglos: desordenados y ordenados.
Arboles: binarios, AVL, 2-3, [óptimos, balanceo heurístico,]
en memoria secundaria (árboles B).
[Skip lists.] Arboles digitales: tries, Patricia.
Hashing: encadenado, abierto, [perfecto,] en memoria secundaria (hashing lineal).
Union-find.
Algoritmos en Grafos (4.5 horas)
Definiciones. Propiedades básicas. Arboles cobertores de costo mínimo.
Búsqueda en grafos. Caminos mínimos. Clausura transitiva.
[Biconectividad. Flujo máximo.]
Búsqueda en texto (3 horas)
Búsqueda de strings: autómata finito, algoritmos de Knuth-Morris-Pratt,
Boyer-Moore, [Rabin-Karp, Shift-Or]. [Búsqueda multipatrón.] Arboles de
sufijos. [Búsqueda aproximada.]
Problemas NP-completos (4.5 horas)
Máquinas de Turing no determinísticas. Las clases P y NP.
El problema de la satisfactibilidad (SAT). Otros problemas NP-Completos.
[Nociones de Co-NP, P-space.]
Bibliografía
"*" indica los textos más recomendados, "+" los recomendados como
referencia pero no para aprender, "-" otros.
- [*]
A.V. Aho, J.E. Hopcroft y J.D. Ullman, "The Design and Analysis of
Computer Algorithms", Addison-Wesley, 1974.
- [*]
A.V. Aho, J.E. Hopcroft y J.D. Ullman, "Data Structures and Algorithms",
Addison-Wesley, 1982.
- [-]
S. Baase, "Computer Algorithms: Introduction to Design and Analysis",
Addison-Wesley 1988.
- [-]
Brassard, G. and Bratley, P., "Algorithmics: Theory and Practice",
Prentice Hall, 1988.
1988.
- [*]
Cormen, Leiserson, Rivest, "Introduction to Algorithms", MIT Press, 1991.
- [+]
Gonnet, G. y Baeza-Yates, R., "Handbook of Algorithms and Data Structures",
Addison-Wesley, 2ed, 1991.
- [-]
Harel, D. Algorithmics, the spirit of computing, Addison Wesley 1987.
- [+]
D.E. Knuth, "The Art of Computer Programing", vol. 1, "Fundamental Algorithms", Addison-Wesley, segunda edición, 1973.
- [+]
D.E. Knuth, "The Art of Computer Programming", Vol. 3, "Sorting and Searching", Addison-Wesley, 1973.
- [-]
Manber, U., "Introduction to Algorithms: A Creative approach", Addison Wesley, 1989.
- [*]
Rawlins, G., "Compared to What? AN Introduction to Analysis of Algorithms",
Computer Science Press, 1991.
- [-]
Reingold, Nievergelt, and Deo., Combinatorial algorithms, Prentice-Hall,
1977.
- [*]
R. Sedgewick, "Algorithms", Addison Wesley, 1987.
|
|
 |
|
 |
|
