Sumários

Resolução de Exercícios típicos de exame

19 Dezembro 2018, 09:30 • André Souto

Resolução de exercícios.

Aula de Dúvidas

19 Dezembro 2018, 08:00 • André Souto

Aula de esclarecimento de dúvidas para o 3º teste e para o exame sobre exercícios tipo e das folhas de exercícios.

Aula de Dúvidas

18 Dezembro 2018, 10:30 • André Souto

Aula de esclarecimento de dúvidas para o 3º teste e para o exame sobre exercícios tipo e das folhas de exercícios.

Completude NP

18 Dezembro 2018, 09:30 • André Souto

Recordar a noção de problema NP com base no verificador e nas MT não deterministas.

Exemplos de problemas em NP e respectivos certificados, verificadores e MT não deterministas.
Noção de redução polinomial entre problemas.

Prova que se A é P e B se reduz a A então B também é P.

Prova que se A é NP e B se reduz a A então B também é NP.
Definição de completude de problemas NP.

Exemplos de problemas NP-completos.

Prova que A é NP e B é NP-completo e se reduz a A então A também é NP -completo.
Exemplos de uso do Lema.Referência ao problema SAT e a sua completude.

Aula de Dúvidas

17 Dezembro 2018, 08:00 • André Souto

Aula de esclarecimento de dúvidas para o 3º teste e para o exame sobre exercícios tipo e das folhas de exercícios.