Checking date: 01/07/2021

Course: 2021/2022

Advanced Computation Theory
Study: Bachelor in Applied Mathematics and Computing (362)

Coordinating teacher: ALONSO WEBER, JUAN MANUEL

Department assigned to the subject: Department of Computer Science and Engineering

Type: Electives
ECTS Credits: 6.0 ECTS


Requirements (Subjects that are assumed to be known)
Theory of Automata and Formal Languages (Course 2 / Semester 1) Discrete Mathematics (Course 1 / Semester 2)
Skills and learning outcomes
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 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 Lambda-Calculus 4.3 Cellular Automata 4.4 Lindenmayer Systems
Learning activities and methodology
THEORETICAL-PRACTICAL CLASSES. [44 hours with 100% classroom instruction, 1.67 ECTS] Knowledge and concepts students must acquire. Student receive course notes and will have basic reference texts to facilitate following the classes and carrying out follow up work. Students partake in exercises to resolve practical problems and participate in workshops and evaluation tests, all geared towards acquiring the necessary capabilities. TUTORING SESSIONS. [4 hours of tutoring with 100% on-site attendance, 0.15 ECTS] Individualized attendance (individual tutoring) or in-group (group tutoring) for students with a teacher. STUDENT INDIVIDUAL WORK OR GROUP WORK [98 hours with 0 % on-site, 3.72 ECTS] WORKSHOPS AND LABORATORY SESSIONS [8 hours with 100% on site, 0.3 ECTS] FINAL EXAM. [4 hours with 100% on site, 0.15 ECTS] Global assessment of knowledge, skills and capacities acquired throughout the course. METHODOLOGIES THEORY CLASS. Classroom presentations by the teacher with IT and audiovisual support in which the subject's main concepts are developed, while providing material and bibliography to complement student learning. PRACTICAL CLASS. Resolution of practical cases and problem, posed by the teacher, and carried out individually or in a group. TUTORING SESSIONS. Individualized attendance (individual tutoring sessions) or in-group (group tutoring sessions) for students with a teacher as tutor. LABORATORY PRACTICAL SESSIONS. Applied/experimental learning/teaching in workshops and laboratories under the tutor's supervision.
Assessment System
  • % end-of-term-examination 35
  • % of continuous assessment (assigments, laboratory, practicals...) 65
Calendar of Continuous assessment
Basic Bibliography
  • Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón. Teoría de autómatas y lenguajes formales. McGraw-Hill. 2007
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 3rd Edition.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación. Addison-Wesley. 2007
  • 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.