Sumários

Resolução de exercícios sobre complexidade

15 Dezembro 2020, 10:30 • Andreia Mordido

Resolução de exercícios sobre classes de complexidade e reduções polinomiais.

Aula em regime misto alternado.

Classe NP

15 Dezembro 2020, 09:30 • André Souto

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.
Consequências de existência de reduções polinomiais entre problemas.

Aula em regime não presencial síncrono transmitida via zoom.

Resolução de exercícios sobre complexidade

14 Dezembro 2020, 08:00 • André Souto

Resolução de exercícios sobre classes de complexidade da folha 10.


Resolução do 4º exercício TP.

Aula em regime misto alternado com transmissão via zoom. Aula dada em regime alternado misto transmitida via Zoom.

Resolução de exercícios sobre decibilididade e redutibilidade

11 Dezembro 2020, 11:30 • André Souto

Resolução de exercícios sobre decibilididade e redutibilidade.

Aula em regime alternado misto com transmissão via zoom.

Resolução de exercícios sobre decibilididade e redutibilidade

11 Dezembro 2020, 08:00 • Andreia Mordido

Resolução de exercícios sobre decibilididade e redutibilidade.

Aula em regime misto alternado.