Programación (1º 1 Cuatrimestre) Técnicas de Programación (1º 2 Cuatrimestre)

1.Introducción a la teoría de Autómatas y Lenguajes Formales. 1.1. Por qué de la Teoría de Autómatas. Historia y Origen 1.2. Relación con otras Áreas de Conocimiento. 1.2. Máquinas, Lenguajes y Algoritmos. 2.- Teoría de Autómatas 2.1.Introducción y Definiciones. 2.2 Modelo Matemático de un Autómata 2.3 Autómatas y Algoritmos 2.4 Autómatas discretos, continuos e hibridos. 2.5 Clases de Autómatas 3.Autómatas Finitos 3.1. Definición y representación de Autómatas Finitos Deterministas (AFD) 3.2. AFD como reconocedores de lenguajes 3.3. Equivalencia y minimización de AFD 3.4. Teoremas sobre AFD 3.5. Definición y representación de Autómatas Finitos No Deterministas (AFND) 3.6. Lenguaje aceptado por un AFND 3.7. Equivalencia entre AFD y AFND 4.Lenguajes y Gramáticas formales. 4.1. Operaciones con Palabras. Operaciones con Lenguajes. Reglas de Derivación 4.2. Concepto de Gramática. Definición de Gramática Formal 4.3. Jerarquía de Chomsky y Gramáticas Equivalentes 4.4. Gramáticas Independientes del Contexto (Tipo 2) 4.5. Lenguaje Generado por una Gramática Tipo 2. Arboles de Derivación 4.6. Gramáticas Bien Formadas 4.7. Forma Normal de Chomsky. Forma Normal de Greibach 5.Lenguajes regulares. 5.1. Definición de Lenguajes regular 5.2. AFD asociado a una Gramática de Tipo 3 5.3. Expresiones Regulares. Equivalencias 5.4. Teoremas de Kleene 5.5. Ecuaciones características 5.6. Algoritmo recursivo de síntesis 5.7. Derivada de una expresión regular 6.Autómatas a pila. 6.1.Definición de Autómata a Pila (AP) 6.2.Movimientos y Descripciones Instantáneas en AP 6.3.AP por vaciado (APV) y AP por estados finales (APF) 6.4.Lenguaje aceptado por un AP: equivalencia APV y APF 6.5.Construcción de APV a partir de una Gramática Tipo 2 6.6.Construcción de una Gramática Tipo 2 a partir de AP 7.Máquina de Turing 7.1.Definición de la Máquina de Turing 7.2.Variaciones de la Máquina de Turing 7.3.Máquina de Turing Universal 8. Complejidad Computacional 8.1 Teoría de la Complejidad 8.2.Complejidad de Algoritmos 8.3.Problemas P versus NP 8.4 Clases de Complejidad 8.5 Complejidad temporal 8.6 Teoremas de jerarquía 8.7 Problemas no computacionales 8.8 Límites de la Computación

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.