Responsable: | (-) |
Altres: | (-) |
Crèdits | Dept. | Tipus | Requisits |
---|---|---|---|
9.0 (7.2 ECTS) | CS |
|
ADA
- Pre-requisit per la EI , ETIG MATD - Pre-requisit per la EI , ETIG |
Responsable: | (-) |
Altres: | (-) |
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.
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 |
|
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. |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
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 |
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.
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.
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