Models Abstractes de Càlcul (MAC)
(http://www-lsi.upc.edu/~mjserna/docencia/mac/mac.html)
| Professors Responsables: |
M. CARMEN ÁLVAREZ FAURA (alvarez lsi.upc.edu)
M JOSE SERNA IGLESIAS (mjsernalsi.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 1.5 P 0.0 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Obligatoria de primer cicle per la EI
Obligatoria per la ETIS
Optativa per la ETIG
Requisits de l'assignatura
|
LGA
- Pre-requisit per la EI , ETIG , ETIS
|
|
Objectius docents
Analitzar la dificultat inherent als processos de càlcul i adquirir un
coneixement teòric de les limitacions d'aquests processos (problemes
indecidibles), i de la manera de classificar els problemes segons la seva
complexitat. Es tracta, en definitiva, d'una introducció a les teories
de la calculabilitat i de la complexitat.
Els estudiants, després de cursar aquesta assignatura, haurien de ser
capaços de discernir sobre la decidibilitat o indecidibilitat d'una
certa varietat de problemes. També
haurien de poder analitzar la complexitat temporal de certs tipus de
problemes decidibles.
Programa
1. Problemes, llenguatges i funcions
2. Màquines de Turing i algorismes.
3. Funcions calculables. Complexitat de càlcul.
4. Problemes decidibles. Temps polinomic i exponencial.
5. Reduccions. Completesa i dificultat.
6. Exemples de problemes indecidibles.
7. Exemples de problemes NP-complets.
Avaluació
Hi haura una prova parcial cap a mitjans del quadrimestre (N1) i una
prova final (N2) durant el periode d'exàmens.
De aquestes proves es calcula una nota (T) que es el màxim entre N2
i (N1+N2)/2.
Durant el curs es proposaran alguns treballs dels
que s'obtindrà una nota, entre 0 i 1.5, (P).
La nota de l'assignatura s'obté d'acord amb la regla
min (T + P,10)
Càrrega
D'acord amb el pla d'estudis, aquesta assignatura correspon a 4.5
crèdits (3 hores/setmana) repartits en 3 crèdits de teoria (2
hores/setmana), 1.5 crèdits de problemes (1 hora/setmana).
Idealment, veiem les classes de teoria com a vehicle dels conceptes bàsics i primers exemples, i les de problemes com a oportunitat de discutir l'aplicació d'aquesta teoria amb més deteniment.
Bibliografia
Bibliografia bàsica
- M. Serna, C. Àlvarez, R. Cases i A. Lozano. Els límits de la computació. Indecidibilitat i NP-completesa. Edicions UPC, 2001
- M. Garey i D. Johnson. Computers and Intractability: A guide to the theory of NP-completeness. Freeman, 1979
- J. Hopcroft i J. Ullman. Introduction to Automata Theory, Languages, andComputation. Addison-Wesley, 1979
- C. Papadimitriou. Computational Complexity. Addison Wesley, 1994
- M. Sipser. Introduction to the theory of computation. PWS, 1997
Bibliografia complementària
- J. L. Balcázar, J. Díaz i J. Gabarró. Structural Complexity I. Springer-Velarg (2nd edition), 1995
- N. J. Cutland. Computability: An introduction to recursive function theory. Cambridge University Press, 1980
- J. Gruska. Foundations of Computing . IInternationalThomson Computer Press , 1997
- H. Lewis i C. Papadimitriou. Elements of the theory of computation. Prentice Hall (2nd edition), 1998
- S. Skiena. The algorithm design manual. Springer-Verlag, 1998
- D. Wood. Theory of Computation. Wiley, 1987
|
