Ciencias de la Computación (plan 1994) 2014-1

Optativas, Complejidad Computacional

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.

Índice

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: Telefonía Celular

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