Materia	Carrera	Plan	Año	Periodo
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	18/11	2022	2° cuatrimestre
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	32/12	2022	2° cuatrimestre

Docente	Función	Cargo	Dedicación
LEGUIZAMON, MARIO GUILLERMO	Prof. Responsable	P.Asoc Exc	40 Hs
APOLLONI, JAVIER MARIANO	Prof. Co-Responsable	P.Adj Exc	40 Hs
VILLEGAS, MARIA PAULA	Auxiliar de Práctico	A.1ra Semi	20 Hs

El presente curso está destinado a estudiantes 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.
La/el estudiante 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, la/el estudiante 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 la/el estudiante 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 la/el estudiante 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 modelos formales de cómputo.
Introducción. Idea intuitiva de Algoritmo. Modelos formales de cómputo: Máquina de Turing. Máquina de Turing como reconocedor. Máquina de Turing como computadora de funciones. Variantes de la Máquina de Turing: extensiones sobre las Máquinas de Turing (Máquina de Turing No Determinística. Máquina de Turing con k-cintas) y restricciones sobre la Máquina de Turing (Autómata Linealmente Acotado).

Bolilla 2. Otros modelos formales de cómputo: Funciones computables.
Funciones recursivas primitivas. Funciones parcialmente computables: Funciones mu-recursivas (operador de minimalización).

Bolilla 3. Otros modelos formales de cómputo: Lenguajes estructurado a frases.
Sistema de Post. Sistema de Post como generalización del concepto de gramática. Capacidad de los lenguajes de programación. Equivalencia de los Modelos Formales. Tesis de Church-Turing.

Bolilla 4. Teoría de la Computabilidad: Lenguajes recursivos y recursivamente enumerables
Formalización del concepto de problema. Relación entre problema y lenguaje. Conjuntos/lenguajes recursivos y recursivamente enumerables. Introducción a cardinales transfinitos. Propiedades de los lenguajes recursivos y recursivamente enumerables. Recursividad de los lenguajes reconocidos por un Autómata Linealmente Acotado.

Bolilla 5. Teoría de la computabilidad: Decibilidad
Problemas decidibles y no decidibles para lenguajes tipo 0, 1, 2 y 3. Lenguajes no recursivamente enumerables. Lenguaje Universal: Máquina de Turing Universal. Problema de Detención (Halting). Reducibilidad: Concepto de Reducción de un problema a otro. Problema de Correspondencia de Post y la no decibilidad del Problema de Correspondencia de Post. Aplicación del Problema de Correspondencia de Post a problemas de decisión vinculados a gramáticas libres del contexto.

Bolilla 6. Teoría de la complejidad: Complejidad temporal y espacial
Introducción al concepto de complejidad computacional. Complejidad temporal y espacial en Máquina de Turing. Medida de complejidad temporal. Notación O-grande y jerarquía de complejidades temporales. Clases de complejidad. Relación entre las complejidades temporales y espaciales. Reducción acotada en el tiempo y espacio.

Bolilla 7. Teoría de la Complejidad: Problemas de decisión tratables e intratables
Clases P y NP. NP-completitud. Problema de Satisfactibilidad. Problemas NP-completos. Ejemplos de Problemas NP-Completos: 3-SAT, Clique, Cobertura de vértices, etc.

Práctico de Aula 1:
Máquina de Turing estándar. Extensiones y simplificaciones a Máquina de Turing estándar.

Práctico de Aula 2:
Funciones Recursivas.

Práctico de Aula 3:
Sistema de Post.

Práctico de Aula 4:
Lenguajes 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.

La propuesta de trabajo, en lo que respecta al régimen de aprobación, está basada en la evaluación continua o formativa, con el objetivo de relacionar la información sobre la evolución del proceso de aprendizaje de las/los estudiantes con las características de la acción didáctica, a medida que se desarrollan y progresan las actividades de enseñanza y aprendizaje. En este sentido, la/el estudiante puede regularizar (para luego rendir el examen final) o promocionar. Las condiciones y la metodología propuesta en la que se desarrollará el curso, son las siguientes:

