Ministerio de Educación, Ciencia y Tecnología
Universidad Nacional de San Luis
FACULTAD DE CS. FISICO MAT. Y NAT.

ANEXO II

PROGRAMA DEL CURSO: COMPUTABILIDAD Y COMPLEJIDAD

DEPARTAMENTO DE:   INFORMATICA
AREA: Area V: Automatas y LenguajesAÑO: 2003 (Id: 2377)
Estado: En tramite de Aprobación

 

I - OFERTA ACADÉMICA

CARRERAS PARA LAS QUE SE OFRECE EL MISMO CURSO

PLAN DE ESTUDIOS
ORD. Nº

CRÉDITO HORARIO

   

SEM.

TOTAL

LIC. EN CIENCIAS DE LA COMPUTACION11/98684

II - EQUIPO DOCENTE

Funciones

Apellido y Nombre

Total hs en
este curso

Cargo y Dedic.

Carácter

Responsable

LEGUIZAMON, MARIO GUILLERMO20  hs.PROFESOR ADJUNTO EXC.Efectivo
Auxiliar de 1ºAPOLLONI, JAVIER MARIANO 20  hs.AYUDANTE DE 1RA. EXC. Interino

III - CARACTERÍSTICAS DEL CURSO

CREDITO HORARIO SEMANAL
MODALIDAD
REGIMEN

Teórico/

Práctico

Teóricas

Prácticas de

Aula

Práct. de lab/ camp/

Resid/ PIP, etc.

2c
 Hs.
3 Hs.
3 Hs.
 Hs.
Asignatura
Otro: 
Duración: 14 semanas
Período del 11/08/03 al 14/11/03

IV.- FUNDAMENTACION

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 no resolubles y resolubles 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. 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 resolubles y no resolubles. 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. Irresolubilidad del problema de correspondencia de Post. Problemas resolubles y no resolubles para lenguajes de tipo 0, 1, 2 y 3. Aplicación del problema de correspondencia de Post para 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. 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. Aplicación del concepto de
reducción.


VII. - PLAN DE TRABAJOS PRÁCTICOS

P1.
Máquina de Turing. Extensiones de Máquina de Turing.

P2.
Funciones Recursivas y Sistemas de Post.

P3.
Problemas Resolubles y No Resolubles

P4.
Complejidad Computacional

P5.
Problemas NP-Completos.


VIII - RÉGIMEN 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.a - BIBLIOGRAFÍA BÁSICA

- Hopcroft - Ullman.``Introduction to automata theory, languages
and computation\\\'\\\'. Addison Wesley.

- Sipser, Michael. ``Introduction to the Theory of Computation\\\'\\\'. PWS Publishing Company.

- Denning - Dennis - Qualitz.``Machine, languages and computation\\\'\\\'. Prentice-Hall.

- Hopcroft - Ullman.``Formal languages and their relation to
automata\\\'\\\'. Addison Wesley.

- Wood, Derick.``Theory of computatio\\\'\\\'. John Wiley & Sons, Inc.

- Sudkamp, Thomas A. ``Languages and Machines (An Introduction to
the Theory of Computer Science)\\\'\\\'. Addison Wesley.

- Papadimitriou - Steiglitz.``Combinatorial Optimization (Algorithms and Complexity)\\\'\\\'. Prentice Hall.



IX b - BIBLIOGRAFÍA COMPLEMENTARIA

- M. Davis - E. Weyuker. ``Computability, Complexity, and Languages´´ (Fundamentals of Computer Science). Academic Press.

- H.Lewis - C. Papadimitriou. ``Elements of the theory of computation´´. Prentice Hall.



COMPLEMENTO DE DIVULGACION


OBJETIVOS DEL CURSO

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.

 

 

PROGRAMA SINTETICO

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



Bolilla 2.
Problemas resolubles y no resolubles. 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.

 


IMPREVISTOS