Ciencias de la Computación (plan 1994) 2012-2

Optativas, Análisis de Algoritmos II

AnálisisdeAlgoritmos II

Semestre 2012-II

Profesora: María de Luz Gasca Soto

·Profundizar en el estudio de la Teoría de los Problemas NP-Completos, revisando los problemas más importantes, aplicando técnicas para identificar su clase de complejidad y revisando algoritmos de aproximación.

·Revisar la Teoría de los Algoritmos Paralelos, presentando diferentes arquitecturas y realizando versiones paralelas de algoritmos clásicos, enfatizando el análisis y diseño.

Temario

I. La Clase de los Problemas NP-Completos.

0. Introducción

1. Algoritmos Deterministicos yNo-Deterministicos.

2. Teoría de los Problemas NP-Completos.

3. Teorema de Cook

4. Técnicas y Ejemplos.

5. Algoritmos de Aproximación

II. Algoritmos Paralelos.

1.Introducción

2 . Técnicas Básicas

3. Listas y Àrboles

4. Búsquedas y Ordenamientos

5. Teoría de Gráficas

6. Geometría Computacional

7. Cadenas

Bibliografía

1.Chartran, G. And Oellermann, O.R. Applied and Algorithmic Graph Theory. Mc Graw Hill. USA, 1993.

2.Manber, Udi Introduction to Algorithms. A Creative Approach, Addison Wesley, USA,1989.

3.Cormen, T.H; L.C.E. & R.R.L.Introduction to Algorithms,Addison Wesley, USA,1990

4. Rawlins, G.J.E.Compared to what? An Introduction to the Analysis of Algorithms, Computer Science Press, USA, 1991

5.Neapolitan, R. and Naimipour, K. Foundations of Algorithms. D.C. Heath and Company, USA, 1996.

6.Garey, J. Computer and Intratability: A guide to the TheoryNP-Completness. Freeman, 1979

7.JáJá, J. An Introduction to Parallel Algorithms. Addison Wesley, USA,1992.

8.Sharp, J. A. An Introduction to Distributed and Parallel Algorithms.Oxford, 1987.

9.Chandí, K.M. & M.J.Parallel Program Design, A foundation. Addison Wesley, USA,1988.

10. Gibbons, A. Algorithmic Graph Theory, Cambridge University Press, USA, 1988.