Profesorado

Antonio J. Tomeu Hardasmal (coordinador)

Situación

Prerrequisitos

El alumno debería tener una madurez matemática razonable, resultado de
haber cursado y superado asignaturas de primer curso como Álgebra y
Matemáticas Discretas. Igualmente debería dominar el lenguaje C y ser
capaz de implementar código que simule modelos de pequeña complejidad.
El conjunto de prerrequisitos se concretar en los siguientes apartados:

a) Dominio de los conceptos básicos de teoría de conjuntos.
b) Dominio de técnicas básica de demostración: inducción, reducción al
absurdo.
c) Dominio de aritmética modular básica.
d) Dominio de la teoría de grafos básica.
e) Soltura con el uso del compilador del lenguaje C
f) Capacidad de simulación e implementación en C de pequeños modelos.

Contexto dentro de la titulación

Troncal de segundo curso.

Recomendaciones

Se hacen al alumno las siguientes recomendaciones:

1) Más vale un mal libro que muchos buenos apuntes: por tanto, para
cada tema concreto del curso se le propondrán como material de
revisión/trabajo/estudio un mínimo de dos y un máximo de cuatro
capítulos de referencias concretas (en inglés, claro está). También se
le proporcionarán unos apuntes (en castellano), que como mucho debería
usar como material de apoyo, pero nunca como texto base.

2) La copia de apuntes en clase ES UNA PÉRDIDA DE TIEMPO: por tanto,
como profesor haré lo posible para que no tenga que copiar apuntes en
clase, proporcionándole en la página de la asignatura con carácter
previo a su explicación todo el material necesario para la preparación
de la misma. En consecuencia, si copia apuntes, es porque es usted un
copiador compulsivo; pero sepa que distraen su atención y suelen ser
fuente de errores en el estudio posterior, ya que lo que se copia mal
se estudia peor.

3) Una clase comienza antes de ser explicada y continua tras ser
explicada: o lo que es lo mismo, llegar a clase a ver qué nos cuenta
hoy este buen señor es un error. La mecánica de trabajo que les
recomiendo a lo largo del curso para preparar una clase debe seguir
las siguientes fases:

1. Lectura y revisión previa de los materiales indicados en el
cronograma del curso para esa clase en concreto. Dicho cronograma
estará disponible en la página virtual del curso cuando comience este.
En él se establecerá la fecha (aproximada) donde se impartirá cada
tópico del temario oficial, el material de lectura para esa clase en
concreto, los problemas recomendados para ejercitar los contenidos
teóricos explicados, y en ocasiones alguna tarea adicional de interés.

2. Asistencia a clase. Dado que no necesita tomar apuntes, preste
atención a los desarrollos y explicaciones del profesor, y
relaciónelos con lo previamente leído por usted. Tome notas de la
dudas o discrepancias que le surjan, para su posterior discusión en la
propia clase o en una tutoría individualizada.

3. Tras la clase, repase los contenidos de la misma, entiéndalos y
aclare con el profesor los conceptos que no estén claros. Póngalos en
práctica con los problemas de la relación que corresponda, y
conéctelos con los contenidos a desarrollar en la próxima clase. Es
decir, GO TO apartado 1.

3) Una asignatura NO se prepara en una semana. NO deje la preparación
del mismo para los últimos días. Probablemente será inútil. Pida ayuda
a su profesor para planificar el tiempo y su preparación de cara al
examen final  con antelación. Si no lo hace, el único perjudicado será
usted.

5) Saber una asignatura NO es saber unos apuntes. Unos apuntes son,
probablemente y en el mejor de los casos, un resumen de lo explicado
por el profesor en clase, lo cual a su vez será un resumen de lo
revisado por el profesor en la bibliografía específica. Por tanto,
olvide aquello de "me sé los apuntes pero me han suspendido", o "esto
no estaba en los apuntes, sino en tal libro" o "este problema no se
parece a  ninguno que hayamos hecho en clase". Si usted  SABE la
materia, estará preparado para aplicarla a situaciones nuevas y
desconocidas. Y ello pasa por haber manejado bibliografía
tal y cómo se indica en el criterio 1. Saber los apuntes es una
condición necesaria para aprobar, pero no suficiente. Por tanto, si
usted sabe sus apuntes, NO SABE la materia. Y recuerde que SABER no es
MEMORIZAR.

