UA
   MODELOS ABSTRACTOS DEL CALCULO    Año académico       Versión PDF.
Código6637Descripción
Crdts. Teor.3Maquinas de Turing. Funciones de recursividad.
Crdts. Pract.1,5
A efectos de intercambios en programas de movilidad, la carga de esta asignatura equivale a 5,62 ECTS.


Departamentos y Áreas
DepartamentosÁreaCrdts. Teor.Crdts. Pract.Dpto. Respon.Respon. Acta
CIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIALCIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL31,5


Estudios en los que se imparte
Ingeniería en Informática - plan 1993


Pre-requisitos
MATEMATICA DISCRETA


Incompatibilidades de matrícula por contenidos equivalentes
Sin Datos


Matriculados (2003-04)
Grupo (*)Número
1 44
3 1
TOTAL 45
(*) 1: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS
(*) 2: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS
(*) 3: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS


Ofertada como libre elección (2003-04)
Sin departamento
Consulta Gráfica de Horario
A efectos de intercambios en programas de movilidad, la carga de esta asignatura equivale aPincha aquí


Horario (2003-04)
Sin horario


Grupos de matricula (2003-04)
Grupo (*)CuatrimestreTurnoIdiomaDistribución (letra nif)
1 2do. M CAS desde - hasta -
2 2do. M CAS desde - hasta -
3 2do. M CAS desde - hasta -
(*) 1: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS
(*) 2: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS
(*) 3: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS


Objetivos de las asignatura / competencias (2003-04)
Conocer los límites de la computación, sabiendo reconocer algunos problemas como no computables.
Conocer diferentes modelos de computación y su equivalencia.
Comprender la importancia de la materia como la base central de los aspectos teóricos de la informática.


Contenidos teóricos y prácticos (2003-04)
1. Preliminares.
a. Conjuntos, Tuplas, Predicados, Funciones, Alfabetos, Cadenas y Lenguajes.
b. Métodos de demostración. Reducción al absurdo. Demostración por inducción.
c. Codificación de pares de números.
d. Numerabilidad. No Numerabilidad.

2. Máquinas de Turing.
a. El modelo conceptual de Máquina de Turing.
b. Equivalencias de modelos de Máquinas de Turing.
i. Máquina de Turing Multipista.
ii. Máquina de Turing con registro acotado de memoria.
iii. Máquina de Turing Multicinta
iv. Máquina de Turing no determinista.
c. Lenguajes computable y funciones.
d. Caracterización de los lenguajes con Máquinas de Turing generadoras.

3. Funciones L-computables.
a. El lenguaje L. Definición sintáctica y semántica de L.
b. Definición de macros. Ejemplos
c. Funciones L-computables.
d. Tesis de Church aplicada al lenguaje L.

4. Funciones recursivas primitivas.
a. Definición. Constructores avanzados.
i. Predicados.
ii. Iteradores acotados.
iii. Cuantificadores acotados.
iv. Minimización acotada.
b. Comparación entre funciones L-computables y funciones recursivas primitivas.
i. Minimización no acotada.
ii. Funciones recursivas.

5. Un programa Universal.
a. Numeración de Gödel. Codificación y descodificación.
b. Codificación de programas L.
i. Codificación de instrucciones.
ii. Codificación y descodificación de programas.
c. Codificación de ejecuciones de programas.
i. Codificación de descripciones instantaneas.
d. El programa Universal.

6. Decidibilidad e Indecidibilidad.
a. El problema de la parada.
b. El castor afanoso.
c. Conjuntos decidibles e indecidibles.
i. Conjuntos recursivos.
ii. Conjuntos recursivamente enumerables.
d. Conjuntos no recursivos.
e. Conjuntos no recursivamente enumerables.
f. Teorema de Rice


Más información
http://www.dccia.ua.es/dccia/inf/asignaturas/C
Profesor/a responsable
ARQUES CORRALES , MARIA DEL PILAR


Metodología docente (2003-04)
Clases teóricas y prácticas
En las clases teóricas se explicarán los conceptos teóricos de la materia, basándonos en ejemplos relacionados con los conceptos explicados.



Tipo de actividades: teóricas y prácticas
Otras
Las clases prácticas se desarrollarán en clases "de pizarra". Se plantearán ejercicios referentes a la teoría y se resolverán en grupos de hasta 4 personas.
La asistencia a prácticas no es obligatoria pero sólo podrán realizar las hojas de problemas aquellos alumnos que tengan menos de 3 faltas de asistencia.


Profesores (2003-04)
ARQUES CORRALES, MARIA DEL PILAR (prof. responsable)
Enlaces relacionados
Sin Datos


Bibliografía
No existen libros recomendados en esta asignatura para este año académico.
Fechas de exámenes oficiales (2003-04)
Información no disponible en estos momentos.
(*) 1: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS
(*) 2: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS
(*) 3: TEORIA DE MODELOS ABSTRACTOS DE CALCULO - CAS


Instrumentos y criterios de evaluación (2003-04)
Examen final
La evaluación de la asignatura consistirá en un único examen teórico-práctico de todos los conceptos estudiados durante el curso. (Este examen puntuará sobre 10 puntos).
A lo largo del curso propondremos 2 hojas de problemas que puntuarán 0,5 puntos cada una, y cuya nota se sumará a la nota de teoría.