| Contents |
| Topic | Sub-topic |
| Introduction | Motivation and Objectives of this subject Chomsky's hierarchy |
| Turing Machine | Description and Representations TM to recognize Formal Languages TM to compute Mathematical Functions The TM Execution Cycle Deterministic TM Non-Deterministic TM The Universal TM |
| An Introduction to the Theory of Calculability | Some Limitations of TM Calculability Principles The Theory of Calculability |
| An Introduction to the Theory of Complexity | Computational Complexity Basic Complexity Classes The Classes L and NL The Classes P, NP i CoNP The Classes EXP i NEXP Complexity Principles The Theory of Complexity |
| Personalized attention |
| Description |
| Els alumnes seran atesos individualment o en grup en l'horari de consultes publicat per l'ETSE. |
| Assessment |
| Other comments and second exam session |
|
The subject can be approved in second call. |
| Sources of information |
| Basic |
D. Riaño, "Models Abstractes de Càlcul", Edicions URV, 2000
J. E. Hopcroft, R. Motwani, J. D. Ullman, "Introducción a la Teoría de Autòmatas, Lenguajes y Computación", Addison-Wesley, 2002
H. R. Lewis i C. H. Papadimitriou, "Elements of the Theory of Computation", Prentice-Hall, 1981 |
||||||||
| Complementary |
M. Garey i D. Johnson, Computers and Intractability. A Guide to Theory of NP-Completeness”, Freeman,, 1978 |
||||||||
(*)The teaching guide is the document in which the URV publishes the information about all its courses. It is a public document and cannot be modified. Only in exceptional cases can it be revised by the competent agent or duly revised so that it is in line with current legislation. |
|||||||||