Automata and Formal Language Theory (Course 2 - Semester 1) Discrete Mathematics (Course 1 - Semester 2)

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. 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. RA4.3: Laboratory/workshop skills and ability to design and conduct experimental investigations, interpret data and draw conclusions in their field of study. CG2: Be able to generate new ideas (creativity), to anticipate new situations, to adapt to new situations, working in a team and interact with others, but at the same time be able to work autonomously. CTE12: Ability to have a thorough knowledge of the fundamental principles and models of computing and know how to apply them to interpret, select, evaluate, assess, model and create new concepts, theories, uses and technological developments related to computing. CTE13: Ability to evaluate the computational complexity of a problem, to know algorithmic strategies that can lead to its resolution and to recommend, develop and implement the one that guarantees the best performance in accordance with the established requirements.

Relevant contents: - Computational Complexity and Computational Cost. - Computational Cost of Structured and Recursive Programs - Computability and Decidability - Turing Machines (Multi-tape, Non deterministic) - Problem Reduction - Complexity Classes P, NP, NP-Complete and NP-Hard. - Other Models of Computation PROGRAMME 1. Computational Cost of Algorithms. 1.1 Computational Complexity and Computational Cost. 1.2 Computational Cost of Structured Programs 1.3 Computational Cost of Recursive Programs 1.4 Probabilistic Analysis 2. Introduction to Computability Theory 2.1 Definition of Problem. Decision Problems 2.2 Turing Machines and Decidability 2.3 Computability and Decidability 3. Introduction to Complexity Theory 3.1 Problem Reduction 3.2 Classes P, NP and NP-Complete. 3.3 Classes PSpace, NPSpace. 3.3 Classes NP-Hard, Exp, CoP, CoNP 4. Models of Computation 4.1 Turing Machines (Multi-tape, Non deterministic) 4.2 Cellular Automata 4.3 Lindenmayer Systems

Theoretical lectures: 1.5 ECTS. To achieve the specific cognitive competences of the course. Practical lectures: 1,5 ECTS. To develop the specific instrumental competences and most of the general competences, such as analysis, abstraction, problem solving and capacity to apply theoretical concepts. Besides, to develop the specific attitudinal competencies. They consist in proposing during the practical lectures a compiler/interpreter project to be developed in teamwork Guided academic activities (in presence of the teacher): 1 ECTS. The student proposes a project according to the teacher's guidance to go deeply into some aspect of the course, followed by a public presentation. Guided academic activities (in absence of the teacher): 1 ECTS. Exercises and complementary readings proposed by the teacher. EXAMINATION: 0,5 ECTS. To complete the development of specific cognitive and procedimental capacities. TUTORING SESSIONS. 0,5 ECTS Individualized attendance (individual tutoring) or in-group (group tutoring) for students with a teacher.