Diseño de Algoritmos I
CI-5651
Enero-Marzo 2011


Índice
Última hora
Horas de Consulta
Horario de Clases
Cronograma de Actividades
Evaluación
Enunciado de los exámenes
Enunciado de Proyectos y normas de documentación y entrega

ULTIMA HORA:

  • MEJORES SOLUCIONES EXAMEN 2 Y PROYECTO 3: SOLUCIONES
  • MEJOR INFORME ETAPA 2 DEL PROYECTO : informe
  • Ejemplo de un programa bien escrito y bien documentado en C : programa
  • Ejemplo de Informe bien redactado (aunque han debido referirse al problema principal que era SUDOKU) : informe
  • En la presentación del proyecto 1 deben hablar sobre las estructuras de datos utilizadas para representar la FNC, ventajas y desventajas. Hablar sobre la implementación del backtracking, si lo hicieron iterativo o recursivo. Dificultades encontradas. Discutir los tiempos de ejecución, comparando con Zchaff.
  • - Los artículos más importantes, los que deben leer, sobre el proyecto son: EfficientSolvers.pdf (donde pueden ver el esquema iterativo y recursivo del backtracking), goldbergFastaSATSolver.pdf, marques-silva96grasp.pdf (versión más extensa: marques-silva96graspReporteDeInv292-96.pdf), EstructurasDeDatosParaSAT.pdf, Chaff.pdf

    Algunos puntos sobre el proyecto 1:

    - Deben implementar un solver general para cualquier instancia de SAT, NO que resuelva sólo instancias correspondientes a SUDOKU.
    - Para esta etapa sólo se les pide implementar el backtracking (puede ser recursivo o iterativo), implementando al menos "Unit Propagation" y "Pure Literal Elimination" (ver http://en.wikipedia.org/wiki/DPLL_algorithm#The_algorithm)
    - Lean el artículo EstructurasDeDatosParaSAT.pdf, para que vean una discusión sobre estructuras de datos para SAT.

  • Lecturas recomendadas sobre el curso:
Semana 1 y 2: Capítulos 1 al 4 de Brassard (hojear), primeras páginas de los capítulos sobre Complejidad de Brassard y Cormen. DFS del libro Grafos y Algoritmos (Oscar Meza y Maruja Ortega), secciones 9.4 a 9.6 de Brassard
Semanas 3 y 4: secciones 9.6 y 9.7 Brassard, sección 3.1 de Garey&Johnson
Semanas 5 y 6 : Brassard capítulo 6 y sección 5.9, Cormen(segunda edicion, 2001) capitulo 16 y 21.
Semanas 7 y 8: Brassard secciones 4.7, 7.1, 7.4, Cormen(segunda edicion, 2001) capítulo 7, sección 16.4
Semanas 9, 10 y 11: Brassard 7.5 y cap. 8, Cormen(segunda edicion, 2001) cap. 9, sección 33.4, secciones 14.1, 15.2 y 15.3

Horas de Consulta: después de clases.
Horario de clases: martes y jueves 3:30-5:30pm           aula: MYS-101A
Cronograma de Actividades:


Enero-Marzo 2011
Martes
Jueves
(1)
10-14 enero
 Presentación del curso.
Análisis y síntesis de algoritmos. Complejidad en tiempo de algoritmos: Complejidad exacta. Análisis PeorCaso y Caso promedio. Análisis amortizado.
 Ej: ordenamiento por inserción.
entrega enunciado proyecto 1 (15%)
 Problemas eficientes, problemas dificiles. Clases P, NP, NP-completo. Discusión del proyecto 1
(2)
17-21 enero
Notación O grande, Omega, etc.
Algoritmos eficientes. Problemas que se pueden resolver eficientemente.
Discusión proyecto 1
 Recorridos en grafos. Modelo general de etiquetamiento. DFS propiedades, BFS propiedades. Aplicaciones: enumeración de conjuntos. Backtracking. EjemplosBacktracking, estrategias de poda más eficientes,
(3)
24-28 enero
Backtracking. ej: n-reinas, el problema de la suma. Branch&Bound. Ejemplo: asignación. Knapsack
(4)
31-4 feb
 retomar definición de Problemas NP, problemas NP-completos, NP-hard. Reducción de problemas. Ejemplos: Cálculo de caminos mínimos en grafos sin circuitos a caminos máximos. Caminos mínimos hasta cada vértice alcanzable desde uno dado en caminos mínimos desde cada vértice que alcanza uno dado.
Ejemplos: SAT, 3-SAT, Coloración, etc. Ejemplos de reducción para mostrar que están en NP-completos (clique máxima).  Reducción de sat a 3-sat a "vertex cover" a "ciclo hamiltoniano" a "agente viajero"
(5)
7-11 feb
Estrategia Greedy. Como heurística: cambio moneda, coloración. Como algoritmo exacto: Kruskal,  Problema de la Mochila fraccionario (knapsack). Secuenciación
Discusión proyecto 2
(6)
14-18 feb
trabajo en el proyecto
entrega solución proyecto 1. Discusión de resultados por los equipos.

entrega enunciado proyecto 2 (10%).  		entrega enunciado 1er. examen (35%)
  Verificar correctitud de Kruskal. Estructura de datos para representar particiones de conjuntos. Uso en Kruskal. Verificacion de que el algoritmo greedy para secuenciación es exacto. 
(7)
21-25 feb

Teoría de Matroides. 
 b-uniformidad.  Solúción de recurrencias útiles en algoritmos recursivos. Teorema maestro.
 
 entrega solución 1er. examen.
Ejemplos de análisis en tiempo de algoritmos recursivos. Corrección de algoritmos recursivos. Ejemplo: merge-sort.
(8)
28-4 mar
Divide-and-Conquer: esquema general. Quicksort (análisis promedio) Multiplicación de enteros grandes. Estadísticos de Orden. Aumento de estructuras de datos para hallar estadísticos de orden.

(9)
7-11 mar
CARNAVAL

 entrega solución proyecto 2. Discusión cada equipo.
entrega enunciado proyecto 3 (10%)
Discusión enunciado, estrategias de bifurcación (próxima variable a asignar en el backtracking). 
(10)
14-18 mar
 Divide-and-Conquer: Cálculo de la mediana en tiempo lineal. Aplicación en geometría computacional: dos puntos más cercanos

 Prog. Dinámica: En qué consiste: Coeficiente binomial. Bellman. 
(11)
21-25 mar
Prog. Dinámica: Floyd-Warshall. Devolver cambio.
entrega enunciado 2do. examen (30%)
 Prog. Din. ejemplos: Knapsack,  evaluación de expresiones, multiplicación de n matrices. Funciones con memoria. Inicialización Virtual. 
(12)
28-01 abr
entrega solución 2do. examen
entrega solucion proyecto 3. Discusión por equipo.
 revisión de examen y proyecto
(*) B: Brassard, C: Cormen, S: Sipser
Evaluación :


Evaluación Semana Valor
primer examen
 el profesor entrega el enunciado  el 17 de febrero
 y el estudiante entrega la solución el 24 de febrero
 35%
segundo examen
 el profesor entrega el enunciado  el 22 marzo
 y el estudiante entrega la solución el 29 de marzo
 30%
primera entrega proyecto
 el profesor entrega el enunciado  el 11 enero
 y el estudiante entrega la solución el 15 feb
 15%
segunda entrega proyecto
 el profesor entrega el enunciado  el 15 febrero
 y el estudiante entrega la solución el 10 mar
 10%
tercera entrega proyecto
 el profesor entrega el enunciado  el 10 de marzo
 y el estudiante entrega la solución el 29 marzo
 10%

             Calificaciones (en pdf)
               
Exámenes:

Los exámenes deben ser elaborados con un procesador de palabras (ej: word)  o con un formateador de documentos (ej: latex) y enviados por e-mail en formato PDF al profesor y entregar en papel el día de la entrega
- Primer examen, para entregar solución el 24 de febrero:  pdf    solucion:  pdf
- Segundo examen, para entregar solucion el 29 de marzo:  pdf      solucion:  pdf


Proyectos:
  • Proyectos:
                Instancias para las pruebas
  • Material para los Proyectos: