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

Notação Big-O
Resolução de exercícios


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

Resolução de exercícios