Algoritmos y Estructuras de Datos 3

Programa

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.

Grafos

• Definiciones básicas
  • Adyacencia
  • Grado de un nodo
  • Isomorfismos
  • Caminos
  • Conexión
  • Etc.
• Grafos bipartitos.
• Arboles
  • Caracterización
  • Arboles orientados
  • Arbol generador
• Enumeración.
• Grafos eulerianos y hamiltonianos.
• Planaridad.
• Coloreo.
• Número cromático.
• Matching, conjunto independiente, recubrimiento.
• Recubrimiento de aristas y vértices.

Algoritmos en grafos y aplicaciones

• Representación de un grafo en la computadora
  • Matrices de incidencia
  • Matrices de 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.

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.

Bibliografía

Marcas:

• (a) están en la biblioteca central (Pabellón II)
• (b) están en la Hemeroteca del Dpto de Matemática (segundo piso del Pabellón I)
• (c) están en la Infoteca del Departamento de Computación

Bibliografía básica

1. Brassard G., Bratley P., "Fundamental of Algorithmics",Prentice Hall,1996. (c)
2. Cormen, T.,Leiserson, C.,Rivest,R.,Stein, C.,"Introduction to Algorithms", The MIT Press, McGraw-Hill,2001.
3. Garey M.R. and Johnson D.S., "Computers and intractability: a guide to the theory of NP- Completeness", W. Freeman and Co., 1979. (a),(c)
4. Gross J., and Yellen J. , "Graph theory and its applications", CRC, 1999, (c)
5. Harary F., "Graph theory", Addison-Wesley, 1969, (a) (hay una reedición de 1996)

Bibliografía de consulta

6. -- Aho A.,Hopcroft J.E. and Ullman J.D., The design and analysis of computer algorithms, Addison-Wesley, 1974. (a),(c) (hay edición en castellano)
7. Aho A.,Hopcroft J.E. and Ullman J.D., Data Structures and algorithms,Addison-Wesley, 1983. (a),(c) (hay edición en castellano)
8. Aho A.,Hopcroft J.E. and Ullman J.D., Foundations of Computer Science, Computer Science Press, 1995.
9. Albertson M.O., Hutchinson J.P., Discrete Mathematics with Algorithms, Wiley, 1988.(a),(c) * 10. Baum G., Complejidad, Kapeluz (I EBAI), 1986. (c)
10. Berge C.,The theory of graphs and applications, Wiley, 1958. (a)
11. Berge C., Graphs, North-Holland, 1985. (b)
12. Bigs N.L., Lloyd E.K., Wilson R.J., Graph theory: 1736-1936, Oxford University Press, 1976.
13. Bondy J.A. and Murty U.S.R.,Graph theory with applications, Macmillan Press, 1976.
14. Campello R., Maculan N.,Algoritmos e heurísticas, Editorial da Universidade Federal Fluminense, 1994.(a)(c)
15. Deo N., Graph theory with applications to engineering and computer science, Prentice-Hall, 1974
16. Even S., Graph algorithms, Computer Science Press, 1979.
17. Ford L.R. and Fulkerson D.R., Flows in Networks, Princeton University Press, 1962. (b)
18. Gondran M. and Minoux M., Graphs and Algorithms, John Wiley and Sons, 1984.
19. Horowitz E. and Sahni S., Fundamentals of Computer Algorithms, Computer Science Press, 1978.
20. Knuth D.E., The art of computer programming, Addison-Wesley, 1973. (a),(c)
21. Mc Hugh James, Algorithmic Graph Theory, Prentice-Hall International, 1990.
22. Papadimitriou C., Computational Complexity, Addison Wesley, 1995.
23. Rayward-Smith V.,Osman I.,Reeves C.,Smith G., Modern heuristic search methods,Wiley, 1996
24. Reeves C., Modern heurístics techniques for combinatorial problems, Blackwell,1993.
25. Segdewick, Algorithms in C++, Addison- Wesley, 1998. (a)(c)
26. Sominsky I.S, Método de Inducción Matemática, Lecciones populares de matemática, Editorial MIR, Moscú, 1985.
27. Syslo M.,Deo N.,Kowaljk J., Discrete Optimization Algorithms, Prentice Hall,1983.
28. Swamy M.N.S. and Thulasiraman D., Graphs, networks and algorithms, Wiley & Sons, 1981.
29. Szwarcfiter J.L.: Grafos e algoritmos computacionais, Editora Campus, Rio de Janeiro, 1987.
30. Tarjan R., Data structures and network algorithms, Society for Industrial and Applied Mathematics,1993 (a)
31. Tucker A., Applied Combinatorics, John Wiley and Sons, 1984. (c)

Otra Bibliografía

33. R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
34. David Joyner, Minh Van Nguyen, David Phillips, Algorithmic Graph Theory and Sage, 2013 May 10.