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

redacté un apunte que corresponde en forma muy precisa al material que dicto en este curso. Este es un curso poco común en los programas de computación, y no hay un conjunto pequeño de libros que cubran adecuadamente todo el material. Eso hace bastante difícil para los alumnos el encontrar referencias externas a los apuntes de clases.

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.

Gonzalo Navarro
DCC, Universidad de Chile
Noviembre de 2018

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