1.1.3 - Teoría de Grafos y Algoritmia
Primer año
| Característica del Área Curricular | |||
|---|---|---|---|
| Plan | 2015 | ||
| Cuatrimestre | Primero | ||
| Hs. Cat. | 120 | ||
| Res. C.S. | 291/2015 | ||
Presentación
La materia se ubica en el primer cuatrimestre del primer año de la carrera. Esta actividad curricular introduce al alumnno en la resulución y sistematización de problemas discretos, computables y en la algoritmia necesaria para su solución.
Objetivos
La asignatura tiene como objetivo que el alumno aprenda los conocimientos básicos y fundamentales de la teoría de grafos y familiarización con las aplicaciones de los mismos en la informática. Esto implicará el conocer el desarrollo de algoritmos y también la capacidad de modelizar problemas reales y su resolución
Contenido temático
Unidad 1: Teoría de Grafos.
Introducción. Caminos y Ciclos. Ciclos Hamiltonianos y el problema del agente viajante. Un algoritmo para el camino más corto. Forma de representar Grafos. Isomorfismo de Grafos. Grafos Planos Instrucciones para el uso del diccionario.
Unidad 2: Arboles.
Introducción. Terminología y caracterización de los árboles. Arboles de Expansión. Arboles de Expansión Mínimos. Arboles Binarios. Recorrido de un Arbol. Arboles de decisión y algoritmos para minimizar el tiempo del ordenamiento. Isomorfismo de árboles. Arboles de Juegos.
Unidad 3: Modelo de Redes.
Definición y Ejemplos. Un algoritmo del flujo máximo. El teorema del flujo máximo y corte mínimo. Teoría de emparejamiento.
Bibliografía
Matemáticas Discreta y Combinatoria - R. Grimaldi - Adisson Wesley.
Matemáticas Discretas - R. Jhonsonbaugh - Prentice Hall
Correlatividades
- Previas: No posee
- Posteriores: