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

Optativas, Complejidad Computacional

Objetivos:

Comprender y aplicar la Complejidad Computacional, desde la teoría básica de NP-Completez, hasta temas más avanzados, contribuyendo así a profundizar la formación del alumno en computación teórica y dotándolo de herramientas y conocimientos que le serán de utilidad tanto para otras materias teóricas como para el resto de su formación.

Seriación obligatoria antecedente: Probabilidad I ; Autómatas y Lenguajes Formales; Lógica Computacional

Evaluación:

- 4 Exámenes parciales: 80% ó 1 examen final: 80%

• Es posible el realizar a lo más dos reposiciones de los parciales elegidos por el alumno en lugar del examen final.

- 4 Tareas: 20%

• Las tareas se pueden entregar en equipos de hasta cinco (5) estudiantes. •
• La fecha de entrega de cada tarea es de aproximadamente una semana y media antes cada examen.
• El objetivo principal de las tareas es el preparar al alumno para los exámenes parciales

Fechas tentativas de examen.

1. 1er. parcial: 5 de febrero del 2019.
2. 2do. parcial: 26 de marzo del 2019.
3. 3er. parcial: 30 de abril del 2019.
4. 4to. parcial: 21 de mayo del 2019.

La calificación de los exámenes y tareas esta a cargo del ayudante del curso.

Temario

I. Introducción y conceptos básicos Contenido:

Contenido:

I.1 Motivación para estudiar complejidad computacional.

I.2 Problemas, algoritmos y complejidad.

I.3 Notación asintótica, codificación y modelos de cómputo.

II. La teoría de NP-Completez

Contenido:

II.1 Máquinas de Turing y la clase P.

II.2 La clase NP.

II.3 Relación P-NP y transformaciones polinomiales.

II.4 Definición de NP-Completez.

II.5 Teorema de Cook.

II.6 Demostraciones de problemas NP-completos.

III. Demostraciones de problemas NP-completos

Contenido:

III.1 Problemas básicos: 3SAT, apareamientos, cubierta de vértices, circuito hamiltoniano, clan y partición.

III.2 Técnicas: restricción, remplazo local y diseño de componentes.

IV. Tema Selecto Elegir:

IV.1 Problemas no computables y máquinas de Turing universales

IV.3 Enfrentando problemas NP-Completos: aproximación, heurísticas, etc.

IV.4 Otras clases de complejidad.

IV.5 Otros modelos de cómputo: DNA, paralelos, distribuidos, cuánticos, etc.

Bibliografía

[1] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

[2] MichaelGareyandDavidJohnson. ComputersandIntractability-aguidetothetheoryofNP-Completeness. PWS Publishing Company, 1997.

[3] Donald E. Knuth. The Art of Computer Programming. Addison-Wesley, Reading, MA, USA, 1973–1981. Three volumes.

[4] Dexter Kozen. Theory of Computation. Texts in Computer Science. Springer, 2006.