Theory of Computation

Credits
6
Types
Specialization 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

Others

Weekly hours

Theory
1
Problems
1
Laboratory
2
Guided learning
0.2
Autonomous learning
5.8

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. Formal languages.
      Alphabets, words, languages, operations on languages (concatenation, reverse, star), morphisms, rewriting systems.
    2. Finite automata.
      Deterministic finite automata, non-deterministic finite automata, finite automata with lambda-transitions, equivalence between automata models, operations on automata, minimization of automata.
    3. Context-free grammars.
      Context-free grammars, generated language by a grammar, derivation tree, ambiguity, operations over grammars, grammar transformations.
    4. Regular expressions.
      Regular expressions, equivalence with automata by Arden's Lemma, operations on regular expressions.
    5. Pushdown automata.
      Non-deterministic pushdown automata and its equivalence to context-free languages, deterministic pushdown finite automata, pushdown automata with unique accepting execution and its equivalence with non-ambiguous context-free languages, closure operations, Chomsky hierarchy.
    6. Non-regularity and non-context freeness.
      Proofs of non-regularity by state repetition and by regularity preserving transformations. Proofs of non-context freeness by variable repetition.
    7. Turing machines.
      Turing machines, extensions by allowing non-determinism or multi-tape, equivalence of Turing machines with high-level algorithms.
    8. Decidability (recursivity), semi-decidability (recursive enumerability), computability.
      Decidable (recursive) languages, semi-decidable (recursively enumerable) languages, computable functions, closure operations, complementation theorem, projection theorem, connexions between semi-decidability and computability.
    9. Non-decidability, non-semi-decidability, non-computability.
      The language K, K is semi-decidable but non-decidable, reductions for proving non-decidability and non-semi-decidability, equivalence between non-semi-decidability and non-computability. Natural non-decidable problems: reachability of words by word rewriting, PCP, intersection non-emptiness and ambiguity of context free grammars, universality of context free grammars and satisfiability of logic over words.
    10. Elements of complexity theory
      Formal definition of P, NP and coNP classes. Polynomial-time reductions and NP-completeness. Time hierarchy theorems. Space complexity.

    Activities

    Activity Evaluation act


    Learning the subject "language theory".

    The students complete the theoretical concepts introduced in the theory classes with the study of the basic bibliography topics indicated by the professor or trying to watch and understand the videos of this topic (AA: 3h). They also try to solve the problems assigned to them on this subject (AA: 3h), attend the class of theory of this subject and ask questions to the teacher (T: 2 hours) and attend the class of problems where all students present their problems publicly on this subject (P: 2h).
    Objectives: 3
    Contents:
    Theory
    1h
    Problems
    2h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    4h

    Learning the subject "Finite automata".

    The students complete the theoretical concepts introduced in the theory classes with the study of the basic bibliography topics indicated by the professor or trying to watch and understand the videos of this topic (AA: 3h). They also try to solve the problems assigned to them on this topic (AA: 3h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 4 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 2h).
    Objectives: 1 2 3
    Contents:
    Theory
    2h
    Problems
    2h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    8h

    Learning the subject "Context-free grammars".

    The students complete the theoretical concepts introduced in the theory classes with the study of the basic bibliography topics indicated by the professor or trying to watch and understand the videos of this topic (AA: 3h). They also try to solve the problems assigned to them on this topic (AA: 3h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 4 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 2h).
    Objectives: 1 2 3
    Contents:
    Theory
    2h
    Problems
    2h
    Laboratory
    6h
    Guided learning
    0h
    Autonomous learning
    8h

    Learning the subject "Regular expressions".

    Students try to watch and understand the videos of this topic (AA: 3h), try to solve the problems assigned to them on this topic (AA: 3h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 2 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 2h).
    Objectives: 1 2 3
    Contents:
    Theory
    0h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    1.5h
    Autonomous learning
    6h

    First 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 try to understand the corresponding theory studying the chapters of the bibliography indicated by the professor or by watching the videos of this topic (AA: 3h). They also try to solve the problems assigned to them on this topic (AA: 3h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 2 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 2h).
    Objectives: 1 2 3
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    6h

    Learning the subject "Non-regularity and non-context-freeness".

    Students try to understand the corresponding theory attending the theory class (T: 1h) and studying the chapters of the bibliography indicated by the professor or by watching the videos of this topic (AA: 3h). They also try to solve the problems assigned to them on this topic (AA: 3h) and attend the class of problems where all students present their problems publicly on this topic (P: 1h).
    Objectives: 1 3
    Contents:
    Theory
    1h
    Problems
    1h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    6h

    Learning the subject "Turing machines".

    Students try to complete the theoretical concepts introdued in the class of theory (T: 1h) by studying the chapters of the basic bibliograpy indicated by the professor or by watching and understanding the videos of this topic (AA: 3h), try to solve the problems assigned to them on this topic (AA: 3h), and attend the class of problems where all students present their problems publicly on this topic (P: 1h).
    Objectives: 1 3
    Contents:
    Theory
    1h
    Problems
    1h
    Laboratory
    1h
    Guided learning
    0h
    Autonomous learning
    6h

    Learning the subject "Decidability (recursivity), semi-decidability (recursive enumerability), computability".

    Students try to complete the theoretical concepts introdued in the class of theory (T: 1h) by studying the chapters of the basic bibliograpy indicated by the professor or by watching and understanding the videos of this topic (AA: 3h), try to solve the problems assigned to them on this topic (AA: 3h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 2 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 1h).
    Objectives: 1 3
    Contents:
    Theory
    1h
    Problems
    1h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    6h

    Learning the subject "Non-decidability, non-semi-decidability, non-computability".

    Students try to complete the concepts introduced in the classes of theory (T: 1h) studying the chapters of the basic bibliography indicated by the professot or by watching and understanding the videos of this topic (AA: 4h), try to solve the problems assigned to them on this topic (AA: 4h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 4 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 3h).
    Objectives: 1 3
    Contents:
    Theory
    2h
    Problems
    3h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    8h

    Learning the subject "Elements of complexity theory".

    Students try to understand the corresponding theoretical concepts studying the chapters of the basic bibliography indicated by the professor or by watching and understanding the videos of this topic (AA: 4h), try to solve the problems assigned to them on this topic (AA: 4h), attend the laboratory class of this topic and try to solve the problems in front of the computer (L: 4 hours) and attend the class of problems where all students present their problems publicly on this topic (P: 4h).
    Objectives: 1 3
    Contents:
    Theory
    2h
    Problems
    1h
    Laboratory
    2h
    Guided learning
    1.5h
    Autonomous learning
    3h

    Second 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

    The main characteristic of this teaching methodology is the self-learning based on the use
    of the teaching material in order to know
    the theoretical fundaments of the subject as well as the discussion of the solutions of problems at the blackboard.The lecturer introduces the basic theoretical foundations of each topic and solves some problems. Students learn the theory during their personal work time by studying the topics indicated by the lecturer of the bibliography or also of the videos and other complementary materials such as notes, books and lists of problems resolved, all of them freely accessible through of the web.

    In problem solving 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 improve explanations. 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 try to solve problems in front of the computer that are evaluated automatically. The teacher is present to solve any question. The students can use these classes to solve the problems which have been assigned to them, and for which they will have to present a solution in the blackboard.

    Evaluation methodology

    This subject can be passed during the class period, i.e. by continuous evaluation (without attending to the final exam). The grade of the continuous evaluation is obtained from the mark L corresponding to the 2 exams (the ones of the evaluation acts, with a value between 0 and 8 in total, with a weight of 50% the first exam and a weight of 50% the second), and the mark P corresponding to the presentations of the student in the blackboard (between 0 and 2 points). The grade of the continuous evaluation C is defined as C=L+P.

    Those students that do not attend to the final exam, have as final grade, the continuous grade C.

    Those students who attend to the final exam resign to the continuous course grade. In such a case, the grade is obtained from the mark C, and the mark F of the final exam (between 0 and 10) according to the following formula:

    max(F,0.5 F+0.5 C)



    The evaluation of competences G7.3, G9.1 and CCO1.1 is done by the professor according to the public presentations made during the continuous evaluation. Te evaluation of the competences is independent from the avaluation of the course.

    Bibliography

    Basic

    Complementary

    Web links

    Previous capacities

    Ability to express problems framed in terms of logical formulae in everyday language.
    Ability to manipulate logical formulae.
    Fundamental algebraic concepts: monoids, groups, closures, morphisms.
    Basic principles of combinatorial algebra.
    Ability to fully exploit the properties of Boolean algebra.
    Understand basic data structures and the fundamental principles governing algorithms.
    Ability to evaluate the temporal complexity of algorithms.