Diferencia entre revisiones de «Algoritmos y Estructuras de Datos III»

De Cuba-Wiki
 
(No se muestran 5 ediciones intermedias del mismo usuario)
Línea 37: Línea 37:


== Parciales ==
== Parciales ==
* [[Primeros Parciales (Algoritmos III) | Primeros Parciales]]
'''Primeros Parciales'''
* [[Segundos Parciales (Algoritmos III) | Segundos Parciales]]
* [[Primer Recuperatorio 23/07/2010 (Algoritmos III)|Recuperatorio del 23/07/2010]] ([[Media:Primer Recuperatorio 23-07-2010 (Algoritmos III).pdf|enunciado]])
* [[Primer Parcial 22/06/2010 (Algoritmos III)|Parcial del 22/06/2010]] ([[Media:Primer Parcial 1c2010 (Algoritmos III).pdf|enunciado]])
* [[Primer Parcial 15/12/2006 (Algoritmos III)|Parcial del 15/12/2006]]
* [[Primer Parcial 20/05/2006 (Algoritmos III)|Parcial del 20/05/2006]]
* [[Primer Parcial 21/10/2006 (Algoritmos III)|Parcial del 21/10/2006]]
* [[Primer Parcial 15/10/2005 (Algoritmos III)|Parcial del 15/10/2005]]
* [[Primer Parcial 22/07/2005 (Algoritmos III)|Parcial del 22/07/2005]]
* [[Primer Parcial 22/05/2004 (Algoritmos III)|Parcial del 22/05/2004]]
* [[Primer Parcial 17/12/2003 (Algoritmos III)|Parcial del 17/12/2003]]
* [[Primer Parcial 18/07/2003 (Algoritmos III)|Parcial del 18/07/2003]]
* [[Primer Parcial 18/05/2002 (Algoritmos III)|Parcial del 18/05/2002]]
 
'''Segundos Parciales'''
 
* [[Segundo Parcial 14/07/2010 (Algoritmos III)|Parcial del 14/07/2010]] ([[Media:Segundo Parcial 1c2010 (Algoritmos III).pdf|enunciado]])
* [[Segundo Parcial 08/02/2010 (Algoritmos III)|Parcial del 08/02/2010]]
* [[Segundo Parcial 21/12/2009 (Algoritmos III)|Parcial del 21/12/2009]]
* [[Recuperatorio Segundo 26/08/2009 (Algoritmos III)|Recuperatorio del 26/08/2009]]
* [[Segundo Parcial 06/12/2006 (Algoritmos III)|Parcial del 06/12/2006]]
* [[Segundo Parcial 06/12/2005 (Algoritmos III)|Parcial del 06/12/2005]]
* [[Segundo Parcial 08/08/2005 (Algoritmos III)|Parcial del 08/08/2005]]
* [[Segundo Parcial 15/07/2005 (Algoritmos III)|Parcial del 15/07/2005]]
* [[Segundo Parcial 17/12/2004 (Algoritmos III)|Parcial del 17/12/2004]]
* [[Segundo Parcial 09/08/2004 (Algoritmos III)|Parcial del 09/08/2004]]
* [[Segundo Parcial 14/07/2004 (Algoritmos III)|Parcial del 14/07/2004]]
* [[Segundo Parcial 10/12/2003 (Algoritmos III)|Parcial del 10/12/2003]]
* [[Segundo Parcial 04/08/2003 (Algoritmos III)|Parcial del 04/08/2003]]
* [[Segundo Parcial 11/07/2003 (Algoritmos III)|Parcial del 11/07/2003]]
* [[Segundo Parcial 10/07/2002 (Algoritmos III)|Parcial del 10/07/2002]]


== Finales ==
== Finales ==
* [[Final del 12/02/10 (Algoritmos III) | Final del 12/02/10]]: Tomado por Paula Zabala.
* [[Final del 12/02/10 (Algoritmos III) | Final del 12/02/10]]: Tomado por Paula Zabala.
* [[Final del 02/03/10 (Algoritmos III) | Final del 02/03/10]]: Tomado por Irene Loiseau.
* [[Final del 02/03/10 (Algoritmos III) | Final del 02/03/10]]: Tomado por Irene Loiseau.
* [[Final del 06/09/10 (Algoritmos III) | Final del 06/09/10]]: Tomado por Paula Zabala.


== Apuntes ==
== Apuntes ==
* [[Resumen (Algoritmos III) | Resumen]]: Temas solamente para el segundo parcial.
* [[Resumen algoritmos grafos (Algoritmos III) | Resumen de algoritmos típicos sobre grafos]].
* [[Resumen (Algoritmos III) | Resumen]]: Temas para el segundo parcial.


== Bibliografía Recomendada ==
== Bibliografía Recomendada ==

Revisión del 06:14 14 sep 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
Segundo Parcial

Parciales

Primeros Parciales

Segundos Parciales

Finales

Apuntes

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

Enlaces externos

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Algoritmos_y_Estructuras_de_Datos_III&oldid=8074»