Quelles notes de cours faut-il lire?

113

Il y a eu plusieurs questions avec le même schéma que celui-ci:

J'étais réticent à en publier un autre, mais les notes de cours de Jeff Erickson sur les algorithmes m'ont fait changer d'avis. J'ai pensé: Oh mon Dieu! Toutes ces années et je n'ai pas vu ces excellentes notes!

J'ai donc pensé qu'il pourrait y avoir d'autres excellentes notes de cours qui méritent vraiment d'être lues. Ainsi, pour chaque sous-domaine informatique ( structures de données, algorithmes, théorie du calcul, complexité de calcul, cryptographie , etc.), recommandez les excellentes notes de lecture de votre choix et expliquez-nous pourquoi vous pensez qu'il excelle.

Une règle simple pour le garder en ordre: une réponse pour chaque sous-champ. (Ce sera un wiki de communauté, vous pourrez donc modifier les réponses existantes et ajouter votre recommandation.)

reference-request soft-question big-list M.S. Dousti
la source
9
Vous obtenez mon vote. Si seulement une telle liste avait existé quand j'étais étudiant ...
Anthony Labarre
7
Merci pour le lien vers les excellentes notes de Jeff Erickson!
Standa Zivny
2
Cette question devrait-elle aussi être un wiki de communauté?
Dave Clarke
@ Dave: Oui, je l'ai déjà signalé comme CW. Cela nécessite une attention particulière.
MS Dousti
Je souhaite que je pourrais upvoter cela plus d'une fois.
Vivek Bagaria

Réponses:

31

Théorie des probabilités et algorithmes aléatoires

Derrick Stolee
la source
2
Ce lien est maintenant mort. Pourriez-vous s'il vous plaît réparer ou il sera supprimé?
Dave Clarke
5
@ Dave, il semble qu'il n'y ait plus de lien entre la page Web de Ryan et le cours. Mais je ne pense pas que supprimer cette entrée soit une bonne idée, il pourrait remettre le lien à un moment donné. Votre commentaire que le lien est brisé est suffisant OMI.
Kaveh
@DaveClarke Le lien est corrigé. Yay!
Jardine
24

Calcul et information quantiques

Quelques excellentes notes de cours de ce domaine:

Un cours d'introduction à l'informatique quantique. Assez bon pour être transformé en livre. Je connais plusieurs chercheurs qui ont imprimé ces notes dans leur bibliothèque.

Un cours avancé sur l'information quantique. Certaines des meilleures notes de conférences que j'ai jamais lues.

Un cours avancé sur les algorithmes quantiques. Une très bonne ressource pour les algorithmes quantiques récents. Si le texte original sur un algorithme quantique est difficile à comprendre, c’est là que je voudrais vérifier.

Je ne peux pas résumer ce cours en une seule ligne. Lisez la description sur la page Web du cours.

Inclut une introduction générale à l'informatique quantique, ainsi que des rubriques spécifiques à la cryptographie telles que la distribution de clés Quantum, les engagements quantiques, le modèle de stockage quantique limité et la connaissance zéro quantique.

Robin Kothari
la source
Très intéressant, merci. J'ai toujours voulu apprendre l'informatique quantique, mais je n'avais pas le temps de lire un livre. Connaissez-vous un cours consacré à la cryptographie quantique ? J'en ai trouvé un ici , mais malheureusement, les notes ne sont pas disponibles en ligne.
MS Dousti
@Sadeq: Désolé, aucune idée.
Robin Kothari
23

Complexité informatique

Il existe de nombreux excellents cours sur ce sujet. Ce qui suit n'est que la pointe de l'iceberg. Pour en choisir un, je suggère de jeter un coup d'œil sur le matériel couvert dans chaque cours, ainsi que sur le niveau proposé:

MS Dousti
la source
22

Une boîte à outils pour théoriciens de Sanjeev Arora.

J'adore ces notes car elles vous fournissent un ensemble assez complet d'outils pour vous attaquer aux problèmes de la théorie de la complexité. Par exemple, la dimension VC est largement utilisée pour prouver les limites inférieures dans le modèle de communication, et ces notes l'expliquent très bien et à partir des bases.

Marcos Villagra
la source
17

PCP & Dureté de l'Approximation

Sadeq Dousti
la source
Lequel avez-vous lu vous-même?
Thomas Ahle
17

Mathématiques discrètes

Mathématiques discrètes pour l'informatique de Lehman, Leighton et Meyer ( ancienne version )

Jeffε
la source
Je reçois une erreur 403 Forbidden sur votre lien.
Derrick Stolee
@Derrick: l'erreur a disparu ou le lien est corrigé.
MS Dousti
Oui, les deux liens fonctionnent maintenant .....
Derrick Stolee
D'où le lien vers l'ancienne version.
Jeffε
1
Version actuellement la plus récente: courses.csail.mit.edu/6.042/spring15/mcs.pdf . C'est comme si trouver le bon lien parmi les nombreux miroirs obsolètes était devenu un problème NP-complet ...
darij grinberg
16

Pseudo-aléatoire

Le meilleur cours sur le sujet est offert par Salil Vadhan . Voir également ce sujet pour un brouillon du livre de Salil sur le pseudo-aléa.

M.S. Dousti
la source
15

Cryptographie

Il existe un certain nombre d'excellentes notes de cours sur le sujet, toutes écrites par des personnalités célèbres sur le terrain. Vous pouvez choisir un (ou deux) parmi les suivants pour étudier; Tout dépend de votre environnement, de votre arrière-plan et de vos exigences:

MS Dousti
la source
11

SAM

J'ai visité un cours SAT il y a quelques années avec le professeur Welzl. Ses notes de cours sont de loin les meilleures que j'ai vues tout au long de mes études.

Malheureusement, seule la version 2005 est en ligne, avec une courte liste de mises à jour .

(L'algorithme SAT le plus rapide ainsi que la preuve constructive du lemme local de Lovász proviennent des membres de son groupe.)

Sacha
la source
9

Le cours "Perles d'algorithmes". Partie 3 : Analyse probabiliste et algorithmes aléatoires. Les notes de cours sont en analyse lissée . J'aime particulièrement la figure 1.1 à la troisième page.

Oleksandr Bondarenko
la source