Quels papiers tout le monde devrait-il lire?

454

Cette question est (inspirée par) / (honteusement volée à) une question similaire chez MathOverflow , mais je m'attends à ce que les réponses ici soient très différentes.

Nous avons tous des articles favoris dans nos domaines théoriques respectifs. De temps en temps, on trouve un article tellement stupéfiant (important, convaincant, trompeusement simple, etc.) qu'on veut le partager avec tout le monde. Alors listez ces papiers ici! Ils ne doivent pas nécessairement être issus de l'informatique théorique - tout ce qui, selon vous, pourrait plaire à la communauté est une bonne réponse.

Vous pouvez donner autant de réponses que vous voulez; s'il vous plaît mettez un papier par réponse ! Notez également qu'il s'agit d'un wiki de communauté, alors votez pour tout ce que vous aimez!

(Notez qu'il y avait une question précédente sur les articles dans la complexité de la théorie de la récursivité, mais elle est assez spécialisée.)

Ryan Williams
la source
65
Dans les réponses, j'aimerais que l'on insiste davantage sur le fait de savoir s'il est vraiment judicieux de lire le document original de nos jours (ou s'il est beaucoup plus logique de lire une exposition de manuels modernes). J'ai trop souvent vu des articles du SDC véritablement déterminants, mais je préfère éviter à mes collègues de tenter de déchiffrer le texte original - qui est trop souvent un résumé de conférence de 10 pages rédigé à la hâte, avec des références vers une "version complète" jamais apparue ...
Jukka Suomela
7
Oui, j'espère qu'il est clair que des papiers de ce type ne sont pas bons pour la liste (si vous voulez le partager avec tout le monde, ça ne devrait pas être difficile à lire)
Ryan Williams
30
Trop de gens postent juste des one-liners. Tout le monde peut publier des centaines de documents uniques sans y penser. S'il vous plaît poster pourquoi vous pensez que tout le monde devrait lire ces journaux. Cela signifie qu'il faut justifier pourquoi ils devraient lire ce journal plutôt que le résultat de quelqu'un d'autre et ce qui est si impressionnant dans le journal que tout le monde devrait le lire.
Robin Kothari
Bonne question. Mon opinion est que si vous voulez comprendre l'esprit des inventeurs, et éventuellement comprendre comment inventer des choses, vous devez lire leurs propres mots. Plus vous travaillez, plus vous vous rapprochez de leur processus de pensée actuel.
ixtmixilix

Réponses:

164

"Une théorie mathématique de la communication" de Claude Shannon, des classiques de la théorie de l'information. Très lisible.

( Miroir )

Grigory Yaroslavtsev
la source
La caractérisation générale la plus sûre d’Internet est qu’il se compose d’une série de notes de bas de page associées à cet article.
Celal Ergün
145

Le document de 1936 qui a probablement lancé l'informatique elle-même:

  • Alan Turing, "On Numbers Computing, avec une application au problème d'Entscheidungs", Actes de la London Mathematical Society s2-42, 230-265, 1937. doi: 10.1112 / plms / s2-42.1.230

