Introducció als Esquemes Algorísmics (IEA)
(http://www.lsi.upc.edu/~iea)
| Professors Responsables: |
FCO. JAVIER LARROSA BONDIA (larrosa lsi.upc.edu )
|
|
Crèdits: 6.0 (3.0 T 1.5 P 1.5 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Optativa per la EI , ETIG
Requisits de l'assignatura
|
EDA
- Pre-requisit per la EI , ETIG
|
|
Objectius docents
Esta asignatura pretende que sus alumnos :
- conozcan un conjunto de técnicas de diseño de algoritmos (algoritmos
voraces, divide y vencerás, algoritmos de vuelta atrás, etc. )
- profundicen en los algoritmos de recorrido exhaustivo de grafos
- frente a un problema determinado, sepan:
- caracterizarlo identificando sus aspectos más relevantes
- elegir la técnica de diseño más adecuada para su resolución
- producir una versión algorítmica eficiente
- argumentar la corrección de la solución obtenida
También se pretende que el alumno se familiarice con el uso de las notaciones
asintóticas y las utilice para valorar la eficiencia de los algoritmos
producidos. Deberá ser capaz de seleccionar los tipos de datos ya conocidos que
resulten más adecuados para mejorar la eficiencia temporal de la solución.
Programa
1. Análisis de la Eficiencia de Algoritmos (Durada: 6 h.)
- Repaso de conceptos. Repaso de las notaciones asintóticas.
- Resolución de recurrencias. Teoremas para la resolución de
recurrencias.
2. Recorridos en Grafos (Durada: 8 h.)
- Repaso de conceptos sobre grafos, su especificación e
implementación.
- Repaso de los esquemas de recorrido en profundidad y anchura.
- Ordenación topológica de grafos acíclicos.
- Aplicaciones.
3. Divide y Vencerás (Durada: 4 h.)
- Caracterización del tipo de problemas resolubles mediante el esquema.
- Fundamentos del esquema algorítmico.
- Problemas representativos: producto de enteros largos,
producto de matrices (Strassen), ordenación por fusión
(mergesort), ordenación rápida (quicksort)
y algoritmos de selección.
4. Algoritmos Voraces (Durada: 8 h.)
- Caracterización del tipo de problemas resolubles
mediante el método voraz.
- Esquema algorítmico.
- El principio de optimalidad y la función de selección.
- Algoritmos de Prim y Kruskal para árboles de expansión mínimos.
- Algoritmo de Dijkstra para caminos mínimos.
- Otros ejemplos: códigos de Huffman, planificación de tareas, ...
5. Esquemas de Exploración Exhaustiva (Durada: 8 h.)
- Caracterización del tipo de problemas resolubles mediante el esquema
de vuelta atrás (backtracking) y el esquema de
ramificación y poda (branch & bound).
- Esquema algorítmico recursivo: una solución, todas y la mejor.
- Elección del árbol de búsqueda.
- Marcajes.
- Poda basada en el coste de la mejor solución en curso.
- Ejemplos: Mochila entera, problema del viajante de comercio,
...
- Búsqueda informada: el esquema de ramificación y poda.
6. Programación Dinámica (Durada: 4 h.)
- Caracterización del tipo de problemas resolubles
mediante programación dinámica.
- Esquema algorítmico.
- Formulación recursiva y memoización.
- Ejemplos: algoritmo de Floyd para caminos mínimos,
distancia de edición, mochila entera, árboles
binarios de búsqueda óptimos, ...
Avaluació
La nota FINAL de la asignatura consta de tres componentes:
* la nota de TEORIA, que aporta un 65% a la nota final. Esta nota es la
calificación del único examen de la asignatura que se realiza al finalizar
el cuatrimestre
* la nota de LABORATORIO, que aporta un 25% a la nota final. Esta nota es
la calificación de la práctica de la asignatura
* la nota de PROBLEMAS, que aporta un 10% a la nota final. El alumno ha de
entregar, a lo largo del curso 3 ejercicios resueltos, cada uno
perteneciente a un tema distinto. La nota media de estas 3 entregas es la nota
de problemas
No se exige nota mínima para ninguna de las 3 calificaciones.
Càrrega
Los 6 créditos de la asignatura corresponden a 4 horas semanales de clase que
se distribuyen en 2 de teoría, 1 de problemas y 1 de laboratorio.
Bibliografia
Bibliografia bàsica
- Abad, M.T. Apuntes de Introducción a los Esquemas Algorítmicos, Informe Técnico LSI-97-6-T , 1997
- Brassard, G., Bratley, P. Fundamentos de Algoritmia Prentice Hall, 1997
- Ferri, F.J., Albert, J.V., Martín, G. Introducció a l'anàlisi i disseny d'algorismes Universitat de València, 1998
- Horowitz, E., Sahni, S., Rajasekaran, S. Fundamentals of Computer Algorithms Computer Science Press, 1997
- Mehlhorn, K., Naher, S. LEDA: A Platform for Combinatorial and Geometric Computing Cambridge University Press, 1999
Bibliografia complementària
- Cormen, T., Leiserson, C., Rivest, R. Introduction to algorithms The MIT Press, 1990
- Manber, U. Introduction to algorithms: a creative approach Addison-Wesley, 1989
- Pearl, J. Heuristics: Intelligent search strategies for computer problem solving Addison-Wesley, 1984
- Sedgewick, R. Algorithms in C++ (3rd edition) Addison-Wesley, 1999
- Skiena, S.S. The Algorithm Design Manual Springer-Verlag (TELOS), 1998
- Weiss, M.A. Data Structures and Algorithm Analysis in C++ (2nd edition) Addison-Wesley, 1999
Informació complementària
La práctica se hace en grupos de dos personas y consiste en diseñar una solución
correcta y lo más eficiente posible para el problema propuesto.
Para el desarrollo de la práctica se empleará
el lenguaje de programación C++ en combinación con
la librería LEDA para computación combinatoria. Las prácticas se podrán desarrollar
tanto en entornos Unix/Linux como en el entorno W95.
|
