MATE 8015. Algoritmos Discretos

Código MATE 8015
Titulo Algoritmos Discretos
Creditos 3
Horas 3 por semana
Prerrequisitos MATE 5CCC (Teoría de Grafos)
Descripción Algoritmos eficientes se obtienen para resolver problemas en matemáticas discretas. Diferentes algoritmos y aplicaciones a diversos problemas se estudian a través de asignaciones de lecturas especiales, presentaciones en conferencia y discusiones grupales. Estrategia de ramificar y acotar. Principio de programación dinámica. Caminos óptimos en grafos. Árboles expansivos óptimos en grafos. 2-coloreo y ciclos impares en un grafo. Búsqueda primero-profundidad en un grafo y sus aplicaciones. Propiedades de un árbol búsqueda primero-profundidad. Algoritmos de descomposición de grafos. Algoritmos de montaje de grafos. Algoritmos de planaridad de grafos. Problemas de Euler. Problemas Hamiltonianos. Algunos problemas de empaque y de cubrimiento para grafos. Problemas métricos en grafos. Algoritmos de transformación de conjuntos. Árboles de búsqueda de diferentes tipos. Algunos algoritmos de ordenamiento. Ideas principales de la teoría-NP (la teoría de complejidad de problemas).
Información adicional