Voici une liste de publications importantes en informatique théorique, organisés par domaine.
Quelques raisons pour lesquelles une publication peut être considérée comme importante: Sujet créateur – Une publication qui a créé un nouveau sujet Découverte – Une publication qui a changé de manière significative les connaissances scientifiques Influence – Une publication qui a considérablement influencé le monde, ou qui a eu un impact massif sur l'enseignement de l'informatique théorique.
Calculabilité
Decidability of second order theories and automata on infinite trees Michael O. Rabin Transactions of the American Mathematical Society, vol. 141, , 1969 Description : ce document présente l'automate d'arbres, une extension de l'automate. l'automate d'arbres a eu de nombreuses applications lors de vérification formelle.
On computable numbers, with an application to the Entscheidungsproblem Alan Turing London Mathematical Society, Série 2, vol. 42, , 1937, . . HTML version, PDF version Description : Cet article fixe les limites de l'informatique. Il a défini la machine de Turing, un modèle pour tous calculs. D'autre part, il a prouvé l'indécidabilité du problème de l'arrêt et de l'Entscheidungsproblem et a ainsi trouvé les limites possible du calcul.
Automates et langages formels
Finite automata and their decision problems Michael O. Rabin et Dana S. Scott IBM Journal of Research and Development, vol. 3, , 1959 Description : le traitement mathématique des automates, la preuve de propriétés de base, et la définition d'automate fini non déterministe. On certain formal properties of grammars
Description : Cet article introduit ce qui est maintenant connu comme la hiérarchie de Chomsky, une hiérarchie des classes de grammaires formelles qui génèrent des langages formels.
Introduction to Automata Theory, Languages, and Computation John E. Hopcroft, Jeffrey D. Ullman, et Rajeev Motwani Addison-Wesley, 2001 Description : Un manuel populaire.
Théorie de la complexité
Computational Complexity de Arora & Barak et Computational Complexity de Goldreich's (Cambridge) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, 579 pages Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, 606 pages
« Une tentative définie avec Arora et Barak pour inclure du matériel à jour, tandis que Goldreich se concentre davantage sur le développement d'une base contextuelle et historique pour chaque concept présenté », et qu'il « applaudit tout... les auteurs pour leurs contributions exceptionnelles. »Daniel Apon, « Joint Review of Computational Complexity: A Conceptual Perspective by Oded Goldreich… and Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak », ACM SIGACT News, Vol. 41(4), December 2010, , see , accessed 1 February 2015.
A machine-independent theory of the complexity of recursive functions
Description : Les axiomes de Blum.
Algebraic methods for interactive proof systems
Description : Ce document a montré que PH est contenu dans IP.
The complexity of theorem proving procedures
Description : Cet article introduit le concept du problème NP-complet et a prouvé que problème SAT est NP-complet. Notez que des idées similaires ont été développés indépendamment un peu plus tard par Leonid Levin.
Computers and Intractability: A Guide to the Theory of NP-Completeness
Description : L'intérêt principal de ce livre est dû à sa longue liste de plus de 300 problèmes NP-complets. Cette liste est devenue une référence et une définition commune.
Degree of difficulty of computing a function and a partial ordering of recursive sets
Description : Ce rapport technique a été la première publication parlant de ce qui a plus tard été renommé la théorie de la complexitéShasha, Dennis, "An Interview with Michael O. Rabin", Communications of the ACM, Vol. 53 No. 2, Pages 37-42, February 2010..
How good is the simplex method? Victor Klee et George J. Minty
Description : Construction du « cube de Klee–Minty » dans la dimension D, dont 2D coins sont étudiés par l'algorithme du simplexe de Dantzig pour l'optimisation linéaire.
How to construct random functions
Description : Ce document montre que l'existence d'une fonction à sens unique conduit à l'aléatoire de calcul.
IP = PSPACE
Description : IP est une classe de complexité dont la caractérisation (basé sur les systèmes de preuve interactives) est tout à fait différente des classes de calcul. Dans cet article, Shamir a étendu la technique de l'article précédent de Lund, , Pour montrer que PSPACE est contenue dans IP, et donc IP = PSPACE, pour faire en sorte que chaque problème dans une classe de complexité est résoluble dans l'autre.
Reducibility among combinatorial problems R. M. Karp In R. E. Miller et J. W. Thatcher, editors, Complexity of Computer Computations, Plenum Press, New York, NY, 1972, Description : Ce document a montré que 21 problèmes différents sont NP-complet et a montré l'importance de ce concept.
The Knowledge Complexity of Interactive Proof Systems
Description : Le présent document introduit le concept de connaissance nulle.
A letter from Gödel to von Neumann Kurt Gödel Une lettre de Gödel à John von Neumann, , 1956 Version en ligne Description : Gödel discute de l'idée d'efficacité de théorème universel.
On the computational complexity of algorithms
Description : Ce document a donné à la complexité de calcul son nom et sa semence.
Theory and applications of trapdoor functions
Description : Cet article a créé un cadre théorique pour les trapdoor functions et décrit certaines de leurs applications, comme en cryptographie. Notez que le concept de trapdoor functions a été amené à de « Nouvelles directions en cryptographie » six ans plus tôt (voir la section V « Problem Interrelationships and Trap Doors. »).
Computational Complexity C.H. Papadimitriou Addison-Wesley, 1994, Description : Une introduction à la théorie de la complexité des calculs, le livre explique la caractérisation du P-SPACE et d'autres résultats.
Interactive proofs and the hardness of approximating cliques
Probabilistic checking of proofs: a new characterization of NP
Proof verification and the hardness of approximation problems
Description : Ces trois documents établi le fait surprenant que certains problèmes NP restent difficiles, même lorsque seule une solution approximative est nécessaire. Voir le théorème PCP.
Algorithmes
« A machine program for theorem proving »
Description : L'algorithme DPLL. L'algorithme de base pour les SAT et d'autres problèmes NP-complets.
« A machine-oriented logic based on the resolution principle » Journal of the ACM 12: 23–41.
Description : Première description de la résolution et de l'unification utilisée dans la démonstration automatique de théorèmes; utilisé dans Prolog.
« The traveling-salesman problem and minimum spanning trees »
Description : L'utilisation d'un algorithme d'arbre couvrant de poids minimal comme un algorithme d'approximation pour le problème NP-complet du voyageur de commerce. Les algorithmes d'approximation sont devenus une méthode commune pour faire face aux problèmes NP-complets.
« Probabilistic algorithm for testing primality »
Description : Le document présente le test de primalité deMiller-Rabin et décrit le programme d'algorithmes probabilistes.
« Optimization by simulated annealing »
Description : Cet article décrit le recuit simulé qui est maintenant une heuristique très commune pour les problèmes NP-complets.
The Art of Computer Programming Donald Knuth Description : Cette monographie a trois livres d'algorithmes populaires et un certain nombre de fascicules. Les algorithmes sont écrits en anglais et en langage MIX. Cela rend les algorithmes à la fois compréhensible et précis. Cependant, l'utilisation d'un langage de programmation de bas niveau frustre certains programmeurs plus familiers avec les langages de programmation structurés modernes.
Algorithms + Data Structures = Programs Niklaus Wirth Prentice Hall, 1976, Description : Un livre influent sur les algorithmes et des structures de données.
The Design and Analysis of Computer Algorithms Alfred V. Aho, John E. Hopcroft, et Jeffrey D. Ullman Addison-Wesley, 1974, Description : L'un des textes de référence portant sur les algorithmes durant la période 1975-1985.
How to Solve It By Computer
Description : Explication du Pourquoi des algorithmes et des structures de données. Explication du Processus de Création, de la Ligne de Raisonnement, et des Facteurs de Conception derrière des solutions innovantes.
Algorithms Robert Sedgewick Addison-Wesley, 1983, Description : Un texte très populaire sur des algorithmes à la fin des années 1980.
Introduction to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein , MIT Press, 2009, . Description : Ce manuel est devenu si populaire qu'il est presque la norme de l'enseignement des algorithmes basiques. La a été publié en 1990, la en 2001, et le en 2009.
Théorie algorithmique de l'information
« On Tables of Random Numbers » .
Description : Projet d'une approche de calcul de la probabilité.
« A formal theory of inductive inference » Ray Solomonoff Information and Control, vol. 7, and 224–254, 1964 Copie en ligne: partie I, partie II Description : Ce fut le début de la théorie algorithmique de l'information et de la complexité de Kolmogorov. Notez que si la complexité de Kolmogorov est nommé d'après Andrey Kolmogorov, cette idée revient à Ray Solomonoff. Andrey Kolmogorov a beaucoup contribué dans ce domaine, mais avec des articles ultérieurs.
« Algorithmic information theory »
Description : Une introduction à la théorie algorithmique de l'information par l'une des personnes importantes de ce domaine.
Théorie de l'information
« A mathematical theory of communication »
Description : Ce document a créé le domaine de la théorie de l'information.
« Error detecting and error correcting codes »
Description : Dans cet article, Hamming a introduit l'idée d'un code de correction d’erreur. Il a créé le code de Hamming et la distance de Hamming.
« A method for the construction of minimum redundancy codes »
Description : Le codage de Huffman.
« A universal algorithm for sequential data compression »
Description : L'algorithme de compression LZ77.
Elements of Information Theory
Description : Une introduction populaire à la théorie de l'information.
Vérification formelle An Axiomatic Basis for Computer Programming
Description : L'article de Tony Hoare décrit un ensemble de règles d'inférence (à savoir la preuve formelle) pour un langage de programmation comme Algol.
Guarded Commands, Nondeterminacy and Formal Derivation of Programs
Description : Ce document propose que, au lieu de vérifier formellement un programme après qu'il a été écrit (c.-à-post facto), les programmes et leurs preuves formelles devraient être développées main dans la main, une méthode connue sous le nom raffinement (ou dérivation) de programme.
Proving Assertions about Parallel Programs Edward A. Ashcroft J. Comput. Syst. Sci. 10(1): 110-135 (1975) Description : Cet article a présenté les preuves d'invariance des programmes concurrents.
An Axiomatic Proof Technique for Parallel Programs I Susan S. Owicki, David Gries Acta Inf. 6: 319-340 (1976) Description : Dans ce document, l'approche axiomatique parallèle de vérification de programmes est présenté.
Denotational Semantics Joe Stoy 1977 Description : Premier livre portant sur l'approche mathématique (ou fonctionnelle) de la sémantique formelle des langages de programmation (contrairement aux approches opérationnelles et algébriques).
The Temporal Logic of Programs