Apunte Curso de Diseño y Análisis de Algoritmos

Departamento de Ciencias de la Computación (DCC), Universidad de Chile

(para descargar el apunte, ver al final del documento)

Con los objetivos de que

• los alumnos tengan una referencia precisa de lo que se ve en clases para estudiar,
• los alumnos no tengan que tomar notas exhaustivas de lo que se ve en clases, liberando de este modo más tiempo para discusión, y
• el curso pueda ser dictado por otro profesor en forma uniforme,

El apunte, actualmente de 155 páginas (faltan agregar imágenes y recordar conceptos elementales en el apéndice), fue escrito con la ayuda de mi profesor auxiliar Ariel Cáceres, quien se encargó de las figuras y apéndice (le faltan) y ha revisado el texto para encontrar errores e inconsistencias. El apunte está dividido en 9 capítulos:

1. Cotas Inferiores
2. Memoria Externa
3. Análisis Amortizado
4. Universos Discretos y Finitos
5. Algoritmos en Línea
6. Algoritmos Probabilísticos y Aleatorizados
7. Algoritmos Aproximados
8. Algoritmos Paralelos
9. Apéndice: Conceptos Básicos

Al final de cada capítulo hay una lista de referencias a libros clásicos donde puede encontrarse material relacionado, así como fuentes online, incluyendo documentos, presentaciones y videos.

El apunte puede descargarse gratuitamente, incluso si no se es alumno del curso. Me gustaría mucho saber que ha resultado útil para enseñar y aprender esta materia en otras universidades de Chile e Hispanoamérica. Por ello están invitados a descargarlo y usarlo. Sólo pido que me envíen un email de dos líneas a gnavarro@dcc.uchile.cl si lo usan para dictar un curso o para estudiar, para mis registros.

Asimismo, agradeceré me hagan saber de cualquier error que encuentren, por insignificante que parezca (soy muy detallista). Lo corregiré inmediatamente y actualizaré el apunte.

Esta obra está bajo una licencia de Creative Commons.
Descargar el apunte PDF (si lo usa fuera del DCC hágamelo saber)