En seulement 36 pages, Turing formule (mais ne nomme pas) la machine de Turing, retransmet le fameux premier théorème d'incomplétude de Gödel en termes de calcul, décrit le concept d'universalité et montre en annexe que la calculabilité par les machines de Turing est équivalente à la calculabilité par Fonctions définissables par (comme l'ont étudié Church et Kleene).λ

András Salamon
la source
7
Il est également très accessible et lisible ...
Sariel Har-Peled le
25
The Annotated Turing de Charles Petzold [Hautement recommandé]
Pratik Deoghare le
1
Voici un lien plus convivial vers le papier .
jameshfisher
123

" Réflexions sur la confiance " de Ken Thompson . Court, doux et hallucinant.

Jɛ ff E
la source
5
En outre, très accessible. Je l'ai lu il y a un certain temps, alors que je n'avais pratiquement aucune formation en informatique, aucune expérience en programmation et que je ne savais même pas ce qu'était un compilateur.
Jörg W Mittag
1
"La semaine dernière, le googler Ken Thompson a reçu le prix japonais d'information et de communication pour ses premiers travaux sur le système d'exploitation UNIX." (src: Buzz post de Life chez Google)
Sebastián Grignoli
4
Je pense que cet article serait assez difficile à digérer sans au moins savoir ce qu'est un compilateur.
Fixee
2
Dans le document, je pense que les figures 2.1 et 2.2 sont échangées.
Dennis
1
En désaccord - rien d’impressionnant ni de déconcertant dans ce document. TL; DR 6 pages du milieu des années 80 sur "la nécessité de modifier le code pénal pour commencer à punir les pirates [tout comme les voleurs ou les cambrioleurs]". Oh oui, mentionne une quine , sans l'appeler par son nom.
c69
94

Ce que tout informaticien devrait savoir sur l'arithmétique en virgule flottante

Cet article explique et renforce la notion selon laquelle la virgule flottante n’est pas magique. Il explique les débordements, les débordements, ce que sont les nombres dénormalisés, ce que sont les NaN, ce que inf est et tout ce que cela implique. Après avoir lu cet article, vous saurez pourquoi a == a + 1.0 peut être vrai, pourquoi a == a peut être faux, pourquoi exécuter votre code sur deux machines différentes peut vous donner deux réponses différentes, pourquoi sommer des nombres de manière différente order peut vous donner une différence d’ordre de grandeur et toutes les choses loufoques qui se produisent dans le monde de la cartographie d’un nombre infini d’innombrables nombres sur un ensemble infiniment fini.

Une version modifiée est également disponible sur le Web.

Rick Weber
la source
3
S'il vous plaît, corrigez le lien. C'est cassé.
Oscar Mederos
1
Depuis que Oracle a acquis Sun, il a détruit la plupart des liens de la page Web de Sun. Bien que vous puissiez atteindre le document original à partir d' ici .
systemsfault
est-ce que ça pourrait être ça? ece.uwaterloo.ca/~dwharder/NumericalAnalysis/02Numerics/Double/…
Blackle Mori
1
Correction du lien cassé.
Ryan
85

Keshav est comment lire un papier . Vous pouvez également télécharger le document à partir d' ici .

Dai Le
la source
Belle lecture en effet.
Anthony Labarre
Je pense toujours que les documents de recherche CS sont écrits dans une langue étrangère.
Berlin Brown
3
Très bien! Il vaut la peine d'être placé sur la bannière du slogan sur le site pour s'assurer qu'aucun élève ne l'oublie.
Vag
Le deuxième lien est actuellement cassé
Christopher Manning
2
Ceci est mon préféré de la liste. Notez également qu'il s'agit d'un document évolutif, contrairement à la plupart des documents qui ne reçoivent pas de mises à jour après leur publication.
Dennis
67

Chemins, arbres et fleurs de J. Edmonds. Cet article sur le problème classique de l'optimisation combinatoire est non seulement bien écrit, mais indique également que la notion d '"algorithmes à temps polynomiaux" est essentiellement synonyme d'efficacité.

ilyaraz
la source
61

Réductibilité des problèmes combinatoires par Richard Karp. Le document contient ce que l'on appelle souvent les "problèmes d'origine de 21 NP-complets" de Karp. À bien des égards, cet article a véritablement motivé l’étude de l’exhaustivité des NP en démontrant son applicabilité à un domaine plus large. Très lisible.

Daniel Apon
la source
6
J'aime ce papier, mais certaines des réductions sont vraiment sommaires et difficiles à suivre. Voir n'importe quel texte de complexité pour plus de détails.
András Salamon le
2
@Andras Salamon, je suis d'accord à 100%.
Tayfun Pay
52

Hartmanis et Stearns, "Sur la complexité de calcul des algorithmes" , Transactions de l'American Mathematical Society 117: 285-306 (1965).

Il s’agissait du premier article qui prenait l’étude de la complexité du temps au sérieux et constituait assurément la principale motivation du prix conjoint de Turing attribué à Hartmanis et Stearns. Bien que leurs définitions initiales ne correspondent pas exactement à celles que nous utilisons aujourd'hui, le document reste extrêmement lisible. Vous avez vraiment le sentiment de la situation dans l’ancienne frontière du "Far West" des années 60.

Ryan Williams
la source
Lien de travail. pdfs.semanticscholar.org/1ce8/…
scott m gardner
51

Ordinateurs mécaniques quantiques (PDF) de Richard Feynman.

Il introduit la notion de calcul quantique, décrit les circuits quantiques, explique comment les circuits classiques peuvent être simulés par des circuits quantiques et montre comment les circuits quantiques peuvent calculer des fonctions sans beaucoup de qubits de déchets (en utilisant un calcul).

Il montre ensuite comment tout circuit classique peut être encodé dans un hamiltonien indépendant du temps! Sa preuve est également valable pour les circuits quantiques, démontrant ainsi que les hamiltoniens évoluant dans le temps sont BQP-difficiles! Sa construction hamiltonienne est également utilisée dans la démonstration de la version quantique du théorème de Cook-Levin, prouvée par Kitaev, qui montre que l'hamiltonien k-local est une QMA-complète.

Robin Kothari
la source
Le lien n'est pas valide. Avez-vous une autre source? edit> Recherché sur Google: wjzeng.net/Ref/Feynman_QuantumMechanicalComputers.pdf Est-ce celui-ci?
Klaim
C'est celui-là. J'ai ajouté un nouveau lien et un lien vers sa page sur le site Web de l'éditeur.
Robin Kothari
Les notions de BQP et QMA existaient-elles lorsque Feynman a écrit cet article? Ou y a-t-il un article récent qui établit ce lien? Toute référence / exposition de ce fait que hamiltonien k-local est QMA complet?
Anirbit
48

Les graphes d'expandage et leurs applications, S. Hoory, N. Linial et A. Wigderson est une très belle enquête sur les graphes d'expandage. Pas étonnant qu'il ait remporté le prix Conant 2008 de l'AMS.

Je tiens à rappeler que les graphiques d’extension sont l’ingrédient essentiel des avancées récentes dans le TCS, par exemple.

et pas si récent:

Dai Le
la source
1
Vous devez surveiller les préconditionneurs combinatoires ou de soutien. Les graphiques Expander sont même utilisés aujourd'hui dans l'analyse numérique.
Shuhalo
44

Je suis surpris de constater que personne n'a publié les "résultats optimaux d'inapproximabilité" de Hastad (JACM, 2001; à l'origine, STOC, 1997). Cet article de référence a été si bien écrit que vous ne pouvez y arriver qu'avec une maturité mathématique et vous donner envie de bien apprendre plusieurs choses, telles que ses techniques de Fourier, sa répétition parallèle, ses gadgets, etc.

utilisateur289
la source
44

O((logN)3)O(exp((649b)13(logb)23))

Pratik Deoghare
la source
42

The Valiant's Theory of the Learnable (1984) a établi l'ordre du jour de la théorie de l'apprentissage pendant des décennies. C'est un document agréable et lisible!

Il existe également de nombreuses explications intuitives dans le document qui le rendent amusant et convaincant. Diverses parties de ce document sont toujours régulièrement citées dans les discussions entre COLT et ALT.

Lev Reyzin
la source
37

La complexité des procédures de démonstration de théorèmes par Stephen A. Cook. Cet article prouve que toutes les langues décidées par les machines de Turing non déterministes peuvent être (Cook) réduites à l’ensemble des tautologies propositionnelles.

L'importance de ce résultat est (au moins) double: premièrement, il montre qu'il existe des problèmes dans NP qui sont au moins aussi difficiles que toute la classe, les problèmes complets de NP ; de plus, il fournit un exemple concret d'un tel problème, qui peut ensuite être réduit à d'autres afin de prouver qu'il est complet.

De nos jours, les réductions de Karp sont plus couramment utilisées que les réductions de Cook, mais la preuve principale de ce document peut facilement être adaptée pour montrer que la SAT est NP- complète en ce qui concerne les réductions de Karp.

Antonio E. Porreca
la source
7
C’est l’un de ces documents de conférence pour lesquels aucune version de journal n’a paru, mais celui-ci mérite certainement d’y revenir: bien écrit et plein d’excellents commentaires.
András Salamon
36

Call-by-value est dual à call-by-name par Philip Wadler est une bonne lecture.

Lyonanderson
la source
25
Tout ce qui est écrit par Phil Wadler est une bonne lecture.
Dave Clarke
36

CAR Hoare, une base axiomatique pour la programmation informatique .

Extrait du résumé: Cet article tente d'explorer les fondements logiques de la programmation informatique en utilisant des techniques qui ont d'abord été appliquées à l'étude de la géométrie et ont ensuite été étendues à d'autres branches des mathématiques.

Il a six pages qui sont assez faciles à suivre.

Radu GRIGore
la source
34

Alon, Matias et Szegedy, La complexité spatiale de l'approximation des moments de fréquence , JCSS 58 (1): 137-147, 1999.

Ce papier plutôt magique a été le premier à formaliser des algorithmes de transmission en continu et à établir des limites supérieures et inférieures rigoureuses pour les tâches fondamentales dans le modèle de diffusion en continu. Ses techniques sont simples, ses preuves sont belles et son impact a été profond. Le travail a valu au prix Gödel à Alon, Matias et Szegedy en 2005.

arnab
la source
dang. J'allais ajouter celui-ci :)
Suresh Venkat
30

Le document d'Immerman prouvant le théorème connu à présent sous le nom de théorème d'Immerman – Szelepcsényi est un excellent exemple de document facile à lire, intelligent et court. J'adore l'histoire racontée dans l'intro.

N. Immerman, L'espace non déterministe est fermé sous complémentation, SIAM Journal on Computing 17, 1988, p. 935–938.

Michaël Cadilhac
la source
1
Pour être juste, l'article de Szelepcsényi, "La méthode du dénombrement forcé pour les automates non déterministes", est tout aussi plaisant.
Lev Reyzin
30

f(n)log(n)

NSPACE(f(n))DSPACE((f(n))2).

NPSPACE=PSPACEPNP

Savitch, Walter J. (1970), "Relations entre complexités de bandes non déterministes et déterministes", Journal of Computer and System Sciences 4 (2): 177-192.

Sadeq Dousti
la source
27

Russell Impagliazzo's Une vision personnelle de la complexité moyenne des cas . C’est un excellent document, car il est intelligemment écrit et résume l’état de la situation dans cinq «mondes» où nos conjectures sur la complexité sont résolues de diverses manières, donnant des conséquences concrètes dans chaque cas.

Steve Flammia
la source
24

Extracteurs et générateurs pseudo-aléatoires de Luca Trevisan. Dans cet article, un bon extracteur d’aléatoire est construit à l’aide de codes de correction d’erreurs et de conceptions combinatoires. La construction est assez facile à comprendre, mais elle est complètement renversante, car il n’est pas évident de savoir quel est le lien entre les extracteurs, les codes et les dessins.

Après tout, c’est un bon exemple de résultat dans TCS qui nécessite une combinatoire sophistiquée.

ilyaraz
la source
24

Comment rédiger une preuve , par Leslie Lamport.

Anthony Labarre
la source
5
J'ai lu ceci et j'ai lu Une lamentation de mathématicien de Lockhart ( maa.org/devlin/LockhartsLament.pdf ). IMHO Je pense que la stratégie suggérée par Lamport va à l'encontre de ce que Lockhart avance sur la beauté des mathématiques.
Marcos Villagra
5
Très intéressante lecture. Je comprends votre opinion, mais si je ne me trompe pas, Lamport adresse son message aux personnes plus "éduquées en mathématiques" que celles visées par Lockhart, qui vise à aider les élèves à acquérir un goût pour les mathématiques. J'admettrai également que suivre un format strict rend les épreuves assez ennuyeuses à lire, mais je suis d'accord avec Lamport sur l'idée d'épreuves par niveaux: vous ne voulez pas / n'avez pas toujours besoin de temps pour lire tout en détail faire, avoir un résumé de ce qui est à venir peut être très utile. Beaucoup plus que ces "facile à voir / clairement / wlog / ..." ;-)
Anthony Labarre
19

Si je peux citer Sarah Palin à ce sujet: "Tous".

Plus sérieusement, je pense que la plupart des papiers ne doivent pas être lus dans l'original. À mesure que le temps passe, les gens trouvent un meilleur moyen de comprendre et de présenter le problème / la solution d'origine. À l'exception du document original de Turing, qui revêt une importance historique, je ne recommanderais pas de lire la plupart des documents originaux s'il y a un travail de suivi qui l'a nettoyé. En particulier, beaucoup de choses sont présentées beaucoup mieux dans les livres que dans l'original.

Sariel Har-Peled
la source
16
Ce commentaire est vrai en général, mais Ryan demande explicitement des exemples pour lesquels ce n'est pas vrai. Il existe de nombreux articles classiques contenant des conjectures non encore prouvées, des techniques négligées ou des résultats qui ont tendance à être oubliés mais qui pourraient être époussetés et utilisés à de nouvelles fins.
András Salamon
12
Je ne suis pas d'accord. Il est vrai que les documents originaux sont parfois illisibles et que les travaux secondaires donnent une meilleure présentation des résultats, mais parfois, les documents originaux contiennent des idées qui ont été omises dans les travaux ultérieurs. La lecture de papiers originaux peut également nous apprendre comment l'auteur a eu cette idée. Jetez un coup d'oeil à ce billet de Timothy Chow sur MO: mathoverflow.net/questions/28268/do-you-read-the-masters
Kaveh le
4
C'est génial quand cela se produit. Je prétends juste que c'est un peu rare.
Sariel Har-Peled
6
Vous dites "tous", mais ne défendez-vous pas alors "aucun d'entre eux"?
Peter Taylor
2
@Peter Taylor, je pense que c'est pour cela que Sarah est mentionnée. :)
Radu GRIGore le
18

Chomsky analyse comment les modèles mathématiques peuvent être utilisés pour décrire le langage naturel, d'un point de vue linguistique.

András Salamon
la source
3
En passant, je ne préconise pas ce document - je viens de le modifier pour corriger les fautes de frappe et ajouter un lien. Je préfère le papier de Gold si on veut un papier classique sur la langue.
András Salamon