Teoria de la computació (TC) 

 


Professors (QP 2023):

Enrique Romero  TC 11L, TC11P i TC12 P

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

Ilario Bonacino  TC 12L


 

 


 

Avisos:


Apunts, exàmens i d’altres exercicis:

 



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: