UNIDAD
1. Grafos
Introducción a la teoría de grafos. Definiciones
básicas. El TDA Grafo. Recorridos de grafos: BFS (Breadth-First-Search)
y DFS (Depth-first-Search). Recorridos de grafos orientados: grafos
acíclicos, ordenamiento topológico, componentes
fuertemente conectadas. Recorridos de grafos no-orientados: componentes
conexas y Puntos de articulación. Caminos “más cortos”:
Algoritmo de Dijkstra y Algoritmo de Floyd-Warshall. Árbol
de recubrimiento de mínimo costo: Algoritmo de Prim y Algoritmo
de Kruskal.
UNIDAD 2. Problemas NP-Completo y NP-Hard
Introducción a complejidad computacional: las clases P,
NP, NP-completo y NP-Hard. Problemas tratables e intratables.
Algoritmos heurísticos. Algoritmos de aproximación.
Esquemas de aproximación. Técnicas de diseño
para problemas NP-Hard: Greedy heurístico, Búsqueda
Local, Backtracking, Branch & Bound. Algoritmos heurísticos
y aproximados para el viajante de comercio. Problemas NP-Hard
en grafos: circuitos hamiltonianos, coloreo de grafos, recubrimiento
mínimo de aristas.
UNIDAD 3. String Matching
Definiciones básicas. Algoritmos de fuerza bruta. Algoritmo
de Rabin-Karp. String matching basado en autómata finito.
Algoritmo de Knuth-Morris-Pratt. Análisis comparativo de
los diferentes algoritmos.
UNIDAD
4. Geometría computacional
Definiciones
básicas. Propiedades de segmentos: producto cruzado y sus
aplicaciones. Algoritmos para determinar la intersección
de pares de segmentos. Problema del polígono convexo: algoritmo
de Graham y algoritmo de Jarvis. Algoritmos para encontrar los
puntos más cercanos.
|