Theory of Computation

Credits
6
Types
Specialisation compulsory (Computing)
Requirements
Department
CS
Web
www.cs.upc.edu/tc/
From a practical point of view, the theory of computation provides students with methods for describing and processing languages. Depending on the method used, one obtains better or worse expressive and computational properties. These methods find applications in areas such as compilers, graphics, programming languages, and algorithms. In fact, this knowledge forms the foundation for any other area of computer science, and it is common to encounter it, for example, in research papers from database or computer architecture conferences.

Beyond its applications, the theory of computation is a foundational subject, as it studies the computational limits of the machines we work with today. Moreover, its study helps develop skills that are extremely useful in any other field, such as the ability to describe information unambiguously, carry out accurate and thorough case analysis, or produce sound reasoning.

Teachers

Person in charge

  • Antoni Lozano Boixadors (antoni.lozano@upc.edu)
  • Ilario Bonacina (ilario.bonacina@upc.edu)

Others

  • Arnau Messegué Buisan (arnau.messegue@upc.edu)
  • Enrique Romero Merino (eromero@cs.upc.edu)

Weekly hours

Theory
1.4
Problems
1.5
Laboratory
1.2
Guided learning
0.2
Autonomous learning
5.7

Competences

Transversal Competences

Reasoning

  • G9 [Avaluable] - Capacity of critical, logical and mathematical reasoning. Capacity to solve problems in her study area. Abstraction capacity: capacity to create and use models that reflect real situations. Capacity to design and perform simple experiments and analyse and interpret its results. Analysis, synthesis and evaluation capacity.
    • G9.3 - Critical capacity, evaluation capacity.

    • Autonomous learning

  • G7 [Avaluable] - To detect deficiencies in the own knowledge and overcome them through critical reflection and choosing the best actuation to extend this knowledge. Capacity for learning new methods and technologies, and versatility to adapt oneself to new situations.
    • G7.3 - Autonomous learning: capacity to plan and organize personal work. To apply the acquired knowledge when performing a task, in function of its suitability and importance, decide how to perform it and the needed time, and select the most adequate information sources. To identify the importance of establishing and maintaining contacts with students, teacher staff and professionals (networking). To identify information forums about ICT engineering, its advances and its impact in the society (IEEE, associations, etc.).

    • Technical Competences of each Specialization

    Computer science specialization

  • CCO1 - To have an in-depth knowledge about the fundamental principles and computations models and be able to apply them to interpret, select, value, model and create new concepts, theories, uses and technological developments, related to informatics.
    • CCO1.1 - To evaluate the computational complexity of a problem, know the algorithmic strategies which can solve it and recommend, develop and implement the solution which guarantees the best performance according to the established requirements.
    • CCO1.2 - To demonstrate knowledge about the theoretical fundamentals of programming languages and the associated lexical, syntactical and semantic processing techniques and be able to apply them to create, design and process languages.
    • CCO1.3 - To define, evaluate and select platforms to develop and produce hardware and software for developing computer applications and services of different complexities.
  • CCO2 - To develop effectively and efficiently the adequate algorithms and software to solve complex computation problems.
    • CCO2.2 - Capacity to acquire, obtain, formalize and represent human knowledge in a computable way to solve problems through a computer system in any applicable field, in particular in the fields related to computation, perception and operation in intelligent environments.
  • CCO3 - To develop computer solutions that, taking into account the execution environment and the computer architecture where they are executed, achieve the best performance.
    • CCO3.1 - To implement critical code following criteria like execution time, efficiency and security.

    • Objectives

    1. To learn how to classify problems according to known complexity classes. In particular, to learn techniques to determine when a set is regular, context free, polynomial time, exponential time, decidable (recursive) or semi-decidable (recursively enumerable).
      Related competences: G9.3, CCO1.2, CCO1.1,
    2. Learning to describe languages ​​using formal systems like context-free grammars and automata. To know the computational capabilities of these formalisms and their practical applications.
      Related competences: G9.3, CCO1.2, CCO1.1, CCO1.3, CCO2.2, CCO3.1,
    3. Solve theoretical and practical problems of this matter and make public presentations of the solutions.
      Related competences: G9.3, CCO1.2, CCO1.1, G7.3,

    Contents

    1. Mathematical introduction.
      Sets, tuples, relations, functions, and homomorphisms. Proof methods.
    2. Formal languages.
      Alphabets, words, languages, operations on languages (concatenation, reverse, star). Language classes and closure properties.
    3. Finite automata.
      Deterministic finite automata, non-deterministic finite automata, finite automata with lambda-transitions, equivalence between automata models, operations on automata, minimization of automata.
    4. Regular expressions.
      Regular expressions, equivalence with automata by Arden's Lemma, operations on regular expressions.
    5. Context-free grammars.
      Context-free grammars, generated language by a grammar, derivation tree, ambiguity, operations over grammars, grammar transformations. CYK algorithm and parsing.
    6. Pushdown automata.
      Nondeterministic pushdown automata and their equivalence with context-free languages, deterministic pushdown automata, uniquely accepting pushdown automata and their equivalence with unambiguous context-free languages, closure properties.
    7. Non-regularity and non-context freeness.
      Proofs of non-regularity by the pumping lemma, by closure properties, and by distinguishing extensions. Proofs of non-context freeness by the pumping lemma for context-free languages and by closure properties.
    8. Turing machines.
      Turing machines, nondeterministic or multi-tape Turing machines, equivalence of Turing machines with high-level algorithms. Universal Turing machine and Church-Turing thesis.
    9. Decidability (recursivity), semi-decidability (recursive enumerability), computability.
      Decidable (recursive) languages, semi-decidable (recursively enumerable) languages, computable functions, closure operations, complementation theorem, projection theorem, arithmetic hierarchy.
    10. Non-decidability, non-semi-decidability, non-computability.
      Diagonalization. Semi-decidable but undecidable languages (K, HALT). Many-one reductions for proving non-decidability and non-semi-decidability, equivalence between non-semi-decidability and non-computability. Examples of natural undecidable problems: non-empty intersection and ambiguity of context-free grammars, totality of context free grammars.
    11. Elements of complexity theory
      Formal definition of P, NP and coNP classes. Polynomial-time reductions and NP-completeness. Time hierarchy theorems. Space complexity. Polynomial hierarchy.

    Activities

    Activity Evaluation act


    Learning the subject "Language Theory".

    Students attend theory classes (T: 2h) and complete the theoretical concepts introduced by studying the recommended bibliography or watching the videos indicated for this topic (AA: 4h). In addition, they attend problem-solving sessions related to this topic (P: 2h).
    Objectives: 3
    Contents:
    Theory
    2h
    Problems
    2h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    4h

    Learning the subject "Regular Languages".

    Students attend theory classes on this topic (T: 4h) and complete the theoretical concepts introduced by studying the recommended bibliography or watching the videos for this topic (AA: 7h). They attend laboratory sessions and solve problems using a computer (L: 3h). They also work on solving the problems assigned for this topic (AA: 7h) and attend the problem-solving/laboratory sessions, where all students publicly present their solutions (P: 4h).
    Objectives: 1 2 3
    Contents:
    Theory
    4h
    Problems
    4h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    14h

    Learning the subject "Context-free languages".

    Students attend theory classes on this topic (T: 4h) and complete the theoretical concepts introduced by studying the recommended bibliography or watching the videos for this topic (AA: 7h). They attend laboratory sessions and solve problems using a computer (L: 3h). They also work on solving the problems assigned for this topic (AA: 8h) and attend the problem-solving/laboratory sessions, where all students publicly present their solutions (P: 4h). This part includes a comprehensive review of the first part of the course as a preparation of the first partial exam (AD: 1,5h).
    Objectives: 1 2 3
    Contents:
    Theory
    4h
    Problems
    4h
    Laboratory
    3h
    Guided learning
    1.5h
    Autonomous learning
    15h

    First partial exam.

    An exam with a duration of 3 hours, partially done in front of the computer and partially hand-written, where the hability to describe regular and context free languages.
    Objectives: 1 2
    Week: 7
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Learning the subject "Pushdown automata".

    Students attend laboratory sessions and solve problems using a computer (L: 3h). They also work on solving the problems assigned for this topic (AA: 5h) and prepare to present their solutions publicly.
    Objectives: 1 2 3
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    5h

    Learning the subject "Computability Theory".

    Students attend theory classes on this topic (T: 4h) and complete the theoretical concepts introduced by studying the recommended bibliography or watching the videos for this topic (AA: 5h). They attend laboratory sessions and solve problems using a computer (L: 3h). They also work on solving the problems assigned for this topic (AA: 6,5h) and attend the problem-solving/laboratory sessions, where all students publicly present their solutions (P: 6,5h).
    Objectives: 1 3
    Contents:
    Theory
    4h
    Problems
    6.5h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    11.5h

    Learning the subject "Elements of complexity theory".

    Students attend theory classes on this topic (T: 4h) and complete the theoretical concepts introduced by studying the recommended bibliography or watching the videos for this topic (AA: 5h). They also work on solving the problems assigned for this topic (AA: 7h) and attend the problem-solving sessions, where all students publicly present their solutions (P: 6h). This part includes a comprehensive review of the second part of the course as a preparation of the second partial exam and final exam (AD: 1,5h).
    Objectives: 1 3
    Contents:
    Theory
    4h
    Problems
    6h
    Laboratory
    0h
    Guided learning
    1.5h
    Autonomous learning
    12h

    Second partial exam

    An exam with a duration of 3 hours, partially done in front of the computer and partially hand-written, where the hability of analyzing the regularity and incontextuality of languages, as well as the decidability of problems and of constructing reductions in order to prove non-decidability and non-semi-decidability.
    Objectives: 1 2
    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final exam.


    Objectives: 1 2
    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    In theory classes, the lecturer introduces the basic theoretical foundations of each topic and solves some problems. Students deepen the theory during their personal study time using the resources indicated by the lecturer (books, videos and other complementary materials).

    In problem solving classes and laboratory classes, students explain their solutions to problems which have been assigned to them in advance. The teacher takes part of the explanation in order to correct mistakes or make improvements. Also, the teacher takes notes about students presentations in order to take them into account in the final evaluation of the subject. In laboratory classes students solve problems in front of the computer that are evaluated automatically.

    Evaluation methodology

    This course can be passed either through continuous assessment or by taking the final exam.

    The continuous assessment grade, C, is obtained by combining the grades of the two partial exams (each worth 40%) and the grade for the assessment of the blackboard presentations of the problems assigned to the students (worth 20%).

    Students who do not take the final exam will have their final course grade (FG) equal to the continuous assessment grade C.

    Students who take the final exam (with grade F) waive the continuous assessment grade C as their final course grade FG, and the new final grade is computed according to the formula:

    FG = max{ F, 0.5F + 0.5C }.

    Students who do not take any exam (Partial exam 1, Partial exam 2, and the Final Exam) will receive the grade NP ("Not Present").

    The assessment of competencies G7.3, G9.1, and CCO1.1 is carried out individually by each instructor for the students in their group, based on the public presentations given during continuous assessment. The assessment of these competencies does not affect the course grade.

    Bibliography

    Basic

    Complementary

    Web links

    Previous capacities

    * Ability to express statements described in natural language as logical formulas.
    * Ability to manipulate logical formulas.
    * Fundamental algebraic knowledge, including modular arithmetic.
    * Basic knowledge of combinatorics.
    * Knowledge of basic data structures and fundamental algorithms.
    * Ability to evaluate the time complexity of an algorithm.