Teoria de la computació (TC) 

 

 

Professors (QP 2025):

 

Carme Àlvarez  (Professora responsable) TC 12

Ilario Bonacina   TC 21

Enrique Romero  TC 11

 

 

 

Planificació del curs

 

·       La pàgina de l’assignatura TC està subjecta a canvis. 

·       Mètode docent i mètode avaluador.

·       Calendari del laboratori i examens.

·       Organització de les classes.

 

 

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.