Que anotações da palestra todos deveriam ler?

113

Houve várias perguntas com o mesmo esquema que este:

Eu relutava em postar mais uma, mas as anotações de Jeff Erickson sobre algoritmos mudaram de idéia. Eu pensei: Oh meu! Todos esses anos e eu não vi essas excelentes notas!

Então, pensei que poderia haver outras ótimas notas de aula, que realmente valem a pena ser lidas. Portanto, para cada subcampo da ciência da computação ( estruturas de dados, algoritmos, teoria da computação, complexidade computacional, criptografia etc.), recomende as excelentes notas de aula de sua escolha e diga por que você acha que é excelente.

Uma regra simples para mantê-lo organizado: uma resposta por cada subcampo. (Este será um wiki da comunidade, para que você possa editar as respostas existentes e adicionar sua recomendação.)

reference-request soft-question big-list M.S. Dousti
fonte
9
Você recebe meu voto. Se apenas como uma lista já existia quando eu era um estudante ...
Anthony Labarre
7
Obrigado pelo link para as excelentes notas de Jeff Erickson!
Standa Zivny
2
Essa pergunta também deve ser wiki da comunidade?
Dave Clarke
@ Dave: Sim, eu já sinalizei como CW. Requer atenção moderada.
MS Dousti
Eu gostaria de poder votar isso mais de uma vez.
Vivek Bagaria #

Respostas:

31

Teoria da Probabilidade e Algoritmos Aleatórios

Derrick Stolee
fonte
2
Este link está morto agora. Você poderia consertar ou ele será removido?
Dave Clarke
5
@ Dave, parece que não há mais um link da página de Ryan para o curso. Mas não acho que remover a entrada seja uma boa ideia, ele pode colocar o link de volta em algum momento. Seu comentário de que o link está quebrado é suficiente IMO.
Kaveh
@DaveClarke O link foi corrigido. Yay!
Jardine
24

Computação quântica e informação

Algumas excelentes notas de aula deste campo:

Um curso introdutório sobre computação quântica. Bom o suficiente para ser transformado em livro. Conheço vários pesquisadores que têm uma impressão dessas anotações em sua estante.

Um curso avançado em informação quântica. Algumas das melhores notas de palestras que eu já li.

Um curso avançado em algoritmos quânticos. Um recurso muito bom para algoritmos quânticos recentes. Se o artigo original de algum algoritmo quântico é difícil de entender, é aqui que eu verificaria a seguir.

Não consigo resumir este curso em uma linha. Leia a descrição na página da web do curso.

Inclui introdução geral à computação quântica, além de tópicos específicos de criptografia, como distribuição de chaves quânticas, compromissos quânticos, modelo de armazenamento quântico vinculado e conhecimento zero quântico.

Robin Kothari
fonte
Muito interessante, obrigado. Eu sempre quis aprender computação quântica, mas não tive tempo suficiente para ler um livro. Você conhece algum curso dedicado à criptografia quântica ? Encontrei um aqui , mas infelizmente as notas não estão disponíveis online.
MS Dousti 5/01/11
@Sadeq: Desculpe, não faço ideia.
Robin Kothari
23

Complexidade computacional

Existem muitos cursos excelentes sobre esse assunto. A seguir, é apenas a ponta do iceberg. Para escolher um, sugiro dar uma olhada no material abordado em cada curso, bem como no nível oferecido:

MS Dousti
fonte
22

A Theorist's Toolkit de Sanjeev Arora.

Adoro essas notas porque elas oferecem um conjunto bastante completo de ferramentas para atacar problemas na teoria da complexidade. Por exemplo, a dimensão VC é amplamente usada para provar limites mais baixos no modelo de comunicação, e essas notas explicam isso muito bem e do básico.

Marcos Villagra
fonte
17

PCP e dureza de aproximação

Sadeq Dousti
fonte
Qual deles você leu a si mesmo?
Thomas Ahle
17

Matemática discreta

Matemática Discreta para Ciência da Computação por Lehman, Leighton e Meyer ( versão mais antiga )

Jeffε
fonte
Eu recebo um erro 403 Proibido no seu link.
Derrick Stolee
@Derrick: O erro desapareceu ou o link foi corrigido.
MS Dousti
Sim, ambos os links funcionam agora ...
Derrick Stolee 13/01
Daí o link para a versão mais antiga.
Jeffε
1
Versão atualmente mais atualizada: cursos.csail.mit.edu/6.042/spring15/mcs.pdf . Ela se sente como encontrar o link certo no meio dos muitos espelhos desatualizados tornou-se um problema NP-completo ...
Darij grinberg
16

Pseudo-aleatoriedade

O melhor curso sobre o assunto é oferecido por Salil Vadhan . Veja também este tópico para um rascunho do livro de Salil sobre pseudo-aleatoriedade.

M.S. Dousti
fonte
15

Criptografia

Há várias excelentes notas de aula sobre o assunto, todas de pessoas famosas no campo. Você pode escolher um (ou dois) dos seguintes para estudar; tudo depende do seu ambiente, histórico e requisitos:

MS Dousti
fonte
11

SENTOU

Eu visitei um curso de SAT alguns anos atrás com o Professor Welzl. Suas anotações de aula são de longe as melhores que eu já vi em todos os meus estudos.

Infelizmente, apenas a versão de 2005 está online, incluindo uma pequena lista de atualizações .

(O algoritmo SAT mais rápido, bem como a prova construtiva do lema local de Lovász, vêm de pessoas do seu grupo.)

Sacha
fonte
9

O curso "Pérolas de Algoritmos". Parte 3 : Análise Probabilística e Algoritmos Aleatórios. As notas das palestras estão em análise suavizada . Gosto especialmente da figura 1.1 na terceira página.

Oleksandr Bondarenko
fonte