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

Objetivo:

Comprender y aplicar la Complejidad Computacional, desde la teoría básica de la NP-completez hasta temas más avanzados.

Profundizar la formación del alumno en Computación Teórica, dotándolo de herramientas y conocimientos utiles para otras materias teóricas.

--- --- --- ---

Dinámica del Curso:

Habrá exposiciones, al menos dos, por parte de los estudiantes.

Se programarán algunos Algoritmos de Aproximación y Heurísticas

Se revisaran Articulos de Investigación del área

Habrá, al menos, una tarea por Tema

--- --- ---

Evaluación:

--- --- --- ---

Temario

I. Introducción y Conceptos Básicos

1. Motivación

2. Problemas, Algoritmos y Complejidad

3. Notación asintótica y Modelos de Cómputo.

II. La Teoría de los Problemas NP-Completos

1. Máquinas de Turing y la Clase P

2. La Clase NP

3. Transformaciones Polinomiales

4. Definición de NP-Completez

5. El Teorema de Cook

6. Jerarquía de Complejidad

III. Demostraciones de Problemas NP-Completos

A. Problemas Básicos

1. 3-SAT; Clan.

2. Cubierta de Vértices; Conjunto Dominante

3. 3-coloración

4. Circuito Hamiltoniano

5. Partición

B. Técnicas

1. Restricción

2. Reemplazo

3. Diseño de componentes

IV. Temas Selectos

1. Algoritmos de Aproximación

2. Heurísticas

3. Aplicaciones

Bibliografía

Goldreich, O. P, NP, and NP-Completeness. Cambridge, University Press, USA, 2010.

Papadimimitriou, Ch. Computational Complexity, Addison Wesley, USA, 1993.

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

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

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

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