Objectius
|
|
|
- Estudi de la dificultad dels processos de càlcul i adquisició d'un coneixement teòric de les seves limitacions. - Anàlisi de diversos mòdels de càlcul. - Introducció a la indecidibilitat dels problemes - Classificació dels problemes d'acord a la seva complexitat. |
|
|
|
Contingut (Programa)
|
|
|
0.- Preliminar. (Temporalització: 3 h.)
0.1.- Llenguatges formals. 0.2.- Jerarquia de Chomsky. 0.3.- Enumerabilitat.1.- Calculabilitat I: Màquines de Turing. (Temporalització: 7 h.)
1.1.- Model bàsic. 1.2.- Disseny. 1.3.- Models equivalents. 1.4.- MT Universal 1.5.- Llenguatges estructurats per frase. 1.6.- Hipòtesi de Church.2.- Calculabilitat II: Models de Càlcul equivalents. (Temporalització: 5 h.)
2.1.- Funcions Recursives. 2.2.- Màquines RAMs. 2.3.- Llenguatges de Programació Elemental. 2.4.- Conclusions.3.- Indecidibilitat. (Temporalització: 9 h.)
3.1.- Indecidibilitat en llenguatges. 3.2.- Reduccions. 3.3.- Teorema de Rice. 3.4.- Indecidibilitat en llenguatges incontextuals.4.- Complexitat. (Temporalització: 6 h.)
4.1.- Les classes P i NP. 4.2.- La classe NP-Complet. 4.3.- La classe co-NP. |
|
|
Bibliografia
|
|
|
- GABARRÓ, J.: "Informàtica clàssica. Autòmats i Gramàtiques. Indecidibilitat. Paral.lelisme massiu", Eumo de., 1995 - GAREY, M.; JOHNSON, D.: "Computer and Intractability: A guide to the Theory of NP-Completeness" Freeman, 1978 - HOPCROFT, J-ULLMAN, J.D.: "Introducción a la Teoría de Autómatas, Lenguajes y Computación", Addison Wesley Iberoamericana, 1991. - BROOKSHEAR, J.G.: "Teoria de la Computación. Lenguajes Formales, Autómatas y Complejidad", Addison-Wesley Iberoamericana, 1993 |
|
|
Mètodes docents
|
|
|
(Mig quadrimestre) Classes de teoria: 4 hores setmanals Laboratori: 2 hora setmanal |
|
|
Tipus d'exàmens i avaluacions
|
|
|
Teoria: Prova final (0..10) Laboratori:Treballs personals (0..10) Nota final:teoria x 0,80 + laboratori x 0,20(Sempre i quan es superin ambdues parts). |
|
|
Informació addicional
|
|
|
- Disseny i implementació d' algorismes en els diversos models de càlcul. - Anàlisi de problemes indecidibles (reduccions) Els alumnes desenvoluparan pel seu compte els següents treballs pràctics : a) Disseny de MT's. b) Resolucions d'indecidibilitat. c) Càlculs de complexitat. |
|
|
|