Complexidade Computacional
Graduação: ICSA41; PPGCC: CCCC

Disciplina ofertada em conjunto para os cursos de graduação do DAINF da UTFPR-CT (Engenharia de Computação e Sistemas de Informação) e para o Programa de Pós-graduação em Ciência da Computação (PPGCC) da UTFPR-PG.

• Estudantes de outros programas de pós-graduação, como PPGINF/UFPR e PPGCA/UTFPR-CT, também são convidados a participar, devendo se inscrever através deste edital (atenção, pois as inscrições serão exclusivamente nos dias 19 e 20 de março de 2025, podendo ser encerradas antes caso as vagas sejam preenchidas). Via de regra, a solicitação de aproveitamento dos créditos é feita após a conclusão da disciplina. No caso do PPGINF, por exemplo, o regimento prevê que podem ser aproveitados até 4 créditos em disciplinas externas. De qualquer forma, é necessário matricular-se na disciplina do PPGCC como aluno externo através do edital supracitado.

Horário:

• Quartas-feiras, 19:30–21:10 (com o tradicional café levado pelo professor)
• Quintas-feiras, 18:40–20:20

Ensalamento: sala CQ-305 (UTFPR-CT, Sede Centro)

Google Meet: link divulgado no grupo do Telegram e do Google Classroom para os participantes do curso

• Apenas estudantes de pós-graduação e participantes ouvintes poderão acompanhar a disciplina via Google Meet, mas ainda assim de modo síncrono.
• As aulas não serão (nem podem ser) gravadas.
• Estudantes de Curitiba, ainda que de pós-graduação, são recomendados fortemente a participarem presencialmente. No caso de estudantes de graduação da UTFPR-CT, a participação presencial é obrigatória.

Pré-requisitos:

• Para estudantes de graduação, é obrigatório ter cursado ICSA31 - Teoria da Computação
• Para todos os participantes, é necessário ter conhecimento sobre:
  1. as classes de complexidade básicas (pelo menos \(\mathsf P\) e \(\mathsf{NP}\));
  2. o Teorema de Cook–Levin;
  3. a \(\mathsf{NP}\)-completude dos principais problemas de Karp, como o Problema do Conjunto Independente.
  4. Estes e outros tópicos podem ser encontrados em Pap93, ArBa09, e nas notas de aula de ICSA31.

Atendimento do professor ao estudante

• Terças-feiras, das 13:50 às 16:50
• Presencial no DAINF, Sala 12, ramal 4964
• Outros horários, assim como atendimentos remotos, poderão ser agendados por e-mail ou mensagem direta no Telegram