Última actualización: 09/02/2024


Curso Académico: 2023/2024

Teoría avanzada de la computación
(18294)
Grado en Matemática Aplicada y Computación (Plan: 433 - Estudio: 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)
Matemática Discreta (Curso 1 - Cuatrimestre 2) Teoría de Autómatas y Lenguajes Formales (Curso 2 - Cuatrimestre 1)
Competencias y resultados del aprendizaje
CB1. Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio. CB2. Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio. CB3. Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética. CB4. Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado. CB5. Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía. CG1. Que los estudiantes sean capaces de demostrar conocimiento y comprensión de conceptos de matemáticas, estadística y computación y aplicarlos a la resolución de problemas en ciencia e ingeniería con capacidad de análisis y síntesis. CG3. Que los estudiantes puedan resolver computacionalmente con ayuda de las herramientas informáticas más avanzadas los modelos matemáticos que surjan de aplicaciones en la ciencia, la ingeniería, la economía y otras ciencias sociales. CG4. Que los estudiantes demuestren que pueden analizar e interpretar las soluciones obtenidas con ayuda de la informática de los problemas asociados a modelos matemáticos del mundo real, discriminando los comportamientos más relevantes para cada aplicación. CG6. Que los estudiantes sepan buscar y utilizar los recursos bibliográficos, en soporte físico o digital, necesarios para plantear y resolver matemática y computacionalmente problemas aplicados que surjan en entornos nuevos, poco conocidos o con información insuficiente. CE12. Que los estudiantes hayan demostrado que conocen las principales estructuras de datos siendo capaz de utilizarlas, diseñarlas e implementarlas determinando su complejidad computacional y de almacenamiento. RA1. Haber adquirido conocimientos avanzados y demostrado una comprensión de los aspectos teóricos y prácticos y de la metodología de trabajo en el campo de la matemática aplicada y computación con una profundidad que llegue hasta la vanguardia del  conocimiento. RA2. Poder, mediante argumentos o procedimientos elaborados y sustentados por ellos mismos, aplicar sus conocimientos, la comprensión de estos y sus capacidades de resolución de problemas en ámbitos laborales complejos o profesionales y especializados que requieren el uso de ideas creativas e innovadoras. RA3. Tener la capacidad de recopilar e interpretar datos e informaciones sobre las que fundamentar sus conclusiones incluyendo, cuando sea preciso y pertinente, la reflexión sobre asuntos de índole social, científica o ética en el ámbito de su campo de estudio. RA4. Ser capaces de desenvolverse en situaciones complejas o que requieran el desarrollo de nuevas soluciones tanto en el ámbito académico como laboral o profesional dentro de su campo de estudio. RA5. Saber comunicar a todo tipo de audiencias (especializadas o no) de manera clara y precisa, conocimientos, metodologías, ideas, problemas y soluciones en el ámbito de su campo de estudio. RA6. Ser capaces de identificar sus propias necesidades formativas en su campo de estudio y entorno laboral o profesional y de organizar su propio aprendizaje con un alto grado de autonomía en todo tipo de contextos (estructurados o no). RA7. Disponer de la madurez profesional necesaria para elegir y valorar los objetivos de su trabajo de una manera reflexiva, creativa, autodeterminada y responsable, en beneficio de la sociedad.
Descripción de contenidos: Programa
Contenidos relevantes: 1.- Coste de los procesos computacionales 2.- Complejidad algoritmos recursivos 3.- Introducción a la teoría de la computabilidad 4.- Introducción a la teoría de la complejidad computacional 5.- Complejidad espacial 6.- Complejidad de Kolmogorov 7.- Modelos de computación 8.- Algoritmos probabilísticos Temario 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 Autómatas Celulares 4.3 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.