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

-Clases teóricas.
-Clases prácticas.

Metodología

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, con asistencia ocasional de medios audiovisuales.

Los contenidos prácticos, en cambio, recibirán un enfoque totalmente
diferente, y estarán orientados hacia la resolución de relaciones de
problemas y a la utilización de simuladores de los modelos explicados durante
el curso.

Con frecuencia semanal o bisemanal el alumno se enfrentará a la resolución de
un conjunto de ejercicios prácticos, que juntos constituyen una asignación (o
entregable) de prácticas, que será puesto a disposición del profesor únicamente
por los medios electrónicos que la plataforma virtual de la UCA oferta.
Su realización y entrega es obligatoria.

Semanalmente el profesor hará público en el Campus Virtual el conjunto completo
de actividades en aula y fuera de ella que el alumno debe desarrollar para una
correcta compresión de los contenidos que se van a impartir en la semana,
incluyendo:

a) Fecha prevista para algunos tópicos 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) Actividades complementarias de interés.

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):  

Técnicas Docentes

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.


B) DEL EXAMEN PRÁCTICO
-Se realizará en ordenador.
-El examen práctico se calificará con APTO O NO APTO. Se obtiene APTO cuando al
menos el 50% de los enunciados del examen son correctos.
-Las condiciones que una solución a un enunciado de examen debe cumplir para
ser considerada correcta son:
a) Los ficheros subidos a través del Campus Virtual que conforman el examen
práctico se ajustan al número, formato y nomenclatura de nombres
explicitados por el profesor en el documento de examen.
b)El contenido de los ficheros es el especificado por el profesor en el
documento de examen.
c)Para ficheros elaborados con JFLAP (en su caso), se pueden abrir y procesar
con el software citado, y realizan un procesamiento técnicamente correcto,
según el enunciado de que se trate.
d)Para ficheros elaborados en lenguaje C (en su caso), la compilación y
ejecución son correctas, y el procesamiento es técnicamente correcto, según el
enunciado de que se trate.


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.

b)Examen Final de Prácticas: contendrá enunciados similares a los desarrollados
durante las prácticas de la asignatura que el alumno resolverá mediante los
simuladores adecuados o los programas que deban desarrollarse, remitiendo los
ficheros solución junto con los documentos que se  especifiquen en los
enunciados al profesor a través del campus virtual. Su duración no será mayor
de 90 minutos. No se permitirá el uso de material alguno durante su realización.

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,siempre que se haya obtenido
APTO en el examen final de prácticas y se hayan entregado todas las
asignaciones de prácticas. Si superándose el examen teórico no se supera el
examen práctico, la calificación final será de 4 puntos.

b)El examen final práctico no será corregido si no se supera el examen final
teórico.

c)Aquél alumno que obtenga NO APTO (menos del 50% de enunciados resueltos
correctamente) en el examen práctico pero supere el 30% podrá compensar la
diferencia y obtener APTO mediante las asignaciones de prácticas que se habrán
ido entregando durante el curso con carácter obligatorio, siempre que se cumpla
el siguiente criterio: todas las asignaciones han sido entregadas y al menos el
70% de las mismas estén bien resueltas.

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

1)La entrega de TODAS las asignaciones de prácticas propuestas en la fecha, hora
y formato de entrega determinados por el profesor es OBLIGATORIA. Si se
dejan sin entregar asignaciones sin causa justificada, no podrá
obtenerse APTO en el Examen Final de Prácticas. En caso de no entregar una
asignación por enfermedad o causa de fuerza mayor documentalmente justificadas,
el profesor indicará al alumno nueva fecha de entrega. Para las convocatorias
de Junio y Septiembre, se habilitará un período de entrega de prácticas
atrasadas a los mismos efectos.

2)Los exámenes finales de Febrero, Junio y Septiembre se regirán por los
Estatutos de la Universidad de Cádiz y normativa derivada en cuanto a número de
llamamientos y días de revisión de calificaciones se refiere.

4)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.

5)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.

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.