Teoria de la computació (TC) 

Professors (QP 2024):

Carme Àlvarez   TC 12 (Professora responsable)

Ilario Bonacina  TC  21

Enrique Romero  TC 11

 Avisos:

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

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

Jutge RACSO:  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

Material docent

Llibres:

Llibre TC (llenguatges regulars i incontextuals).  

Llibre TC (computabilitat i indecidibilitat). 

           Michael Sipser. Introduction to the Theory of Computation. Third Edition. CENGAGE Learning, 2013

Vídeos apunts 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 sobre indecidibilitat:

• 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). 

Més material complementari:

• 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.