Información general

Curso avanzado de análisis y diseño de algoritmos para estudiantes del postgrado de computación.

El curso se focaliza en:

  • Técnicas de análisis de algoritmos.
  • Técnicas de diseño de algoritmos.
  • Estructuras de datos avanzadas.
  • Grafos.

Instructor: Leandro Rabindranat Leon - lrleon punto ula punto ve

Ayudante docente: Alejandro Mujica - alejandromujica at ula punto ve

Hay una lista de correo electrónico cuyo propósito es la divulgación de información de interés y posibilitar discusión. Su dirección es pgcomp_AyDa at listas punto ula punto ve. Normalmente, los estudiantes del postgrado son inscritos por la coordinación; pero ud. puede solicitar inscripción a través del siguiente enlace.

Horario

  • Martes de 4-6 pm
  • Viernes de 3-5 pm

    • Las clases se impartirán en el salón del postgrado de computación.


    Requisitos

    • Destrezas en diseño y uso de estructuras de datos clásicas: arreglos, listas enlazadas, árboles y tablas hash.
    • Lenguaje de programación C++; nivel intermedio en adelante.
    • Altamente deseable pero no indispensable: biblioteca de GUI QT. Recomiendo el uso del IDE QT Creator como entorno de desarrollo.
    • Los exámenes y el trabajo práctico se realizarán con la biblioteca ALEPH.

    • Técnicamente, el compilador y sistema operativo no son imperativos. Empero es bueno advertir que ALEPH no ha sido probada en otras circunstancias. Por esa razón, es altamente recomendable el compilador gcc y el sistema operativo LINUX. La distribución la puede escoger ud.

      Para la instalación de ALEPH puede descargar un manual de instalación escrito por Alejandro Mujica.

      De todos modos, si ud. se anima, yo apreciaría pruebas de ALEPH en otros sistemas operativos.

    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

    • 13/2/2011: clase de inducción el viernes 18 de febrero de 2011. Salón de clase del postgrado.

    Programa

      1. Técnicas de análisis de algoritmos
        1. Notación O
        2. Ecuaciones recurrentes
      2. Repaso a estructuras de datos y estructuras avanzadas
        1. Heaps
        2. Treaps
        3. Árboles AVL
        4. Tablas hash dinámicas
      3. Análisis amortizado
        1. La técnica
        2. Árboles splay
      4. Grafos
        1. Fundamentos: definiciones, estructuras de datos, interfaz
        2. Algoritmos fundamentales: recorridos, conectividad, aciclicidad, caminos, puntos de corte
        3. Árboles abarcadores mínimos
        4. Caminos mínimos
        5. Redes de flujos
          1. Definiciones
          2. Algoritmos de flujo máximo: Ford-Fulkerson, Edmonds-Karp, empuje de preflujo
          3. Modelos de problemas de optimización con redes de flujo
          4. Flujos con coste mínimo
          5. Modelos de problemas de optimización con redes de flujo a coste mínimo

    Evaluación

    Se realizarán tres exámenes parciales y un sistema programado.

    Los parciales consistirán en la realización de programas que serán asignados un viernes de clase. La clase se consagrará a discutir el examen. El resultado será entregado en la clase del martes.

    • Tres exámenes parciales (60 %); se elimina la peor calificación
    • 1 proyecto (50 %)
    • Nota apreciativa (15 %)
     
     

    AYDA pgcomp 2011 a