Presentación del grupo 7014 - 2011-1.

Introducción al Análisis de Algoritmos I

Semestre 2011-I

Profesora: María de Luz Gasca S.

Ayudante: Luis D. Hernández S. Lab: Ernesto Carrillo E.

Objetivos Generales. En este curso se estudian los conceptos de complejidad: justificación, análisis y diseño de algoritmos. Para desarrollar estos temas se revisan algoritmos de búsqueda, ordenamiento y aquellos que involucran gráficas. Se discuten clases de complejidad, revisando con detalle la Clase de los Problemas NP-Completos.

T E M A R I O

I. Conceptos Básicos.

1. Problemas y Algoritmos.

2. Tipos de Problemas.

3. Complejidad.

II. Justificación de Algoritmos.

1. Inducción Matemática

2. Algoritmos Iterativos.

3. Algoritmos Recursivos.

III. Diseño de Algoritmos usando Inducción Matemática.

IV. Algoritmos que Involucran Secuencias

1. Árboles Binarios

2. Búsquedas

3. Ordenamientos.

V. Algoritmos que Involucran Gráficas.

1. Árboles Generadores.

2. Ruta más Corta.

3. Teoría de Redes.

VI. La Clase de los Problemas NP-Completos.

1. Introducción.

2. Algoritmos No-Deterministicos.

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

4. Técnicas para determinar problemas NP-Completos.

VII. Geometría Computacional [Opcional]

VIII. Algoritmos que involucran Números [Opcional]

B I B L I O G R A F Í A

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

Cormen, T.H; L.C.E. & R.R.L. Introduction to Algorithms, Mc Graw Hill, USA, 1990.

Flaming, B. Practical Algorithms in C++, Coriolis Group Books, USA, 1995.

Kingston, J.Algorithms and Data Structures: Design, Correctness, and Analysis. ,Addison Wesley, USA, 1990.

Manber, U. Introductionto Algorithms. A Creative Approach, Addison Wesley, USA, 1989.

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

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