UA
   COMPUTABILIDAD    Año académico       Versión PDF.  Versión PDF para convalidación.
Código9177Descripción
Crdts. Teor.2,25MAQUINAS 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 en Informática - 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
9361COMPUTABILIDAD
3168MODELOS ABSTRACTOS DE CALCULO
9294COMPUTABILIDAD


Matriculados (2011-12)
Grupo (*)Número
1 12
TOTAL 12
(*) 1: GRUPO 1 - CAS


Ofertada como libre elección (2011-12)
Número máximo de alumnos: Sin límite
Pincha aquí para ver a qué estudios se oferta
Consulta Gráfica de Horario
A efectos de intercambios en programas de movilidad, la carga de esta asignatura equivale aPincha aquí


Horario (2011-12)
ModoGrupo (*)Día inicioDía finDíaHora inicioHora finAula
PRÁCTICAS DE PROBLEMAS / TALLER 1 01/02/2012 25/05/2012 L 11:30 13:00
(*) CLASE TEÓRICA
1: GRUPO 1 - CAS
(*) PRÁCTICAS DE PROBLEMAS / TALLER
1: GRUPO PRACTICAS DE COMPUTABILIDAD - CAS


Grupos de matricula (2011-12)
Grupo (*)CuatrimestreTurnoIdiomaDistribución (letra nif)
1 2do. M CAS desde - hasta -
(*) 1: GRUPO 1 - CAS


Objetivos de las asignatura / competencias (2011-12)
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 (2011-12)
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 (2011-12)
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 (2011-12)
Grupo Profesor/a
TEORIA COMPARTIDA DE 9177 Y 92941Arques Corrales, Maria Del Pilar
PRÁCTICAS DE PROBLEMAS DE 91771Arques 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 teoría de autómatas, lenguajes y computación
Autor(es):HOPCROFT, John; MOTWANI, Rajeev; ULLMAN, Jeffrey D.
Edición:Madrid : Addison-Wesley, 2002.
ISBN:978-84-7829-056-7
Recomendado por:ARQUES CORRALES,MARIA DEL PILAR (*1)
[ Acceso al catálogo de la biblioteca universitaria ]

Introducción a la teoría de la computabilidad
Autor(es):GALLARDO LÓPEZ, Domingo; ARQUES CORRALES, Pilar; LESTA PELAYO, Ignacio
Edición:Alicante : Universidad de Alicante, 2005.
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 (2011-12)
ConvocatoriaGrupo (*)fechaHora inicioHora finAula(s) asignada(s)Observ:
Exámenes extraordinarios de finalización de estudios (diciembre) -1 08/11/2011 12:00 15:00 A1/1-42S -
Periodo ordinario para asignaturas de segundo semestre y anuales -1 05/06/2012 12:00 15:00 EP/S-08M -
Periodo extraordinario de julio -1 18/07/2012 11:30 14:30 EP/0-24P -
(*) 1: GRUPO 1 - CAS


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