UA
   COMPUTABILIDAD    Año académico       Versión PDF.
Código9361Descripción
Crdts. Teor.2,25MÁ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ÁreaCrdts. Teor.Crdts. Pract.Dpto. Respon.Respon. Acta
CIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIALCIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL2,252,25


Estudios en los que se imparte
Ingeniería Técnica en Informática de Sistemas - 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ódigoAsignatura
9177COMPUTABILIDAD
9294COMPUTABILIDAD
3168MODELOS ABSTRACTOS DE CALCULO


Matriculados (2009-10)
Grupo (*)Número
1 39
2 36
TOTAL 75
(*) 1: GRUPO 1 - CAS
(*) 2: GRUPO 2 - CAS


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


Horario (2009-10)
ModoGrupo (*)Día inicioDía finDíaHora inicioHora finAula
CLASE TEÓRICA 1 01/02/2010 21/05/2010 L 10:00 11:30 A2/B13
  2 01/02/2010 21/05/2010 L 15:30 17:00 A2/E03
PRÁCTICAS DE PROBLEMAS / TALLER 1 01/02/2010 21/05/2010 L 18:00 19:30 A2/D23
  2 01/02/2010 21/05/2010 L 19:30 21:00 A2/D23
  3 01/02/2010 21/05/2010 J 18:00 19:30 A2/D23
  4 01/02/2010 21/05/2010 J 19:30 21:00 A2/D23
  5 01/02/2010 21/05/2010 V 11:00 12:30 A2/B01
(*) CLASE TEÓRICA
1: GRUPO 1 - CAS
2: GRUPO 2 - CAS
(*) PRÁCTICAS DE PROBLEMAS / TALLER
1: PRACTICAS DE 9361 - CAS
2: PRACTICAS DE 9361 - CAS
3: PRACTICAS DE 9361 - CAS
4: PRACTICAS DE 9361 - CAS
5: PRACTICAS DE 9361 - CAS


Grupos de matricula (2009-10)
Grupo (*)CuatrimestreTurnoIdiomaDistribución (letra nif)
1 2do. M CAS desde A hasta M
2 2do. T CAS desde N hasta Z
(*) 1: GRUPO 1 - CAS
(*) 2: GRUPO 2 - CAS


Objetivos de las asignatura / competencias (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.


Contenidos teóricos y prácticos (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


Más información
http://www.dccia.ua.es/dccia/inf/asignaturas/C/
Profesor/a responsable
Arques Corrales , Maria Del Pilar


Metodología docente (2009-10)
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 (2009-10)
Grupo Profesor/a
TEORIA DE 93611Arques Corrales, Maria Del Pilar
MOLINA CARMONA, RAFAEL
2Arques Corrales, Maria Del Pilar
MOLINA CARMONA, RAFAEL
PRÁCTICAS DE PROBLEMAS DE 93611LOPEZ MARTIN, VICENTE MANUEL
2LOPEZ MARTIN, VICENTE MANUEL
3LOPEZ MARTIN, VICENTE MANUEL
4LOPEZ MARTIN, VICENTE MANUEL
5Arques 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

Introducción a la informática : modelos de cómputo
Autor(es):Llamas Bello, César
Edición:Madrid : Thomson, 2004.
ISBN:84-9732-279-7
Recomendado por:MOLINA CARMONA, RAFAEL (*1)
[ Acceso al catálogo de la biblioteca universitaria ]

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 (2009-10)
ConvocatoriaGrupo (*)fechaHora inicioHora finAula(s) asignada(s)Observ:
Exámenes extraordinarios de finalización de estudios (diciembre) -1 28/10/2009 -
Periodo ordinario para asignaturas de segundo semestre y anuales -1 25/05/2010 12:00 15:00 0039PB005
EP/0-22M
0039PB013
-
Periodo extraordinario de julio -1 06/07/2010 08:30 11:30 A2/E01
A2/E02
-
(*) 1: GRUPO 1 - CAS
(*) 2: GRUPO 2 - CAS


Instrumentos y criterios de evaluación (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.