6) La revisión de calificaciones NO es una subasta. La directriz que
debe motivarle a solicitar y revisar sus calificaciones es saber
DÓNDE, CÓMO Y POR QUÉ ha fallado, y PLANIFICAR con su profesor la fase
posterior de estudio orientada a subsanar esos fallos. Por tanto, por
favor, no acuda a revisión con la intención de discutir sobre:

1. Los criterios de corrección, ya que estos los define su
profesor, y no es ni puede ser algo sujeto a negociación.

2. La distribución de la puntuación entre los diferentes
enunciados de los ejercicios del examen, ya que su profesor sabe qué
es más importante que usted haya aprendido, y cómo evaluar ese
aprendizaje, y ajustará esa distribución en consecuencia. El que
considere que esa distribución le perjudica es un error, ya que habrá
sido aplicada por igual a sus compañeros, y además lo que hará será
demostrar que no tiene claros aquellos conceptos que son más
relevantes.

3. Lo parecido o distinto de los ejercicios del examen a los
realizados en clase. (Ver principio 5)  Un examen no tiene por qué
parecerse a lo ya ejercitado. Los ejercicios de clase  le CAPACITAN
para dominar los conceptos. Los exámenes DEMUESTRAN que usted sabe
aplicar esos conceptos aprendidos a situaciones novedosas o
simplemente diferentes a las estudiadas.

4. La verificación de si determinado ejercicio estaba o no en sus
apuntes (Ver principio 5)

5. La simple pataleta por no haber superado la asignatura. No
entienda un suspenso más que con la siguiente lectura: el trabajo
realizado ha sido válido, pero no suficiente. Debe trabajar más.
Cualquier otra interpretación por su parte es un error (Ver principio
10)

7) Procure estar informado. Visite con asiduidad la sección de
noticias del web de la asignatura y en caso de duda consulte por e-
mail a su profesor. No utilice argumentos de "no sabía nada..." o "no
me he enterado de que.." para excusar un fallo. Recuerde que ES su
obligación y su responsabilidad  estar enterado.

8) Utilice la tutoría. Es el único medio por el cual el profesor puede
ofrecerle una enseñanza de carácter individualizado. Por tanto,
aproveche la tutoría, en sus versiones presencial, electrónica, o vía
el foro de la asignatura. Y hágalo con frecuencia: siga el método
descrito en el principio 3 y visite a su profesor cada vez que tenga
dudas. Con carácter ordinario, un mínimo de una visita al profesor
cada tres semanas debería ser normal para usted. Si hay dificultades,
tan a menudo como necesite.

9) NO se quede con una duda. Es muy habitual entre nuestros alumnos
que cuando les surge una duda se queden con ella hasta el mismo
momento del examen. Luego, durante la revisión reconocen: "sí, esto no
me quedó claro, pero..." EVITE estos comportamientos. En una
asignatura como esta, el progreso con garantías hacia nuevos
contenidos implica haber asimilado correctamente los contenidos
previos.
10) El profesor es su juez, NO es su verdugo. Mi labor en el momento
de evaluarle se limitará a juzgar la cantidad y calidad del esfuerzo
realizado por usted. Cualquier otro aspecto es irrelevante.

11) Participe en clase. Plantee sus dudas, y fomente la discusión
entre sus compañeros y con el profesor. Ello contribuirá de forma
positiva a su evaluación continua, y hará la dinámica académica más
rica. Además, contribuirá positivamente a su crecimiento personal.

Competencias

Competencias transversales/genéricas

- Análisis y síntesis de contenidos técnicos
- Lectura comprensiva y escritura comprensible
- Determinación del ámbito de la solución de un problema
- Elección del nivel de abstracción de solución de un problema
- Capacidad de planificación temporal de tareas
- Elaboración de juicios críticos sobre contenidos
- Capacidad de elaborar documentación técnicamente correcta

Competencias específicas

