Última actualización: 01/07/2021


Curso Académico: 2021/2022

Teoría Avanzada de la Computación
(18294)
Titulación: Grado en Matemática Aplicada y Computación (362)


Coordinador/a: ALONSO WEBER, JUAN MANUEL

Departamento asignado a la asignatura: Departamento de Informática

Tipo: Optativa
Créditos: 6.0 ECTS

Curso:
Cuatrimestre:




Requisitos (Asignaturas o materias cuyo conocimiento se presupone)
Teoría de Autómatas y Lenguajes Formales (Curso 2 / Cuatrimestre 1) Matemática Discreta (Curso 1 / Cuatrimestre 2)
Competencias y resultados del aprendizaje
Descripción de contenidos: Programa
Contenidos relevantes: - Coste Computacional de Programas Estructurados y Recursivos - Computabilidad y Decidibilidad - Máquinas de Turing multicinta, no deterministas - Reducción entre problemas - Clases de Complejidad P, NP, NP-Completo y NP-Hard - Otros Modelos de Computación 1. Coste Computacional de los Algoritmos. 1.1 Coste y Complejidad Computacional 1.2 Coste Computacional de Programas Estructurados 1.3 Coste Computacional de Programas Recursivos. 1.4 Análisis Probabilístico de Coste Computacional 2. Introducción a la Teoría de la Computabilidad 2.1 Definición de Problema. Problemas de decisión. 2.2 Máquinas de Turing y Decibilidad 2.3 Computabilidad y Decibilidad 3. Introducción a la Teoría de la Complejidad Computacional 3.1 Reducción entre problemas 3.2 Clases P, NP y NP-Completo 3.3 Clases PSpace, NPSpace 3.3 Clases NP-Hard, Exp, CoP, CoNP 4. Modelos de Computación 4.1 Máquinas de Turing (multicinta, no deterministas) 4.2 Lambda Calculus 4.3 Autómatas Celulares 4.4 Lindenmayer Systems
Actividades formativas, metodología a utilizar y régimen de tutorías
CLASES TEÓRICO-PRÁCTICAS [44 horas con un 100% de presencialidad, 1.67 ECTS] Conocimientos que deben adquirir los alumnos. Estos recibirán las notas de clase y tendrán textos básicos de referencia para facilitar el seguimiento de las clases y el desarrollo del trabajo posterior. Se resolverán ejercicios, prácticas problemas por parte del alumno y se realizarán talleres y prueba de evaluación para adquirirlas capacidades necesarias. TUTORÍAS [4 horas con un 100% de presencialidad, 0.15 ECTS] Asistencia individualizada (tutorías individuales) o en grupo (tutorías colectivas) a los estudiantes por parte del profesor. TRABAJO INDIVIDUAL O EN GRUPO DEL ESTUDIANTE. [98 horas con 0% de presencialidad, 3.72 ECTS] TALLERES Y LABORATORIOS. [8 horas con 100% de presencialidad, 0.3 ECTS] EXAMEN FINAL. [4 horas con 100% de presencialidad, 0.15 ECTS] Se valorarán de forma global los conocimientos, destrezas y capacidades adquiridas a lo largo del curso. METODOLOGÍAS DOCENTES CLASE TEORÍA. Exposiciones en clase del profesor con soporte de medios informáticos y audiovisuales, en las que se desarrollan los conceptos principales de la materia y se proporcionan los materiales y la bibliografía para complementar el aprendizaje de los alumnos PRÁCTICAS. Resolución de casos prácticos, problemas, etc. planteados por el profesor de manera individual o en grupo. TUTORÍAS. Asistencia individualizada (tutorías individuales) o en grupo (tutorías colectivas) a los estudiantes por parte del profesor. PRÁCTICAS DE LABORATORIO. Docencia aplicada/experimental a talleres y laboratorios bajo la supervisión de un tutor.
Sistema de evaluación
  • Peso porcentual del Examen Final 35
  • Peso porcentual del resto de la evaluación 65
Calendario de Evaluación Continua
Bibliografía básica
  • Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón. Teoría de autómatas y lenguajes formales. McGraw-Hill. 2007
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 3rd Edition.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación. Addison-Wesley. 2007
  • Michael Sipser. Introduction to the Theory of Computation. 2nd ed.. Boston, MA: Course Technology. 2005
  • Michael Sipser. Introduction to the Theory of Computation. 3d ed.. Boston, MA: Course Technology. 2013
  • S. Wolfram. Cellular Automata and Complexity. Addison-Wesley. 1996
Bibliografía complementaria
  • C. Papadimitriou. Computational Complexity. Addison-Wesley. 1995
  • C. Papadimitriou, K. Steiglitz. Combinatorial Optimization. Dover. 1998
  • H. S. Wilf. Algorithms and Complexity. Prentice-Hall. 1986
  • Jeffrey Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press. 2008
  • S. Wolfram. A New Kind of Science. Wolfram Media. 2003

El programa de la asignatura podría sufrir alguna variación por causa de fuerza mayor debidamente justificada o por eventos académicos comunicados con antelación.