| Competences |
| Code | |
| A14 | Aplicar els coneixements de matemàtiques a l'enginyeria informàtica. |
| B2 | Resoldre problemes de forma efectiva. |
| B3 | Aplicar pensament crític, lògic i creatiu. |
| B4 | Treballar de forma autònoma amb iniciativa. |
| B14 | Capacitat d'anàlisi i síntesi. |
| Learning aims |
| Objectives | Competences | ||
| Comprendre el model de Màquina de Turing | A14 |
B2 B4 |
|
| Entendre el concepte de Calculabilitat i les seves limitacions | A14 |
B3 B4 B14 |
|
| Ser capaç d'analitzar la complexitat d'un problema informàtic | B2 B3 B4 |
||
| Relacionar tots aquests aspectes des d'un prisma formal matemàtic. | A14 |
||
| 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 |
| Planning |
| Methodologies :: Tests | |||||||||
| Competences | (*) Class hours | Hours outside the classroom | (**) Total hours | ||||||
| Introductory activities |
|
1 | 0 | 1 | |||||
| Lecture |
|
29 | 49.3 | 78.3 | |||||
| Problem solving, classroom exercises |
|
12.5 | 12.5 | 25 | |||||
| Personal tuition |
|
2 | 0 | 2 | |||||
| Extended-answer tests |
|
2.5 | 3.75 | 6.25 | |||||
| (*) On e-learning, hours of virtual attendance of the teacher. (**) The information in the planning table is for guidance only and does not take into account the heterogeneity of the students. | |||||||||
| Methodologies |
| Description | |
| Introductory activities | Introducció aspectes relacionats amb l'assignatura, durant primera hora del curs. |
| Lecture | A les classes teòriques el professor exposarà els continguts de l'assignatura. |
| Problem solving, classroom exercises | Cada sessió de problemes (2h bisetmanalment) es dedicarà a resoldre una tipologia de problema. El procediment seguit serà: 1er descriure el tipus de problema, 2n exposar les alternatives de resolució, 3er proposta i resolució d'un o diversos problemes pel professor, 4rt realització d'una prova d'avaluació de 20min individual. |
| Personalized attention |
|
|
| Assessment |
| Description | Weight | ||
| Extended-answer tests | A classes de problemes, bisetmanalment l'alumne realitzarà una prova d'avaluació continuada individual i sense apunts sobre la temàtica exposada a classe. Seran proves de 20min, a excepció de la darrera que serà de 2h i avaluadora de la totalitat de continguts de l'assignatura. | 50% (proves parcials) + 50% (prova final) | |
| 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 |
||||||||
| Recommendations |
| Subjects that it is recommended to have taken before | ||
|
||
(*)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.