Información general

Este es un curso avanzado de análisis y diseño de algoritmos. Es el último curso de programación en la carrera de Ingeniería de Sistemas y se enfatiza en los grafos y muchos de sus problemas asociados: árboles abarcadores mínimos, caminos mínimos, puntos de corte, ordenamiento topológico, redes de flujo, emparejamientos, etc..

Bibliografía

  • Tejiendo Algoritmos - Leandro Rabindranath Leon
  • Estructura de datos y algoritmos - Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman - Addison-Wesley Iberoamericana: Sistemas Técnicos de Edición, 1988. ISBN 968-6048-19-7
  • Graph Theory and Its Applications - Gross and Yellen - Chapman and Hall/CRC. ISBN: 978-1584885054
  • Algorithms in C, Part 5: Graph Algorithms, 3rd Edition - Sedgewick - Addison-Wesley Professional. -10: 0-201-31663-3
  • Combinatorial Optimization: Algorithms and Complexity - Christos H. Papadimitriou and Kenneth Steiglitz - Dover Publications. ISBN-10: 0486402584
  • Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - The MIT Press - ISBN-10: 0262033844
Todos las estructuras de datos y algoritmos enseñados en este curso están disponibles en la biblioteca Aleph.

Últimas noticias

  • 4/2/2011: Notas definitivas aquí
  • 13/2/2011: Notas 3er parcial (y de los demás) aquí
  • 16/12:2010: Notas 2do parcial aquí
  • 12/12/2010: el semestre pasado, a efectos de probar y estar seguro de que solicitaba un proyecto factible, me dediqué unas tres semanas, en mis ratos libres, a codificar mi propia versión del proyecto. Es sólo un prototipo y no minimiza el coste, pero hacerlo es fácil. Los fuentes están aquí.
  • 11/12/2010: /
  • 10/12/2010: proyecto aquí - Versión pdf - Fuentes dot de graphviz

Programa

    1. Repaso a estrcuturas de datos y estructuras avanzadas
      1. Heaps
      2. Treaps
      3. Árboles AVL
    2. Análisis amortizado
      1. La técnica
      2. Árboles splay
    3. Introducción a los grafos
    4. Estructuras de datos para representar grafos en memoria
    5. Recorridos sobre grafos
      1. En profundidad y en amplitud
      2. Prueba de conectividad
      3. Prueba de aciclicidad
      4. Detección y búsqueda de caminos
      5. Puntos de articulación
    6. Grafos dirigidos
      1. Fundamentos: conectividad, inversión
      2. Clausura transitiva - algoritmo de Warshall
      3. Cálculo de componentes fuertemente conexos
        1. Algoritmo de Kosaraju
        2. Algoritmo de Tarjan}
        3. Prueba de aciclicidad
        4. Cálculo de ciclos
      4. Digrafos acíclicos
        1. Planificación de tareas
        2. Ordenamiento topológico
    7. Árboles abarcadores mínimos
      1. Algoritmo de Kruskal
      2. Algoritmos de Prim
    8. Caminos mínimos
      1. Algoritmo de Dijkstra
      2. Algoritmo de Floyd-Warshall
      3. Algoritmo de Bellman-Ford
        1. Detección de ciclos negativos
        2. Cálculo de ciclos negativos
    9. Redes de flujo
      1. Definiciones fundamentales, múltiples fuentes/sumideros, corte de red, semi-camino, caminos de aumento
      2. Algoritmos de flujo máximo
        1. Ford-Fulkerson
        2. Edmonds-Karp
        3. Empuje y preflujo
          1. FIFO
          2. HEAP
          3. Aleatorio
      3. Reducciones y aplicaciones
        1. Flujo en redes no dirigidas
        2. Capacidades en los nodos
        3. Flujo realizable
        4. Emparejamiento bipartito máximo
        5. Circulaciones
        6. Conectividad de grafos mediante redes de flujo
      4. Flujos de coste mínimo
        1. Algoritmos basados en eliminación de ciclos negativos
        2. Simplex para redes de flujo
        3. Aplicaciones
          1. Transporte
          2. Trasbordo
          3. Asignación de trabajos
          4. Caminos mínimos

Evaluación

Las evaluaciones, con sus porcentajes sobre la nota definitiva entre paréntesis, son las siguientes:

  • Tres exámenes parciales (50 %): se elimina la peor calificación
    • Primer parcial: 19 de octubre de 2010 - notas
    • Segundo parcial: 25 de noviembre de 2010 - notas
  • 1 proyecto (50 %)
  • Nota apreciativa (15 %)
  • Asistencia (2 %)

Otros

  • Horarios: martes y jueves de 10 AM a 12 PM - Aula SO01
  • Lista de clase
 
 

AYDA B 2010