Código	9294	Descripción
Crdts. Teor.	2,25	MÁQUINAS DE TURING. FUNCIONES RECURSIVAS.
Crdts. Pract.	2,25
A efectos de intercambios en programas de movilidad, la carga de esta asignatura equivale a 5,62 ECTS.

Departamentos y Áreas
Departamentos	Área	Crdts. Teor.	Crdts. Pract.	Dpto. Respon.	Respon. Acta
CIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL	CIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL	2,25	2,25

Estudios en los que se imparte

Ingeniería Técnica en Informática de Gestión - plan 2001

Pre-requisitos

ÁLGEBRA

Incompatibilidades de matrícula por contenidos equivalentes
Esta asignatura es incompatible, por tener contenidos equivalentes, con las asignaturas siguientes:
Código	Asignatura
9177	COMPUTABILIDAD
3168	MODELOS ABSTRACTOS DE CALCULO
9361	COMPUTABILIDAD

Matriculados (2014-15)

Sin Datos

Ofertada como libre elección (2014-15)

Sin departamento

Consulta Gráfica de Horario

Pincha aquí

Horario (2014-15)

Sin horario

Grupos de matricula (2014-15)
Grupo (*)	Cuatrimestre	Turno	Idioma	Distribución (letra nif)
1	2do.	M	CAS	desde - hasta -

(*) 1: GRUPO 1 - CAS

Objetivos de las asignatura / competencias (2014-15)

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 (2014-15)

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-mu. 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 (2014-15)

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. Dentro de nuestro compromiso con la adaptación al Espacio Europeo de Educación Superior, se introducirán nuevos métodos docentes: trabajo en grupo en las clases prácticas, posibilidad de realizar trabajos adicionales, formento de la participación activa en las clases, etc.

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 será obligatoria.

Profesores (2014-15)
	Grupo	Profesor/a
TEORIA COMPARTIDA DE 9177 Y 9294	1	Arques Corrales, Maria Del Pilar

Enlaces relacionados

http://es.wikipedia.org/wiki/Computaci%C3%B3n_basada_en_ADN

http://es.wikipedia.org/wiki/Computaci%C3%B3n_cu%C3%A1ntica

http://es.wikipedia.org/wiki/N%C3%BAmero_primo#Primalidad_del_n.C3.BAmero_1

http://primes.utm.edu/notes/faq/one.html

http://www.youtube.com/watch?v=4rzAL5YwFow&feature=player_embedded

Bibliografía

Ordenar por título del libro Ordenar por profesor que lo recomienda

Introducción a la teoría de autómatas, lenguajes y computación Autor(es): Hopcroft, John E. ; Motwani, Rajeev Edición: Madrid : Addison-Wesley, 2008. ISBN: 978-84-7829-088-8 Recomendado por: ARQUES CORRALES,MARIA DEL PILAR (*1) [ Acceso al catálogo de la biblioteca universitaria ] [ Acceso a las ediciones anteriores ] Introducción a la teoría de la computabilidad Autor(es): Gallardo López, Domingo ; Arqués Corrales, Pilar Edición: San Vicente del Raspeig : Universidad de Alicante, 2003. ISBN: 84-7908-763-3 Recomendado por: ARQUES CORRALES,MARIA DEL PILAR (*1) [ Acceso al catálogo de la biblioteca universitaria ] [ Acceso a las ediciones anteriores ] Introduction to the theory of computation Autor(es): SIPSER, Michael Edición: Boston : Thomson Course Technology, 2006. ISBN: 978-0-6192-1764-8 Recomendado por: ARQUES CORRALES,MARIA DEL PILAR (*1) [ Acceso al catálogo de la biblioteca universitaria ] [ Acceso a las ediciones anteriores ]

(*1) Este profesor ha recomendado el recurso bibliográfico a todos los alumnos de la asignatura.

Fechas de exámenes oficiales (2014-15)
Convocatoria	Grupo (*)	fecha	Hora inicio	Hora fin	Aula(s) asignada(s)	Observ:
Periodo ordinario para asignaturas de segundo semestre y anuales	-1	05/06/2015				-
Pruebas extraordinarias para asignaturas de grado y máster	-1	08/07/2015				-

(*) 1: GRUPO 1 - CAS

Instrumentos y criterios de evaluación (2014-15)

Examen final

La evaluación de la asignatura consistirá en un examen teórico-práctico de todos los conceptos estudiados durante el curso.