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)
|