Programming (Course: 1 - Semester: 1) Algorithms and Data Structures (Course: 1 - Semester: 2)

K5: Knowledge and application of the basic algorithmic procedures of computer technologies to design solutions to problems, analyzing the suitability and complexity of the proposed algorithms. K10: Knowledge and application of the necessary tools for storing, processing and accessing information systems, including web_based systems. K12: Knowledge and application of the fundamental principles and basic techniques of intelligent systems and their practical application. S1: Ability to know the theoretical foundations of programming languages and the associated lexical, syntactic and semantic processing techniques, and to know how to apply them to the creation, design and processing of languages. C6: Ability to apply the theoretical foundations of programming languages and lexical, syntactic and semantic processing techniques in the design, implementation and optimization of programming languages and development environments, ensuring their efficiency and adaptability to different computational contexts

1.Introduction to the theory of automata and formal languages. 1.1. Why study Automata Theory. History and Origins 1.2. Relationship with others Areas of Knowledge 1.3. Machines, Languages and Algorithms. 2.- Automata Theory 2.1 Introduction and Definitions. 2.2 Mathematical model of an automaton 2.3 Automata and algorithms. 2.4 Discrete, continuous, and hybrid automata. Classes of automata. 3.Finite Automata 3.1 Definition and Representation of Deterministic Finite Automata (DFA) 3.2. DFA as Recognition Device 3.3. Equivalence and Minimization of DFA 3.4. Theorems of DFA 3.5. Definition and Representation of Nondeterministic Finite Automata (NDFA) 3.6. The Language of a NDFA 3.7. Equivalence of DFA and NDFA 4.Languages and Formal Grammars. 4.1. Operations with Words. Operations with Languages. Derivations. 4.2 Concept of Grammar. Formal Grammar. 4.3. Chomsky Hierarchy and Equivalent Grammar 4.4 Context-Free Grammar 4.5. Language of a Context-Free Grammar. Parse Tree 4.6. Well-Formed Grammar 4.7. Chomsky Normal Form. Greibach Normal Form 5.Regular Languages. 5.1. Definition of Regular Languages 5.2. DFA for a Regular Grammar 5.3. Equivalence of Regular Expressions 5.4. Kleene's Theorem 5.5. Characteristic equations 5.6. Synthesis Problem: Recursive Algorithm 5.7. Derivatives of Regular Expressions 6.Pushdown Automata. 6.1. Definition of Pushdown Automata (PDA). 6.2. Transitions, Movement and Instantaneous Description in PDA. 6.3. Acceptance by Empty Stack. Acceptance by Final State. 6.4. Language Accepted by a PDA. Equivalence of PDA by Empty Stack and PDA by Final State. 6.5. From Context-Free Grammar to Push-Down Automata. 6.6. From Pushdown Automata to Context-Free Grammar. 7.Turing Machine. 5.1. Definition if Turing Machine. 5.2. Variations of Turing Machine. 5.3. Universal Turing Machine. 8. Compilers 8.1. Syntactic Analysis 8.2. Code generation

THEORETICAL-PRACTICAL CLASSES (theoretical content): 3.5 ECTS. The knowledge to be acquired by the students will be presented. They will receive the class notes and will have basic reference texts to facilitate the follow-up of the classes and the development of the subsequent work. Exercises will be solved by the student that will serve as self-evaluation and to acquire the necessary skills. Classes of problems, in which the problems proposed to the students will be developed and discussed. WORKSHOPS AND/OR LABORATORY PRACTICES. 1.5 ECTS. Developed with or without the presence of the teacher, they aim to complete and integrate the development of all the specific and transversal competences, in the resolution of two practical cases where the approach to the problem, the choice of the resolution method, the results obtained and their interpretation are well documented. FINAL EXAM. 0,5 ECTS The knowledge, skills and abilities acquired throughout the course will be globally assessed. TUTORIALS. 0,5 ECTS Individualized assistance (individual tutorials) or in group (collective tutorials) to the students by the professor.