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 (2009-10)
Grup (*)	Nombre
1	31
2	25
3	3
TOTAL	59

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

(*) 3: GRUPO 3 Valenciano - VAL

Oferida com a lliure elecció (2009-10)

Sense departament

Consulta Gràfica d'Horari

Feu clic ací

Horari (2009-10)
Mode	Grup (*)	Data d’inici	Data de finalització	Dia	Hora d’inici	Hora d’fi	Aula
CLASSE TEÒRICA	1	01/02/2010	21/05/2010	X	11:00	12:30	A2/D23
	2	01/02/2010	21/05/2010	X	17:00	18:30	A2/D23
	3	01/02/2010	21/05/2010	X	09:30	11:00	A2/D21
PRÀCTIQUES DE PROBLEMES / TALLER	1	01/02/2010	21/05/2010	M	16:30	18:00	A2/D13
	2	01/02/2010	21/05/2010	M	18:00	19:30	A2/D13
	3	01/02/2010	21/05/2010	M	19:30	21:00	A2/D13
	4	01/02/2010	21/05/2010	X	16:30	18:00	A2/D13
	5	01/02/2010	21/05/2010	V	12:30	14:00	A2/B01

(*) CLASE TEÓRICA
	1: GRUPO 1 - CAS
	2: GRUPO 2 - CAS
	3: GRUPO 3 Valenciano - VAL
(*) PRÁCTICAS DE PROBLEMAS / TALLER
	1: GRUPO PRACTICAS DE COMPUTABILIDAD - CAS
	2: GRUPO PRACTICAS DE COMPUTABILIDAD - CAS
	3: GRUPO PRACTICAS DE COMPUTABILIDAD - CAS
	4: GRUPO PRACTICAS DE COMPUTABILIDAD - CAS
	5: GRUPO PRACTICAS DE COMPUTABILIDAD - CAS

Grups de matricula (2009-10)
Grup (*)	Quadrimestre	Torn	Idioma	Distribució (lletra nif)
1	2do.	M	CAS	des de A fins a M
2	2do.	T	CAS	des de N fins a Z
3	2do.	M	VAL	des de - fins a -

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

(*) 3: GRUPO 3 Valenciano - VAL

Objectius de l'assignatura / competències (2009-10)

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 (2009-10)

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 (2009-10)

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 (2009-10)
	Grup	Professor
TEORIA COMPARTIDA DE 9177 Y 9294	1	Arques Corrales, Maria Del Pilar
		MOLINA CARMONA, RAFAEL
	2	Arques Corrales, Maria Del Pilar
	3	Arques Corrales, Maria Del Pilar
		MOLINA CARMONA, RAFAEL
PRÁCTICAS DE PROBLEMAS DE 9177	1	VICHE CLAVEL, JOSE IGNACIO
	2	VICHE CLAVEL, JOSE IGNACIO
	3	VICHE CLAVEL, JOSE IGNACIO
	4	VICHE CLAVEL, JOSE IGNACIO
	5	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 informática : modelos de cómputo Autors: Llamas Bello, César Edició: Madrid : Thomson, 2004. ISBN: 84-9732-279-7 Recomanat per: MOLINA CARMONA, RAFAEL (*1) [ Accés al catàleg de la biblioteca universitària ] 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 (2009-10)
Convocatòria	Grup (*)	Data	Hora d’inici	Hora d’fi	Aules assignades	Observacions:
Exàmens extraordinaris de finalització d'estudis (desembre)	-1	28/10/2009				-
Període ordinari per a assignatures de segon semestre i anuals	-1	25/05/2010	12:00	15:00	EP/0-22M 0039PB005 0039PB013	-
Període extraordinari de juliol	-1	06/07/2010	08:30	11:30	A2/E02 A2/E01	-

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

(*) 3: GRUPO 3 Valenciano - VAL

Instruments i criteris d'avaluació (2009-10)

Examen final

La evaluación de la asignatura tiene dos componentes. Por un lado, se realizará examen teórico-práctico de todos los conceptos estudiados durante el curso. Por otro lado, las prácticas fomentarán la evaluación contínua y la retroalimentación, valorándose la asistencia y la participación e implicación en clase. Además. a lo largo del curso propondremos 2 controles prácticos que puntuarán 1 punto cada uno. Nota final = Examen teórico-práctico (80%) + Controles Prácticos (20%). Para aprobar la asignatura habrá que aprobar cada parte por separado.