CI1339 / INFO 7007

Complexidade Computacional

Segundo Semestre de 2025

Disciplina introdutória de Complexidade Computacional, com especial ênfase no estudo das classes P e NP.

É desejável (ainda que não indispensável) que o aluno tenha conhecimentos elementares de Teoria da Computação e Teoria dos Grafos.

Professor: Renato

Horário: terças e quintas-feiras das 15h30 às 17h10

Sala: CT-09

Lista de e-mails: https://listas.inf.ufpr.br/lists/ci1339.listas.inf.ufpr.br/

  1. Ao inscrever-se você receberá mensagem pedindo confirmação. Só após a confirmação você estará efetivamente inscrito.
  2. A lista só aceita mensagens enviadas a partir do endereço com o qual você se inscreveu.
  3. Você pode inscrever mais de um endereço.

Datas Importantes

11/9: não haverá aula

18/9: não haverá aula

23/9: não haverá aula: Semana Acadêmica de Computação e Informática (SACI)

25/9: não haverá aula: Semana Acadêmica de Computação e Informática (SACI)

21/10: não haverá aula: Festival da UFPR da Ciência, Cultura e Inovação/Semana Integrada de Ensino, Pesquisa e Extensão (SIEPE)

23/10: não haverá aula: Festival da UFPR da Ciência, Cultura e Inovação/Semana Integrada de Ensino, Pesquisa e Extensão (SIEPE)

30/10: não haverá aula

11/11: Avaliação:

Selton:
cobertura por vértices  ⪯ P conjunto dominante mínimo
Gabriel C.:
A Hipótese do Tempo Exponencial

13/11: Avaliação:

Rafael:

3Sat  ⪯ P 3-coloração  ⪯ P k-coloração  ⪯ P coloração mínima (:math:`= `número cromático)

System Message: WARNING/2 (index.rst, line 127); backlink

Inline interpreted text or phrase reference start-string without end-string.

System Message: WARNING/2 (index.rst, line 127); backlink

Inline interpreted text or phrase reference start-string without end-string.
André:
ciclo Hamiltoniano  ⪯ P caminho hamiltoniano  ⪯ P caminho hamiltoniano direcionado  ⪯ P grafo equivalente mínimo

18/11: Avaliação:

Henrique:
equipartição de conjunto  ⪯ P mochila
Maurício:
A Hierarquia Polinomial

20/11: não haverá aula: Dia Nacional de Zumbi e da Consciência Negra.

25/11: Avaliação:

Lucas:
3Sat  ⪯ P inequivalência de expressões regulares livres de *
Fernando:
emparelhamento 3D  ⪯ P equipartição de conjunto  ⪯ P escalonamento de Tarefas

27/11: Avaliação:

Sofia:
3Sat/cobertura por vértices  ⪯ P soma de subconjuntos  ⪯ P equipartição de conjunto  ⪯ P bin packing
Thiago:
3Sat  ⪯ P cobertura por vértices  ⪯ P conjunto independente  ⪯ P clique  ⪯ P isomorfismo de subgrafo

2/12: Avaliação:

Isadora:
Genus de grafo e o Teorema do "Graph Minor"

4/12: Avaliação:

Luiz:
cobertura exata por 3-conjuntos  ⪯ P partição de grafo em triângulos
Gabriel V.:
cobertura por vértices  ⪯ P ciclo hamiltoniano  ⪯ P caixeiro viajante

Material de Apoio

Lista de Exercícios

Miscelânea