Universidad de Oviedo Oferta formativa Página oficial  
   Uniovi Directo   Alumnos   Profesores, PDI   P.A.S.   Oferta Formativa   
English

Información de la asignatura
Curso académico: 2017/2018

Horario Calendario de exámenes

Código:
936
Asignatura:
TEORIA DE COMPUTABILIDAD
Plan de estudios:
Centro:
Tipo:
Optativa
Créditos totales:
9
Teóricos:
6
Prácticos:
3
Ciclo:
Curso:
Período:
ANUAL
Profesores:
Objetivos:
1.- Dominar las clases de lenguajes formales: ámbito, relaciones de contenidos y sus respectivos dispositivos reconocedores / generadores (jerarquía de Chomsky).
2.- Comprender el concepto de algoritmo y conocer técnicas para tratar de averiguar lo que es y lo que no es algorítmico.
3.- Entender la filosofía subyacente en el concepto de Modelo de Computación, así como en la Tesis de Church; y la equivalencia entre los diferentes modelos.
4.- Saber utilizar de forma adecuada los resultados de Universalidad, Parametrización y Recursión.
5.- Comprender la importancia de la Complejidad Algorítmica en las tareas de comprobación teórica de eficiencia y comparación de algoritmos.

En cuanto a objetivos relacionados con competencias transversales, enunciamos los siguientes:
1.- Capacidad de expresión oral en público.
2.- Capacidad de análisis y síntesis.
3.- Capacidad de resolución de problemas.
4.- Capacidad de intuición.
Contenido:
TEMA 1: Autómatas Finitos y Lenguajes Regulares
Autómatas Finitos Determinísticos, No Determinísticos, con lambda-movimientos. Expresiones Regulares. Minimización de Autómatas. Propiedades de los Lenguajes Regulares.
TEMA 2: Gramáticas y Lenguajes Libres de Contexto.
Gramáticas Libres de Contexto. Derivaciones y Arboles de Derivación. Ambigüedad. Simplificación de gramáticas. Formas Normales de Chomsky y Greibach. Autómatas con pila. Propiedades de los Lenguajes Libres de Contexto.
TEMA 3: Modelos de Computación.
El concepto de algoritmo. Máquinas de Turing. Funciones Parciales Recursivas. Programas while. Equivalencia de todos los modelos de computación anteriores. Tesis de Church.
TEMA 4: Enumeración de la funciones Computables y Teoremas Fundamentales.
Enumeración de los programas y de las funciones computables. Teorema de Universalidad. Teorema de Parametrización ó S.M.N. Teorema de Recursión.
TEMA 5: Resolubilidad e Irresolubilidad algorítmica.
Problemas resolubles e irresolubles algorítmicamente: Problema de la Totalidad (método de diagonalización); Problema de la parada (método de reducción). Teorema de Rice. Resolubilidad parcial. Conjuntos recursivos y recursivamente enumerables.
TEMA 6: Complejjidad Algorítmica.
Complejidad y medidas de complejidad. Ordenes de magnitud. Clases de complejidad: Las clases P y NP. El concepto de problema completo para una clase. Algunos problemas NP-completos.
Bibliografía:
1.- Brookshear, J. G., Teoría de la Computación. Addison- Wesley Iberoamericana, 1993.
2.- Dean, K., Automata and Formal Languages. An Introduction. Ed. Prentice-Hall, 1995
3.-Hopcroft, J.E.; Motwanni, R.; Ullman, J.D., Introducción a la Teoría de Autómatas, Lenguajes y Computación. Segunda edición, Ed. Addison-Wesley, 2001.
4.- Kfoury, A. J., Moll, R. N., Arbib, M. A., A Programming Approach to Computability. Springer-Verlag, 1982.
5.- Kozen, D. C., Automata and Computability. Ed. Springer, 1997.
6.- Martin, J. C., Introduction to Languajes and the Theory of Computation. Ed. McGraw Hill 1991.
7.- McNaughton, R., Elementary Computability, Formal Languages, and Automata. Prentice-Hall, 1982.
8.- Moret, B. M., The Theory of Computation. Ed. Addison Wesley, 1998.
9.- Sudkamp, T. A., Languajes and Machines. Ed. Addison Wesley 1997 (second edition).
Metodología y Evaluación:
La evaluación se realizará mediante tareas y trabajos que se propondrán a lo largo del curso, asi como exámenes finales correspondientes a las convocatorias de Junio Septiembre y Febrero.

Información ECTS
Código:
E-LSUD-4-MATH-407-CT
Créditos ECTS:
7,2
Teóricos:
4,8
Prácticos:
2,4
Método:
Clases Magistrales
Prácticas problemas
Trabajos aula
Sistemas de evaluación:
Examen escrito
Evaluación continua

©2002 Universidad de Oviedo