Gestión Académica

La asignatura de Computabilidad está incluida en el módulo de las asignaturas Comunes a la Informática, y dentro de la materia del Grado denominada Fundamentos Informáticos. Su impartición se desarrolla en el primer semestre del segundo curso del Grado. Esta asignatura es una continuación natural de otra incluida en el primer curso, denominada Autómatas y Matemáticas Discretas, ya que mediante los diferentes modelos de computación se avanza en el estudio de Lenguajes Formales, concretamente los Lenguajes Recursivos y Recursivamente Enumerables, y también en dar respuesta a la pregunta de qué problemas pueden y no pueden ser resueltos computacionalmente. El conjunto de las dos asignaturas constituye la justificación teórica de importantes aspectos de la Informática y debería hacer reflexionar al alumno sobre cómo se produjo el origen y desarrollo de la misma. Asimismo, existen importantes relaciones entre la Computabilidad y las siguientes asignaturas:

Metodología de la Programación (Primer Curso)

La manera de presentar los modelos de computación estudiados supone una forma de introducir lenguajes de programación que podríamos denominar “teóricos”. Para el alumno esto constituye una forma diferente de ver distintos paradigmas de programación ya  tratados en primer curso.

Algoritmia (Segundo Curso)

Buena parte de la Computabilidad está dedicada al estudio de lo que es y lo que no es computable. El diseño de algoritmos para las funciones computables y la demostración de la irresolubilidad algorítmica de problemas es algo que se encuentra muy presente.

Algebra Lineal (primer curso)

La primera parte del temario de la asignatura de Computabilidad comprende la totalidad de la Lógica que el alumno estudiará durante su permanencia en el Grado. No obstante, en el primer curso hay asignaturas de carácter matemático, como el Álgebra Lineal, en las que el proceso demostrativo y la notación que se utiliza están relacionados con aspectos sencillos de la Lógica.

Otras asignaturas relacionadas con la Computabilidad son: Diseño de Lenguajes de Programación (3º curso) y Sistemas Inteligentes (4º curso).

Teniendo en cuenta el apartado anterior, resulta fundamental para un correcto seguimiento de esta asignatura, que el alumno haya cursado previamente la materia de Autómatas y Matemáticas Discretas. También es aconsejable que esté familiarizado con los aspectos tratados en Metodología de la Programación, si bien esto no resulta crucial. Finalmente, es conveniente que el alumno tenga nociones de notación y lenguaje matemático, además de poseer cierta destreza en los métodos demostrativos.

Según la memoria de verificación, las competencias a alcanzar por los estudiantes en cuyo desarrollo colabora la asignatura de Computabilidad son las siguientes:

Competencias generales

CG3:   Abstracción

CG11:  Trabajo en equipo

CG25:  Razonamiento crítico

Competencias específicas de formación básica

Bas.3: Capacidad para comprender y dominar los conceptos básicos de Autómatas y Matemáticas Discretas, Lógica, Algorítmica y Complejidad Computacional y su aplicación para la resolución de problemas propios de la Ingeniería.

Competencias específicas comunes a la rama de informática

Com 6: Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.

Resultados de aprendizaje      

Los resultados de aprendizaje esperados, relacionados con la asignatura son los siguientes:

1. Conocer y manejar los lenguajes de Lógica Proposicional y Lógica de Predicados.
2. Representar información de dominio en lenguajes formales de Lógica.
3. Comprender el concepto de algoritmo y conocer algún modelo de computación como contexto para la construcción de códigos de funciones computables.
4. Entender y asumir la Tesis de Church como un aspecto crucial de la Computación.
5. Saber utilizar de forma adecuada los resultados fundamentales de la Computabilidad.
6. Comprender el concepto de función No-computable y conocer técnicas para tratar de diferenciar lo que es y lo que no es computable.

Parte 1 Fundamentos de Lógica

Tema 1. Lógica de Proposiciones

1. Sintaxis y Semántica
2. Métodos semánticos de prueba
3. Formas Normales Conjuntiva y Disyuntiva y Resolución Proposicional
4. Deducción Natural

Tema 2. Lógica de Predicados

1. Sintaxis y Semántica
2. Forma Clausal, Unificación y Resolución General
3. Deducción Natural en Lógica de Predicados

