Checking date: 05/06/2022

Course: 2023/2024

Advanced theory of computation
Bachelor in Computer Science and Engineering (Plan: 489 - Estudio: 218)

Coordinating teacher: ALONSO WEBER, JUAN MANUEL

Department assigned to the subject: Computer Science and Engineering Department

Type: Electives
ECTS Credits: 6.0 ECTS


Requirements (Subjects that are assumed to be known)
Automata and Formal Language Theory (Course 2 - Semester 1) Discrete Mathematics (Course 1 - Semester 2)
Skills and learning outcomes
Link to document

Description of contents: programme
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
Learning activities and methodology
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.
Assessment System
  • % end-of-term-examination 35
  • % of continuous assessment (assigments, laboratory, practicals...) 65
Calendar of Continuous assessment
Basic Bibliography
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 3rd Edition.
  • Michael Sipser. Introduction to the Theory of Computation. 2nd ed.. Boston, MA: Course Technology. 2005
  • Michael Sipser. Introduction to the Theory of Computation. 3d ed.. Boston, MA: Course Technology. 2013
  • S. Wolfram. Cellular Automata and Complexity. Addison-Wesley. 1996
Additional Bibliography
  • C. Papadimitriou. Computational Complexity. Addison-Wesley. 1995
  • C. Papadimitriou, K. Steiglitz. Combinatorial Optimization. Dover. 1998
  • H. S. Wilf. Algorithms and Complexity. Prentice-Hall. 1986
  • Jeffrey Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press. 2008
  • S. Wolfram. A New Kind of Science. Wolfram Media. 2003

The course syllabus may change due academic events or other reasons.