Universidad Nacional de Ingeniería

Análisis y Diseño de Algoritmos

Cómo diseñar un algoritmo para un problema nuevo, demostrar que es correcto y reconocer cuándo un problema es difícil. En C++.

Teoría4 h por semanaDos sesiones de 2 h

Laboratorio2 h por semanaUna sesión

DocenteGerson Garrido

Primera semana

Semana 1Demostrar y dividir

TeoríaPresentación · Demostrar un algoritmo: invariantes e inducción · Matching estable: Gale-Shapley
LabAsignar postulantes a carreras

Bienvenidos al curso
Este curso continúa Estructuras de Datos y usa lo aprendido en Matemática Discreta. Antes del primer laboratorio, revisen la guía del entorno y su cuenta de GitHub. Para la primera sesión, lean el capítulo 1 de los apuntes.

Invariantes e inducción, recurrencias, divide y vencerás.

Argumentos de intercambio, Huffman, Dijkstra, árboles de expansión mínima y DFS.

Subproblemas sobre secuencias, intervalos y árboles, y caminos mínimos.

Flujo máximo, reducciones, NP-completitud y qué hacer con un problema difícil.