Sumários

Aula Teórica 25

4 janeiro 2011, 10:00 • Maria Paula Antunes Abrantes Gouveia

Revisões. Esclarecimento de dúvidas.

Aula Teórica 25

4 janeiro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia

Revisões. Esclarecimento de dúvidas.

Aula Prática 14

4 janeiro 2011, 08:30 • Manuel Biscaia Martins

Conclusão dos exercícios da Aula Prática 13. Esclarecimento de dúvidas para o teste 4.

Aula Prática 13

17 dezembro 2010, 12:00 • Manuel Biscaia Martins

Exercícios 1.1a, 1.1b, 1.3b, 1.3c e 2.1b da  lista de exercícios para a aula prática 13.

Aula Teórica 24

16 dezembro 2010, 12:00 • Maria Paula Antunes Abrantes Gouveia

Resolução de exercícios de Testes 4 de 2009/2010.  Exercício 1: Seja f:\Sigma^*->\Sigma^* uma função total em PF e seja x um elemento do contradomínio de f. Mostre que a linguagem A={y\in Sigma^*: f(y)=x} pertence à classe P. Exercício 2: (a) Mostre que se L1 se reduz polinomialmente a L2 e L2 se reduz polinomialmente a L3 então L1 reduz-se polinomialmente a L3; (b) Mostre que se uma linguagem L é C-difícil eL se reduz polinomialmente a L' então L' é C-difícil.