Programa

UNIDAD 1. Grafos

Introducción a la teoría de grafos. Definiciones básicas. El TDA Grafo. Recorridos sobre grafos: BFS (Breadth-First-Search) y DFS (Depth-first-Search). Recorridos sobre grafos orientados: grafos acíclicos, ordenamiento topológico, componentes fuertemente conectadas. Recorridos sobre grafos no-orientados: componentes conexas y puntos de articulación. Problemas de caminos mínimos: Algoritmo de Dijkstra y Algoritmo de Floyd-Warshall. Árbol de recubrimiento de mínimo costo: Algoritmo de Prim y Algoritmo de Kruskal.

UNIDAD 2. Algoritmos heurísticos y de aproximación

Introducción a complejidad computacional: las clases P, NP, NP-completo, NP-Hard y PSPACE-completo. Problemas tratables e intratables. Ejemplos de problemas NPcompleto y NP-Hard en grafos. Ejemplos de problemas NP-completo, NP-Hard y PSPACE-completo en juegos. Eficiencia versus calidad. Caracterización de algoritmos heurísticos versus algoritmos de aproximación. Algoritmos heurísticos y aproximados para el viajante de comercio euclidiano. Algoritmo heurístico y aproximado para el problema de la mochila 0/1. Algoritmo heurístico y aproximado para el problema del
llenado de cajas.

UNIDAD 3. Técnicas de búsqueda exhaustiva
 
Introducción: Modelo de espacio del problema. Búsqueda por fuerza bruta: Búsqueda en ancho (Breath First Search - BFS), Búsqueda de costo uniforme, Búsqueda en profundidad (Depth First Search - DFS), Búsqueda en profundidad iterativa (Depth First Iterative Search - DFIS). Búsqueda herurística: Algoritmos A*.

Backtracking. Caracterización del tipo de problemas resolubles por búsqueda exhaustiva. Esquema algorítmico recursivo de backtracking. Ejemplo de resolución de problemas de dificultad NP representativos: mochila, suma de subconjuntos, viajante de comercio, recubrimiento mínimo de vértices de un grafo, recubrimiento mínimo de aristas en un grafo y circuito hamiltoniano. 
Backtracking y juegos. Búsqueda exhaustiva en árboles de juego y el principio de Minimax. Ejemplos de resolución de problemas representativos de juegos de tablero de 2 jugadores.

Ramificación y poda (Branch & Bound). Caracterización del tipo de problemas resolubles por ramificación y poda. Algoritmos de ramificación y poda para problemas NP clásicos: el viajante de comercio, problema de la mochila, asignación de tareas.

Búsqueda local. Caracterización de problemas resolubles por búsqueda local. Introducción a la resolución de problemas de dificultad NP por búsqueda local. Algoritmos de búsqueda local: k-opt para el problema del viajante; el problema de la mochila.

UNIDAD 4. Integración de técnicas de diseño de algoritmos

Integración de algoritmos greedy heurísticos, backtracking y búsqueda local en la resolución de problemas de dificultad NP clásicos.  Algoritmo greedy heurístico integrado con transformaciones de soluciones parciales para el coloreo de un grafo. Evaluación experimental de soluciones aproximadas.

UNIDAD 5. 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 6. 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. Ejemplificar problemas NP-Hard en geometría computacional.