Este es un curso de análisis y diseño de algoritmos para los estudiantes del postgrado de Computación. El curso está dirigido por igual a estudiantes presenciales y a distancia. El fin del curso es enseñar un panorama general de las técnicas de análisis y diseño, las principales estructuras de datos que sustentan la instrumentación de algoritmos y un recorrido por distintos tipos de algoritmos.

  • Profesor: Leandro Rabindranat Leon - lrleon punto ula punto ve
  • Preparador: Alejandro Mujica - alejandromujica at ula punto ve
  • Horario:
    • jueves de 4-6 pm
    • viernes de 3-5 pm

    • Las clases se dictan en el salón de postgrado

  • Consultas: martes 7:30-8:30 pm por skype (skype name: leandro.r.leon). En modo presencial u otro horario es posible previo acuerdo.

    De antemano aclaro que muy pocas veces respondo dudas por email; no espere pues que yo le responda una duda o le dé consulta por email (es demasiado costoso en tiempo),. La mejor forma de obtener feedback conmigo es mediante la consulta en skype o presencialmente.

El estilo del curso serán clases magistrales, relativamente cortas, luego discusión. Las clases serán filmadas y las transparencias (cuando se utilicen) serán puestas en web por el personal del postgrado. Los vídeos de los cursos se colocan en youtube bajo la cuenta pgcomp1

Para los trabajos prácticos y en muchas explicaciones del curso, se emplea la biblioteca Aleph. La versión fuente más reciente puede descargarse de aquí.

Últimas noticias

Evaluación

En este curso ud. puede optar y combinar entre dos modalidades de evaluación: exámenes presenciales y trabajos prácticos

Cada evaluación tiene una ponderación porcentual sobre la calificación final. La calificación final del curso es la suma de los productos de las calificaciones obtenidas en las evaluaciones multiplicadas por su ponderación.

Ud. tiene libertad total para presentar las evaluaciones que desee según su circunstancia. Puesto que la suma de todas las evaluaciones es el 200 %, una evaluación que ud. no pueda o no desee presentar se puede reemplazar por otra alternativa. Así que no se angustie si obtiene una mala calificación o no puede asistir a una evaluación.

Para aprobar la materia se requiere obtener más de diez puntos en la calificación total.

Al final de mes se publicará una selección de problemas. Al final de cada clase se propondrá un conjunto de ejercicios. Su acometimiento temprano y solución satisfactoria deberían de ser suficiente para hacerse una idea de su preparación para los exámenes. Por razones de tiempo, los ejercicios no se corrigen, pero ud. podría emplear mis tiempos de consulta en ello.

Exámenes presenciales

Tres exámenes parciales en las siguientes fechas y ponderaciones:

  • Lunes 30 de abril: 30% sobre la nota total.
  • Lunes 4 de junio: 40% sobre la nota total.
  • Lunes 16 de julio: 60% sobre la nota total.

Los temas de los exámenes son acumulativos; es decir, la materia a evaluar es lo impartido desde el inicio del curso asta el penúltimo jueves precedente al examen. Por ejemplo, para el examen del 4 de junio, se evaluará todo lo impartido entre el 22 de marzo y el 24 de mayo.

Trabajos prácticos

Tres trabajos prácticos:

    Número Fecha de enunciadoFecha de entregaTema Porcentaje
    15 de abril30 de abrilPor definir30%
    226 de abril4 de junioPor definir50%
    317 de mayo16 de julioPor definir80%

Trabajo entregado en retardo tendrá una penalización de 2^días de retardo. ¡No se pase más de un día!

Los trabajos prácticos deberán programarse en C++ y compilados con gcc (4.4 superior) y bajo la biblioteca Aleph-w.

Para el 2do o 3er trabajo es altamente probable que requiera una interfaz gráfica. En este caso, la interfaz sería QT.

Tips para aprobar el curso

Mi recomendación personal es hacer dos trabajos y prepararse para dos exámenes. Con ello, ud. tendrá al menos 150% de ponderación; lo que significa, por ejemplo, que si obtiene 10 puntos en cada evaluación, entonces ud tendrá una nota final de 15 puntos.

¡No se retrase!, este es el "truco". Esté al día con los ejercicios y asegúrese de hacerlos y comprenderlos cabalmente por su propia cuenta. Lo mismo aplica a los trabajos prácticos; comience a hacerlos desde el primer día. De hecho, en el caso de los trabajos prácticos, es mi experiencia que aquellos estudiantes que comienzan tardíamente simplemente no llegan a un nivel suficiente para entregarlo en forma operativa. Por supuesto, un trabajo práctico no operativo no es digno de evaluación. Así que si ud no está dispuesto a empezar desde el comienzo, entonces no pierda su tiempo ni me haga perder el mío.

Si su interés es trabajar lo mínimo, cuestión para mí perfectamente válida y comprensible, y si sigue y cumple fielmente la recomendación anterior, entonces apueste a los dos primeros exámenes y el primer trabajo. Si ud se desempeña exitosamente, entonces ud. podría estar mucho más relajado, o inclusive abandonar el curso, a mediados de junio, pues para ese entonces ud. ya tendría una calificación total del curso que podría serle satisfactoria.

Si su interés es profundizar sus conocimientos en algoritmos, estructuras de datos y programación, entonces apueste a los proyectos. Pero de nuevo, le insisto, no empiece tarde. respecto a las evaluaciones, las cuáles sólo se evalúan, los trabajos prácticos poseen la enorme ventaja de ud podrá recibir correcciones.

Si las ciencias de la computación son el centro de su vida, entonces haga todo. Es la mejor manera, en los cánones del curso, de que ud desarrolle su potencial y descubra su nivel.

Programa General

  • Análisis de algoritmos
    1. Repaso a estructuras de datos básicas
    2. Análisis de algoritmos por asíntotas
    3. Análisis amortizado
  • Métodos de diseño de algoritmos
    1. Perspectivas de diseño
    2. Dividir/Combinar
    3. Algorítmos ávidos
    4. Programación dinámica
  • Estructuras de datos de soporte a los algoritmos
    1. Grafos y digrafos
    2. Heaps
    3. Árboles Splay
    4. Árboles equilibrados fuertes (AVL y Rojo-negro)
    5. Arboles binarios y aleatorización (treaps y árboles aleatorizados)
    6. Tablas hash
  • Grafos y algoritmos
    1. Nociones fundamentales, recorridos y aplicaciones
    2. Grafos dirigidos
      1. Conectividad
      2. Ordenamiento topológico
    3. Árboles abarcadores mínimos
    4. Caminos mínimos
  • Redes de flujo
    1. Definiciones, propiedades fundamentales, interfaz
    2. Algoritmos de flujo máximo basados en caminos de aumentos
    3. Algoritmos de flujo máximo basados en empuje de preflujo
    4. Aplicaciones de las redes de flujo
    5. Redes de flujo con costes - Flujo máximo al mínimo costo
    6. Aplicaciones de las redes de flujo con costes

Bibliografía

  • Tejiendo Algoritmos - Leandro Rabindranath Leon
  • 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.

 
 

AYDA PGCOM 2011