Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico-Matemáticas y Naturales
Departamento: Informatica
Área: Area V: Automatas y Lenguajes
(Programa del año 2006)
(Programa en trámite de aprobación)
(Programa presentado el 25/09/2006 16:53:07)
I - Oferta Académica
Materia Carrera Plan Año Periodo
COMPUTABILIDAD Y COMPLEJIDAD LIC. CS. COMP. 006/05 4 2c
II - Equipo Docente
Docente Función Cargo Dedicación
LEGUIZAMON, MARIO GUILLERMO Prof. Responsable P.ADJ EXC 40 Hs
APOLLONI, JAVIER MARIANO Responsable de Práctico P.ADJ EXC 40 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total C - Teoria con prácticas de aula Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
 Hs. 3 Hs. 3 Hs.  Hs. 6 Hs. 2 Cuatrimestre 07/08/2006 10/11/2006 14 84
IV - Fundamentación
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.
V - Objetivos
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.
VI - Contenidos
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, 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.

VII - Plan de Trabajos Prácticos
P1.
Máquina de Turing. Extensiones de Máquina de Turing. Autómata Linealemente Acotado.

P2.
Funciones Recursivas y Sistemas de Post.

P3.
Problemas Decidibles y No Decidibles

P4.
Complejidad Computacional

P5.
Problemas NP-Completos.
VIII - Regimen de Aprobación
El alumno podrá optar por cursar la materia bajo régimen promocional o regular:


- Régimen para Alumnos Promocionales:

-- Aprobar 2 examenes parciales (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 2 examenes parciales prácticos 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.



IX - Bibliografía Básica
[1] - Hopcroft - Ullman.``Introduction to automata theory, languages
[2] and computation\\\\\\\'\\\\\\\'. Addison Wesley.
[3] - Sipser, Michael. ``Introduction to the Theory of Computation\\\\\\\'\\\\\\\'. PWS Publishing Company.
[4] - Denning - Dennis - Qualitz.``Machine, languages and computation\\\\\\\'\\\\\\\'. Prentice-Hall.
[5] - Hopcroft - Ullman.``Formal languages and their relation to
[6] automata\\\\\\\'\\\\\\\'. Addison Wesley.
[7] - Wood, Derick.``Theory of computatio\\\\\\\'\\\\\\\'. John Wiley & Sons, Inc.
[8] - Sudkamp, Thomas A. ``Languages and Machines (An Introduction to
[9] the Theory of Computer Science)\\\\\\\'\\\\\\\'. Addison Wesley.
[10] - Papadimitriou - Steiglitz.``Combinatorial Optimization (Algorithms and Complexity)\\\\\\\'\\\\\\\'. Prentice Hall.
X - Bibliografia Complementaria
[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.
XI - Resumen de Objetivos
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 resolubles y resolubles 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.
XII - Resumen del Programa
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.
XIII - Imprevistos