Ciencias de la Computación (plan 2013) 2024-2

Quinto Semestre, Análisis de Algoritmos

Curso presencial de Análisis de Algoritmos

*Comenzamos el martes 30 de enero.


Titular: Jesús Nestaly Marín Nevárez
Correo: nestaly@ciencias.unam.mx

Dinámica del curso:

En las clases se presentan conceptos y técnicas de análisis y diseño de algoritmos. Esto es acompañado de ejemplos en los que se aplican los conceptos así como de demostraciones formales en algunos casos.

En las tareas se incluyen ejercicios y problemas similares a los vistos en clase que tienen por objetivo la aplicación de los conceptos y técnicas de demostración vistas en clase.

El objetivo de las ayudantías teóricas será acompañar a los alumnos en la resolución de las tareas, lo cual incluye realizar ejemplos complementarios y discutir las dudas presentadas por los alumnos.

Tanto en las clases como en la ayudantía se espera la participación activa de los alumnos.


Evaluación:

Tareas: 50%, Exámenes: 50%.
Participación en clase: puede ayudar a tener unas décimas extra al final del semestre.

Se encargarán de 5 a 6 tareas a lo largo del curso y se realizarán dos exámenes. Los exámenes se pueden realizar únicamente de manera presencial. No habrá exámenes de reposición.

Una vez entregada una tarea o realizado un examen no se es elegible para NP.

Temario

1 - Conceptos básicos

1.1 Problemas y algoritmos: Especificación de un problema por su entrada y la salida esperada; Instancias de un problema; Algoritmo; Algoritmo correcto.

1.2 - Tipos de problemas: Optimización; Decisión; Enumeración; Salida General.

1.3 - Complejidad: Problemas tratables e intratables; Reducciones; Clases de problemas de decisión; Peor caso, mejor caso y caso promedio.

1.4 - Modelos de cómputo: Modelo RAM.

2 - Justificación y diseño de algoritmos

2.1 - Notación asintótica: Propiedades de los órdenes de crecimiento asintóticos; Dominancia; Operaciones con notación asintótica.

2.2 - Algoritmos iterativos: Estrategia; Invariantes de ciclo.

2.3 - Algoritmos recursivos. Estrategia; Demostraciones por inducción.

2.4 - Diseño de algoritmos: Técnicas de diseño de algoritmos (divide y vencerás, algoritmos greedy, programación dinámica, algoritmos aleatorizados, algoritmos de aproximación, etc.).

3 - Divide y vencerás

3.1 - Estrategia. Ejemplo inicial: Merge Sort.

3.2 - Relaciones de recurrencia: Teorema maestro; Método de Sustitución; Árbol de recursión.

3.3 - Búsqueda Binaria.

3.4 - Mediana y k-selección. Demostración por método de sustitución.

3.5 - Quicksort.

4 - Algoritmos que involucran secuencias y conjuntos

4.1 - Ordenamiento: Cota mínima; Ordenamiento en tiempo lineal (Counting Sort, Radix Sort)

4.2 - Árboles binarios. Montículos: colas de prioridad, montículos (heaps); Heap Sort; Árboles binarios de búsqueda.

4.3 - Diccionarios: Comparación las operaciones con listas ligadas, arreglos y árboles binarios de búsqueda.

5 - Algoritmos para teoría de gráficas 1

5.1 - Algoritmos de búsqueda: Búsqueda por anchura; Búsqueda por profundidad.

5.2 - Trayectorias más cortas desde una fuente: Algoritmo de Dijkstra

5.3 - Árbol generador de peso mínimo: Propiedad de corte; Algoritmo de Prim; Algoritmo de
Kruskal.

6 - Algoritmos greedy

6.1 - Estrategia. Subestructura óptima.

6.2 - Ejemplos: Códigos de Huffman; Calendarización.

7 - Programación dinámica

7.1 - Estrategia: Diferencia entre greedy y programación dinámica; Subproblemas superpuestos (overlapping subproblems).

7.2 - Calendarización de intervalos con pesos.

7.3 - Multiplicación de matrices.

8 - Algoritmos para teoría de gráficas 2

8.1 - Trayectoria más corta entre todos los pares: Algoritmo de Floyd-Warshall.

8.2 - Algoritmos de redes de flujos: Redes residuales; Caminos de aumento; Algoritmo de Ford-
Fulkerson.



Recursos:

Utilizaremos la plataforma Classroom para realizar anuncios y para publicar tareas, así como para tener la opción de que los alumnos entreguen tareas por este medio.

Enlace de Classroom: https://classroom.google.com/c/NjU0MjgwODAyNDcy?cjc=e25li4q

Si alguien tiene problemas para acceder a classroom escríbanme un correo por favor.



Bibliografía básica del curso:

Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein. MIT Press.
(Tercera o Cuarta edición.)

Algorithm Design. John Kleinberg y Éva Tardos. Addison-Wesley Professional.
(Segunda edición)