Diferencia entre revisiones de «Algoritmos y Estructuras de Datos III»
Sin resumen de edición |
|||
(No se muestran 3 ediciones intermedias del mismo usuario) | |||
Línea 1: | Línea 1: | ||
'''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 | '''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 de Software I]]. | ||
== Información general sobre la cursada == | == Información general sobre la cursada == | ||
Línea 39: | Línea 39: | ||
* [[Primeros Parciales (Algoritmos III) | Primeros Parciales]] | * [[Primeros Parciales (Algoritmos III) | Primeros Parciales]] | ||
* [[Segundos Parciales (Algoritmos III) | Segundos Parciales]] | * [[Segundos Parciales (Algoritmos III) | Segundos Parciales]] | ||
== Finales == | |||
* [[Final 12-02-10 - Paula Zabala (Algoritmos III) | Final 12-02-10 - Paula Zabala]] | |||
== Apuntes == | == Apuntes == | ||
Línea 46: | Línea 49: | ||
* Cormen, ''Introduction to Algorithms''. [http://rapidshare.com/files/56683722/Cormen.rar Descargar] | * 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] | * Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen [http://rapidshare.com/files/56920448/Gross_Yellen_Handbook_of_Graph_Theory__2004_.rar Descargar] | ||
* Graph theory and its applications, Gross J., and Yellen J.[http://books.google.com.ar/books?id=unEloQ_sYmkC&lpg=PP1&dq=gross%20yellen%20graph&pg=PP1#v=onepage&q=&f=false Google Books] | |||
== Enlaces externos == | == Enlaces externos == | ||
Línea 52: | Línea 56: | ||
[[Category:Materias]] | [[Category:Materias]] | ||
[[Category:Computación]] | [[Category:Computación]] | ||
[[Category:Programación]] |
Revisión del 02:55 23 feb 2010
Algoritmos y Estructuras de Datos III (antes llamada Matemática Discreta) pertenece al area de Programación y, según el Plan de la Carrera es una materia a ser cursada en Tercer año. Es correlativa de Algoritmos y Estructuras de Datos II y es necesaria para cursar Ingeniería de 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
- Práctica 2: Complejidad
- Práctica 3: Técnicas Algorítmicas
- Práctica 4: Problemas de Grafos
- Práctica 5: Clases de Grafos
- Práctica 6: Árboles
- Práctica 7: Camino Mínimo / PERT
- Segundo Parcial
- Práctica 8: Caminos Eulerianos y Hamiltonianos
- Práctica 9: Planaridad / Coloreo
- Práctica 10: Matching / Flujo Máximo
- Práctica 11: Problemas P y NP
Parciales
Finales
Apuntes
- Resumen: Temas solamente para el segundo parcial.
Bibliografía Recomendada
- Cormen, Introduction to Algorithms. Descargar
- Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen Descargar
- Graph theory and its applications, Gross J., and Yellen J.Google Books