| Competències |
| Codi | |
| 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. |
| Objectius d'aprenentatge |
| Objectius | Competències | ||
| 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 |
||
| 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 |
| Planificació |
| Metodologies :: Proves | |||||||||
| Competències | (*) Hores a classe | Hores fora de classe | (**) Hores totals | ||||||
| Activitats Introductòries |
|
1 | 0 | 1 | |||||
| Sessió Magistral |
|
29 | 49.3 | 78.3 | |||||
| Resolució de problemes, exercicis a l'aula ordinària |
|
12.5 | 12.5 | 25 | |||||
| Atenció personalitzada |
|
2 | 0 | 2 | |||||
| Proves de desenvolupament |
|
2.5 | 3.75 | 6.25 | |||||
| (*) En el cas de docència no presencial, són les hores de treball amb suport vitual del professor. (**) Les dades que apareixen a la taula de planificació són de caràcter orientatiu, considerant l’heterogeneïtat de l’alumnat | |||||||||
| Metodologies |
| Descripció | |
| Activitats Introductòries | Introducció aspectes relacionats amb l'assignatura, durant primera hora del curs. |
| Sessió Magistral | A les classes teòriques el professor exposarà els continguts de l'assignatura. |
| Resolució de problemes, exercicis a l'aula ordinària | 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. |
| Atenció personalitzada |
|
|
| Avaluació |
| Descripció | Pes | ||
| Proves de desenvolupament | 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) | |
| Altres comentaris i segona convocatòria | |||
|
L'assignatura pot ser aprovada 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 |
||||||||
| Recomanacions |
| Assignatures que es recomana haver cursat prèviament | ||
|
||
(*)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