Theory of Computation

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Informatics Engineering » Curriculum » Syllabus » Theory of Computation
Credits
6
Types
Specialization compulsory (Computing)
Requirements
  • Prerequisite: EDA
  • Corequisite: PROP
Department
CS
Web
www.cs.upc.edu/~alvarez/tc2.html
Des d'un punt de vista pràctic, la teoria de la computació proporciona als alumnes mètodes de descripció i tractament de llenguatges. Depenent del mètode utilitzat, s'obtenen millors o pitjors propietats expressives i computacionals. Aquests mètodes troben aplicacions en àrees com compiladors, gràfics, llenguatges de programació i algorísmia. Però de fet, aquests coneixements són la base per a qualsevol altra àrea de les ciències de la computació, i és habitual trobar-los, per exemple, en articles de recerca de congressos de bases de dades o arquitectura de computadors. A part de les aplicacions, TC és una assignatura de fonament, doncs estudia quins són els límits computacionals de les màquines amb què treballem avui en dia. A més a més, el seu estudi ajuda a desenvolupar habilitats que són de gran ajuda en qualsevol altre àmbit, tals com la capacitat de descriure la informació sense ambigüitats, fer un anàlisi de casos acurat i exhaustiu, o produir una argumentació correcta.

Teachers

Person in charge

  • Maria del Carme Alvarez Faura ( )

Others

  • Enrique Romero Merino ( )
  • Ilario Bonacina ( )

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 in the Chomsky's hierarchy. In particular, to learn techniques to determine when a set is regular, contex-free, decidable (recursive) and 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.
  10. 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.

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
Type: lab exam
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
8h

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
2h
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
2h
Problems
1h
Laboratory
0h
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
2h
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 "Natural non-decidable problems".

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
0h
Problems
1h
Laboratory
4h
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)
Type: lab exam
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
8h

Final exam.


Objectives: 1 2
Week: 15 (Outside class hours)
Type: theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

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 during the theory class 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 who have a grade C greater than or equal to 5 and do not attend to the final exam, have as final grade, the continuous grade C.

The students who have a grade C less than 5 and do not attend to the final exam obtain a final qualification of NP.

Those students who attend to the final exam resign to the continuous course grade (in the case it was passed). 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.