Sumários
Esclarecimento de dúvidas para o teste 4.
18 dezembro 2012, 08:00 • João Rasga
Esclarecimento de dúvidas para o teste 4.
Aula Prática 13
14 dezembro 2012, 12:00 • Maria Paula Antunes Abrantes Gouveia
Exercícios 2.4 a) b) e 2.5 a) b) da lista de exercícios para a aula prática 13.
Aula Teórica 24
13 dezembro 2012, 12:00 • Maria Paula Antunes Abrantes Gouveia
Proposição: Se existe uma máquina de Turing que reconhece L em espaço s construtível no espaço e \(s(n)\geq log_2(n+1)\) então L é decidível. Prova da proposição (conclusão). Referência informal ao problema P vs NP e a exemplos de problemas NP-completos (problema do caixeiro viajante e SAT).
Funções construtíveis no tempo. Classes de complexidade.
13 dezembro 2012, 12:00 • João Rasga
Resolução dos exercícios: 1.2f, 2.1b, 4a e 4b