Sumários

Resolução exercícios folha 8

10 Dezembro 2021, 08:00 • André Souto

Resolução de exercícios sobre redutibuilidade.

Não se realizou

7 Dezembro 2021, 10:30 • André Souto

Por motivos de assistência à família não se realizou.

O docente disponibilizou horário de dúvidas extra e o video com a resolução dos exercícios da aula.

Por motivos de assistência à família não se realizou.
O docente disponibilizou um horário de dúvida extra para esclarecimento de dúvidas.
Além disso disponibilizou um vídeo com o conteúdo da matéria que seria leccionada:

A classe complexidade NP.

Noção de verificador de tempo polinomial.

Definição de certificado.

Definição de problemas da classe NP como sendo a classe de problemas que admitem um verificador de tempo polinomial.

Exemplos de linguagens em NP.

Recordar a noção de tempo de execução numa máquina não determinista.

Noção de problema em NP via máquinas não deterministas.

Prova que as duas definições de NP são equivalentes.

Mais exemplos de problemas em NP.

Noção de redução polinomial.

Redução por mapeamento entre linguagens

6 Dezembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Resolução de exercícios

Resolução de exercícios folha 7

3 Dezembro 2021, 11:30 • André Souto

Resolução de exercícios sobre decidibilidade.