Teoria de la computació (TC) 

Professors:

Carme Àlvarez   TC 13 i TC 21P (Responsable) 

Maria Blesa   TC 21L

Antoni Lozano  TC 12 i TC 22

Enrique Romero  TC 11

Avisos:

• La pàgina de l’assignatura TC està subjecta a canvis. 
• Calendari del laboratori i examens. Mètode Docent i Avaluador.

Apunts, exàmens i d’altres exercicis:

• Llibre TC (llenguatges regulars i incontextuals). Llibre TC (computabilitat i indecidibilitat). 
• Llenguatges de Dyck. 
• Exemples de construcció d'autòmats finits: aquí teniu una col.lecció elaborada per Lluís Màrquez i Enrique Romero, que exposa el mètode estàndard de construcció d'autòmats finits, així com exemples d'algunes excepcions i material complementari. 
• Exercicis antics. 
• Exàmens d'anys anteriors. 

Informació per a  l’avaluació contínua:

Juez online.

Exercicis per a l’avaluació contínua:

1.      Teoria de llenguatges

2.      Autòmats Finits

3.     Gramàtiques incontextuals

4.      Expressions regulars

5.      No regularitat. Autòmats amb pila. Jerarquia de Chomsky 

6.      Màquines de Turing. Decidibilitat, semidecidibilitat i computabilitat

7.      Indecidibilitat, no semidecibilitat i no computabilitat

8.      Problemes naturals indecidibles

Vídeos del curs: 

1. Teoria de llenguatges (1). 
2. Teoria de llenguatges  (2). 
3. Teoria de llenguatges (3). 
4. Autòmats finits deterministes.
5. Autòmats finits indeterministes. 
6. Notacions de DFAs i NFAs (1). 
7. Notacions de DFAs i NFAs (2). 
8. Operacions sobre Reg (1). 
9. Operacions sobre Reg (2). 
10. Operacions sobre Reg (3). 
11. Minimització de DFAs (1). 
12. Minimització de DFAs (2). 
13. Minimització de DFAs (3). 
14. Gramàtiques incontextuals. 
15. Operacions sobre gramàtiques. 
16. Depuració de gramàtiques (1). 
17. Depuració de gramàtiques (2). 
18. Depuració de gramàtiques (3). 
19. Expressions regulars (1). 
20. Expressions regulars (2). 
21. No regularitat (1). 
22. No regularitat (2). 
23. Autòmats amb pila (PDA). 
24. Equivalència entre CFG i PDA (1). 
25. Equivalència entre CFG i PDA (2). 
26. Operacions sobre PDA, i Jerarquia de Chomsky. 
27. Màquines de Turing (1). 
28. Màquines de Turing (2). 
29. Equivalència TM-programes. 
30. Assumpcions sobre TM-programes. 
31. Operacions sobre TM-programes. 
32. No decidibilitat. 
33. No semidecidibilitat. 
34. No computabilitat 
35. Accessibilitat i PCP-INI. 
36. PCP, Intersecció no buida, ambigüitat 
37. No universalitat, Lògica dels mots. 

Vídeos complementaris:

• Diagonalització i no decidibilitat de K. 
• Problemes resolts sobre preservació de decidibilitat i  semidecidibilitat. 
• Exercicis resolts sobre reduccions (1). 
• Exercicis resolts sobre reduccions (2). 
• Exercicis resolts sobre reduccions (3). 
• Exercicis resolts sobre reduccions (4).