| Continguts |
| Tema | Subtema |
| 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 |
| Atenció personalitzada |
| Descripció |
| Els alumnes seran atesos individualment o en grup en l'horari de consultes publicat per l'ETSE. |
| Avaluació |
| Altres comentaris i segona convocatòria |
|
Hi haurà un procés d'avaluació de l'assignatura en base a 3 o 4 proves individuals, una d'elles de caràcter global. Hi haurà una opció d'avaluació en segona convocatòria. |
| Fonts d'informació |
| Bàsica |
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 |
||||||||
| Complementària |
M. Garey i D. Johnson, Computers and Intractability. A Guide to Theory of NP-Completeness”, Freeman,, 1978 |
||||||||
(*)La Guia docent és el document on es visualitza la proposta acadèmica de la URV. Aquest document és públic i no es pot modificar, llevat de casos excepcionals revisats per l'òrgan competent/ o degudament revisats d'acord amb la normativa vigent |
|||||||||