|
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. |
|
|
|
|
|
La bibliografia a la biblioteca