Curso acelerado de Diseño de Algoritmos (Verano de 2013)

Responsable: Dr. Francisco Javier Zaragoza Martínez

Todas las actividades presenciales serán en el Laboratorio de Simulación (G206), para entrar necesitas descargar e imprimir este permiso y traer tu credencial. Abajo iré agregando material conforme esté disponible. Cada tema del curso lo cubriremos en diferentes días (martes y jueves, 10:00-13:00), de acuerdo a los calendarios mostrados abajo. Cada día veremos problemas tipo y varias formas de resolverlos. Por el momento puse algunas transparencias, fotos de un curso que impartí en 2008 y en la bibliografía hay cinco libros que puedes descargar legalmente (dos de ellos en español y tres en inglés).

Problemas tipo: La evaluación de recuperación tendrá problemas similares a los del libro de Parberry para los temas 1 a 5 y a los del libro de Baase para el tema 6.

Calendario, fotos y problemas

17/07: Reunión informativa (también mandé información a tu correo institucional).
18/07: Reunión informativa y examen diagnóstico de programación estructurada.
23/07: Algoritmos, inducción y recursión (fotos). Resuelvan los problemas 100, 371 y 10696 del UVa. Dos en español.
25/07: Mínimo, búsqueda y ordenamiento (fotos). Resuelvan los problemas 369, 10474, 11032, 11413 y 11536 del UVa.
30/07: Multiplicación de enteros y de matrices (fotos). Resuelvan los problemas 374, 10106 y 11149 del UVa.
01/08: Ordenamiento recursivo y torres de Hanoi (fotos). Resuelvan los problemas 254, 10017 y 10098 del UVa.
06/08: Suma de subconjuntos y permutaciones (fotos). Resuelvan los problemas 439, 714, 750, 861, 10130 y 11137 del UVa.
08/08: Problema de la mochila (fotos). Resuelvan los problemas 562, 624 y 990 del UVa.
15/08: Problema del agente viajero (fotos). Resuelvan los problemas 216, 10496 y 11643 del UVa.
20/08: Evaluación de recuperación (07:00-10:00, F109). Corresponde al 100% de la evaluación.

1. Conceptos fundamentales

Estas son fotos de un curso que impartí en 2008. Puedes revisar el tema de inducción en el capítulo 2 del libro de Parberry o en el capítulo 3 del libro de Baase. Si necesitas recordar tus conocimientos de recursión, revisa este material. Si necesitas practicar tus conocimientos de programación estructurada comienza resolviendo ejercicios de este libro.

23/07: Algoritmos y Fibonacci (inducción, recursión, memoización y tablas).
25/07: Mínimo, búsqueda y ordenamiento (recursión, eliminación de recursión).

2. Dividir y vencer

Estas son fotos de un curso que impartí en 2008. Este tema lo puedes estudiar en el capítulo 7 del libro de Parberry, en el capítulo 4 del libro de Baase, en el capítulo 2 del libro de Dasgupta, en el capítulo 3 del libro de Guerequeta.

30/07: Multiplicación de enteros y de matrices (divide y vencerás).
01/08: Ordenamiento recursivo y torres de Hanoi (divide y vencerás).
06/08: Suma de subconjuntos (memoización, divide y vencerás).
08/08: Problema de la mochila (memoización, divide y vencerás).

3. Programación dinámica

Estas son fotos de un curso que impartí en 2008. Este tema lo puedes estudiar en el capítulo 8 del libro de Parberry, en el capítulo 10 del libro de Baase, en el capítulo 6 del libro de Dasgupta, en el capítulo 11 del libro de Skiena y Revilla, en el capítulo 5 del libro de Guerequeta y en los capítulos 18 y 19 del libro de Skiena.

06/08: Suma de subconjuntos (programación dinámica y obtención de soluciones).
08/08: Problema de la mochila (programación dinámica y obtención de soluciones).
15/08: Agente viajero (programación dinámica y obtención de soluciones).

4. Búsqueda con retroceso

Estas son fotos de un curso que impartí en 2008. Este tema lo puedes estudiar en el capítulo 10 del libro de Parberry, en el capítulo 9 del libro de Dasgupta, en el capítulo 8 del libro de Skiena y Revilla, en el capítulo 6 del libro de Guerequeta.

06/08: Suma de subconjuntos y permutaciones (búsqueda con retroceso).
08/08: Problema de la mochila (búsqueda con retroceso).
15/08: Agente viajero (búsqueda con retroceso).

5. Métodos heurísticos

Estas son fotos de un curso que impartí en 2008. Este tema lo puedes estudiar en el capítulo 9 del libro de Parberry (algoritmos glotones), en el capítulo 9 del libro de Dasgupta (búsqueda local) y en el capítulo 26 del libro de Skiena.

08/08: Problema de la mochila (heurísticos, glotón, aleatorio).
15/08: Agente viajero (heurísticos, glotón, aleatorio, aproximación).

6. Programación concurrente (paralelismo)

Estas son fotos de un curso que impartí en 2008. Este tema lo puedes estudiar en el capítulo 14 del libro de Baase.

25/07: Mínimo (paralelismo).
30/07: Multiplicación de matrices (paralelismo).
01/08: Ordenamiento recursivo (paralelismo).

Bibliografía

  1. Baase y Van Gelder. Algoritmos computacionales: Introducción al análisis y diseño. Addison Wesley. [Libro en español]
  2. Dasgupta, Papadimitriou y Vazirani. Algorithms. Mc Graw Hill. [Descarga legal en inglés]
  3. Guerequeta y Vallecillo. Técnicas de diseño de algoritmos. Universidad de Málaga. [Descarga legal en español]
  4. Llana, et al. Ejercicios de programación creativos y recreativos en C++. Prentice Hall. [Descarga legal en español]
  5. Sedgewick. Algoritmos en C++. Addison Wesley. [Libro en español]
  6. Skiena. The Algorithm Design Manual. Springer. [Descarga legal en inglés]
  7. Skiena y Revilla. Programming Challenges. Springer. [Sitio de evaluación automática]
  8. Parberry. Problems on Algorithms. Prentice Hall. [Descarga legal en inglés]
  9. UVa Online Judge. [Sitio de evaluación automática]