Parte 2 Teoría de la Computabilidad

Tema 3. Modelos de Computación y Funciones Computables

1. Introducción: Concepto intuitivo de algoritmo
2. El modelo de los programas while
3. El modelo de las máquinas de Turing
4. La Tesis de Church-Turing

Tema 4. Resultados Fundamentales y Resolubilidad de Problemas

1. Enumeración de los algoritmos
2. Teoremas fundamentales: Universalidad, Parametrización y Recursión
3. Resolubilidad e irresolubilidad algorítmicas
4. Introducción a la complejidad algorítmica

De acuerdo con las pautas que establece el EEES, la asignatura se desarrollará mediante actividades presenciales y trabajo autónomo del estudiante.

Las actividades presenciales son aquellas en las que estará siempre presente el profesor. Se dividen en clases expositivas, seminarios, prácticas de laboratorio, tutorías grupales y sesiones de evaluación.

• Clases expositivas: Impartidas al grupo completo, no necesariamente como lección magistral, sino procurando una participación activa del alumno en la dinámica de las mismas. En estas clases se desarrollarán contenidos teóricos de la asignatura, combinados con alguna resolución de pequeños ejercicios. Se utilizará la pizarra y los diferentes medios audiovisuales.
• Seminarios: Impartidos a grupos más reducidos, aproximadamente la mitad de un grupo completo. En estas sesiones se tratarán de afianzar los conocimientos presentados en las clases expositivas, describiendo ejemplos y realizando ejercicios. La participación del alumno será de mayor intensidad.
• Prácticas de Laboratorio: Dedicadas a resolver ejercicios y problemas prácticos utilizando siempre que sea posible el PC.  Se desarrollarán en varios grupos, de manera eminentemente participativa.
• Tutorías grupales: Dedicadas a la aclaración de dudas sobre teoría, problemas o trabajos en curso. Estas actividades podrán servir para ir comprobando el grado de adquisición de competencias y destrezas por parte del alumno. Se desarrollarán en varios grupos, disponiendo por tanto los estudiantes de una atención algo más personalizada por parte  del profesor.
• Sesiones de evaluación: Se dedicarán a la realización de pruebas escritas o bien con un PC, con las que se pueda valorar de forma objetiva el nivel alcanzado por los estudiantes en la adquisición de algunas de las competencias previstas.

La metodología docente a emplear estará basada en la participación activa del alumno, sobre todo en las sesiones de seminario, prácticas de laboratorio y tutorías grupales. En caso de que el tamaño del grupo lo permita, se plantearán actividades y ejercicios que impliquen al alumno y propicien su participación, ya sea resolviendo las tareas de manera privada o públicamente en el aula.

Asimismo, al final de cada uno de los temas podrá realizarse, si los profesores lo estiman conveniente, un pequeño control con objeto de conocer el grado de adquisición de las competencias cognitivas más relacionadas con los contenidos de la asignatura.

Con respecto a las prácticas de laboratorio, al finalizar cada una de las prácticas programadas, el alumno podría tener que elaborar un informe para entregarlo posteriormente al profesor. También podrían plantearse ejercicios para entregar al final de cada sesión de prácticas o bien pequeños cuestionarios sobre los conceptos trabajados, que el alumno deberá resolver.

En caso de que el tamaño del grupo lo permita, se utilizarán metodologías docentes acordes con el tamaño de dicho grupo.

De forma excepcional, si las condiciones sanitarias lo requieren, se podrán incluir métodos de evaluación no presencial. En cuyo caso, se informará al estudiantado de los cambios efectuados. 

A continuación se presentan una serie de tablas que especifican la temporalidad de las actividades tanto presenciales como no presenciales:

Volumen de trabajo estimado para el estudiante

Distribución del trabajo por temas

Trabajo presencial

Trabajo no presencial

Evaluación en la convocatoria ordinaria

En la evaluación ordinaria se utilizarán diversos procedimientos que permitirán el seguimiento del proceso de aprendizaje del alumno.  

            Los diferentes procedimientos evaluadores serán los siguientes:

1. Evaluación de los controles realizados al finalizar cada uno de los temas así como otras actividades planteadas en las sesiones presenciales.
2. Evaluación de los cuestionarios y ejercicios prácticos propuestos.
3. Evaluación final: Examen escrito y evaluación práctica de la asignatura.

