Codi	9177	Descripció
Crdts. Teor.	2,25	MÀQUINES DE TURING. FUNCIONS RECURSIVES.
Crdts. Pract.	2,25
A efectes d'intercanvis en programes de mobilitat, la càrrega d'aquesta assignatura equival a 5,62 ECTS.

Departamentos y Áreas
Departaments	Àrea	Crdts. Teor.	Crdts. Pract.	Dpto. Respon.	Respon. Acta
CIÈNCIA DE LA COMPUTACIÓ I INTEL·LIGÈNCIA ARTIFICIAL	CIÈNCIA DE LA COMPUTACIÓ I INTEL·LIGÈNCIA ARTIFICIAL	2,25	2,25

Estudis en què s'imparteix

Enginyeria en Informàtica - pla 2001

Prerequisitos

ÀLGEBRA

Incompatibilitats de matricula per continguts equivalents
Aquesta assignatura és incompatible, per tenir continguts equivalents, amb les següents assignatures:
Codi	Assignatura
9361	COMPUTABILITAT
3168	MODELS ABSTRACTES DE CÀLCUL
9294	COMPUTABILITAT

Matriculats (2013-14)
Grup (*)	Nombre
1	5
TOTAL	5

(*) 1: GRUPO 1 - CAS

Oferida com a lliure elecció (2013-14)

Sense departament

Consulta Gràfica d'Horari

Feu clic ací

Horari (2013-14)

Sense horari

Grups de matricula (2013-14)
Grup (*)	Quadrimestre	Torn	Idioma	Distribució (lletra nif)
1	2do.	M	CAS	des de - fins a -

(*) 1: GRUPO 1 - CAS

Objectius de l'assignatura / competències (2013-14)

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.

Continguts teòrics i pràctics (2013-14)

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

Enllaç al programa

http://www.dccia.ua.es/dccia/inf/asignaturas/C/

Professor/a responsable

Arques Corrales , Maria Del Pilar

Metodologia docent (2013-14)

Classes teòriques i pràctiques

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.

Tipus d'activitats: teòriques i pràctiques

Altres

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.

Professorat (2013-14)
	Grup	Professor
TEORIA COMPARTIDA DE 9177 Y 9294	1	Arques Corrales, Maria Del Pilar

Enllaços relacionats

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

Bibliografia

Ordena pel títol del llibre Ordena pel professor que recomana

Introducción a la teoría de autómatas, lenguajes y computación Autors: Hopcroft, John E. ; Motwani, Rajeev Edició: Madrid : Addison-Wesley, 2008. ISBN: 978-84-7829-088-8 Recomanat per: ARQUES CORRALES,MARIA DEL PILAR (*1) [ Accés al catàleg de la biblioteca universitària ] [ Accés a les edicions anteriors ] Introducción a la teoría de la computabilidad Autors: Gallardo López, Domingo ; Arqués Corrales, Pilar Edició: San Vicente del Raspeig : Universidad de Alicante, 2003. ISBN: 84-7908-763-3 Recomanat per: ARQUES CORRALES,MARIA DEL PILAR (*1) [ Accés al catàleg de la biblioteca universitària ] [ Accés a les edicions anteriors ] Introduction to the theory of computation Autors: SIPSER, Michael Edició: Boston : Thomson Course Technology, 2006. ISBN: 978-0-6192-1764-8 Recomanat per: ARQUES CORRALES,MARIA DEL PILAR (*1) [ Accés al catàleg de la biblioteca universitària ] [ Accés a les edicions anteriors ]

(*1) Aquest professor ha recomanat el recurs bibliogràfic a tot l'alumnat de l'assignatura.

Dates d'exàmens oficials (2013-14)
Convocatòria	Grup (*)	Data	Hora d’inici	Hora d’fi	Aules assignades	Observacions:
Proves extraordinarias de finalització d'estudis	-1	27/11/2013				-
Període ordinari per a assignatures de segon semestre i anuals	-1	06/06/2014	12:00	15:00	0039PS002	-
Proves extraordinàries de assignatures de grau i màster	-1	30/06/2014	09:00	12:00	0039PS003	-

(*) 1: GRUPO 1 - CAS

Instruments i criteris d'avaluació (2013-14)

Examen final

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