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: quartas e sextas-feiras das 13h30 às 15h30
Sala: PA-04
Lista de e-mails: https://listas.inf.ufpr.br/cgi-bin/mailman/listinfo/ci1339
- 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.
25/9: não haverá aula: Semana ABERta de Informática (SABER)
27/9: não haverá aula: Semana ABERta de Informática (SABER)
18/10: não haverá aula
15/11: não haverá aula: feriado da Proclamação da República
20/11: não haverá aula: feriado do Dia Nacional de Zumbi e da Consciência Negra
Um simulador de Máquina de Turing
Uma animação da prova do Problema da Parada (em inglês, legendado)
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).
A personal view of average-case complexity (Russell Impagliazzo): uma descrição de "cinco mundos possíveis" com relação à questão "P = NP?" (também disponível aqui em caso de dificuldade de acesso)
Graph of NP-Complete Problems: um grafo direcionado de problemas NP-Completos e reduções entre eles (agradecimento ao Vinícius Tikara pela dica).
Complexity Zoo: Um mapa de classes de complexidade computacional.