Materia	Carrera	Plan	Año	Periodo
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	18/11	2021	2° cuatrimestre
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	006/05	2021	2° cuatrimestre
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	32/12	2021	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 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.

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 los/las 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, el estudiante puede regularizar (para luego rendir el examen final) o promocionar. Las condiciones en función a la modalidad de dictado mayormente no presencial y a la metodología propuesta en la que se desarrollará el curso, son las siguientes:

A. Régimen para Estudiantes Regulares
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 los docentes, y/o trabajos de investigación de temas o problemas particulares sobre los contenidos de la materia. También en caso de ser necesario se puede requerir la evaluación mediante examen parcial de uno o más temas con sus respectivas dos recuperaciones según lo establece la reglamentación actual.

Con la finalidad de realizar un trabajo colaborativo de comprensión, se efectuarán devoluciones evaluativas como parte del proceso de aprendizaje. Además, todas las evaluaciones pueden tener una instancia de defensa oral posterior a la entrega donde el/la estudiante exponga, explique y responda dudas o inquietudes de sus compañeros y/o docentes acerca del trabajo realizado en sus entregas.

Los/las estudiantes deben contar además con un porcentaje mínimo igual o superior al 60% de participación activa en todas las actividades sincrónicas y asíncronas propuestas por 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. Si cualquier punto no fuera cumplimentado implica que el estudiantes 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 un porcentaje de asistencia igual o superior al 80%.
2. Además el estudiante tendrá que desarrollar y aprobar un coloquio integrador oral o escrito que incluya el análisis y discusión de conceptos teóricos dados en el curso. Dicho coloquio podrá ser de forma virtual o presencial (en el caso que estén dadas las condiciones para ello).

La nota final de promoción se computará promediando, las notas obtenidas en las evaluaciones requeridas para la regularidad y la nota obtenida en el ítem 2 del punto B. En todas las evaluaciones, la nota obtenida por el alumno debe ser igual a 7 o superior, según lo establece la normativa vigente.

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.

D. El examen final puede ser oral y/o escrito.

[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.

De acuerdo al art. 2 de la resolución de la Facultad de Cs. Fco. Mat. y Nat. 26/21, el Calendario Académico establece que el segundo cuatrimestre sea de 14 semanas. A los efectos de que se impartan todos los contenidos y se respete el crédito horario establecido en el Plan de Estudios de la carrera para esta asignatura, se establece que se de cómo máximo 7 horas por semana distribuidas en teorías, prácticos de aula y consultas, hasta completar las 90 horas correspondientes al Crédito Horario Total de la asignatura.

Además, en función de la situación epidemiológica provocada por la pandemia COVID-19, los contenidos teóricos y prácticos de este programa se desarrollará mayoritariamente en modalidad no presencial, utilizando para tal fin diferentes herramientas virtuales, para el dictado de clases teóricas, clases de práctica, consultas, etc. aunque se prevén realizar clases de consulta y/o evaluaciones de manera presencial siempre que lo permita la situación epidemiológica.


Correo de contacto: javierma@unsl.edu.ar (Javier Apolloni)