Calendário

  • P1 - 27/mar
  • P2 - 03/mai
  • P3 - 07/jun
  • PF - 03/jul

Avaliação

São 3 provas (P1, P2, P3) com mesmo peso e conteúdo cumulativo e uma prova final (PF) sobre toda a matéria.

  • Alunos de Pós não fazem PF

Nas provas, NÃO é permitido qualquer tipo de consulta

Bibliografia

  • Logicomix: An Epic Search for Truth, Doxiadis e Papadimitriou (Logicomix)
  • The Nature of Computation, Moore e Mertens (Nature)
  • Quantum Computing Since Democritus, Aaronson (Democritus)

Material das Aulas



Busca da Verdade
ID Título Aula Exercícios Leituras
1.1 "Faça-se a Verdade" file_download attachment Logicomix, Democritus (Cap. 1)

(esse material)
(esse video)
1.2 O Maior Número file_download attachment Logicomix, Democritus (Cap. 2)
1.3 Boole, Frege, Russell, Hilbert, Zermelo, Godel,... file_download attachment Logicomix, Democritus (Cap. 3)
1.4 Infinito e Além file_download attachment Democritus (Cap. 2)

(esse video)
(Cap. 23 - "Maxwell e os Nerds")
1.5 Calculemus! Pois não há Ignorabimus! file_download attachment Nature (Seção 7.1), Logicomix

(artigo do Turing'1936)
(para quem tiver tempo)
1.6 Mais Problemas que Soluções file_download attachment Nature (Seção 7.2), Democritus (Cap. 3)

(problemas indecidíveis)
1.7 A Tese de Church e Turing file_download attachment Nature (Seção 7.5.3), Democritus (Cap. 4)

(artigo da Wikipedia)
1.8 Mentes e Máquinas file_download Democritus (Cap. 4 e 11)



O Fácil, o Impossível, e o que está no Meio
ID Título Aula Exercícios Leituras
2.1 Olá Complexidade! file_download attachment Nature (Seções 2.1 e 2.2)

(1a aula do Knuth)
(para quem tiver tempo)
2.2 O Poder dos Algoritmos file_download attachment Nature (Seções 2.3 e 6.3), Democritus (Cap. 5)

(artigo de Hartmanis e Stearns'1965)
(linha do tempo de algoritmos)
2.3 Topo do Politopo file_download attachment Nature (Seções 2.4, 2.5, 9.4)

(artigo de Jack Edmonds'1965)
2.4 Escadaria da Dificuldade file_download attachment Nature (Seção 3.8)
2.5 O Que Está no Meio file_download attachment Nature (Seções 4.1, 4.2, 4.3.1, 4.3.2, 6.1.1)
2.6 Solucionar ou Verificar, Eis a Questão file_download Democritus (Cap. 6), Nature (Seções 6.1 e 6.8)

(O homem que tentou redimir o mundo com lógica)
(carta de Gödel - original)
(carta de Gödel - inglês)
2.7 A Noz Mais Dura de Todas file_download attachment Democritus (Cap. 6), Nature (5.1, 5.2)

(enquete de 2002)
(enquete de 2012)
(uma opinião controversa sobre "P = NP?")
2.8 O Melhor file_download Nature (Seções 9.1 e 9.2.1)



Jogando Dados
ID Título Aula Exercícios Leituras
3.1 Aleatoriedade file_download (Aleatoriedade)

(Teoria Algorítmica da Informação)
3.2 Las Vegas, Monte Carlo ou Atlantic City file_download (Algoritmos Aleatorizados)
3.3 Dados são Jogados? file_download Nature (Seção 10.9), Democritus (Cap. 7)
3.4 Provas file_download Nature (Seções 11.1 e 11.2), Democritus (Cap. 13)
3.5 Quântica 1 file_download Nature (Seção 15.1 e 15.2), Democritus (Cap. 9 e 10)
3.6 Quântica 2 file_download Nature (Seção 15.1 e 15.2), Democritus (Cap. 9 e 10)
3.7 Aprendibilidade file_download Democritus (Cap. 16)