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/
- Ao inscrever-se você receberá mensagem pedindo confirmação. Só após a confirmação você estará efetivamente inscrito.
- A lista só aceita mensagens enviadas a partir do endereço com o qual você se inscreveu.
- Você pode inscrever mais de um endereço.
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)
28/10: não haverá aula: Dia do Servidor Público
20/11: não haverá aula: Dia Nacional de Zumbi e da Consciência Negra.
Computers and Intractability: A Guide to the Theory of NP-Completeness (Michael R. Garey and David S. Johnson)
The Nature of Computation (Cristopher Moore, Stephan Mertens)
Uma animação da prova do Problema da Parada (em inglês, legendado)
Um Quine é um programa que escreve seu próprio texto. É uma aplicação Segundo Teorema da Recursão de Kleene relativa a pontos fixos de funções computáveis.
A Quine Page recolhe Quines em diversas linguagens.
Math's Fundamental Flaw é um vídeo do Canal Veritassium sobre a relação entre os trabalhos de Cantor, Hilbert, Russel e Whitehead, Gödel e Turing (deixo aqui meu agradecimento ao Richard Heise pela indicação).