• Cognitivas(Saber):

  -Dominar la terminología específica de la materia.
  -Conocer el concepto de función computable.
  -Conocer el concepto de función recursiva, clase PRC.
  -Conocer el Teorema de Universalidad y sus implicacioes.
  -Dominar el diseño de Máquinas de Turing.
  -Conocer el  otros modelos de computación y su imbricación en el
  ámbito de la Tesis de Church.

• Procedimentales/Instrumentales(Saber hacer):

  -Manejar con competencia un cuerpo bibliográfico mínimo (3-4
  referencias) como fuente de apoyo al aprendizaje de la materia.
  -Redactar correctamente documentación de contenido técnico de
  acuerdo a formatos predefinidos
  -Demostrar la computabilidad de funciones de complejidad media
  -Demostrar la recursividad primitiva de funciones de complejidad
  media .
  -Utilizar software de simulación de propósito específico (JFLAP,
  ILC y otros) como herramientas de ayuda en las tareas
  anteriores.
  -Utilizar software de propósito general (compilador de C) como
  herramienta para simular máquinas de Turing o Redes Neuronales.

• Actitudinales:

  -Autoaprendizaje e independencia de criterio.
  -Conciencia crítica sobre el trabajo propio bien hecho.
  -Conciencia de la necesidad del esfuerzo y el trabajo personal como
  medio de lograr los objetivos fijados.
  -Conciencia de la necesidad de cumplir con las obligaciones en
  materia de asistencia, trabajo personal, rendimiento y espíritu
  universitario que la legislación universitaria actualmente en vigor
  impone a sus alumnos.

Objetivos

La asignatura plantea el estudio de lo que se podrían denominar
fundamentos de la computación, en el sentido de que determinan por qué
existen, por qué son programables, y cuáles son los límites de las
computadoras modernas. Los conocimientos adquiridos por el alumno deberán
permitirle:

1. Conocer el concepto de funciones parcial y totalmente computables. En
particular, ser capaz de escribir L-programas que calculen a funciones
propuestas concretas.
2. Saber aplicar los conceptos de configuración y configuración sucesora.
En particular, dado un L-programa y sus datos de entrada, ser capaz de
calcular la computación completa inducida por ellos.
3. Saber expandir macros a efectos de lograr L-programas básicos
4.  Conocer el concepto de predicado. Utilizarlos para diseñar sentencias
de bifurcación condicional.
5.  Saber obtener nuevas funciones computables mediante composición
funcional y recursión primitiva.
6. Conocer el concepto de clase PRC. Saber determinar si una clase de
funciones es o no PRC.
7. Saber demostrar si una función es o no recursiva primitiva.
8. Conocer y utilizar las operaciones iteradas y los cuantificadores
acotados para realizar demostraciones.
9. Saber aplicar la minimización no acotada para definir nuevas funciones.
10. Conocer los Teoremas de la Forma Normal y sus implicaciones
11. Conocer y saber aplicar las técnicas de codificación y decodificación
numérica descritas mediante las funciones de emparejamiento y de Gödel.
12. Saber codificar y decodificar L-programas.
13. Ser capaz de interpretar el problema de la parada como ejemplo de
problema no computable.
14. Conocer el concepto de problema indecidible, y determinar si un
problema lo es para casos sencillos.
15. Conocer el concepto de función universal. Determinar la computabilidad
de las funciones universales y su importancia como marco subyacente del
concepto de programabilidad.
16. Conocer el concepto de conjunto recursivo y recursivo enumerable. En
particular, y dado un conjunto, saber clasificarlo en una de las dos
categorías mediante una demostración
17. Conocer el concepto de máquina de Turing. Conocer el concepto de
función Turing-computable.
18. Saber escribir máquinas de Turing en sus versiones de cuadruplas, de
cuadruplas no deterministas y de quintuplas que calculen a funciones
computables.
19. Conocer la estructura y funcionamiento de una máquina universal de
Turing.
20. Conocer el concepto de máquina URM. Ser capaz de probar la urm-
computilidad de funciones.
21. Conocer el concepto de autómata celular, su clases de  comportamiento
y su papel en la teoría de la Computabilidad.
22. Conocer el concepto de red de neuronal y los principios básicos de
utilización en problemas de pattern-matching.
23. Conocer la Tesis de Church-Turing, su interpretación, y el papel que
juega en el ámbito de la Teoría de la Computabilidad.

