Análisis y Diseño de Algoritmos (300CIG004)

Información Básica

  • Créditos: 3
  • Horas de trabajo acompañado: 5 / semana (3 horas de clase, 2 de taller)
  • Horas de trabajo independiente: 4 / semana
  • Pre-requisitos: Árboles y Grafos, Computabilidad y Lenguajes Formales, Probabilidad Discreta
  • Tipo de curso: Núcleo de Formación Fundamental

Descripción del Curso

El curso estudia técnicas para diseñar algoritmos como, por ejemplo, dividir y conquistar, programación dinámica, programación voraz/avara y reintento. A los algoritmos desarrollados mediante estas técnicas se les aplican los dos tipos de análisis fundamentales en algoritmia: el de corrección y el de eficiencia. El curso también aborda técnicas de diseño de algoritmos aleatorizados y de algoritmos de aproximación, al igual que explora técnicas en la teoría de números computacional y en la computación geométrica. En la última parte del curso se introducen modelos de computación en paralelo.

Objetivos

Al finalizar el curso los participantes podrán:

  1. Usar técnicas de diseño algorítmico para resolver problemas de decisión, optimización y búsqueda computacional.
    1. Diseñar algoritmos basándose en los principios de dividir y conquistar, programación avara/voraz y reintento.
    2. Describir las ventajas y desventajas de algoritmos aleatorizados y de aproximación.
    3. Aplicar técnicas para optimización de recursos en el diseño de una solución algorítmica.
  2. Demostrar y argumentar la corrección y eficiencia de un algoritmo.
    1. Plantear contratos (i.e., precondición, poscondición, invariantes) para algoritmos iterativos y recurrentes.
    2. Demostrar que un algoritmo es correcto con respecto a su especificación; en particular, justificar por qué una fórmula es invariante de un ciclo.
    3. Calcular las complejidades temporal y espacial de una algoritmo en el peor de los casos.
  3. Implementar correcta y eficientemente soluciones algorítmicas en un lenguaje de programación.
    1. Escribir programas en un lenguaje de programación con base en el diseño algorítmico de una solución.
    2. Conocer las ventajas y desventajas de los lenguajes de programación utilizados para implementar un diseño algorítmico.
  4. Identificar técnicas de aproximación algorítmica para resolver problemas intratables (i.e., computacionalmente difíciles).
    1. Entender la programación lineal como un método general para resolver problemas de optimización.
    2. Usar la aproximación lineal para obtener algoritmos de aproximación para problemas algorítmicos combinatorios.
  5. Comprender las diferencias entre los modelos de computación secuenciales y los modelos de computación en paralelo.
    1. Distinguir entre modelos de computación secuencial y modelos de computación en paralelo.
    2. Conocer las limitaciones prácticas de los modelos de computación en paralelo.

Se desarrollan competencias en

  • El uso de un lenguaje de programación imperativo.
  • La implementación de algoritmos correctos y eficientes en un lenguaje de programación.
  • La estimación de complejidades algorítmicas para el peor de los casos.
  • El diseño de casos de prueba para validar el comportamiento de los algoritmos diseñados.

Contenido

Capítulo 1: Introducción

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
1-2 3 2 Introducción y repaso. Inducción matemática. Diseño algorítmico. Notación asintótica. Algoritmos cuadráticos de ordenamiento. Uso [1 caps 1,2] [2 cap 2][3 cap 0, app 1][5 cap 1]

Total de Horas: 5.

Sesión Horas de trabajo independiente Temas Bibliografía
1-2 4 Tareas semanales, resolución de problemas en temas vistos [1,cap 1,2][2 cap 2][3 cap 0, app 1][5 cap 1]

Total de Horas: 4.

Capítulo 2: Dividir y conquistar

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
3-6 6 4 Dividir, conquistar y combinar. Relación con inducción matemática. MergeSort. HeapSort. Bisección y búsqueda binaria. Teorema Maestro. Evaluación [1 cap 4][2 cap 5][3 cap 1][5 cap 2]

