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

RA1.1: Knowledge and understanding of the mathematics and other basic sciences underlying their engineering specialisation, at a level necessary to achieve the other programme outcomes. RA1.2: Knowledge and understanding of engineering disciplines underlying their specialisation, at a level necessary to achieve the other programme outcomes, including some awareness at their Forefront. RA1.3: Awareness of the wider multidisciplinar y context of engineering. RA4.1: Ability to conduct searches of literature, to consult and to critically use scientific databases and other appropriate sources of information, to carry out simulation and analysis in order to pursue detailed investigations and research of technical issues in their field of study. RA5.4: Ability to apply norms of engineering practice in their field of study. RA5.5: Awareness of non-technical ¿ societal, health and safety, environmental, economic and industrial ¿ implications of engineering practice. RA6.1: Ability to gather and interpret relevant data and handle complexity within their field of study, to inform judgements that include reflection on relevant social and ethical issues. RA7.1: Ability to communicate effectively information, ideas, problems and solutions with engineering community and society at large. RA7.2: Ability to function effectively in a national and international context, as an individual and as a member of a team and to cooperate effectively with engineers and non-engineers. RA8.1: Ability to recognise the need for and to engage in independent life-long learning. RA8.2: Ability to follow developments in science and tech. CB1: Students have demonstrated possession and understanding of knowledge in an area of study that builds on the foundation of general secondary education, and is usually at a level that, while relying on advanced textbooks, also includes some aspects that involve knowledge from the cutting edge of their field of study. CB3: Students have the ability to gather and interpret relevant data (usually within their field of study) in order to make judgements which include reflection on relevant social, scientific or ethical issues. CB5: Students will have developed the learning skills necessary to undertake further study with a high degree of autonomy. CGO9: Ability to solve problems with initiative, decision-making, autonomy and creativity. Ability to know how to communicate and convey the knowledge, skills and abilities of the profession of Technical Engineer in Computer Science. CECRI5: Knowledge, administration and maintenance of computer systems, services and applications. CECRI6: Knowledge and application of the basic algorithmic procedures of com- puter technologies to design solutions to problems, analysing the suitability and complexity of the proposed algorithms. CECRI15: Knowledge and application of the fundamental principles and basic techniques of intelligent systems and their practical application.

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.