Anúncios
Teórica #23
19 maio 2020, 16:38 • Carlos Caleiro
Separação de classes de complexidade
Teorema de hierarquia espacial e aplicações (vídeo)
Teorema de hierarquia temporal e aplicações (vídeo)
estes conteúdos estarão disponíveis até 2a-feira, 1 de Junho
Teórica #22
19 maio 2020, 16:35 • Carlos Caleiro
NP-completude
Teorema de Cook-Levin para SUBSETSUM (vídeo)
NP-completude de PARTITION (vídeo)
Decisão versus pesquisa (vídeo)
estes conteúdos estarão disponíveis até 5a-feira, 28 de Maio
Prática #11
19 maio 2020, 14:05 • Carlos Caleiro
Os exercícios para a aula prática 11, sobre classes de complexidade, redução polinomial, problemas difíceis e completos, são: capítulo 4, exercícios 3.4, 5.1(a,b), 5.2(a,b), extra (reduções entre SUBSETSUM e PARTITION, em unário e em binário), 5.5.
Teórica #21
13 maio 2020, 17:32 • Carlos Caleiro
O problema P versus NP
Caracterização determinística de NP (vídeo)
NP-completude (vídeo)
estes conteúdos estarão disponíveis até 5a-feira, 21 de Maio
Teórica #20
13 maio 2020, 17:31 • Carlos Caleiro