Teoria de la Computació ( TC )

Professors

Responsable:	Rafel Cases Muñoz (caseslsi.upc.edu).
Altres:	Albert Atserias Peri (atseriaslsi.upc.edu) Guillem Godoy Balil (ggodoylsi.upc.edu) Jordi Cortadella Fortuny (jordi.cortadellaupc.edu) M. Carmen Alvarez Faura (alvarezlsi.upc.edu).

Objectius Generals

Donar una estructura teórica que permeti analitzar els procesos de càlcul en funció de la dificultat de computació. Estudiar la relació entre generativitat (gramàtiques) i resolubilitat (automats), amb vista al seu us en Compiladors. Adquirir un coneixement teòric de les limitacions d'aquests processos (problemes indecidibles).

Els estudiants, després de cursar aquesta assignatura, haurien de coneixer els graus de complexitat intrínsecs dels llenguatges regulars i incontextuals. Disposaran d'algunes eines per descriure aquests llenguatges, per reconeixer-los i per caracteritzar-los.

Objectius Específics

Coneixements

1. Complexitat d'algorismes i complexitat de problemes
   
2. Processos de computació que requereixen només memòria finita.
   Autòmats finits
3. Gramàtiques formals. Anàlisi i compilació. Generativitat.
   
4. Relació entre processos generatius i processos recognoscitius
5. Jerarquització dels problemes segons la complexitat
6. Els límits lògics de la capacitat computacional
7. Problemes indecidibles

Habilitats

1. Trobar el model de computació més simple per a cada problema.
2. Disposar d'eines que permeten descartar solucions massa simples per a problemes donats.
3. Disposar d'eines que permeten descriure adequadament els procssos de càlcul.

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. Capacitat per transformar enunciats informals a enunciats formals, i a l'inrevés.
3. Capacitat d'aplicar els coneixements de matemàtiques i lògica a la resolució de problemes.
4. Capacitat per crear i utilitzar models de la realitat.
5. Capacitat d'anàlisi i de síntesi.

Continguts

Hores estimades de:

Metodologia docent

(Informació no introduïda)

Mètode d'avaluació

La nota final (F) té dues components additives: una component
de la part teòrica (T) i una component de la part de problemes (P).
Determinació de la component teòrica:
-------------------------------------------------------------
Cap a mitjans del quadrimestre es passarà una prova de la part del
temari que s'hagi estudiat fins a aquell moment. En acabar el curs es
passarà una prova de la totalitat del temari.
La nota corresponent a la part teòrica s'obté així:
....... Sigui N1 la nota sobre 10 de la prova parcial.
....... Sigui N2 la nota sobre 10 de la prova final.
....... Sigui N3 la mitjana aritmètica de N1 i N2.
............... T = MAX{N2 , N3}
Determinació de la component de problemes:
------------------------------------------------------------------------
Hi ha possibilitat de resoldre uns exercicis, l'enunciat dels quals
es farà públic al llarg del curs. La nota que s'obté amb aquests
exercicis, que pot sumar un màxim d'un punt, és la component P.
Determinació de la nota final:
-----------------------------------------------
Si la component teòrica és com a mínim de 3,5, s'obté la nota final
sumant les components teòrica i pràctica, sense que el resultat pugui
superar el 10. Es a dir:
............... F = MIN{10 , T+P}
Però si la component teòrica no arriba a 3,5, la nota final serà T.

Bibliografía bàsica

• Cases, R. i Màrquez, L. Llenguatges, gramàtiques i autòmats. Curs bàsic, Edicions UPC, 2003.
• Hopcroft, J.E.; Motwani, R. i Ullman, J.D. Introduction to Automata Theory, Languages, and Computation (hi ha traducció a l'espanyol de la mateixa editorial amb el títol "Introducción a la Teoría de Autómatas, Lenguajes y Computación"), Addison-Wesley, 2001 (2a ed.).
• Kelley, Dean Automata and Formal Languages (Hi ha trad. a l'espanyol de la mateixa editorial), Prentice Hall, 1995.
• Serna, M.; Àlvarez, C.; Cases, R. i Lozano, A. Els límits de la computació. Indecidibilitat i NP-completesa, Edicions UPC, 2001.
• Sipser, M. Introduction to the theory of computation, PWS, 1997.

Bibliografía complementària

• Brookshear, J.G. Teoria de la Computación, Addison-Wesley Iberoamericana, 1993.
• Gabarró, J. Informàtica clàssica, Eumo, Vic, 1995.
• Gruska, J. Foundations of computing, InternationalThomson Computer Press, 1997.
• Kinber, E. i Smith, C. Theory of computing, Prentice Hall, 2001.
• Kozen, D. Automata and Computability, Springer-Verlag, 1997.
• Lewis, H.R. i Papadimitriou, C.H. Elements of the Theory of Computation, Prentice-Hall, Eglewood Cliffs, NJ, 1998 (2a ed.).
• Simovici, D.A. i Tenney, R.L. Theory of formal languages with applications, World Scientific Publ. Co., 1999.
• Vancells, J. i Sesa, E. Teoria d'autòmats i llenguatges formals I, UOC, 1999.
• Wood, D. Theory of Computation, Harper and Row, NY, 1987.

Enllaços web

Capacitats prèvies

Capacitat d'expressar en fórmules lògiques els enunciats descrits en llengua comú
Capacitat de manipular fórmules lògiques
Coneixements algebraics fonamentals: monoides, grups, tancaments, morfismes.
Coneixements bàsics de combinatòria
Capacitat d'utilitzar amb facilitat les propietats d'una àlgebra de Boole
Coneixement de les estructures de dades bàsiques i d'algorísmia fonamental
Capacitat d'avaluar la complexitat temporal d'un algorisme