Esta versión de la guía docente es provisional hasta que no finalize el periodo de edición de las guías del nuevo curso.

Logo UAB

Teoría de la Computación

Código: 107891 Créditos ECTS: 6
2025/2026
Titulación Tipo Curso
Ingeniería Informática FB 1

Contacto

Nombre:
Joan Serra Sagrista
Correo electrónico:
joan.serra@uab.cat

Equipo docente

Joaquin Borges Ayats

Idiomas de los grupos

Puede consultar esta información al final del documento.


Prerrequisitos

Aviso sobre el idioma de impartición y las traducciones de la guía docente

En principio, el idioma de impartición de todos los grupos de esta asignatura es el catalán.

Se ofrecen traducciones automáticas de la guía docente al inglés y al castellano con fines informativos.

En caso de discrepancia o incoherencia entre las versiones en distintos idiomas, prevalecerá siempre la versión en catalán, como referencia oficial.

 

==

 

Aunque no hay prerrequisitos oficiales es fundamental que los alumnos tengan muy buen dominio de las nociones más básicas de las matemáticas, como:

 

-              Preservar la manipulación del lenguaje matemático

-              Preservar las demostraciones por inducción y por contradicción

-              Preservar la capacidad de abstracción

 

El alumnado que no tenga un mínimo bagaje de matemáticas previas tendrá que hacer un esfuerzo en preocuparse por resolver estas deficiencias.


Objetivos y contextualización

-              Ordenar las propiedades de los modelos formales en que se basan los ordenadores 

-              Identificar las posibilidades y los límites de la computación

-              Adquirir buenos hábitos de programación


Resultados de aprendizaje

  1. CM05 (Competencia) Integrar técnicas basadas en modelos computacionales en problemas de la informática
  2. KM09 (Conocimiento) Explicar procedimientos algorítmicos de la teoría computacional para la resolución de problemas de ingeniería informática
  3. SM13 (Habilidad) Aplicar conocimientos de autómatas, gramáticas y de complejidad computacional para la resolución de problemas

Contenido

1. Lenguajes formales y modelos abstractos de cálculo.

1.1. Alfabetos, palabras y lenguajes.

1.2. Problemas, lenguajes formales y modelos de cálculo.

1.3. Sistemas digitales.

1.4. Métodos de demostración.

 

2. Autómatas finitos y lenguajes regulares.

2.1. Autómatas finitos deterministas.

2.2. Autómatas finitos no deterministas.

2.3. Operaciones, expersiones y lenguajes regulares.

2.4. Minimización del número de estados internos.

2.5. Autómatas con salida.

 

3. Gramáticas independientes del contexto.

3.1. Introducción.

3.2. Definiciones. Generación de lenguajes.

3.3. Simplificación de gramáticas.

3.4. Formas normales de Chomsky y Greibach.

 

4. Autómatas con pila.

4.1. Descripción.

4.2. Aceptación por estado final y por pila vacía.

4.3. Autómatas con pila y lenguajes independientes del contexto.

4.4. Propiedades de los lenguajes independientes del contexto.

 

5. Máquinas de Turing.

5.1. Descripción del modelo básico.

5.2. Lenguajes y funciones calculables.

5.3. Variantes de la máquina de Turing.

5.4. Hipótesis de Church. Máquina de Von Neumann.

5.5. Máquinas de Turing como enumeradores.

 

6. Indecidibilidad.

6.1. Problemas y lenguajes decidibles e indecidibles.

6.2. Lenguajes recursivos y recursivamente enumerables.

6.3. Máquina universal de Turing y problemas indecidibles.

6.4. El problema de la correspondencia de Post y el problema del paro.

6.5. Ejemplos de lenguajes no recursivos.

 

7. Complejidad computacional.

7.1. Introducción. Tipos de problemas.

7.2.Clases de complejidad.

7.3. NP-Completasa,

7.4. Algunos problemas NP-Completos.

 


Actividades formativas y Metodología

