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:
- Teoria de llenguatges (1).
- Teoria de llenguatges (2).
- Teoria de llenguatges (3).
- Autòmats finits deterministes.
- Autòmats finits indeterministes.
- Notacions de DFAs i NFAs (1).
- Notacions de DFAs i NFAs (2).
- Operacions sobre Reg (1).
- Operacions sobre Reg (2).
- Operacions sobre Reg (3).
- Minimització de DFAs (1).
- Minimització de DFAs (2).
- Minimització de DFAs (3).
- Gramàtiques incontextuals.
- Operacions sobre gramàtiques.
- Depuració de gramàtiques (1).
- Depuració de gramàtiques (2).
- Depuració de gramàtiques (3).
- Expressions regulars (1).
- Expressions regulars (2).
- No regularitat (1).
- No regularitat (2).
- Autòmats amb pila (PDA).
- Equivalència entre CFG i PDA (1).
- Equivalència entre CFG i PDA (2).
- Operacions sobre PDA, i Jerarquia de Chomsky.
- Màquines de Turing (1).
- Màquines de Turing (2).
- Equivalència TM-programes.
- Assumpcions sobre TM-programes.
- Operacions sobre TM-programes.
- No decidibilitat.
- No semidecidibilitat.
- No computabilitat
- Accessibilitat i PCP-INI.
- PCP, Intersecció no buida, ambigüitat
- No universalitat, Lògica dels mots.
Vídeos complementaris: