TEORIA DE COMPUTACION - 503371
- Descripción :Esta asignatura caracterizada como teorica, es la que permite formalizar los conceptos adquiridos en las asignaturas hasta aqui cursadas por el estudiante. El enfasis esta dado en los fundamentos historicos del estudio de los aspectos teoricos de computacion.
- Resultados aprendizaje esperados :Al aprobar la asignatura, el alumno sera capaz de:
? Conocer las nociones precisas de lo que se entiende formalmente por computable, insoluble, algoritmo, ?enumerable?.
? Usar Maquinas de Turing y Funciones Recursivas como formalismos de decision y computabilidad.
? Tener una apreciacion del rango y las limitaciones teoricas existentes para la computacion.
- Contenidos :INTRODUCCION
1.1 Algoritmos
1.2 Historia
2. MAQUINAS ABSTRACTAS. REVISION
2.1 Automatas Finitos
2.2 Automatas con Pilas
2.3 Maquina de Turing
3. ENUMERACION Y NUMERACION DE GODEL
3.1 Enumeraciones y Conjuntos Contables
3.2 Numeraciones de Godel
4. FUNCIONES RECURSIVAS
4.1 Definicion de Funciones Recursivas Primitivas
4.2 Algunas Funciones Primitivas Recursivas Utiles
4.3 Minimizacion. Funciones Regulares, Parciales y Totales
4.4 Funciones Recursivas y Funciones Recursivas Parciales
5. EQUIVALENCIA DE LAS FUNCIONES RECURSIVAS Y LAS FUNCIONES
COMPUTABLES POR MAQUINA DE TURING
5.1 Computabilidad de Turing
5.2 Recursividad Implica Turing Computable
5.3 Turing Computable Implica Recursividad
6. CONJUNTOS RECURSIVAMENTE ENUMERABLES
6.1 Definiciones y Teoremas Basicos
- Metodología :Las clases de teoria se utilizan para entregar los fundamentos de la teoria de la computacion. Las tareas a desarrollar durante el semestre permitiran ejercitar los conceptos estudiados para su reforzamiento, ademas se utilizaran para conectar la tematica base de la teoria con otros topicos.
- Evaluación :La evaluacion de la asignatura incluye controles escritos y tareas o trabajos.
- Facultad :INGENIERIA
- Departamento :INFORMATICA Y CS COMPUTACION
- Creditos :4
- Cupos :30
- Campus :CONCEPCION