Título Horas ECTS Resultados de aprendizaje
Tipo: Dirigidas      
Clases de Teoría y Problemas 50 2 CM05, KM09, SM13, CM05
Tipo: Supervisadas      
Ejercicios propuestos en clase 28 1,12 CM05, KM09, SM13, CM05
Tipo: Autónomas      
Estudio y preparación de las pruebas de evaluación 38,5 1,54 CM05, KM09, SM13, CM05
Preparación y trabajo autónomo 26 1,04 CM05, KM09, SM13, CM05

Las sesiones se impartirán según la tipología de Prácticas de Aula (PAUL): Discusión y realización de ejercicios y actividades en grupo o individuales.

 

La metodología docente está orientada al aprendizaje de la materia de forma continuada. Actividades que se desarrollarán a lo largo del curso:

Sesiones de teoría y problemas, donde el profesorado suministrará información sobre los conocimientos y sobre estrategias para adquirir, ampliar y organizarlos. Se fomentará la participación activa del alumnado. Se realizará un seguimiento del aprendizaje mediante el desarrollo individual y/o en grupo de actividades de validación y logro.

 

Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.


Evaluación

Actividades de evaluación continuada

Título Peso Horas ECTS Resultados de aprendizaje
Entrega de ejercicioys y/o actividades validación 30 3,5 0,14 CM05, KM09, SM13
Prueba Parcial 1 35 2 0,08 CM05, KM09, SM13
Prueba Parcial 2 35 2 0,08 CM05, KM09, SM13

Durante el curso se irán haciendo una serie de entregas de ejercicios y/o actividades de validación al final de cada uno de los temas. Las notas de estos ejercicios y/o actividades supondrán el 30% de la nota final. Esta parte de la nota NO será recuperable.

Habrá un examen (Primer Parcial = P_1) antes de medio semestre en el que se evaluará el trabajo realizado hasta ese momento. La nota de este examen aportará el 35% de la calificación final. Todos los estudiantes que hagan este examen ya no podrán ser calificados como NO EVALUABLE. Aquel estudiante que no haya hecho este examen constará como NO EVALUABLE a efectos académicos y no tendrá derecho a recuperarlo (excepto por causa debidamente justificada, en caso en que se permitirá hacer el examen de recuperación).

Al final del semestre habrá un segundo examen parcial (que decimos P_2) en el que se evaluarán los conocimientos impartidos tras el primer parcial. La nota de este examen aportará otro 35% de la calificación final. Aquel estudiante que no haya hecho este examen no tendrá derecho a recuperarlo (excepto por causa debidamente justificada, en caso en que se permitirá hacer el examen de recuperación).

Calificación:

Si la media de las notas (sobre 10) de los dos parciales M=(P_1+P_2)/2 es inferior a 2.5 el alumno ha suspendido la asignatura, con nota final M, sin derecho a ir al examen de recuperación. Si M es superior a 2,5 pero menor o igual 3.5 el alumno debe ir al examen de recuperación. Si M es superior o igual a 3,5 semillas si NF=0,7 M+ 0,3 S, (donde S es la nota media del libramiento de ejercicios y/o actividades de validación, sobre 10) es mayor o igual que 5 el alumno/a ha aprobado y tiene NF como nota final, en caso contrario debe ir al examen de recuperación. Si el alumno/a debe hacer el examen de recuperación, entonces si lanota de recuperación R, es inferior a 3.5, el alumno ha suspendido con nota final R; si R es superior o igual a 3,5 la nota final será min({0,7 R + 0,3 S},7) donde R es la nota del examen de recuperación (sobre 10). El uso de calculadora en los exámenes parciales y en el de recuperación no está permitido. Podrán obtener la calificación de Matrícula de Honor el 5% de las notas más altas siempre que: la nota de cada parcial no sea inferior a 9 y la nota NF descrita antes supere 9.1. Estas condiciones de evaluación serán iguales para todos los estudiantes matriculados en la asignatura, independientemente de si son de primera matrícula o si ya se habían matriculado en cursos anteriores. La decisión final sobre la calificación de MH la decidirá el profesorado.

