Materia	Carrera	Plan	Año	Periodo
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	32/12	2019	2° cuatrimestre
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	006/05	2019	2° cuatrimestre

Docente	Función	Cargo	Dedicación
LEGUIZAMON, MARIO GUILLERMO	Prof. Responsable	SEC F EX	7 Hs
APOLLONI, JAVIER MARIANO	Prof. Co-Responsable	P.Adj Exc	40 Hs
VILLEGAS, MARIA PAULA	Auxiliar de Práctico	A.1ra Simp	10 Hs

El presente curso está destinado a alumnos avanzados de la Lic. en Ciencias de la Computación. Se profundiza el estudio de los modelos formales relacionados con la teoría de la computación iniciados en la materia Autómatas y Lenguajes y que son de gran importancia para el entendimiento de la idea intuitiva de algoritmo.
El alumno debe aprender y entender la forma en la que funcionan cada uno de dichos modelos formales para que a través de ellos sea posible el estudio de la teoría de computabilidad y complejidad. Y a través de dicha teoría, el alumno podrá comprender la división de la clases de problemas en decidibles y no decidibles y dentro de éstos, establecer jerarquías de clases de complejidad.

Al finalizar el curso se espera que el alumno sea capaz de entender el funcionamiento de los modelos formales de la Teoría de la Computación, que extienden el poder computacional de aquellos modelos más limitados estudiados en la materia Autómatas y Lenguajes. El modelo principal de computación usado aquí es la Máquina de Turing y alguna de sus variantes.
Además se espera que el alumno pueda comprender y dominar adecuadamente los fundamentos de la Ciencia de la Computación, en cuanto a lo que puede y no puede ser computado (computabilidad), y también el costo en tiempo y/o espacio (complejidad) de aquellos lenguajes (problemas) que pueden ser decididos (resueltos).

Bolilla 1.
Algoritmo y Computabilidad. Introducción a cardinales transfinitos. Conjuntos recursivos y recursivamente enumerables. Máquina de Turing. Máquina de Turing como reconocedor. Máquina de Turing como computadora de funciones enteras. Máquina de Turing No Determinística. MT con k-Cintas. Restricciones sobre una MT: Autómata Linealmente Acotado (ALA). Recursividad y lenguajes reconocidos por un ALA. Otros modelos de computación. Sistema de Post. Sistema de Post como generalización del concepto de gramática. Funciones recursivas primitivas y mu-recursivas. Capacidad de los lenguajes de programación. Equivalencia de los Modelos Formales. Tesis de Church.

Bolilla 2.
Problemas decidibles y no decidibles. Concepto de Reducción de un problema a otro. Propiedades de los lenguajes recursivos y recursivamente enumerables. Lenguajes no-recursivamente enumerables. Máquina de Turing Universal. Problema de Halting. Problema de correspondencia de Post. La no decibilidad del problema de correspondencia de Post. Problemas decidibles y no decidibles para lenguajes de tipo 0, 1, 2 y 3. Aplicación del problema de correspondencia de Post para problemas de decisión vinculados a gramáticas libres del contexto.

Bolilla 3.
Introducción al concepto de complejidad computacional. Complejidad temporal y espacial. Medida de complejidad temporal. Notación O-grande. Jerarquía de algunas complejidades temporales. Introducción a la complejidad espacial. Clases de problemas según su complejidad espacial. Relación entre las complejidades temporales y espaciales. Otras notaciones de complejidad. Análisis de Algoritmos.

Bolilla 4.
Problemas de decisión tratables e intratables. Clases P y NP. NP-completitud. Problema de Satisfactibilidad - Teorema de Cook. Problemas NP-completos y aplicación del concepto de reducción: 3-SAT, Clique, Cobertura de vértices, etc.

Práctico de Aula 1:
Máquina de Turing. Extensiones de Máquina de Turing. Autómata Linealmente Acotado.

Práctico de Aula 2:
Funciones Recursivas.

Práctico de Aula 3:
Sistema de Post.

Práctico de Aula 4:
Conjuntos Recursivos y Recursivamente Enumerables

Práctico de Aula 5:
Problemas Decidibles y No Decidibles.

Práctico de Aula 6:
Complejidad Temporal y Espacial.

Práctico de Aula 7:
Problemas NP-Completos.

Práctico de Investigación:
El legado dejado por Alan Turing

Se admiten alumnos que podrán cursar la materia bajo régimen de aprobación con examen final o por promoción sin examen final.

A. Régimen para Regularizar el curso:

1. Tener un mínimo de 60% de asistencia a las clases prácticas.

2. Entregar el 70% de los ejercicios de prácticos de aula solicitados.

3. Aprobar el práctico de investigación propuesto.