Programa

Programa Teórico

Tema 1 : Modelo de Funciones Computables. (4 horas)
1.1 Un modelo de programación.
1.1.1 Variables, etiquetas e instrucciones.
1.1.2 Construcción de programas.
1.2 Ejemplos de programas.
1.2.1 Programa para el cálculo de la función identidad.
1.2.2 Programa para el cálculo de la función suma.
1.2.3 Programa para el cálculo de la función resta.
1.2.4 Programas para calcular otras funciones.
1.3 Funciones parcial y totalmente computables.
1.3.1 Concepto de función parcialmente computable.
1.3.2 Concepto de función totalmente computable.
1.4 Predicados.
1.4.1 Predicados como funciones bivaluadas en el dominio {0,1}.
1.4.2 Computabilidad de predicados.
1.5 Macros.
1.5.1 Concepto de macro.
1.5.2 Renombrado de variables y etiquetas.
1.5.3 Utilización de macros.

Tema 2 : La Jerarquía de Funciones. (12 horas)
2.1 Composición de funciones.
2.1.1 Definición.
2.1.2 Teorema de composición.
2.1.3 Ejemplos.
2.2 Funciones definidas recursivamente.
2.2.1 Definición.
2.2.2 Teorema de recursión.
2.2.3 Ejemplos.
2.3 Funciones iniciales.
2.3.1 Definición de las funciones  .
2.3.2 Computabilidad de las funciones iniciales.
2.4 Clases PRC.
2.4.1 Definición de clase PRC.
2.4.2 Definición de funciones recursivas-primitivas.
2.4.3 Computabilidad de las funciones recursivas primitivas.
2.5 Algunas funciones recursivas primitivas.
2.5.1 Función suma.
2.5.2 Función producto.
2.5.3 Función factorial.
2.5.4 Función potencia.
2.5.5 Función predecesor.
2.5.6 Función resta restringida.
2.5.7 Función valor absoluto.
2.5.8 Función de negación.
2.6 Predicados recursivos primitivos.
2.6.1 Negación de predicados recursivos primitivos.
2.6.2 Disyunción de predicados recursivos primitivos.
2.6.3 Conjunción de predicados recursivos primitivos.
2.6.4 Teorema de definición por casos.
2.7 Operaciones Iteradas y cuantificadores acotados.
2.7.1 Definición de las operaciones iteradas.
2.7.2 Los predicados para todo y existe en versión acotada.
2.7.3 Ejemplos definidos en términos de los elementos anteriores.
2.8 Minimización.
2.8.1 Definición de la función mínimo acotado.
2.8.2 Ejemplos de funciones definidas sobre el mínimo acotado.
2.8.3 Minimización no acotada.
2.8.4 Teorema de la Forma Normal.
2.9 Funciones de apareamiento y números de Gödel.
2.9.1 Definición de la función de apareamiento.
2.9.2 Teorema de la función de apareamiento.
2.9.3 Definición de la función de codificación de Gödel.
2.9.4 Teorema de la secuencia de números.

Tema 3 : Universalidad. (6 horas)
3.1 Codificación de programas mediante números.
3.1.1 Codificación de etiquetas, variables e instrucciones.
3.1.2 Codificación de programas.
3.2 El problema de la parada.
3.2.1 Problemas no computables.
3.2.2 Problema de la parada.
3.2.3 Conjetura de Goldbach.
3.3 Teorema de Universalidad.
3.3.1 Funciones universales.
3.3.2 Teorema de Universalidad.
3.3.3 Teorema contador de pasos.
3.4 Conjuntos recursivamente enumerables.
3.4.1 Definición.
3.4.2 Operaciones de conjuntos sobre conjuntos r.e.
3.5 Conjuntos recursivos.
3.5.1 Definición.
3.5.2 Relación entre los conjuntos r.e. y los conjuntos recursivos.
3.5.3 Teorema de enumeración.
3.5.4 Existencia de conjuntos r.e. pero no recursivos.
3.6 Teorema del parámetro.
3.6.1 Proposición del teorema.
3.6.2 Utilidad práctica.
3.7 Teorema de recursión.
3.7.1 Proposición del teorema.
3.7.2 Utilidad práctica.
3.7.3 Consecuencias: el teorema del punto fijo.
3.8 Teorema de Rice.
3.8.1 Familias de funciones.
3.8.2 Conjuntos índice.
3.8.3 Teorema de Rice.
3.8.4 Utilidad práctica.

