Sumários
Aula Teórica 23
14 dezembro 2010, 10:00 • Maria Paula Antunes Abrantes Gouveia
Classes de complexidade SPACE(s), PSPACE e EXPSPACE. Referência às inclusões de P em PSPACE e de PSPACE em EXP. Refefência a um exemplo de linguagem em EXP mas não em P (máquinas de Turing que aceitam uma palavra w em no máximo 2^|w| passos). Referênia a exemplos de linguagens para as quais é um problema em aberto saber se pertencem ou não a P (primalidade de um inteiro, factorização prima de um inteiro, caixeiro viajante, caminhos hamiltonianos). Classes de complexidade PF e PSPACEF. Redução polinomial de uma linguagem A a uma linguagem B. Enunciado e prova da proposição: se A se reduz polinomialmente a B e B está em PSPACE então A está em PSPACE.
Aula Teórica 23
14 dezembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia
Classes de complexidade SPACE(s), PSPACE e EXPSPACE. Referência às inclusões de P em PSPACE e de PSPACE em EXP. Refefência a um exemplo de linguagem em EXP mas não em P (máquinas de Turing que aceitam uma palavra w em no máximo 2^|w| passos). Referênia a exemplos de linguagens para as quais é um problema em aberto saber se pertencem ou não a P (primalidade de um inteiro, factorização prima de um inteiro, caixeiro viajante, caminhos hamiltonianos). Classes de complexidade PF e PSPACEF. Redução polinomial de uma linguagem A a uma linguagem B. Enunciado e prova da proposição: se A se reduz polinomialmente a B e B está em PSPACE então A está em PSPACE. Linguagem C-difícil e linguagem C-completa.
Aula Prática 13
14 dezembro 2010, 08:30 • 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 Prática 12
10 dezembro 2010, 12:00 • Manuel Biscaia Martins
Exercícios 1, 2, 3, 4a, 4c, 4e, 5c, 5e e 7 da lista de exercícios para a aula prática 12.
Aula Prática 12
9 dezembro 2010, 14:30 • Maria Paula Antunes Abrantes Gouveia
Exercícios 1, 2, 3, 4a, 4c, 4e, 5c, 5e e 7 da lista de exercícios para a aula prática 12.