 |
|
| ||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||
|
|
|
|
|
| ||||||||
This is a list of important publications in computer science, organized by field.
Some reasons why a particular publication might be regarded as important:
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 , Effect
Description: The Chomsky hierarchy, a containment hierarchy of classes of formal grammars that generate formal languages was introduced.
Importance: Topic creator, Breakthrough , Effect
Description: Mathematical treatment of automata, proof of core properties, and definition of non-deterministic finite automaton
Importance: Topic creator, Breakthrough , Effect, Introduction
Description: This paper gave NP-Completeness and proved that Boolean satisfiability problem(SAT) is NP-Complete.
Importance: Topic creator, Breakthrough, Effect
Importance: Effect
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, Effect, Latest and greatest
Description: This paper introduced the concept of Trapdoor functions and described some of its application, like in cryptography.
Importance: Topic creator, Breakthrough
Importance: Topic creator, Breakthrough
Description: IP is a complexity class whose characterization is quite different from the usual time/space bounded computational classes. In this paper Shamir showed the IP = PSPACE, hence each problem in one complexity class is solvable in the other.
Importance: Breakthrough
Importance: Breakthrough, Effect
Importance: Topic Creator, Breakthrough, Effect
Importance: Effect
Description: This set of textbooks used to be very popular algorithms books. The algorithms were written in the MIX assembly language. Due to that, the algorithms were very precise but not very readable...
Importance: Effect
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, Effect
Description: A good introduction to Algorithmic information theory by one of the important people in the area.
Importance: Introduction
Importance: Topic creator, Breakthrough, Introduction, Effect
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, Effect
Description: The Huffman coding.
Importance: Effect, Breakthrough
Importance: Effect, Breakthrough
This idea changed the interaction with computer systems.
Importance: Effect
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: Effect, Breakthrough
Importance: Breakthrough, Effect
Importance: Breakthrough, Introduction, Effect
Importance: Topic creator, Breakthrough, Introduction, Effect, Latest and greatest (A great paper from every perspective...)
Description: The RSA encryption method. The first public key encryption method.
Importance: Breakthrough, Effect
Description: A safe method for sharing a secret.
Importance: Topic creator, Breakthrough
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, Effect
Importance: Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Breakthrough, Effect
Importance: Topic creator, Breakthrough, Effect
Importance: Breakthrough, Effect
Importance: Effect
Importance: Breakthrough, Effect
Importance: Effect
Importance: Effect
Importance: Introduction, Effect
Description: Introduced the idea of attaching logical assertions to points in a program in order to prove its correctness and influenced C. A. R. Hoare's seminal work on program verification.
Importance: Topic creator, Breakthrough, Effect, Introduction
Description: Axiomatic foundation for program correctness proofs was laid. The importance of the use of formal methods is explained.
Importance: Topic creator, Breakthrough, Effect, Introduction
Description: The use of temporal logic was suggested as a method for formal verification. Importance: Topic creator, Effect
Importance: Topic creator, Effect.
Importance: Topic creator, Effect
Description: The importance of modularization and information hiding.
Importance: Effect
Description: Throwing more people at the task will not speed its completion...
Importance: Effect
Description: We will keep having problems with software...
Importance: Effect
Description: Open source methodology.
Importance: Effect
Importance: Topic creator, Effect
Description: Requirements that guarantee the correct execution of multi process programs were defined.
Importance: Breakthrough, Effect
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: Effect
Importance: Effect, Latest and greatest
|
||||
| View Live Article | This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License | |
||
