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..

Para el curso se emplea la biblioteca Aleph. La versión fuente más reciente puede descargarse de aquí.

Últimas noticias

Evaluación

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

  • Tres exámenes parciales (40%): se elimina la peor calificación
  • 1 proyecto bajo las siguientes reglas generales (45%):
    1. Grupos de máximo 3 personas.
    2. Sistema operativo Linux, compilador GNU gcc, biblioteca Aleph
    3. Interfaz gráfica con biblioteca QT
    4. Fecha de entrega: a definir
    5. Pulse aquí para leer mis consideraciones sobre la importancia de hacer un proyecto y su evaluación
    6. Corrección proyecto:
      1. No compila o no cumple ningún requerimiento ==> cero de calificación
      2. Cumplimiento de requerimientos: 60%
      3. Manual del usuario: 10%
      4. Documento de diseño: 5%
      5. Estilo de codificación: 10%
      6. Interfaz usuario: 15%
  • Nota apreciativa individual (15%).

Programa

    1. Repaso a estrcuturas de datos y estructuras avanzadas
      1. Heaps
      2. Árboles aleatorizados
      3. Árboles AVL
      4. Hash lineal
    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

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

Todas las estructuras de datos y algoritmos enseñados en este curso están disponibles en la biblioteca Aleph.

Otros

  • Horarios: lunes y jueves de 10 AM a 12 PM
  • Laboratorio: sábados de 10 AM a 12 PM.
 
 

AYDA B 2011