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

** por motivo del paro, el examen será el 20 de octubre a las 10am

El Examen consta de dos partes: una teórica (examen) y otra práctica (dos programas).

Usaremos la Plataforma Classroom para contactarnos; ahí pondrmos el examen y las descripciones de los programas.

Parte Teórica:

Consta de un examen sobre los temas del curso. El alumno tendrá 48 horas para entregar el examen

Parte Práctica:

Consiste en realizar dos programas, los cuales se dejaran una vez que entregue el examen teorico.

El alumno tendrá una semana para entregar los programas

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

Fecha del Examen Teórico: Miércoles 19 de octubre a las 10am

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

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

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

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

* Goldreich, O. Computational Complexity. A Conceptual Perspective. Cambridge, University Press, USA, 2008

* Ausielllo, G. Crescenzi, P. Kann, V. Marchetti-Spaccamela, A. Protasi, M. Complexity and Aproximation. Combinatorial Optimization Problems and their Approximability Properties. Springer, 1999.

Du, Ding-Zhu & Ko, Ker-I. Theory of Computational Complexity. Wiley & Son Inc. 2014

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

Papadimitriou, Ch.H & Steiglitz, K. Combinatorial Optimization. Algorithms and Complexity. Dover Pu. Inc, 1998

Even, S. Graph Algorithms. Technion Institute, Computer Science Press, 1979

Gibbons, A.M. Algorithmic Graph Theory. Cambridge University Press, 1985

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, Addison Wesley, USA, 1999

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

Neapolitan, R. & Naimipour K. Fundations of Algorithms. 2nd Ed. Jones and Bartlett Pu, 1997

Kleingerg, J. & Tardos, E. Algorithm Design. Addison Wesley, 2005