Análisis y Diseño de Algoritmos

Sílabo

Accede al sílabo de Análisis y Diseño de Algoritmos de la UNMSM:

• Sílabo 2023-II

Contenido del curso

A modo de resumen, estos son los temas que se llevan:

• Semana 01: Fundamentos matemáticos (Series, Sumatorias, Logaritmos, Límites, Derivadas). Algoritmos (Formalismo y Abstracción, Especificación, Terna de Hoare). Definición de complejidad algorítmica.
• Semana 02: Notaciones asintóticas (O, Ω, θ). Análisis de estructuras de control. Análisis de las estructuras de datos básicas.
• Semana 03: Algoritmos Recursivos. Análisis de complejidad: Método de la Substitución. Métodos del Árbol de Recursión. Método del Maestro.
• Semana 04: Algoritmos de Ordenación. Análisis de complejidad de los algoritmos comunes (Bubble Sort, Insertion Sort, Selection Sort, Merge Sot, Shell Sort, Quick Sort, HeapSort). Análisis de Complejidad de los algoritmos especiales. Tiempo Lineal (Radix Sort, Counting Sort).
• Semana 05: Algoritmos de Búsqueda y Selección. Análisis de Complejidad (secuencial, por bloques, Quick select, binaria, indexada, árbol binario de búsqueda, Heaps).
• Semana 06: Análisis de Algoritmos en Grafos. Algoritmos de Búsqueda en Anchura, Búsqueda en Profundidad, 
• Semana 07: Análisis de Algoritmos en Grafos. Orden Topológico, Componentes fuertemente Conexas.
• Semana 08: Examen Parcial.
• Semana 09: Algoritmos Voraces. Problema de la asignación de Carga: Interval Scheduling. Problema de la Mochila: Knapsack Problem. Problema del cambio de moneda: Coin Changing.
• Semana 10: Algoritmos Voraces en Grafos. Caminos Cortos en Grafos: Dijkstra's Algorithm. Puentes en grafos: Selecting Breakpoints. Cobertura de vértices (Vertex cover). Árbol de expansión mínimo. Prim's Algorithm. Kruskal's Algorithm.
• Semana 11: División y Conquista. Análisis de Merge Sort. Problema de contar inversiones: Couting Inversions.. Problema del par de puntos cercanos: Closest Pair of Points. Problema de la multiplicación de N enteros: Integer Multiplication. Problema de la Multiplicación de Matrices: Matrix Multiplication.
• Semana 12: Programación dinámica. Definición del Criterio Optimo (OPT). Problema de la asignación de Tareas ponderadas: Weighted Interval Scheduling. Problema de la mayor subsecuencia creciente: Longest Increasing Subsequence. 
• Semana 13: Programación dinámica. Problema de la mochila óptima: Knapsack Problem. Problema de la alineación de secuencia: Sequence Alignment. Problema de la alineación de secuencia en espacio Lineal: Sequence Alignment in Linear Space.
• Semana 14: Algoritmo de retroceso: Ramificación y poda. Introducción a las clases P, NP y NP completos. Reducción y completitud NP: (Reducción, reducciones polinómicas, máquinas de Turing, no determinista, teorema de Coook, completitud NP, pruebas de integridad NP, jerarquía en complejidad computacional). Tratamiento de problemas NP-completos: (algoritmos aproximados, aseguramiento de la calidad, búsqueda heurística, algoritmos heurísticos, algoritmos exactos, enumeración).
• Semana 15: Presentación y exposición del proyecto.
• Semana 16: Examen Final.