|
On computable numbers, with an application to the Entscheidungsproblem Description: This article set the limits of computer science. It defined the Turing Machine, a model for all computations. On the other hand it proved the undecidability of the halting problem and Entscheidungsproblem and by doing so found the limits of possible computation. Importance: Topic creator, Breakthrough, Influence On certain formal properties of grammars Importance: Topic creator, Breakthrough, Influence Finite automata and their decision problem Description: Mathematical treatment of automata, proof of core properties, and definition of non-deterministic finite automaton Importance: Topic creator, Breakthrough, Influence, Introduction Introduction to Automata Theory, Languages, and Computation Description: A popular textbook. Importance: Introduction Computability: An introduction to recursive function theory Description: A popular textbook. Importance: Introduction On the computational complexity of algorithms Importance: Topic creator, Breakthrough, Influence The complexity of theorem proving procedures Description: This paper introduced the concept of NP-Completeness and proved that Boolean satisfiability problem(SAT) is NP-Complete. Importance: Topic creator, Breakthrough, Influence Karps_21_NP-complete_problems|Reducibility among combinatorial problems Description: This paper showed that 21 different problems are NP-Complete and showed the importance of the concept. Importance: Influence Computers and Intractability: A Guide to the Theory of NP-Completeness Description: The main importance of this book is due to its extensive list of more than 300 NP-Complete problems. This list became a common reference and definition. It is important to note that though the book was published only few years after the concept was defined such an extensive list was found. Importance: Introduction, Influence, Latest and greatest Theory and Applications of Trapdoor functions Importance: Topic creator, Breakthrough The Knowledge Complexity of Interactive Proof Systems Description: This paper introduced the concept of zero knowledge. Importance: Topic creator, Breakthrough How to Construct Random Functions Importance: Topic creator, Breakthrough, Latest and greatest, Influence Algebraic methods for interactive proof systems Importance: Breakthrough IP (complexity)|IP PSPACE In this paper, Shamir extended the technique of the previous paper by Lund, et al., to show that PSPACE is contained in IP, and hence IP = PSPACE, so that each problem in one complexity class is solvable in the other. Importance: Breakthrough 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: These three papers established the surprising fact that certain problems in NP remain hard even when only an approximative solution is required. Importance: Topic creator, Breakthrough, Influence Computational complexity theory|Computational Complexity Description: This book provides a very good introduction to Computational Complexity Importance: Introduction A machine program for theorem proving Importance: Breakthrough, Influence A Machine-Oriented Logic Based on the Resolution Principle Importance: Topic Creator, Breakthrough, Influence Optimization by simulated annealing Description: This article described simulated annealing which is now a very common heuristic for NP-Complete problems. Importance: Influence The Art of Computer Programming Description: This monograph has three popular algorithms books and a number of fascicles. The algorithms are written in both English and MIX assembly language (or MMIX assembly language in more recent fascicles). This makes algorithms both understandable and precise. However, the use of a low-level programming language frustrates some programmers more familiar with modern structured programming languages. Importance: Influence Introduction to Algorithms Description: As its name indicates this textbook is a very good introduction to algorithms. This book became so popular that it is almost the de facto standard for basic algorithms teaching. Importance: Introduction, Influence How to Solve It By Computer Description: Explains the Whys of algorithms and data-structures. Explains the Creative Process, the Line of Reasoning, the Design Factors behind innovative solutions. Importance: Introduction See Also: How to Solve It The Design and Analysis of Computer Algorithms Description: One of the standard texts on algorithms for the period of approximately 1975–1985. Importance: Influence, Introduction Algorithms Description: A very popular text on algorithms in the late 1980s. It was more accessible and readable (but more elementary) than Aho, Hopcroft, and Ullman. There are more recent editions. Importance: Influence Algorithms + Data Structures Programs Description: An early, influential book on algorithms and data structures, with implementations in Pascal. Importance: Influence A formal theory of inductive inference Description: This was the beginning of Algorithmic information theory and Kolmogorov complexity. Note that though Kolmogorov complexity is named after Andrey Kolmogorov, he said that the seeds of that idea are due to Ray Solomonoff. Andrey Kolmogorov contributed a lot to this area but in later articles. Importance: Topic creator, Breakthrough, Influence Algorithmic information theory Importance: Introduction A mathematical theory of communication Description: This paper created communication theory and information theory. Importance: Topic creator, Breakthrough, Introduction, Influence Error detecting and error correcting codes Description: In this paper, Hamming introduced the idea of error-correcting code. He created the Hamming code and the Hamming distance and developed methods for code optimality proofs. Importance: Topic creator, Breakthrough, Introduction, Influence A Method for the Construction of Minimum Redundancy Codes Description: The Huffman coding. Importance: Influence, Breakthrough A Universal Algorithm for Sequential Data Compression Description: The LZ77 compression algorithm. Importance: Influence, Breakthrough Elements of Information Theory Importance: Influence, Introduction An experimental timesharing system. Description: This paper discuss time-sharing as a method of sharing computer resource. This idea changed the interaction with computer systems. Importance: Influence The Unix|UNIX Time-Sharing System Description: The Unix operating system and its principles were described in this paper. The main importance is not of the paper but of the operating system, which had tremendous effect on operating system and computer technology. Importance: Influence, Breakthrough Operating Systems: Design and implementation Description: Theoretical as well as practical textbook of the operating systems, with Minix as the example. The book is often referred to as the Minix bible, as it includes the full source. Importance: Breakthrough, Influence Scheduling Techniques for Concurrent Systems Importance: Influence A relational model for large shared data banks Description: This paper introduced the relational model for databases. This model became the number one model. Importance: Topic creator, Breakthrough, Influence The Entity Relationship Model & Towards a Unified View of Data Description: This paper introduced the Entity-relationship diagram(ERD) method of database design. Importance: Breakthrough, Influence Mining association rules between sets of items in large databases Description: Association rules, a very common method for data mining. Importance: Topic creator, Introduction, Influence Principles of Transaction-Oriented Database Recovery Description: Introduced the ACID-Paradigma for transactions. Importance: Topic creator, Introduction, Influence Communication Theory of Secrecy Systems Description: Information theory based analysis of cryptography. Importance: Breakthrough, Introduction, Influence New directions in cryptography Description: This paper suggested public key cryptography and presented Diffie-Hellman key exchange. Importance: Topic creator, Breakthrough, Introduction, Influence, Latest and greatest (A great paper from every perspective...) A Method for Obtaining Digital Signatures and Public Key Cryptosystems Description: The RSA encryption method. The first public key encryption method. Importance: Breakthrough, Influence How to Share a Secret Description: A safe method for sharing a secret. Importance: Topic creator, Breakthrough How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design Description: This paper explains how to construct a zero-knowledge proof system for any language in NP. Importance: Breakthrough, Influence How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority Description: Seminal paper in secure function evaluation Importance: Breakthrough, Influence Computing machinery and intelligence Description: This paper discusses whether machine can think and suggested the Turing test as a method for checking it. In a sense, this was the beginning of artificial intelligence Importance: Topic creator, Breakthrough, Influence A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence Description: This summer research proposal marks the areas of research in artificial intelligence since then. It was a very long summer. Importance: Influence Fuzzy sets Description: The seminal paper published in 1965 provides details on the mathematics of fuzzy set theory. Importance: Topic creator, Influence Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference Description: This book introduced Bayesian methods to AI. Importance: Topic creator, Influence Artificial Intelligence: A Modern Approach Description: The standard textbook in Artificial Intelligence. The authors claim that it used in over 900 colleges and universities in 89 countries. Importance: Introduction, Influence Language identification in the limit Description: This paper created Algorithmic learning theory. Importance: Topic creator, Breakthrough, Influence On the uniform convergence of relative frequencies of events to their probabilities Description: Computational learning theory, VC theory, statistical uniform convergence and the VC dimension. Importance: Breakthrough, Influence A theory of the learnable Description: The Probably approximately correct learning (PAC learning) framework. Importance: Topic creator, Breakthrough, Influence Learnability and the Vapnik-Chervonenkis dimension Description: The complete characterization of PAC learnability using the VC dimension. Importance: Breakthrough, Influence Cryptographic limitations on learning boolean formulae and finite automata Importance: Influence The strength of weak learnability Importance: Breakthrough, Influence Learning in the presence of malicious errors Importance: Breakthrough, Influence The Phase correlation|Phase Correlation Image Alignment Method Description: A correlation method based upon the inverse Fourier transform Importance: Influence An Iterative image registration|Image Registration Technique with an Application to Binocular vision|Stereo Vision Description: This paper provides efficient technique for image registration Importance: Influence The Laplacian Pyramid as a compact image code Description: A technique for image encoding using local operators of many scales Importance: Influence Snakes algorithm|Snakes: Active contour models Description: An interactive variational technique for image segmentation and visual tracking Importance: Influence, topic creator Condensation algorithm|Condensation -- conditional density propagation for visual tracking Description: A technique for visual tracking Importance: Influence On the translation of languages from left to right Description: Bottom up parsing for deterministic context-free languages from which later the LALR approach of Yacc developed. Importance: Breakthrough, Influence Semantics of Context-Free Languages. Description: About grammar attribution, the base for yacc's s-attributed and zyacc's LR-attributed approach. Importance: Breakthrough, Influence YACC: Yet another compiler-compiler Description: Yacc is a tool that made compiler writing much easier. Importance: Influence Compilers: Principles, Techniques and Tools Description: This book became a classic in compiler writing. It is also known as the Dragon book, after the (red) dragon that appears on its cover. Importance: Introduction, Influence Assigning meanings to programs Importance: Topic creator, Breakthrough, Influence, Introduction An axiomatic basis for computer programming Importance: Topic creator, Breakthrough, Influence, Introduction The temporal logic of programs Importance: Topic creator, Influence Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints Importance: Topic creator, Influence. Model Checking Importance: Introduction The Computer from Pascal to von Neumann Description: Perhaps the first book on the history of computation. Importance: A History of Computing in the Twentieth Century edited by: Description: Several chapters by pioneers of computing. Importance: Software engineering: Report of a conference sponsored by the NATO Science Committee Description: Conference of leading figures in software field circa 1968 Importance: Defined the field of Software engineering Goto|Go To Statement Considered harmful|Considered Harmful Description: Don't use goto – the beginning of structured programming. Importance: Topic creator, Influence On the criteria to be used in decomposing systems into modules Description: The importance of modularization and information hiding. Importance: Influence The Mythical Man-Month: Essays on Software Engineering Description: Throwing more people at the task will not speed its completion... Importance: Influence No Silver Bullet: Essence and Accidents of Software Engineering Description: We will keep having problems with software... Importance: Influence The Cathedral and the Bazaar Description: Open source methodology. Importance: Influence Design Patterns: Elements of Reusable Object Oriented Software Description: This book was the first to define and list design patterns in computer science Importance: Topic creator, Influence The Structure of "THE"-Multiprogramming System Description: The introduction of basic primitives like mutex as the basis of multiprocessing programming. Importance: Breakthrough, Influence How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs Importance: Breakthrough, Influence LogP: Towards a realistic model of parallel computation Description: The LogP framework for parallel computing was suggested. The LogP provided a way to bridge the gap between theoretical analysis of algorithm and building real world systems. Importance: Influence Ethernet: Distributed packet switching for local computer networks Description: The Ethernet protocol. Importance: Influence, Latest and greatest A Dynamic Network Architecture Description: Network software in distributed systems. Importance: Influence Computer Networks Description: Textbook description of all network standards at the time. In 2005, it is in its fourth edition (published in 2002), include all current networking technology. Importance: Influence The Byzantine Generals Problem Description: Impossibility result for distributed computing, see Byzantine failure. Importance: Influence, Breakthrough Impossibility of Distributed Consensus with One Faulty process Description: Impossibility to achieve consensus in asynchronous systems if one process is faulty . Importance: Influence, Breakthrough See also | |||||||
|
| ||||||||
 |
|
| |