Total de Horas: 10.

Sesión Horas de trabajo independiente Temas Bibliografía
3-6 8 Tareas semanales, resolución de problemas en temas vistos [1 cap 4][2 cap 5][3 cap 1][5 cap 2]

Total de Horas: 8.

Capítulo 3: Técnicas de diseño algorítmico

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
7-11 7 5.5 Programación dinámica. Memorización (top-down). Tabulación (bottom-up). Técnicas de ahorro de memoria. Evaluación [1 cap 15][2 cap 6][3 caps 5,6][5 cap 3]
12-15 6 4 Algoritmos avaros/voraces. Óptimos locales. Técnicas de demostración de optimalidad. Evaluación [1 cap 16][2 cap 4][3 cap 7][5 cap 4]
16-18 5 2.5 Reintento (backtracking). Búsqueda exhaustiva. Heurísticas. Evaluación [3 cap 3][5 caps 5,6]

Total de Horas: 30.

Sesión Horas de trabajo independiente Temas Bibliografía
7-18 24 Tareas semanales, resolución de problemas en temas vistos [1 caps 15,16][2 caps 4,6][3 caps 3,5-7][5 caps 3-6]

Total de Horas: 24.

Capítulo 4: Temas seleccionados

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
19-21 4 3.5 Teoría de números computacional. El algoritmo de Euclides. Criba de Eratóstenes. Test de primalidad. Factorización de números. Funciones multiplicativas. Aritmética de precisión arbitraria. Ciframiento. Evaluación [1 cap 31][4 cap 5][5 cap 10]
22-24 4 3.5 Geometría computacional. Representación de puntos, líneas, segmentos, polígonos. Intersección de segmentos, polígonos. Envolvimiento convexo. Evaluación [1 cap 33][4 cap 7]

Total de Horas: 15.

Sesión Horas de trabajo independiente Temas Bibliografía
19-24 12 Tareas semanales, resolución de problemas en temas vistos [1 caps 31,33][4 caps 5,7][5 cap 10]

Total de Horas: 12.

Capítulo 5: Otras técnicas algorítmicas

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
25-26 3 2 Algoritmos aleatorizados. Quicksort. El algoritmo de Rabin y Karp. Uso [1 cap 7][3 cap 13]
27-29 5 2.5 Algoritmos de aproximación. Programación lineal entera. El algoritmo Simplex. Eliminación Gaussiana. Rounding. Cubrimiento de vértices. Uso [1 cap 29,35][3 caps 26]

Total de Horas: 12.5.

Sesión Horas de trabajo independiente Temas Bibliografía
25-29 10 Tareas semanales, resolución de problemas en temas vistos [1 caps 7,29,35][3 caps 13,26]

Total de Horas: 10.

Capítulo 7: Modelos de computación en paralelo

Sesión Horas teóricas Prácticas acompañadas Temas Profundidad Bibliografía
30-32 5 2.5 Modelos formales de programación en paralelo. Computación secuencial vs. en paralelo. Parallel programming vs. concurrent programming. La ley de Amdahl Uso [5 cap 11]

Total de Horas: 7.5.

Sesión Horas de trabajo independiente Temas Bibliografía
30-32 6 Tareas semanales, resolución de problemas en temas vistos [5 cap 11]

Total de Horas: 6.

Bibliografía

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. Third Edition. MIT Press, Cambridge, MA, USA, 2009.
  2. J. Kleinberg, É. Tardos. Algorithm Design. Pearson, 2005.
  3. J. Erickson. Algorithms. Urbana, USA, 2015. Available online: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/
  4. S. Halim, F. Halim. Competitive Programming 3: The new lower bound of programming contests. Lulu, 2013.
  5. R. Neapolitan, K. Naimipour. Foundations of Algorithms. 4th Edition. Jones and Barlett Publishers, 2011.

Instalaciones

Salón de clase con computador y proyector. Laboratorio de Ingeniería de Sistemas y Computación.

Material de este semestre

Curso en Moodle

Material adicional del curso