Tema 4 : Máquinas de Turing. (4 horas)
4.1 Definición y modelo.
4.1.1 Alfabeto, estados internos y funciones de transición.
Cuadruplas.
4.1.2 Relación funciones computables-máquinas de Turing.
4.1.3 Ejemplos de máquinas de Turing.
4.2 Técnicas de diseño.
4.2.1 Necesidad de las técnicas.
4.2.2 Almacenamiento en el control finito.
4.2.3 Shifting-over.
4.2.4 Speed-Up.
4.3 Modelos alternativos.
4.3.1 Máquinas de varias pistas.
4.3.2 Máquinas de varias cintas.
4.3.2 Máquinas de quintuplas.
4.3.4 Equivalencia de modelos.
4.3.5 Equivalencia formal entre los distintos modelos.
4.4 Máquinas universales.
4.4.1 Proposición de un modelo de máquina de Turing universal.
4.4.2 Consecuencias teóricas.
4.5 Tesis de Church.
4.6 Otros Modelos de Computacion.
4.5.1 Lenguajes de Post.
4.5.2 Computación con Modelos de ADN.
4.5.3 Computación con Autómatas Celulares.
4.5.4 Computación URM.
4.5.5 Modelos de Computación en los Números Reales.
4.5.6 Redes Neuronales.


Programa de Prácticas

Dado el carácter netamente teórico de la asignatura, las prácticas se
centrarán en el uso de algunos de los siguientes simuladores: de máquinas
URM,
de máquinas de Turing, de autómatas celulares y del simulador ILC. Es
posible
también la realización de alguna práctica de programación en lenguaje C
sobre
los contenidos de la asignatura.

Actividades

ASIGNATURA EN EXTINCIÓN SIN ACTIVIDADES DOCENTES

Metodología

ASIGNATURA EN EXTINCIÓN SIN ACTIVIDADES DOCENTES

Distribución de horas de trabajo del alumno/a

Nº de Horas (indicar total): 87.5

• Clases Teóricas: 30  
• Clases Prácticas: 15  
• Exposiciones y Seminarios:  
• Tutorías Especializadas (presenciales o virtuales):
  • Colectivas:  
  • Individules:  
• Realización de Actividades Académicas Dirigidas:
  • Con presencia del profesorado:  
  • Sin presencia del profesorado:  
• Otro Trabajo Personal Autónomo:
  • Horas de estudio: 40.5  
  • Preparación de Trabajo Personal:  
  • ...
     
• Realización de Exámenes:
  • Examen escrito: 2  
  • Exámenes orales (control del Trabajo Personal):  

Criterios y Sistemas de Evaluación

CRITERIOS DE EVALUACIÓN

A) DEL EXAMEN TEÓRICO
-El examen teórico se calificará de cero a diez puntos. Se obtiene
Aprobado con una calificación igual o superior a cinco puntos.
-Cada enunciado incluirá la calificación que se le atribuye entre
corchetes.
-Una pregunta teórica o problema se considera correcto únicamente si la
solución que se proporciona es completamente correcta. En otro caso se
considera incorrecta.
-Una pregunta teórica o problema de múltiples apartados se considera
correcto si todos los apartados que lo conforman son correctos. En
cualquier otro caso es incorrecto y no puntúa.

TÉCNICAS DE EVALUACIÓN

