Presentación

La problemática abordada por esta materia se relaciona con el área de competencia 5, relativa al desarrollo de programas.

La resolución automática de un problema obliga a analizar previamente y en forma exhaustiva las diferentes situaciones y condiciones que puede presentar.

La forma que adopta la solución es un algoritmo que computa la función pretendida y que, por su complejidad, debe ser verificado metódicamente para asegurar su corrección y validez.

El instrumento utilizado para programar es un lenguaje que tiene características de los lenguajes formales y que, de acuerdo al tipo de problema que intenta representar y las estrategias en que se basa, tiene estructuras, reglas, operaciones y objetos propios.

Programar es una actividad compleja que combina procesos teóricos (propios de la matemática), de abstracción o experimentales (típicamente de la ciencia) y de diseño (de la ingeniería).

Objetivos

Al finalizar esta materia los estudiantes estarán en condiciones de demostrar un desempeño competente resolviendo las dificultades con responsabilidad y con autonomía en actividades como:

• Encarar estrategias de resolución de problemas
• Modelizar situaciones y problemáticas para luego abordar y sistematizar soluciones.

Los estudiantes demostrarán sus competencias en contextos laborales caracterizados por:

• Algoritmos válidos y correctos con la justificación de las decisiones adoptadas y documentación de los procesos de depuración efectuados.
• Informes claros y legibles del proceso de desarrollo de los programas.
• Cuadros comparativos, con análisis y explicación de las diferencias.

Contenidos

Unidad 1: Teoría de Grafos.

Inducción matemática. Introducción. Caminos y Ciclos. Subgrafos, complementos. Recorridos y circuitos Eulerianos. Ciclos Hamiltonianos y el problema del agente viajante. Coloración de Grafos. Un algoritmo para el camino más corto: Dijkstra. Forma de representar Grafos. Isomorfismo de Grafos. Grafos Planos Instrucciones para el uso del diccionario.

Unidad 2: Arboles.

Definiciones, propiedades y ejemplos. Terminología y caracterización de los árboles. Árboles recubridores. Arboles recubridores y minimales: Los algoritmos de Kruskal y Prim. Árboles binarios. Recorridos de árboles. Árboles de decisión y algoritmos para minimizar el tiempo del ordenamiento. Isomorfismo de árboles. Árboles de Juegos. Componentes biconexas y puntos de articulación

Unidad 3: Modelo de Redes.

Definición y Ejemplos. Algoritmo del flujo máximo. El método Ford-Fulkerson con redes residuales. El teorema del flujo máximo y corte mínimo. Acoplamiento.

Bibliografía

R. Johnsonbaugh, Matemáticas discretas, 4ta Ed., Prentice Hall
R. Grimaldi, Matemáticas discretas y combinatorias. Tercera Edición, Mc Graw Hill.
K. Ross C. Wright, Matemáticas Discretas, Prentice Hall, 1990
Cormen, Leiserson, Rivest, Stein Introduction to Algorithms. Segunda Edición.

Recursos Web

Comunidades - UNR