Ver el código de «Algoritmos y Estructuras de Datos III»

'''Algoritmos y Estructuras de Datos III''' (antes llamada Matemática Discreta) pertenece al area de [[Programación (Area)|Programación]] y, según el [[Plan de la Carrera]] es una materia a ser cursada en [[Plan de la Carrera#Tercer año|Tercer año]]. Es correlativa de [[Algoritmos y Estructuras de Datos II]] y es necesaria para cursar [[Ingeniería del Software I]].

== Información general sobre la cursada ==
La cursada consiste de clases de laboratorio, teóricas y prácticas. Para aprobar la materia se deben rendir 2 exámenes parciales y 3 trabajos prácticos, y se puede promocionar si tanto en las notas de los parciales como en las de los TPS se obtiene 7 de promedio.

== Programa ==
1. '''Algoritmos'''

Definición de algoritmo. Modelos de computación: modelo RAM, Máquina de Turing. Complejidad, definición, complejidad en el peor caso, en el caso promedio. Algoritmos de tiempo polinomial y no polinomial. Límite inferior. Ejemplo: análisis de algoritmos de ordenamiento. Algoritmos recursivos. Análisis de la complejidad de algoritmos recursivos. Técnicas de diseño de algoritmos: dividir y conquistar, backtracking, algoritmos golosos, programación dinámica. 

2. '''Grafos'''

Definiciones básicas: adyacencia, grado de un nodo, isomorfismos, caminos, conexión, etc. Grafos bipartitos. Arboles: caracterización, árboles orientados, árbol generador. Enumeración. Grafos eulerianos y hamiltonianos. Planaridad. Coloreo. Número cromático. Matching, conjunto independiente, recubrimiento. Recubrimiento de aristas y vértices. 

3. '''Algoritmos en grafos y aplicaciones'''

Representación de un grafo en la computadora: matrices de incidencia y adyacencia, listas. Algoritmos de búsqueda en grafos: BFS, DFS, A*. Mínimo árbol generador, algoritmos de Prim y Kruskal. Arboles ordenados: códigos unívocamente descifrables. Algoritmos para detección de circuitos. Algoritmos para encontrar el camino mínimo en un grafo: Dijkstra, Ford, Dantzig. Planificación de procesos: PERT/CPM. Algoritmos heurísticos: ejemplos. Nociones de evaluación de heurísticas y de técnicas metaheurísticas. Algoritmos aproximados. Heurísticas para el problema del viajante de comercio. Algoritmos para detectar planaridad. Algoritmos para coloreo de grafos. Algoritmos para encontrar el flujo máximo en una red: Ford y Fulkerson. Matching: algoritmos para correspondencias máximas en grafos bipartitos. Otras aplicaciones. 

4. '''Problemas NP-completos'''

Problemas tratables e intratables. Problemas de decisión. P y NP. Maquinas de Turing no determinísticas. Problemas NP-completos. Relación entre P y NP. Problemas de grafos NP-completos: coloreo de grafos, grafos hamiltonianos, recubrimiento mínimo de las aristas, corte máximo, etc.

== Prácticas ==
; Primer Parcial :
* [[Práctica 1: Inducción (Algoritmos III) | Práctica 1: Inducción]]
* [[Práctica 2: Complejidad (Algoritmos III) | Práctica 2: Complejidad]]
* [[Práctica 3: Técnicas Algorítmicas (Algoritmos III) | Práctica 3: Técnicas Algorítmicas]]
* [[Práctica 4: Problemas de Grafos (Algoritmos III) | Práctica 4: Problemas de Grafos]]
* [[Práctica 5: Clases de Grafos (Algoritmos III) | Práctica 5: Clases de Grafos]]
* [[Práctica 6: Árboles (Algoritmos III) | Práctica 6: Árboles]]
* [[Práctica 7: Camino Mínimo (Algoritmos III) | Práctica 7: Camino Mínimo / PERT]]
; Segundo Parcial :
* [[Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III) | Práctica 8: Caminos Eulerianos y Hamiltonianos]]
* [[Práctica 9: Planaridad - Coloreo (Algoritmos III) | Práctica 9: Planaridad / Coloreo]]
* [[Práctica 10: Matching - Flujo Máximo (Algoritmos III) | Práctica 10: Matching / Flujo Máximo]]
* [[Práctica 11: Problemas P y NP (Algoritmos III) | Práctica 11: Problemas P y NP]]

== Parciales ==
* [[Primeros Parciales (Algoritmos III) | Primeros Parciales]]
* [[Segundos Parciales (Algoritmos III) | Segundos Parciales]]

== Apuntes ==
* [[Resumen (Algoritmos III) | Resumen]]: Temas solamente para el segundo parcial.

== Bibliografía Recomendada ==
* Cormen, ''Introduction to Algorithms''. [http://rapidshare.com/files/56683722/Cormen.rar Descargar]
* Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen [http://rapidshare.com/files/56920448/Gross_Yellen_Handbook_of_Graph_Theory__2004_.rar Descargar]

== Enlaces externos ==
*[http://www-2.dc.uba.ar/materias/aed3/homepage.html Pagina Oficial de la Materia]

[[Category:Materias]]
[[Category:Computación]]