Programación Estructuras de Datos y Algoritmos

El objetivo de este curso es que el estudiante adquiera las siguientes competencias y los resultados de aprendizaje: 1.- Competencias Generales y Básicas: CGB3 - Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería. CGO9 - Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática. 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 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 CB5 - Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía 2. Competencias específicas: CECRI5 - Conocimiento, administración y mantenimiento sistemas, servicios y aplicaciones informáticas. CECRI6 - Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos. CECRI15 - Conocimiento y aplicación de los principios fundamentales y técnicas básicas de los sistemas inteligentes y su aplicación práctica. 3. Resultados del aprendizaje: R1. Conocimiento y comprensión: Tener conocimientos básicos y la compresión de los fundamentos científicos y tecnológicos de la Ingeniería Informática, así como un conocimiento específicos de las ciencias de la computación, la ingeniería de computadores y sistemas de información. R5 Aplicaciones de la Ingeniería: Los egresados serán capaces de aplicar su conocimiento y comprensión para resolver problemas, dirigir investigaciones y diseñar dispositivos o procesos del ámbito de la Ingeniería Informática de acuerdo con criterios de coste, calidad, seguridad, eficiencia, respeto por el medioambiente e implicaciones éticas. Estas habilidades incluyen el conocimiento, uso y limitaciones de sistemas informáticos, ingeniería de procesos, arquitecturas de computadores, modelos computacionales, equipos, trabajo práctico, bibliografía técnica y fuentes de información.

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 (contenido teórico): 3.5 ECTS. En ellas se presentarán los conocimientos que deben adquirir los estudiantes. Éstos 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 por parte del estudiante que le servirá de autoevaluación y para adquirir las capacidades necesarias. Clases de problemas, en las que se desarrollen y discutan los problemas que se proponen a los estudiantes. TALLERES Y/O PRÁCTICAS DE LABORATORIO. 1,5 ECTS Desarrollados con o sin presencia del profesor, tienen por objetivo completar e integrar el desarrollo de todas las competencias específicas y transversales, en la resolución de dos casos prácticos donde queden bien documentados el planteamiento del problema, la elección del método de resolución, los resultados obtenidos y la interpretación de los mismos. EXAMEN FINAL. 0,5 ECTS Se valorarán de forma global los conocimientos, destrezas y capacidades adquiridas a lo largo del curso. TUTORÍAS. 0,5 ECTS Asistencia individualizada (tutorías individuales) o en grupo (tutorías colectivas) a los estudiantes por parte del profesor