A. Régimen para Estudiantes Regulares
* Aprobar 1 examen parcial práctico o alguna de sus dos respectivas recuperaciones, tal como lo establece la reglamentación vigente.
* Entregar, en tiempo y forma, y aprobar el 100% de las evaluaciones periódicas propuestas por la cátedra, las cuales consistirán en ejercicios de los prácticos de aula, y/o ejercicios prácticos extras propuestos por las/los docentes, y/o trabajos de investigación de temas o problemas particulares sobre los contenidos de la materia. Como parte del proceso de aprendizaje y con la finalidad de realizar un trabajo colaborativo de comprensión, se efectuarán devoluciones evaluativas de las entregas. Todas las evaluaciones pueden tener una instancia de defensa oral posterior a la entrega donde la/el estudiante exponga, explique y responda dudas o inquietudes de sus compañeras o compañeros y/o docentes acerca del trabajo realizado en sus entregas.
* Las/los estudiantes deben contar además con un porcentaje mínimo igual o superior al 60% de asistencia y participación activa en las clases prácticas y/o actividades prácticas propuestas por las/los docentes durante el cursado de la materia.

Nota:
1. Las evaluaciones se aprueban con un porcentaje mínimo de setenta por ciento (70%).
2. El examen parcial se aprueba con un porcentaje mínimo total de setenta por ciento (70%) de los ejercicios a resolver. Además se debe desarrollar correctamente al menos el 50% de cada uno de los ejercicios involucrados en el parcial para considerar su aprobación.
3. Si cualquier punto no fuera cumplimentado implica que la/el estudiante pase a condición de libre.

B. Régimen para Estudiantes Promocionales
1. Ídem a lo requerido para estudiantes regulares excepto que se debe alcanzar el porcentaje mínimo de 80% de asistencia a las clases teóricas y prácticas tal cual lo solicitado por la reglamentación vigente.
2. La/el estudiante tendrá que rendir y aprobar un coloquio integrador oral o escrito donde demuestre la integración, el análisis y discusión de los conceptos teóricos dados en el curso.

**La nota final de promoción se computará promediando las notas obtenidas en el examen parcial y en las demás evaluaciones requeridas para la regularidad y la nota obtenida en el ítem 2 del punto B. Cada instancia de evaluación (examenes parciales, evaluaciones períodicas, trabajos de laboratorio, examen integrador de promoción, etc.) se aprueba con una nota igual a 7 o superior, según lo establece la normativa vigente.

C. Régimen para rendir examen en condición de estudiantes 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 estudiantes regulares.

D. Examen final:
1. La/el estudiante en condición de regular tendrá que rendir y aprobar el examen final oral o escrito donde demuestre la integración, el análisis y discusión de los conceptos teóricos dados en el curso.

[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, la/el estudiante 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.
Algoritmo. Modelos formales de computación: Máquina de Turing (extensiones y restricciones).

Bolilla 2.
Funciones recursivas.

Bolilla 3.
Sistema de Post. Tesis de Church.

Bolilla 4.
Teoría de la Computabilidad. Relación entre problemas y lenguajes. Conjuntos/lenguajes recursivos y recursivamente enumerables.

Bolilla 5.
Problemas decidibles y no decidibles. Concepto de Reducción. Lenguaje Universal (Máquina de Turing Universal). Problema de Halting. Problema de Correspondencia de Post (y su vínculo con problemas relacionados a gramáticas libres del contexto).

Bolilla 6.
Teoría de la Complejidad. Complejidad temporal y espacial en Máquina de Turing. Medida de complejidad temporal. Notación O-grande y jerarquía de complejidades temporales. Clases complejidades. Reducción.

Bolilla 7.
Problemas de decisión tratables e intratables. Clases P y NP. NP-completitud. Ejemplo de problemas NP-Completos.

Correo de contacto: apojavi@gmail.com (Javier Apolloni)