4. Aprobar 2 (dos) examen parcial de ejercicios prácticos o alguna de sus respectivas recuperaciones. Se otorgan 2 (dos) recuperaciones para cada examen parcial según lo establece la reglamentación vigente (Ord. 32/14-CS).

5. Si cualquier punto no fuese cumplimentado, implicará que el alumno pase a condición de libre.

Nota: El porcentaje mínimo de los ejercicios a resolver necesarios para aprobar el examen parcial y/o sus respectivas recuperaciones es de 70%. Además, al menos el 50% de cada uno de los ejercicios involucrados en el examen parcial y/o sus respectivas recuperaciones deberán ser completados para considerar su aprobación.


B. Régimen para Promoción sin Examen Final:

1. Ídem a lo requerido en el régimen para regularizar el curso, salvo que:
a. El alumno deberá asistir a un 80% de las clases teóricas y prácticas.

2. Aprobar con una nota mínima de 7 (siete) todas las evaluaciones establecidas en el curso, incluido el examen integrador oral y/o escrito al final del cuatrimestre.

3. La nota final se computará promediando las notas obtenidas en cada uno de los puntos mencionados previamente.


C. Régimen para rendir examen en condición de alumnos Libres:

1. Realizar un examen escrito de la parte práctica.

2. Habiendo aprobado el examen anterior, pasará a un examen oral o escrito, el cual tendrá las mismas características de un examen final para alumnos regulares.

[1] J.E. Hopcroft, J. D. Ullman and R. Motwani. "Introduction to automata theory, languages and computation". Tercera Edición. Addison Wesley Publishing Company (2006).
[2] J.E. Hopcroft and J. D. Ullman. "Introduction to automata theory, languages and computation". Addison Wesley Publishing Company (1979).
[3] M. Sipser. "Introduction to the Theory of computation". PWS Publishing Company (1997).
[4] P. J. Denning, J. B. Dennis and J. E. Qualitz. "Machine, languages and computation". Prentice-Hall (1978).
[5] J. Hopcroft and J. Ullman. "Formal languages and their relation to automata". Addison Wesley Publishing Company (1969).
[6] D. Wood. "Theory of computation". John Wiley & Sons, Inc. (1986)
[7] T. A. Sudkamp. "Languages and Machines: An Introduction to the Theory of Computer Science". Segunda Edición. Addison Wesley. (1997)
[8] C. H. Papadimitriou. "Computational Complexity". Addison Wesley Publishing Company (1994).
[9] C. H. Papadimitriou and K. Steiglitz. "Combinatorial Optimization: Algorithms and Complexity". Prentice Hall (1998)

[1] M. D. Davis and E. J. Weyuker. "Computability, Complexity, and Languages: Fundamentals of Computer Science". Academic Press Inc (1993).
[2] H. R. Lewis and C. H. Papadimitriou. "Elements of the theory of computation". Segunda Edición. Prentice Hall (1998).
[3] C. Teuscher. "Alan Turing: Life and Legacy of a Great Thinker". Springer Verlag (2004).
[4] A. Hodges. "Turing". Routledge (1999)

El objetivo principal de este curso es profundizar en los modelos formales de la Teoría de la Computación iniciados en la materia Autómatas y Lenguajes, y lograr un dominio de los fundamentos de la Ciencias de la Computación. De manera que al finalizar el curso, el alumno podrá ser capaz de:
-lograr un entendimiento de la idea intuitiva de algoritmo utilizando los modelos formales, principalmente la Máquina de Turing,
-determinar aquellos lenguajes (problemas) que pueden y no ser decididos (resueltos) dentro de la Teoría de la Computabilidad,
-utilizar el costo en tiempo y/o espacio para establecer dentro de la Teoría de la Complejidad una jerarquía de clases de complejidad de los lenguajes decidibles,
-determinar cuáles problemas de decisión son tratables y cuáles intratables.

Bolilla 1.
Repaso: Algoritmo y Computabilidad. Modelos formales de computación. Tesis de Church. Máquina de Turing (extensiones y restricciones). Sistema de Post. Funciones recursivas.

Bolilla 2.
Problemas decidibles y no decidibles. Concepto de Reducción. Máquina de Turing Universal. Problema de Halting. Problema de correspondencia de Post. Aplicación del problema de correspondencia de Post para gramáticas libres del contexto.

Bolilla 3.
Complejidad temporal y espacial. Medida de complejidad temporal. Notación O-grande. Jerarquía de algunas complejidades temporales. Clases de problemas según su complejidad espacial. Otras notaciones de complejidad. Análisis de Algoritmos.

Bolilla 4.
Problemas de decisión tratables e intratables. Clases P y NP. NP-completitud. Problemas NP-Completos. Aplicación del concepto de reducción.