Teoría de Autómatas y Lenguajes Formales (Curso 2 - Cuatrimestre 1) Matemática Discreta (Curso 1 - Cuatrimestre 2)

RA1.2: Conocimiento y comprensión de las disciplinas de ingeniería propias de su especialidad, en el nivel necesario para adquirir el resto de competencias del título, incluyendo nociones de los últimos adelantos. RA4.1: Capacidad para realizar búsquedas bibliográficas, consultar y utilizar con criterio bases de datos y otras fuentes de información, para llevar a cabo simulación y análisis con el objetivo de realizar investigaciones sobre temas técnicos de su especialidad. RA4.3: Capacidad y destreza para proyectar y llevar a cabo investigaciones experimentales, interpretar resultados y llegar a conclusiones en su campo de estudio. CG2: Ser capaz de generar nuevas ideas (creatividad) y de anticipar nuevas situaciones y de adaptarse a Trabajar en equipo y relacionarse con otros, pero al mismo tiempo tener capacidad de trabajar de forma autónoma. CTE12: Capacidad para tener un conocimiento profundo de los principios funda- mentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y de sarrollos tecnológicos relacionados con la informática. CTE13: Capacidad para evaluar la complejidad computacional de un problema, cono- cer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

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, NP-Hard - Otros Modelos de Computación PROGRAMA 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

CLASES TEÓRICAS: 1.5 ECTS. Tienen por objetivo alcanzar las competencias específicas cognitivas de la asignatura. CLASES PRÁCTICAS: 1.5 ECTS. Desarrollan las competencias específicas instrumentales y la mayor parte de las transversales, como son la de trabajo en equipo, capacidad de aplicar los conocimientos a la práctica, de planificar y organizar y de análisis y síntesis. También tienen por objetivo desarrollar las capacidades específicas actitudinales. Consisten en el diseño y desarrollo de un proyecto de compilador/intérprete elaborado en grupos de trabajo. Realización de Actividades Académicas Dirigidas - Con presencia del profesor: 1 ECTS Planteamiento de un estudio, orientado por el profesor pero propuesto por el alumno, donde profundiza sobre algún aspecto de la materia, realizando una exposición pública del mismo. - Sin presencia del profesor: 1 ECTS. Ejercicios y lecturas complementarias propuestas por el profesor EXAMENES: 0.5 ECTS. Tienen por objeto incidir y complementar en el desarrollo de las capacidades específicas cognitivas y procedimentales TUTORÍAS. 0.5 ECTS. Asistencia individualizada (tutorías individuales) o en grupo (tutorías colectivas) a los estudiantes por parte del profesor.