Para cada actividad de evaluación, se indicará un lugar, fecha y hora de revisión en la que el estudiante podrá revisar la actividad con el profesorado. En este contexto, se podrán hacer reclamaciones sobre la nota de la actividad, que serán evaluadas por el profesorado responsable de la asignatura. Si el estudiante no se presenta a esta revisión, no se revisará posteriormente esta actividad. Las fechas de los exámenes parciales se publicarán en el Campus Virtual (CV) y pueden estar sujetas a posibles cambios de programación por motivos de adaptación a posibles incidencias; siempre se informará al CV sobre estos cambios ya que se entiende que el CV es el mecanismo habitual de intercambio de información entre profesor y estudiantes.

En esta asignatura, NO se permite el uso de ningún tipo de dispositivo digital en el aula (ni ordenadores, ni tablets, ni teléfonos móviles, ...); por consiguiente, no se perda el uso de tecnologíes de Inteligencia Artificial (IA) en el aula. Cualquier trabajo realizado en elaula que incluya fragmentos generados con IA será considerado una falta de honestidad académica y puede conllevar una penalización parcial o total en la nota de la actividad, o sanciones mayores en casos de gravedad. Se permite el uso de tecnologías de Inteligencia Artificial (IA) en las actividades autónomas fuera del aula. Sin perjuicio de otras medidas disciplinarias que se consideren oportunas y de acuerdo con la normativa académica vigente, las irregularidades cometidas por un estudiante que puedan conducir a una variación de la calificación se calificarán con un cero (0). Por ejemplo, plagiar, copiar, dejar copiar, tener dispositivos de comunicación (como teléfonos móviles, smart watches, etc.) en una actividad de evaluación, implicará suspender esta actividad de evaluación con un cero (0). Las actividades de evaluación calificadas de esta forma y por este procedimiento no serán recuperables. Si es necesario superar cualquiera de estas actividades de evaluación para aprobar la asignatura, esta asignatura quedará suspendida directamente, sin oportunidad de recuperarla en el mismo curso. La nota numérica del expediente será el valor menor entre 3.0 y la media ponderada de las notas en caso de que el estudiante haya cometido irregularidades en un acto de evaluación (y por tanto no será posible el aprobado por compensación). La evaluación de las competencias transversales está integrada en la rúbrica (o pauta de corrección de los problemas) de los exámenes parciales. La puntuación de los apartados de la rúbrica correspondientes a competencias transversales tiene un valor de entre el 5% y el 10% de la puntuación del problema correspondiente. Esta asignatura no contempla un tratamiento diferenciado por los estudiantes repetidores.
Esta asignatura no contempla el sistema de evaluación única.


Bibliografía

BIBLIOGRAFIA BÁSICA 

Borges, J.; Serra, J i Arqués, J. M. (1996). Teoria d’autòmats. Materials 28, Publicacions de la UAB.

BIBLIOGRAFIA COMPLEMENTARIA 

Casas, R. i Màrquez, L. (2000). Llenguatges, gramàtiques i autòmats. Curs bàsic. Aula teòrica 41, UPC.

Hopcroft, J. E.; Motwani, R. and Ullman, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley.

(https://docencia.eafranco.com/materiales/teoriacomputacional/books/TeoriaDeAutomatas,lenguajesYComputacion-Hopcroft.pdf)

Linz, P. (2001). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers.

Martin, J. C. (2004) [2003]. Lenguajes formales y teoría de la computación. McGraw-Hill Interamericana.


Software

No hay Prácticas de Laboratorio; en principio, no utilizaremos ningún software.


Grupos e idiomas de la asignatura

La información proporcionada es provisional hasta el 30 de noviembre de 2025. A partir de esta fecha, podrá consultar el idioma de cada grupo a través de este enlace. Para acceder a la información, será necesario introducir el CÓDIGO de la asignatura

Nombre Grupo Idioma Semestre Turno
(PAUL) Prácticas de aula 411 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 412 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 431 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 432 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 451 Catalán segundo cuatrimestre tarde
(PAUL) Prácticas de aula 452 Catalán segundo cuatrimestre tarde