| 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 |
||
| Comprendre el model de Màquina de Turing | |||
| Entendre el concepte de Calculabilitat i les seves limitacions | |||
| Ser capaç d'analitzar la complexitat d'un problema informàtic | |||
| Relacionar tots aquests aspectes des d'un prisma formal matemàtic. | |||
| Comprendre el model de Màquina de Turing | |||
| Entendre el concepte de Calculabilitat i les seves limitacions | |||
| Ser capaç d'analitzar la complexitat d'un problema informàtic | |||
| Relacionar tots aquests aspectes des d'un prisma formal matemàtic. | |||
| Continguts |
| Tema | Subtema |
| Introducció | Motivació i Objectius La jerarquia de Chomsky |
| La màquina de Turing | Descripció i Representació MT per reconèixer Llenguatges MT per computar funcions Cicle d'Avaluació MT Determinista MT Indeterminista MT Universal |
| Calculabilitat | Limitacions de les MT Calculabilitat Teoria de la Calculabilitat |
| Complexitat | Complexitat Computacional Classes de Complexitat Fonamentals Les Classes L i NL Les Classes P, NP i CoNP Les Classes EXP i NEXP Complexitat Teoria de la Complexitat |
| Planificació |
| Metodologies :: Proves | |||||||||
| Competències | (*) Hores a classe | Hores fora de classe | (**) Hores totals | ||||||
| Activitats Introductòries |
|
1 | 0 | 1 | |||||
| Sessió Magistral |
|
23 | 0 | 23 | |||||
| Resolució de problemes, exercicis a l'aula ordinària |
|
15 | 0 | 15 | |||||
| Resolució de problemes, exercicis |
|
0 | 6 | 6 | |||||
| Atenció personalitzada |
|
0 | 0 | 0 | |||||
| (*) 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 (1h/setmana) 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 plantejament d'un problema per a que l'alumne ho resolgui, 5è sortida a pissarra d'un alumne per a mostrar la solució i 6è finalització amb una llista de problemes proposats per a resoldre a casa. |
| Resolució de problemes, exercicis | El curs emprarà 6h dins l'horari de classes teòriques per fer 3 proves d'avaluació continuada (2h cada una, una per cada tema del curs). S'estima que el temps de preparació per cadascuna de les proves per part de l'alumne oscil·la entre 10 i 20h. |
| Atenció personalitzada |
|
|
| Avaluació |
| Descripció | Pes | ||
| Resolució de problemes, exercicis | 3 proves d'avaluació continuada, cadascuna 1/3 de la nota del curs. | 100% | |
| Altres comentaris i segona convocatòria | |||
| Fonts d'informació |
| Bàsica |
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
D. Riaño, "Models Abstractes de Càlcul", Edicions URV, 2000 |
|
| 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 | ||
|
||