Antonio J. Tomeu Hardasmal (coordinador)

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. Dado lo
anterior, los objetivos a cubrir serán:

a)Introducir el concepto de función computable y de máquina de Turing como
correlato formal de la noción de algoritmo.
b) Establecer la programabilidad de las computadoras modernas como una
consecuencia directa de la demostración de la existencia de funciones
universales y del Teorema de Universalidad.
c) Presentar las nociones de computabilidad, decidibilidad, incompletitud y
consistencia en el marco de los sistemas formales que determinan los
principios de diseño de las computadoras digitales, y derivar de ellas aspectos
como la iteración infinita o los problemas no computables.
d) Establecer los límites de la Computación, con independencia de la potencia,
fiabilidad y tecnología de base que el soporte tecnológico utilizado ofrezca,
utilizando para ello el marco que la Tesis de Church establece.
e) Introducir el concepto de red neuronal como herramienta de utilidad en
problemas de pattern matching.

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 : Funciones Computables y Recursivas. (8 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. (8 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. (6 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.5.1 Lambda cálculo de Church.
4.5.2 Máquinas RAM.
4.5.3 Autómatas Celulares.
4.5.4 Lenguajes de Post.
4.5.5 Tesis de Church.

Tema 5 : Conceptos Básicos en Redes Neuronales. (4 horas)
5.1 Conceptos de fisiología neuronal básica.
5.1.1 Neuronas.
5.1.2 Potenciales de acción.
5.1.3 Sinapsis interneuronal.
5.2 La neurona formal de McCulloch-Pitts.
5.2.1 Funciones de activación sigmoide y tangente hiperbólica.
5.2.2 El perceptrón de Rosenblatt.
5.2.3 Aprendizaje Hebbiano.
5.3 Descripción matemática de redes neuronales.
5.3.1 Campos de neuronas.
5.3.2 Descripción matricial de los campos.
5.3.3 Matrices de conexión sináptica.
5.4 Memorias Asociativas.
5.4.1 Memorias asociativas bidireccionales (BAM).
5.4.2 Redes de Hopfield.


Programa de Prácticas

Dado el carácter netamente teórico de la asignatura, las prácticas se
centrarán en la resolución de problemas graduados en dificultad que ilustren,
amplíen y afiancen los conceptos principales del temario teórico. En
particular, incluirán aspectos como: resolución de problemas de
Computabilidad, y uso de simuladores de máquinas URM, de máquinas de Turing y
del simulador ILC. La planificación -tentativa- prevista establece la siguiente
distribución temporal:

Problemas: 5 horas.
Simulación: ICL, máquinas de Turing y máquinas URM: 10 horas
-Trabajando con ILC
-Macros con ILC
-Trazando Computaciones con ILC
-Programando con ILC
-Composición Funcional con ILC
-Recursión Primitiva con ILC
-Universalidad con ILC
-Máquinas de Turing con JFLAP
-Applet Simulador de Neurona Artificial

-Clases teóricas.
-Clases de problemas.
-Clases de laboratorio.

En los contenidos teóricos se insistirá en el uso de una metodología orientada
al razonamiento formalizado y simbólico con el objeto de desarrollar en el
alumno sus capacidades deductivas y de abstracción. Dichos contenidos se
cubrirán por tanto mediante clases teóricas basadas en un esquema expositivo
formal. Los contenidos prácticos, en cambio, recibirán un enfoque totalmente
diferente, y estarán orientados hacia la resolución de relaciones de
problemas, visitas a páginas web afines a la disciplina, y a la utilización de
simuladores de los modelos explicados durante el curso.

El alumno dispondrá de cronogramas de teoría y prácticas orientativos, donde se
recogerá, al menos, la siguiente información:
a) Fecha prevista para impartir cada tópico concreto del programa.
b) Material de lectura mínimo recomendado para preparar la clase.
c) Conjunto de lecturas y ejercicios para consolidar el tópico de que se trate
d) Fechas de interés: entrega de asignaciones, exámenes, etc.

La evaluación tendrá en cuenta los siguientes componentes:

a)Examen Final de la Asignatura: conteniendo preguntas teóricas cortas y
problemas, con un tiempo de duración nunca superior a las 3 horas, y durante
el cual se permite al alumno el uso de apuntes de clase y bibliografía
libremente. La Convocatoria Oficial se hará pública en el tablón del
Departamento, en la página web de la asignatura, y en el Campus Virtual de la
misma.
b)Asignaciones de Prácticas: se plantearán asignaciones de prácticas que
el alumno resolverá mediante los simuladores adecuados, remitiendo los
ficheros solución resultantes al profesor en la fecha y forma que este
determine. Su realización es obligatoria. Su calificación, consideradas
globalmente será de APTO o NO APTO.

La calificación final de la asignatura vendrá determinada por la calificación
obtenida en el examen final,siempre que se haya obtenido APTO en prácticas.

El alumno debe conocer además que la evaluación se regirá por las siguientes
normas adicionales:

1)La entrega de las asignaciones de prácticas en la fecha, hora y formato de
entrega determinados por el profesor es obligatoria para superar la asignatura.
Se admitirá un retraso de hasta 24 horas sobre la fecha
prevista de entrega, pero minorando la calificación en un 20%. Entregas fuera
de este plazo no se admitirán, y la calificación otorgada será de cero puntos.
En caso de enfermedad o fuerza mayor documentalmente justificadas, el profesor
indicará al alumno nueva fecha de entrega.
2)Es necesario tener superadas las prácticas para poder aprobar la
asignatura.
3)La calificación de las prácticas será de APTO o NO APTO. En este
último caso el alumno deberá concurrir a un examen práctico de acuerdo a
convocatoria hecha pública por el Centro, de duración no mayor de 90 minutos
en el que se permitirá el uso de apuntes y material bibliográfico. El
resultado del citado examen será igualmente de APTO o NO APTO.
4)Los exámenes finales de Junio y Septiembre se regirán por los
Estatutos de la Universidad de Cádiz en cuanto a número de convocatorias y
días de revisión de calificaciones se refiere.
5)A toda convocatoria se acude con el temario completo (tanto teórico como
práctico). No se reservarán calificaciones de partes de la asignatura para
convocatorias sucesivas.
6)Para lo no contemplado en estas notas se estará a lo dispuesto en el
Reglamento de Régimen Académico y Evaluación del Alumnado de la Universidad de
Cádiz.

BIBLIOGRAFÍA BÁSICA

[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.