Sumários
resolução de exercícios folha 9
14 Dezembro 2021, 10:30 • André Souto
Resolução de exercícios da folha 9 sobre complexidade, classe P e NP.
Problemas NP completos
14 Dezembro 2021, 09:30 • André Souto
Noção de problema NP-completo.
Exemplos de problemas NP completos: SAT e 3SAT.
Formas de provar que um problema é NP-completo.
Prova que A\leq_p B e A é NP e B é P então P=NP.
Prova que A\leq_p B e A é NP-completo e B é NP então B é NP completo.
Enunciado e ideia da prova de que 3SAT é NP-completo.
Resolução de exercícios tipo de exame sobre esta matéria.
Complexidade temporal
13 Dezembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano
Análise da Complexidade temporal de programas
Resolução exercícios folha 8
10 Dezembro 2021, 11:30 • André Souto
Resolução de exercícios sobre redutibuilidade.
Redução por mapeamento entre linguagens
10 Dezembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano
Funções computáveis