Materia	Carrera	Plan	Año	Periodo
COMPUTABILIDAD Y COMPLEJIDAD	LIC. CS. COMP.	006/05	4	2c

Docente	Función	Cargo	Dedicación
LEGUIZAMON, MARIO GUILLERMO	Prof. Responsable	P.ADJ EXC	40 Hs
APOLLONI, JAVIER MARIANO	Responsable de Práctico	JTP EXC	40 Hs

El estudio de los modelos formales de computación es de gran importancia para el entendimiento de la idea intuitiva de algoritmo. A través de dichos modelos formales es posible el estudio de la teoría de computabilidad y complejidad, la cual nos permite dividir en clases de problemas decidibles y no decidibles y dentro de estos últimos, establecer jerarquías de clases de complejidad.

Esta asignatura tiene como objetivo introducir al alumno en los modelos formales de la Teoría de la Computación a los efectos de obtener un entendimiento y dominio adecuado de los fundamentos de la Ciencia de 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). Los contenidos de esta materia son una continuación de la materia Autómatas y Lenguajes en la cual fueron estudiados modelos más limitados del concepto de computación. El modelo principal de computación usado aquí es la Máquina de Turing y alguna de sus variantes.

Bolilla 1.
Algoritmo y Computabilidad. 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. 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 Linealemente Acotado.

Práctico de Aula 2:
Funciones Recursivas y Sistemas de Post.

Práctico de Aula 3:
Problemas Decidibles y No Decidibles

Práctico de Aula 4:
Complejidad Computacional

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

El alumno podrá optar por cursar la materia bajo régimen promocional o regular:


- Régimen para Alumnos Promocionales:

-- Aprobar 1 examen parcial (parte teórica y práctica) o sus respectivas recuperaciones.

-- Rendir un coloquio integrador al final del cuatrimestre.

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

Setenta por ciento (70%) es el porcentaje mínimo, de los ejercicios ha resolver, necesario para aprobar cada parcial.

Si el segundo punto no fuera cumplimentado, el alumno quedará automáticamente en condición de alumno regular, debiendo rendir el examen final. Si el primer punto no fuera cumplimentado, el alumno pasará a condición de libre.


- Régimen para Alumnos Regulares

-- Aprobar 1 examen parcial práctico o sus respectivas recuperaciones.


En ambos casos, régimen promocional o regular, al menos el 50%
de cada uno de los ejercicios involucrados en los parciales
deberán ser completados para considerar la aprobación de cada
parcial.


-- Régimen para Alumnos Libres

Para rendir en condición de libre, el alumno deberá:

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

-- 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] Hopcroft - Ullman. "Introduction to automata theory, languages and computation". Addison Wesley.
[2] Sipser, Michael. "Introduction to the Theory of computation". PWS Publishing Company.
[3] Denning - Dennis - Qualitz. "Machine, languages and computation". Prentice-Hall.
[4] Hopcroft - Ullman. "Formal languages and their relation to automata". Addison Wesley.
[5] Wood, Derick. "Theory of computation". John Wiley & Sons, Inc.
[6] Sudkamp, Thomas A. "Languages and Machines (An Introduction to the Theory of Computer Science)". Addison Wesley.
[7] Papadimitriou - Steiglitz. "Combinatorial Optimization (Algorithms and Complexity)". Prentice Hall.

[1] M. Davis - E. Weyuker. "Computability, Complexity, and Languages" (Fundamentals of Computer Science). Academic Press.
[2] H.Lewis - C. Papadimitriou. "Elements of the theory of computation". Prentice Hall.

El estudio de los modelos formales de computación son de gran importancia para el entendimiento de la idea intuitiva de algoritmo. A través de dichos modelos formales es posible el estudio de la teoría de computabilidad y complejidad, la cual nos permite dividir en clases de problemas no decidibles y decidibles y dentro de estos últimos, establecer jerarquías de clases de complejidad.

Esta asignatura tiene como objetivo introducir al alumno en los modelos formales de la Teoría de la Computación a los efectos de obtener un entendimiento y dominio adecuado de los fundamentos de la Ciencia de Computación en cuanto a lo que puede y no puede ser computado (computabilidad) y también las costo en tiempo y/o espacio (complejidad) de aquellos lenguajes (problemas) que pueden ser decididos (resueltos). Los contenidos de esta materia son una continuación de la materia Autómatas y Lenguajes en la cual fueron estudiados modelos más limitados del concepto de computación. El modelo principal de computación usado aquí es la Máquina de Turing y alguna de sus variantes.

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