Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Teoria de la Computació (TC)

Crèdits Dept. Tipus Requisits
9.0 (7.2 ECTS) CS
  • 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:  (-)
Altres:(-)

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

La metodologia docent i la forma d'avaluació tenen per objectiu augmentar el nivell d'activitat dels alumnes a classe, potenciar l'autoaprenentatge i millorar l'aprenentatge de la matèria en general.

A classe no s'imparteixen els continguts de la matèria. Aquests es donen a videos accessibles per internet. Les classes s'aprofiten per a resoldre dubtes dels alumnes i fer avaluació continuada.

Mètode d'avaluació

L'avaluació final s'obté de 3 notes, l'examen final F (valorat entre 0 i 10 punts), 3 controls fets al llarg del curs C (que en total valen entre 0 i 1 punt), i l'avaluació de les presentacions a la pissarra dels problemes que s'han assignat als alumnes P (entre 0 i 2.5 punts). L'avaluació de l'assignatura s'obté segons la fórmula:

max(F,min(10,0.75F+C+P))

Notem que l'expressió 0.75F+C+P pot sumar fins a 11. D'aquí que s'agafi el mínim amb 10. El maxim amb F es fa per tal d'evitar que l'avaluació continuada perjudiqui a qui faci bé l'examen final.

Bibliografía bàsica

  • Rafel Cases, Lluís Màrquez Llenguatges, gramàtiques i autòmats : curs bàsic, Edicions UPC, 2003.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to automata theory, languages, and computation, Pearson Education International, 2003.
  • Dean Kelley Automata and formal languages : an introduction, Prentice Hall, 1995.
  • Maria Serna ... [et al.] Els Límits de la computació : indecidibilitat i NP-completesa, Edicions UPC, 2001.
  • Michael Sipser Introduction to the theory of computation, Thomson Course Technology, 2006.

Bibliografía complementària

  • J. Glenn Brookshear Teoría de la computación : lenguajes formales, autómatas y complejidad, Addison-Wesley Iberoamericana, 1993.
  • Joaquim Gabarró Vallès Informàtica clàssica : autòmats i gramàtiques, indecidibilitat, parallelisme massiu, Eumo, 1995.
  • Jozef Gruska Foundations of computing, International Thomson Computer Press, 1997.
  • Efim Kinber, Carl Smith Theory of computing : a gentle introduction, Prentice-Hall, 2001.
  • Dexter C. Kozen. Automata and computability, Springer-Verlag,, 1997.
  • Harry R. Lewis, Christos H. Papadimitriou Elements of the theory of computation, Prentice-Hall,, 1998.
  • Dan A. Simovici, Richard L. Tenney Theory of formal languages with applications, World Scientific, 1999.
  • Joan Vancells i Flotats Teoria d'autòmats i llenguatges formals I, Universitat Oberta de Catalunya, 2000.
  • Derik Wood Theory of computation, Harper & Row, 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


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil