Augmentar lletres   Inici   Informació   Contactar   Mapa
Castellano   English

Teoria de la Computació (TC)

Crèdits Dept. Tipus Requisits
9.0 (7.2 ECTS) LSI
  • Obligatòria per a l'EI
  • Optativa per a l'ETIG
 ADA - Pre-requisit per la EI , ETIG
MATD - Pre-requisit per la EI , ETIG

Professors

Responsable:  Guillermo Godoy Balil (ggodoy@lsi.upc.edu)
Rafel Cases Muñoz (cases@lsi.upc.edu)
Altres:Dieter Wilhelm Mitsche M ()
Enrique Romero Merino (eromero@lsi.upc.edu)
Glyn Verden Morrill (morrill@lsi.upc.edu)
Luis Marquez Villodre (lluism@lsi.upc.edu)
M. Del Carme Alvarez Faura (alvarez@lsi.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:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Llenguatges formals
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 1,0 0 0 0 4,0 0 8,0
1. Introducció
2. Alfabets i mots
3. Operacions amb mots
4. Llenguatges. Concatenació
5. Altres operacions amb llenguatges
6. Morfismes i substitucions

2. Gramàtiques incontextuals
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 6,0 0 0 0 10,0 0 20,0
1. Introducció
2. Definició
3. Arbre de derivació. Ambigüitat
4. Verificació de gramàtiques
5. Operacions bàsiques amb gramàtiques
6. La intersecció de dos CFL pot no ser CFL.

3. Normalització de gramàtiques
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Introducció
2. Eliminació de produccions nul·les
3. Eliminació de produccions unàries
4. Eliminació de símbols inútils
5. Gramàtiques depurades
6. Forma normal de Chomsky

4. Autòmats finits
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 4,0 0 0 0 8,0 0 16,0
1. Introducció
2. Autòmats finits deterministes
3. Verificació d'automats finits
4. Autòmats finits indeterministes
5. Equivalència dels NFA amb els DFA
6. Autòmats finits amb lambda-transicions
7. Operacions bàsiques amb autòmats
8. Llenguatges no regulars

5. Minimització d'autòmats finits
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Minimització d'un DFA
2. Algorisme de minimització
3. Sobre la talla del DFA mínim
4. Equivalència entre autòmats

6. Expressions regulars i gramàtiques regulars
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 4,0 0 0 0 8,0 0 16,0
1. Introducció
2. Expressions regulars
3. Equacions lineals entre llenguatges. Lema d'Arden
4. Sistemes d'equacions lineals associats a un NFA
5. Gramàtiques regulars
6. Correspondència entre gramàtiques regulars i autòmats finits
7. Morfismes i substitucions de llenguatges regulars

7. Propietats d'iteració
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 4,0 0 0 0 6,0 0 12,0
1. Lema de bombament de llenguatges regulars
2. Lemes de bombament de llenguatges incontextuals

8. Autòmats amb pila
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 2,0 0 0 0 6,0 0 12,0
1. Introducció
2. Autòmats amb pila deterministes
3. Autòmats amb pila indeterministes
4. Equivalència entre autòmats amb plia i gramàtiques incontextuals
5. Propietats de tancament dels CFL i dels DCFL

9. Autòmats bidireccionals i jerarquia de Chomsky
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Introducció
2. Autòmats finits bidireccionals
3. Autòmats amb pila bidireccionals
4. Relació entre les famílies de llenguatges estudiades
5. La jerarquia de Chomsky. Gramàtiques de tipus 0

10. Màquines de Turing
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 3,0 0 0 0 6,0 0 12,0
1. Introducció a la calculabilitat. Problemes indecidibles
2. Definició de TM. Interpretació
3. Computació. Convergència i divergència
4. Llenguatge reconegut i funció computada per una TM
5. TM d'aturada segura. Temps de càlcul
6. Llenguatges enumeralbes recursivament i llenguatges decidibles
7. Funcions computables
8. Extensions del model bàsic de TM

11. Màquines de Turing i algorismes
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Els esquemes algorísmics bàsics
2. Codificació de les TM
3. Intèrprets i simuladors. La TM universal
4. La tesi de Church-Turing

12. Computabilitat i decidibilitat
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 2,0 0 0 0 4,0 0 8,0
1. Teorema de la projecció
2. Propietats de tancament dels llenguatges e.r. i decidibles
3. Teorema del complementari
4. Alguns llenguatges e.r. El llenguatge K
5. Llenguatges no decidibles

13. Reductibilitat i completesa
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 5,0 0 0 0 7,0 0 14,0
1. Reducció entre problemes
2. Propietats de les reduccions. Exemples de reduccions
3. Teorema de Rice
4. Conjunts enumerable recursivament complets

14. Alguns problemes indecidibles clàssics
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 0 0 0 0 3,0 0 6,0
1. El problema dels mots de Thue
2. El problema de la correspondència de Post
3. Problemes indecidibles sobre llenguatges incontextuals

15. Computació fitada. Espai i temps
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
1. Temps de càlcul
2. Espai de càlcul
3. Classes de complexitat
4. Propietats


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
41,0 39,0 0 0 0 80,0 0 160,0
Hores addicionals dedicades a l'avaluació 20,0
Total hores de treball per l'estudiant 180,0

Metodologia docent

(-)

Mètode d'avaluació

L'avaluació es basa en dos components:

1. Una successió de proves al llarg del quadrimestre.
Anomenem P a la suma de les notes d'aquestes proves.
El valor màxim de P estarà comprès entre 2 i 3.

2. L'examen final. Anomenem F la nota obtinguda (sobre 10).

La nota global, N, s'obté així: N = P + F·(1 - P/10).

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

(Informació no introduïda)

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



 
logo FIB © Facultat d'Informàtica de Barcelona - webmaster@fib.upc.edu - RSS RSS