Sumários
Décima segunda aula prática
21 abril 2022, 12:30 • Francisco Miguel Alves Campos de Sousa Dionísio
Exercícios do capítulo 5: 3.4, 5.1(ab), 5.2(ab), 5.5. Avaliação MAP.
Décima primeira aula prática
20 abril 2022, 14:30 • Francisco Miguel Alves Campos de Sousa Dionísio
Exercícios sobre classes de complexidade do capítulo 5: 2.1(c), 2.3(bd), 3.5(abc), 3.7(a)
Teórica #13
19 abril 2022, 16:00 • Carlos Caleiro
A questão P versus NP. Verificação em tempo polinomial, testemunhas, caracterização alternativa da classe NP. Redutibilidade polinomial, linguagens NP-difíceis e NP-completas. Teorema de Cook-Levin, NP-completude dos problemas SUBSETSUM, PARTITION e SAT.
Teórica #13
19 abril 2022, 14:00 • Carlos Caleiro
A questão P versus NP. Verificação em tempo polinomial, testemunhas, caracterização alternativa da classe NP. Redutibilidade polinomial, linguagens NP-difíceis e NP-completas. Teorema de Cook-Levin, NP-completude dos problemas SUBSETSUM, PARTITION e SAT.
Prática 11 (aula online)
19 abril 2022, 14:00 • Eduardo Skapinakis
Exercícios 2.1(c), 3.1(bd), 3.5(abc) e 3.7(ab).