• Prácticas de laboratorio: En las prácticas de laboratorio se plantearán ejercicios y cuestionarios para realizar en la sesión y las soluciones propuestas podrán ser evaluadas al final de la misma.
• Controles y actividades en el aula: Los alumnos podrán defender en el aula algunos pequeños ejercicios o trabajos propuestos periódicamente por los profesores, ya sea de forma individual o grupal. También se realizarán en el aula los diferentes controles tras la impartición de los contenidos fijados.

Los dos apartados anteriores constituyen el proceso de evaluación continua y tienen un peso del 50% en la calificación final de la asignatura. Dicho peso se obtiene considerando un 10% para las actividades en las sesiones de prácticas y un 40% para los controles y resto de actividades evaluadoras programadas.

• Prueba final: Consistirá en una o más  pruebas de diferente carácter, con un peso del 50% en la calificación final.

De forma excepcional, si las condiciones sanitarias lo requieren, se podrán incluir métodos de evaluación no presencial. En cuyo caso, se informará al estudiantado de los cambios efectuados.

Consideraciones importantes:

• Aquellos alumnos que con los controles y actividades propuestas hayan obtenido en alguna de las partes del programa (Lógica y Teoría de la Computabilidad) una nota mayor o igual que 5 puntos sobre 10, podrán, si así lo desean, liberar esa parte y no presentarse a ella en el examen final de la convocatoria ordinaria, considerándose la nota obtenida como la calificación correspondiente a esa parte en el examen final.
• El peso en cada ítem de la evaluación de cada una de las dos partes del programa será proporcional al número de horas presenciales dedicadas a dicha parte.
• La nota final de cada parte de la asignatura será la máxima de las calificaciones obtenidas en cada parte, entre los controles y el examen final.
• La calificación final de la asignatura se calculará sumando las notas ponderadas obtenidas en las dos partes, en caso de que se haya alcanzado un mínimo de 5 puntos sobre 10 en ambas. En otro caso, la nota de la asignatura será el mínimo entre 4 y esa media ponderada.

Resumen de la evaluación

Evaluación en las convocatorias extraordinarias

En las convocatorias de carácter extraordinario el alumno debe realizar un examen escrito, que representará el 100% de la calificación final y que incluirá la evaluación de las sesiones teóricas y prácticas con la misma ponderación que en la prueba escrita de la convocatoria ordinaria.

La calificación final de la asignatura en la convocatoria extraordinaria se calculará sumando las notas ponderadas obtenidas en el examen en las dos partes, en caso de que se haya alcanzado un mínimo de 5 puntos sobre 10 en ambas. En otro caso, la nota de la asignatura será el mínimo entre 4 y esa media ponderada.

De forma excepcional, si las condiciones sanitarias lo requieren, se podrán incluir métodos de evaluación no presencial. En cuyo caso, se informará al estudiantado de los cambios efectuados.

Evaluación diferenciada

Aquellos alumnos con derecho a evaluación diferenciada, serán evaluados del mismo modo que en las convocatorias extraordinarias.

Bibliografía básica

1. L. Arenas, Lógica Formal para Informáticos, Díaz de Santos, ISBN: 84-7978-240-4 (1996)
2. J. Cuena, Lógica Informática, Alianza Editorial
3. Cutland, N. J, Computability: An Introduction to Recursive Function Theory. Cambridge University Press.
4. Garey, M.R.; Johnson, D.S. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman & Company.
5. Kfoury, A. J., Moll, R. N., Arbib, M. A., A Programming Approach to Computability. Springer-Verlag, 1982.

Bibliografía complementaria

1. M. Ben-Ari, Mathematical Logic for Computer Science. Prentice-Hall
2. Huth, M.R.A., Ryan, M.D., Logic in Computer Science. Modelling and reasoning about systems. Cambridge University Press.
3. Kozen, D. C., Automata and Computability. Springer, 1997.
4. McNaughton, R. Elementary Computability, Formal Languages and Automata. Prentice-Hall
5. E. Burke and E. Foxley, Logic and Its Applications, Prentice Hall International, ISBN: 0130302635 (1996)