|
Escuela
Politécnica
Superior
Universidad
Autónoma de
Madrid
genCoordinador
|
Análisis de Algoritmos
>
>
>
>
>
>
>
>
|
|
Titulación:
|
Ingeniería Informática
|
|
Plan de Estudios:
|
1992 (modificado 1998)
|
|
Web de la asignatura:
|
http://www.ii.uam.es/~aa/intro.html
|
|
Ciclo/Curso/Semestre:
|
Segundo Ciclo / Tercer Curso / Primer Semestre
|
|
Tipo de materia:
|
Optativa
|
|
Créditos:
|
7,0
|
|
Código de asignatura:
|
11333
|
|
Objetivos:
|
Es un curso orientado a estudiantes que quieran profundizar en algoritmos y técnicas básicas de resolución de problemas computacionales. En concreto, y sobre una selección de problemas que se pueden considerar como relevantes, se abordarán:
1. Conceptos básicos sobre el problema en cuestión y cuestiones afines.
2. Formulación de los correspondientes algoritmos y su pseudocódigo.
3. Análisis de la corrección de los algoritmos.
4. Análisis y discusión de las estructuras de datos más adecuadas.
5. Desarrollo manual de los algoritmos sobre ejemplos pequeños.
6. Programación en lenguaje C de los algoritmos.
7. Análisis del rendimiento en el caso peor.
Estudio de recursión, programación dinámica y algoritmos codiciosos como técnicas generales de resolución de problemas y diseño de algoritmos.
|
|
Recomendaciones:
|
Se recomienda haber aprobado MTP II y es conveniente haber aprobado EDI II.
Se considera imprescindible la asistencia continua a las clases de teoría y problemas, y a las clases de prácticas.
|
|
Metodología Docente:
|
- |
|
Programa:
|
- Revisión de Algoritmos elementales en grafos: Conceptos básicos. Algoritmo de Dijkstra
- Árboles abarcadores mínimos: Algoritmo de Kruskal. TAD Conjunto Disjunto. Corrección de los algoritmos de Prim y Kruskal.
- Grafos de tareas: Grafos dirigidos acíclicos. Hitos. Holgura. Caminos críticos.
- Aplicaciones de Búsqueda en Profundidad: Introducción. Grafos biconexos. Circuitos eulerianos. Circuitos hamiltonianos y el Problema del Viajante
- Flujos en grafos: Introducción. Algoritmo de Ford-Fulkerson. Cortes mínimos y flujos máximos. Algoritmo de Edmonds-Karp.
- Programación dinámica: El problema de la suma y la criptografía de clave pública. Ordenación óptima en el producto de matrices. Problemas resolubles por programación dinámica. Árboles binarios de búsqueda óptimos. Distancias mínimas sobre todos los vértices en grafos densos (opcional). Búsquedas aproximadas en cadenas (opcional). 2.
- Recursividad: El problema de Selección. Problemas resolubles mediante recursividad. Multiplicación de matrices. La Transformada Rápida de Fourier. Distancias mínimas entre conjuntos (opcional).
- Algoritmos codiciosos Secuenciación lineal en colas de trabajos. Problemas resolubles mediante algoritmos codiciosos. Codificación Hufman. Algoritmos codiciosos y de programación dinámica.
|
|
Bibliografía orientativa:
|
- Cormen, Leiserson, Rivest, "Introduction to algorithms", The MIT Press--Mc Graw Hill. 1990.
- Weiss, "Data structures and algorithm analysis in C", Benjamin Cummings, 1993.
- Sedgewick, "Algorithms in C", Addison-Wesley.
- Aho, Hopcroft, Ullman, "The design and analysis of algorithms", Addison Wesley.
- Aho, Hopcroft, Ullman, "Data Structures and Algorithms", Addison Wesley.
Catálogo Biblioteca - Bibliografía Recomendada
|
| Coordinador/a teoría: |
José Ramón Dorronsoro
|
| Coordinador/a prácticas: |
Álvaro Barbero
|
| Profesorado: |
Teoría:
Prácticas:
|
| Evaluación: |
|
|
|
|
|
Webmaster.eps@uam.es