Teoria de la computaci— (TC)

 


Professors:

Carme Ëlvarez  grup 11 (coordinadora)
Enrique Romero grup 12
Antoni Lozano  grup 13

 


 

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.      Expressions regulars.

4.      Gramˆtiques incontextuals.

5.      No regularitat.

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

7.    Indecidibilitat, no-semidecidibilitat 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 semi-decidibilitat.
  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: