UFC - Departamento de Computação
Complexidade Computacional (CK198 / CKP8599)
Semestre: 2025.2
Horário: Segundas e Quartas 14h-16h
Local: Sala 1074, Bloco 915
Atendimento: Por meio do SIGAA da disciplina.
Apresentação:
Listas de Exercícios
Cada questão tem um prazo de entrega diferente. A data de entrega de cada exercício está marcada ao lado de cada questão.
Cada questão receberá uma nota entre 0 e 1.
Questões entregues até no máximo 2 dias após o prazo receberão no máximo 0.75. Até no máximo 1 semana, receberão no máximo 0.5.
Não serão aceitas questões entregues após 1 semana do prazo.
Enviar os exercícios até 23h59 para os emails jmbmaluno@alu.ufc.br e rudini@ufc.br
com o título "Complexidade Computacional - Questão X", onde X é o número da questão.
As questões devem ser escritas à mão e devem ser enviadas como imagem (foto) ou PDF digitalizado.
Tópicos adicionais:
- Classes de Complexidade de Aproximação para Problemas de Otimização (slides)
- Classes de Complexidade Probabilística para Problemas de Decisão (slides)
- EXPTIME-completude (slides)
Livro-texto:
- M. Sipser, Introdução a Teoria da Computação, Thomson, 2007
- T. H. Cormen, C. E. Leiserson e R. L. Rivest, Algoritmos - Teoria e Prática, Editora Campus, 2014.
- S. Araujo, N. Martins, N. Nisse, R. Sampaio, Teoria dos Jogos Combinatórios em Grafos, IMPA, 2025
- J. Araujo, M. Dourado, F. Protti, R. Sampaio, Introduction to Graph Convexity, Springer, 2025