• Sesión 1: Introducción

 
Reseña histórica, preeliminares matemáticos, funciones de complejidad.

 

• Sesión 2: Midiendo el tiempo de ejecución
 

Análisis asintótico, notación O, propiedades de la notación O.

• Sesión 3:  Análisis de Algoritmos y  Recurrencias

El Teorema Maestro

Análisis de algoritmos, eficiencia de programas, estimación del tiempo de ejecución.
Recurrencias, método de sustitución, método de iteración, método maestro.

• Sesión 4: Métodos de Ordenamiento

Tipos de ordenamiento, medidas de eficiencia. Algoritmos básicos. QuickSort, HeapSort, BinSort y RadixSort. Arboles de Decisión.

• Sesión 5: Algunas Funciones y Sumatorias (Notas del Dr. Guillermo Morales Luna)

  Polinomios, potencias, logaritmos, factoriales, funciones iteradas, sumatorias y productos.

   

• Sesión 6: El Problema de Búsqueda

  El problema de búsqueda. Arboles de decisión para el problema de búsqueda. Búsqueda secuencial y búsqueda binaria. Arboles 2-3.

  Árboles binarios

   

• Sesión 7: Arboles Rojinegros

Definición y propiedades. Búsqueda, Rotaciones, Inserción y Supresión.

 

• Sesión 8: Tablas de Dispersión

 
Dispersión directa. Funciones de Dispersión: método de la división, método de la multiplicación. Dispersión Universal. Direccionamiento abierto.

• Sesión 9: Algunos Problemas Sobre Teoría de Gráficas
        Algunos Algoritmos sobre Gráficas

Definición. Ciclo Euleriano, Ciclo Hamiltoniano, Arbol Libre. Gráficas dirigidas. Recorridos. Gráficas dirigidas acícliclas. Orden Topológico. Gráficas no dirigidas. Arboles generadores de costo mínimo.

• Sesión 10: Técnicas de Diseño de Algoritmos

 
Divide y vencerás. Algoritmos ávidos. Programación dinámica. Backtracking. Branch and bound.

 

• Sesión 11: Algoritmos de Búsqueda Local

 
Estrategia General. Búsqueda local para corte máximo en gráficas. Búsqueda local para el problema del agente viajero.

 

• Sesión 12: Recocido Simulado y Búsqueda Tabú

 
Algoritmo de Metropolis. Búsqueda Tabú.

 

• Sesión 13: Técnicas de Aleatorización

 
Estrategia General. Aplicación al problema de satisfactibilidad. Aplicación al problema de satisfactibilidad pesada.

 

• Sesión 14: Completitud NP

Tratabilidad e Intratabilidad. Decidibilidad. Problemas de Decisión y Problemas de Optimización. Clase P y NP. Problemas NP     Completos.
 

LÁMINAS ADICIONALES

• Modelos Computacionales
 

Compuerta lógica, máquina de estados finitos, autómatas de pila, Máquina de acceso aleatorio, máquina de Turing.

 

• Complejidad Computacional

  Lenguajes formales, teoría de la complejidad, computabilidad.

   

  ---