a)Examen Final Teórico de la Asignatura: conteniendo preguntas teóricas
cortas y/o problemas, con un tiempo de duración nunca superior a las 3
horas. Al comienzo del mismo, el alumno dispondrá de 15 minutos para
realizar las consultas que estime oportunas sobre sus apuntes y/o material
bibliográfico, y realizar las anotaciones que estime pertinentes. El resto
del tiempo de duración de la prueba transcurrirá sin acceso a material
alguno.

SISTEMA DE EVALUACIÓN
a) La calificación final de la asignatura vendrá determinada por la
calificación obtenida en el examen final teórico.

Recursos Bibliográficos

BIBLIOGRAFÍA BÁSICA

[Alf07] Alfonseca, A., Alfonseca, M. y Moriyón, R. Teoría de Autómatas y
Lenguajes Formales. McGraw-Hill, 2007.

[Bro93] Brookshear, J. Teoría de la Computación: lenguajes formales,
autómatas
y complejidad. Addison-Wesley Iberoamericana, 1993.

[Cut94] Cutland, N.J. Computability: An Introduction to Recursive Function
Theory . Cambridge University Press, 1994.

[Dav94] Davis, M., Sigal, R. and Weyuker, E. Computability, Complexity and
Languages. Academic Press, 1994.

[Dav02] Davis, M. La Computadora Universal. Ed. Debate, 2002.

[Hop79] Hopcroft, J. and Ullman, J. Introduction to Automata Theory,
Languages
and Computation. Addison-Wesley, 1979.

[Hop02] Hopcroft, J.;  Ullman, J. & Motwani, R. Introducción a la Teoría
de
Autómatas, Lenguajes y Computación. (2ª ed.). Addison-Wesley, 2002.

[Gar79] Garey, M and Johnson, D. Computers and Intractability: a guide to
the
theory of NP-completness. New York, Freeman, 1979.

[Lee90] Leeuwen, J. V. (ed.) Handbook of Theoretical Computer Science.
Elsevier, 1990.

[Pen90] Penrose, R.. La Nueva Mente del Emperador. Ed. Mondadori, 1990.

[San90] Sancho, J. Lógica Matemática y Computabilidad. Díaz de Santos,
S.A.,
1990.

BIBLIOGRAFÍA DE CONSULTA

[Aho92] Aho, A. and Ullman, J.D. Foundations of Computer Science. W. H.
Freeman and Company. New York, 1992

[Cal88] Calude, C. Theories of Computational Complexity. North-Holland,
1988.

[Car89] Carroll, J. and Darrell, L. Theory of Finite Automata with an
Introduction to Formal Languages. Englewood Cliffs, NJ. Prentice Hall,
1989.

[Coh91] Cohen, D. Introduction to Computer Theory. John Wiley and Sons,
Inc.
1991.

[Deh93] Dehornoy, P. Complexite et decidabilite. Springer-Verlag, 1993.


[Fer95] Fernández, G. y Sáez, F. Fundamentos de Informática: lógica,
autómatas, algoritmos y lenguajes.  Anaya Multimedia, 1995.

[Jon97] Jones, N. D. Computability and Complexity. The MIT Press, 1997.

[Lew91] Lewis, H and Papadimitriou, C. Elements of the Theory of
Computation.
Englewood Cliffs, NH. Prentice Hall, 1991.

[Mar91] Martin, J. Introduction to Languages and the Theory of
Computation.
New York, McGraw-Hill, 1991.

[Mcn82] McNaughton, R. Elementary Computability, Formal Languages and
Automata. Prentice Hall, 1982.

[Rev83] Revesz, G. Introduction to Formal Languages. McGraw-Hill, 1983.

[Som88] Sommerhalder, R. and Van Westerhenen S. C. The Theory of
Computability : Programs, Machines, Effectiveness and Feasibility. Addison-
Wesley, 1988.

[Sud88] Sudkamp, T. Languages and Machines, An Introduction to the Theory
of
Computer Science. Addison-Wesley Series in Computer Science. Readin, MA.
Addison-Wesley Inc 1988.

[Wil86] Wilf, H.S. Algorithms and Complexity. Prentice-Hall, 1986.

[Woo87] Wood, D. Theory of Computation, New York, John Wiley & Sons, 1987.