List of important publications in computer science
This article has an unclear citation style. (October 2011) |
This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: citations in headings. (August 2013) |
This is a list of important publications in computer science, organized by field.
Some reasons why a particular publication might be regarded as important:
- Topic creator – A publication that created a new topic
- Breakthrough – A publication that changed scientific knowledge significantly
- Influence – A publication which has significantly influenced the world or has had a massive impact on the teaching of computer science.
Contents
- 1 Artificial intelligence
- 1.1 Computing Machinery and Intelligence
- 1.2 A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence
- 1.3 Fuzzy sets
- 1.4 Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
- 1.5 Artificial Intelligence: A Modern Approach
- 1.6 Machine learning
- 1.6.1 An Inductive Inference Machine
- 1.6.2 Language identification in the limit
- 1.6.3 On the uniform convergence of relative frequencies of events to their probabilities
- 1.6.4 A theory of the learnable
- 1.6.5 Learning representations by back-propagating errors
- 1.6.6 Induction of Decision Trees
- 1.6.7 Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm
- 1.6.8 Learning to predict by the method of Temporal difference
- 1.6.9 Learnability and the Vapnik–Chervonenkis dimension
- 1.6.10 Cryptographic limitations on learning boolean formulae and finite automata
- 1.6.11 The strength of weak learnability
- 1.6.12 Learning in the presence of malicious errors
- 1.6.13 A training algorithm for optimum margin classifiers
- 1.6.14 Knowledge-based analysis of microarray gene expression data by using support vector machines
- 2 Collaborative networks
- 3 Compilers
- 3.1 On the translation of languages from left to right[1]
- 3.2 Semantics of Context-Free Languages.
- 3.3 A program data flow analysis procedure
- 3.4 A Unified Approach to Global Program Optimization
- 3.5 YACC: Yet another compiler-compiler
- 3.6 gprof: A Call Graph Execution Profiler
- 3.7 Compilers: Principles, Techniques and Tools
- 4 Computer architecture
- 4.1 Colossus computer
- 4.2 First Draft of a Report on the EDVAC[2]
- 4.3 Architecture of the IBM System/360
- 4.4 The case for the reduced instruction set computer
- 4.5 Comments on "the Case for the Reduced Instruction Set Computer"
- 4.6 The CRAY-1 Computer System
- 4.7 Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities
- 4.8 A Case for Redundant Arrays of Inexpensive Disks (RAID)
- 4.9 The case for a single-chip multiprocessor
- 5 Computer graphics
- 6 Computer vision
- 6.1 The Phase Correlation Image Alignment Method
- 6.2 Determining Optical Flow
- 6.3 An Iterative Image Registration Technique with an Application to Stereo Vision
- 6.4 The Laplacian Pyramid as a compact image code
- 6.5 Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images
- 6.6 Snakes: Active contour models
- 6.7 Condensation – conditional density propagation for visual tracking
- 6.8 Object recognition from local scale-invariant features
- 7 Concurrent, parallel, and distributed computing
- 8 Databases
- 8.1 A relational model for large shared data banks
- 8.2 Binary B-Trees for Virtual Memory
- 8.3 Relational Completeness of Data Base Sublanguages
- 8.4 The Entity Relationship Model – Towards a Unified View of Data
- 8.5 SEQUEL: A structured English query language
- 8.6 The notions of consistency and predicate locks in a database system
- 8.7 Federated database systems for managing distributed, heterogeneous, and autonomous databases
- 8.8 Mining association rules between sets of items in large databases
- 9 History of computation
- 10 Information retrieval
- 11 Networks and security
- 12 Operating systems
- 12.1 An experimental timesharing system.
- 12.2 The Working Set Model for Program Behavior
- 12.3 Virtual Memory, Processes, and Sharing in MULTICS
- 12.4 A note on the confinement problem
- 12.5 The UNIX Time-Sharing System
- 12.6 Weighted voting for replicated data
- 12.7 Experiences with Processes and Monitors in Mesa
- 12.8 Scheduling Techniques for Concurrent Systems
- 12.9 A Fast File System for UNIX
- 12.10 The Design and Implementation of a Log-Structured File System
- 12.11 Microkernel operating system architecture and Mach
- 12.12 An Implementation of a Log-Structured File System for UNIX
- 12.13 Soft Updates: A Solution to the Metadata Update problem in File Systems
- 13 Programming languages
- 13.1 The FORTRAN Automatic Coding System[4]
- 13.2 Recursive functions of symbolic expressions and their computation by machine, part I[5]
- 13.3 ALGOL 60
- 13.4 Pascal
- 13.5 The next 700 programming languages[5]
- 13.6 Fundamental Concepts in Programming Languages
- 13.7 Lambda Papers
- 13.8 Structure and Interpretation of Computer Programs
- 13.9 The C Programming Language
- 13.10 The C++ Programming Language
- 13.11 The Java Programming Language
- 14 Scientific computing
- 15 Software engineering
- 15.1 Software engineering: Report of a conference sponsored by the NATO Science Committee
- 15.2 Go To Statement Considered Harmful[5]
- 15.3 On the criteria to be used in decomposing systems into modules
- 15.4 Hierarchical Program Structures
- 15.5 A technique for software module specification with examples
- 15.6 Structured Design
- 15.7 The Emperor's Old Clothes
- 15.8 The Mythical Man-Month: Essays on Software Engineering
- 15.9 No Silver Bullet: Essence and Accidents of Software Engineering
- 15.10 The Cathedral and the Bazaar
- 15.11 Design Patterns: Elements of Reusable Object Oriented Software
- 15.12 Statecharts: A Visual Formalism For Complex Systems
- 16 Theoretical computer science
- 17 See also
- 18 References
- 19 External links
Artificial intelligence[edit source | edit]
Computing Machinery and Intelligence[edit source | edit]
- Alan Turing
- Mind, 59:433–460, 1950.
- Online copy
Description: This paper discusses whether machines can think and suggested the Turing test as a method for checking it.
A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence[edit source | edit]
Description: This summer research proposal inaugurated and defined the field. It contains the first use of the term artificial intelligence and this succinct description of the philosophical foundation of the field: "every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it." (See philosophy of AI) The proposal invited researchers to the Dartmouth conference, which is widely considered the "birth of AI". (See history of AI.)
Fuzzy sets[edit source | edit]
- Lotfi Zadeh
- Information and Control, Vol. 8, pp. 338–353. (1965).
- Online copy
Description: The seminal paper published in 1965 provides details on the mathematics of fuzzy set theory.
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[edit source | edit]
- Judea Pearl
- ISBN 1-55860-479-0 Publisher: Morgan Kaufmann Pub, 1988
Description: This book introduced Bayesian methods to AI.
Artificial Intelligence: A Modern Approach[edit source | edit]
- Stuart J. Russell and Peter Norvig
- Prentice Hall, Englewood Cliffs, New Jersey, 1995, ISBN 0-13-080302-2
- Textbook's website
Description: The standard textbook in Artificial Intelligence. The book web site lists over 1100 colleges.
Machine learning[edit source | edit]
An Inductive Inference Machine[edit source | edit]
- Ray Solomonoff
- IRE Convention Record, Section on Information Theory, Part 2, pp. 56–62, 1957
- (A longer version of this, a privately circulated report, 1956, is online).
Description: The first paper written on machine learning. Emphasized the importance of training sequences, and the use of parts of previous solutions to problems in constructing trial solutions to new problems.
Language identification in the limit[edit source | edit]
- E. M. Gold
- Information and Control, 10:447–474, 1967
- Online version(HTML)
Description: This paper created Algorithmic learning theory.
On the uniform convergence of relative frequencies of events to their probabilities[edit source | edit]
- V. Vapnik, A. Chervonenkis
- Theory of Probability and its Applications, 16(2):264—280, 1971
Description: Computational learning theory, VC theory, statistical uniform convergence and the VC dimension.
A theory of the learnable[edit source | edit]
- Leslie Valiant
- Communications of the ACM, 27(11):1134–1142 (1984)
Description: The Probably approximately correct learning (PAC learning) framework.
Learning representations by back-propagating errors[edit source | edit]
- David E. Rumelhart, Geoffrey E. Hinton and Ronald J. Williams
- Nature, 323, 533—536, 1986
Description: Development of Backpropagation algorithm for artificial neural networks. Note that the algorithm was first described by Paul Werbos in 1974.
Induction of Decision Trees[edit source | edit]
- J.R. Quinlan
- Machine Learning, 1. 81—106, 1986.
Description: Decision Trees are a common learning algorithm and a decision representation tool. Development of decision trees was done by many researchers in many areas, even before this paper. Though this paper is one of the most influential in the field.
Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm[edit source | edit]
- Nick Littlestone
- Machine Learning 2: 285–318, 1988
- Online version(PDF)
Description: One of the papers that started the field of on-line learning. In this learning setting, a learner receives a sequence of examples, making predictions after each one, and receiving feedback after each prediction. Research in this area is remarkable because (1) the algorithms and proofs tend to be very simple and beautiful, and (2) the model makes no statistical assumptions about the data. In other words, the data need not be random (as in nearly all other learning models), but can be chosen arbitrarily by "nature" or even an adversary. Specifically, this paper introduced the winnow algorithm.
Learning to predict by the method of Temporal difference[edit source | edit]
- Richard S. Sutton
- Machine Learning 3(1): 9–44
- Online copy
Description: The Temporal difference method for reinforcement learning.
Learnability and the Vapnik–Chervonenkis dimension[edit source | edit]
- A. Blumer
- A. Ehrenfeucht
- D. Haussler
- M. K. Warmuth
- Journal of the ACM, 36(4):929–965, 1989.
Description: The complete characterization of PAC learnability using the VC dimension.
Cryptographic limitations on learning boolean formulae and finite automata [edit source | edit]
- M. Kearns
- L. G. Valiant
- In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433–444, New York. ACM.
- Online version(HTML)
Description: Proving negative results for PAC learning.
The strength of weak learnability[edit source | edit]
- Robert E. Schapire
- Machine Learning, 5(2):197–227, 1990.
- Online version(HTML)
Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework. The proof was done by introducing the boosting method.
Learning in the presence of malicious errors[edit source | edit]
- Michael Kearns
- Ming Li
- Journal on Computing, 22(4):807–837, August 1993.
- Online version(HTML)
Description: Proving possibility and impossibility result in the malicious errors framework.
A training algorithm for optimum margin classifiers[edit source | edit]
- Bernhard E. Boser
- Isabelle M. Guyon
- Vladimir N. Vapnik
- Proceedings of the Fifth Annual Workshop on Computational Learning Theory 5 144–152, Pittsburgh (1992).
- Online version(HTML)
Description: This paper presented support vector machines, a practical and popular machine learning algorithm. Support vector machines utilize the kernel trick, a generally used method.
Knowledge-based analysis of microarray gene expression data by using support vector machines[edit source | edit]
- MP Brown
- WN Grundy
- D Lin
- Nello Cristianini
- CW Sugnet
- TS Furey
- M Ares Jr,
- David Haussler
- PNAS, 2000 January 4;97(1):262–7 <http://www.pnas.org/cgi/content/abstract/97/1/262>
Description: The first application of supervised learning to gene expression data, in particular Support Vector Machines. The method is now standard, and the paper one of the most cited in the area.
Collaborative networks[edit source | edit]
- Camarinha-Matos, L. M.; Afsarmanesh,H. (2005). Collaborative networks: A new scientific discipline, J. Intelligent Manufacturing, vol. 16, Nº 4–5, pp 439–452.
- Camarinha-Matos, L. M.; Afsarmanesh,H. (2008). Collaborative Networks: Reference Modeling, Springer: New York.
Compilers[edit source | edit]
On the translation of languages from left to right[1][edit source | edit]
- Donald Knuth
- Information and Control 8 (1965), 607–639.
Description: Bottom up parsing for deterministic context-free languages from which the LALR parser was derived, the parsing approach used by Yacc.
Semantics of Context-Free Languages.[edit source | edit]
- Donald Knuth
- Math. Systems Theory 2:2 (1968), 127–145.
Description: About grammar attribution, the base for yacc's s-attributed and zyacc's LR-attributed approach.
A program data flow analysis procedure[edit source | edit]
- F.E. Allen, J. Cocke
- Commun. ACM, 19, 137—147.
Description: From the abstract: "The global data relationships in a program can be exposed and codified by the static analysis methods described in this paper. A procedure is given which determines all the definitions which can possibly reach each node of the control flow graph of the program and all the definitions that are live on each edge of the graph."
A Unified Approach to Global Program Optimization[edit source | edit]
- Gary Kildall
- Proceedings of ACM SIGACT-SIGPLAN 1973 Symposium on Principles of Programming Languages.
Description: Formalized the concept of data-flow analysis as fixpoint computation over lattices, and showed that most static analyses used for program optimization can be uniformly expressed within this framework.
YACC: Yet another compiler-compiler[edit source | edit]
- Stephen C. Johnson
- Unix Programmer's Manual Vol 2b, 1979
- Online copy (HTML)
Description: Yacc is a tool that made compiler writing much easier.
gprof: A Call Graph Execution Profiler[edit source | edit]
- Susan L. Graham, Peter B. Kessler, Marshall Kirk McKusick
- Proceedings of the ACM SIGPLAN 1982 Symposium on Compiler Construction, SIGPLAN Notices 17, 6, Boston, MA. June 1982.
- Online copy; pdf
Description: The gprof profiler
Compilers: Principles, Techniques and Tools [edit source | edit]
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.
Computer architecture[edit source | edit]
Colossus computer[edit source | edit]
- T. H. Flowers
- Annals of the History of Computing, Vol. 5 (No. 3), 1983, pp. 239–252.
- The Design of Colossus
Description: The Colossus machines were early computing devices used by British codebreakers to break German messages encrypted with the Lorenz Cipher during World War II. Colossus was an early binary electronic digital computer. The design of Colossus was later described in the referenced paper.
First Draft of a Report on the EDVAC[2][edit source | edit]
- John von Neumann
- June 30, 1945, the ENIAC project.
- First Draft of a report on the EDVAC (PDF)
Description: It contains the first published description of the logical design of a computer using the stored-program concept, which has come to be known as the von Neumann architecture.
Architecture of the IBM System/360[edit source | edit]
- Gene Amdahl, Fred Brooks, G. A. Blaauw
- IBM Journal of Research and Development, 1964.
- Architecture of the IBM System/360
Description: The IBM System/360 (S/360) is a mainframe computer system family announced by IBM on April 7, 1964. It was the first family of computers making a clear distinction between architecture and implementation.
The case for the reduced instruction set computer[edit source | edit]
- DA Patterson, DR Ditzel
- Computer ArchitectureNews, vol. 8, no. 6, October 1980, pp 25–33.
- Online version(PDF)
Description: The reduced instruction set computer( RISC) CPU design philosophy. The RISC is a CPU design philosophy that favors a reduced set of simpler instructions.
Comments on "the Case for the Reduced Instruction Set Computer"[edit source | edit]
- DW Clark, WD Strecker
- Computer Architecture News, 1980.
- Online version(PDF)
Description:
The CRAY-1 Computer System[edit source | edit]
- DW Clark, WD Strecker
- Communications of the ACM, January 1978, volume 21, number 1, pages 63–72.
- Online version(PDF)
Description: The Cray-1 was a supercomputer designed by a team including Seymour Cray for Cray Research. The first Cray-1 system was installed at Los Alamos National Laboratory in 1976, and it went on to become one of the best known and most successful supercomputers in history.
Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities[edit source | edit]
- Gene Amdahl
- AFIPS 1967 Spring Joint Computer Conference, Atlantic City, N.J.
- Online version(PDF)
Description: The Amdahl's Law.
A Case for Redundant Arrays of Inexpensive Disks (RAID)[edit source | edit]
- David A. Patterson, Garth Gibson, Randy H. Katz
- In International Conference on Management of Data, pages 109—116, 1988.
- Online version(PDF)
Description: This paper discusses the concept of RAID disks, outlines the different levels of RAID, and the benefits of each level. It is a good paper for discussing issues of reliability and fault tolerance of computer systems, and the cost of providing such fault-tolerance.
The case for a single-chip multiprocessor[edit source | edit]
- Kunle Olukotun, Basem Nayfeh, Lance Hammond, Ken Wilson, Kunyung Chang
- In SIGOPS Oper. Syst. Rev. 30, pages 2–11, 1996.
- Online version(PDF)
Description: This paper argues that the approach taken to improving the performance of processors by adding multiple instruction issue and out-of-order execution cannot continue to provide speedups indefinitely. It lays out the case for making single chip processors that contain multiple "cores". With the mainstream introduction of multicore processors by Intel in 2005, and their subsequent domination of the market, this paper was shown to be prescient.
Computer graphics[edit source | edit]
The Rendering Equation[edit source | edit]
- J. Kajiya
- SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques pages 143—150 [3]
Elastically deformable models[edit source | edit]
- D. Terzopoulos, J. Platt, A. Barr, K. Fleischer
- Computer Graphics, 21(4), 1987, 205–214, Proc. ACM SIGGRAPH'87 Conference, Anaheim, CA, July 1987.
- Online version(PDF)
Description: The Academy of Motion Picture Arts and Sciences cited this paper as a "milestone in computer graphics".
Computer vision[edit source | edit]
The Phase Correlation Image Alignment Method [edit source | edit]
- C.D. Kuglin and D.C. Hines
- IEEE 1975 Conference on Cybernetics and Society, 1975, New York, pp. 163–165, September
Description: A correlation method based upon the inverse Fourier transform
Determining Optical Flow[edit source | edit]
- B.K.P. Horn and B.G. Schunck
- Artificial Intelligence, Volume 17, 185–203, 1981
Description: A method for estimating the image motion of world points between 2 frames of a video sequence.
An Iterative Image Registration Technique with an Application to Stereo Vision[edit source | edit]
- Lucas, B.D. and Kanade, T.
- Proceedings of the 7th International Joint Conference on Artificial Intelligence, 674–679,Vancouver, Canada,1981
- Online version
Description: This paper provides efficient technique for image registration
The Laplacian Pyramid as a compact image code[edit source | edit]
- Peter J. Burt and Edward H. Adelson
- IEEE Transactions on Communications, volume = "COM-31,4", pp. 532–540, 1983.
- Online version
Description: A technique for image encoding using local operators of many scales.
Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images[edit source | edit]
- Stuart Geman and Donald Geman
- IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984
Description: introduced 1) MRFs for image analysis 2) the Gibbs sampling which revolutionized computational Bayesian statistics and thus had paramount impact in many other fields in addition to Computer Vision.
Snakes: Active contour models[edit source | edit]
- Michael Kass, Andrew Witkin, and Demetri Terzopoulos
- International Journal of Computer Vision, 1(4):321–331, 1988. (Marr Prize Special Issue)
- Online version
Description: An interactive variational technique for image segmentation and visual tracking.
Condensation – conditional density propagation for visual tracking[edit source | edit]
- M. Isard and A. Blake
- International Journal of Computer Vision, 29(1):5–28, 1998.
- Online version
Description: A technique for visual tracking
Object recognition from local scale-invariant features [edit source | edit]
- David Lowe
- International Conference on Computer Vision, pp. 1150–1157, 1999
- [1]
Description: A technique (scale-invariant feature transform) for robust feature description
Concurrent, parallel, and distributed computing[edit source | edit]
Topics covered: concurrent computing, parallel computing, and distributed computing.
Databases[edit source | edit]
[edit source | edit]
- E. F. Codd
- Communications of the ACM, 13(6):377–387, June 1970
Description: This paper introduced the relational model for databases. This model became the number one model.
Binary B-Trees for Virtual Memory[edit source | edit]
- Rudolf Bayer
- ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219–235.
Description: This paper introduced the B-Trees data structure. This model became the number one model.
Relational Completeness of Data Base Sublanguages[edit source | edit]
- E. F. Codd
- In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972)
- Online version (PDF)
Description: Completeness of Data Base Sublanguages
The Entity Relationship Model – Towards a Unified View of Data[edit source | edit]
Description: This paper introduced the entity-relationship diagram(ERD) method of database design.
SEQUEL: A structured English query language[edit source | edit]
- Donald D. Chamberlin, Raymond F. Boyce
- International Conference on Management of Data, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, Ann Arbor, Michigan, pp. 249–264
Description: This paper introduced the SQL language.
The notions of consistency and predicate locks in a database system[edit source | edit]
- K.P. Eswaran, J. Gray, R.A. Lorie, I.L. Traiger
- Communications of the ACM 19, 1976, 624—633
Description: This paper defined the concepts of transaction, consistency and schedule. It also argued that a transaction needs to lock a logical rather than a physical subset of the database.
Federated database systems for managing distributed, heterogeneous, and autonomous databases[edit source | edit]
- Amit Sheth, J.A. Larson,"
- ACM Computing Surveys (CSUR) - Special issue on heterogeneous databases Surveys, Volume 22 Issue 3, Pages 183 - 236, Sept. 1990
- ACM source
Description: Introduced federated database systems concept leading huge impact on data interoperability and integration of hetereogenous data sources.
Mining association rules between sets of items in large databases[edit source | edit]
- Rakesh Agrawal, Tomasz Imielinski, Arun Swami
- Proc. of the ACM SIGMOD Conference on Management of Data, pages 207–216, Washington, D.C., May 1993
- Online copy (HTML)
Description: Association rules, a very common method for data mining.
History of computation[edit source | edit]
The Computer from Pascal to von Neumann[edit source | edit]
- Goldstine, Herman H. (1972). The Computer from Pascal to von Neumann. Princeton University Press. ISBN 0-691-08104-2.
Description: Perhaps the first book on the history of computation.
A History of Computing in the Twentieth Century[edit source | edit]
edited by:
Description: Several chapters by pioneers of computing.
Information retrieval[edit source | edit]
A Vector Space Model for Automatic Indexing[edit source | edit]
- Gerard Salton, A. Wong, C. S. Yang
- Commun. ACM 18(11): 613–620 (1975)
Description: Presented the vector space model.
Extended Boolean Information Retrieval[edit source | edit]
- Gerard Salton, Edward A. Fox, Harry Wu
- Commun. ACM 26(11): 1022–1036 (1983)
Description: Presented the inverted index
Networks and security[edit source | edit]
Topics covered: cryptography and computer security, computer networks and the Internet.
Operating systems[edit source | edit]
An experimental timesharing system.[edit source | edit]
- Fernando J. Corbató, M. Merwin-Daggett, and R.C. Daley
- Proceedings of the AFIPS FJCC, pages 335–344, 1962.
- Online copy (HTML)
Description: This paper discuss time-sharing as a method of sharing computer resource. This idea changed the interaction with computer systems.
The Working Set Model for Program Behavior[edit source | edit]
- Peter J. Denning
- Communications of the ACM, Vol. 11, No. 5, May 1968, pp 323–333
- Online version(PDF)
Description: The beginning of cache. For more information see SIGOPS Hall of Fame.
Virtual Memory, Processes, and Sharing in MULTICS[edit source | edit]
- Robert C. Daley, Jack B. Dennis
- Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 306–312.
- Online version(PDF)
Description: The classic paper on Multics, the most ambitious operating system in the early history of computing. Difficult reading, but it describes the implications of trying to build a system that takes information sharing to its logical extreme. Most operating systems since Multics have incorporated a subset of its facilities.
A note on the confinement problem[edit source | edit]
- Butler W. Lampson
- Communications of the ACM, 16(10):613–615, October 1973.
- Online version(PDF)
Description: This paper addresses issues in constraining the flow of information from untrusted programs. It discusses covert channels, but more importantly it addresses the difficulty in obtaining full confinement without making the program itself effectively unusable. The ideas are important when trying to understand containment of malicious code, as well as aspects of trusted computing.
The UNIX Time-Sharing System[edit source | edit]
- Dennis M. Ritchie and Ken Thompson
- Communications of the ACM 7, 7, July 1974.
- Online copy (few formats)
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.
Weighted voting for replicated data[edit source | edit]
- David K. Gifford
- Proceedings of the 7th ACM Symposium on Operating Systems Principles, pages 150–159, December 1979. Pacific Grove, California
- Online copy (few formats)
Description: This paper describes the consistency mechanism known as quorum consensus. It is a good example of algorithms that provide a continuous set of options between two alternatives (in this case, between the read-one write-all, and the write-one read-all consistency methods). There have been many variations and improvements by researchers in the years that followed, and it is one of the consistency algorithms that should be understood by all. The options available by choosing different size quorums provide a useful structure for discussing of the core requirements for consistency in distributed systems.
Experiences with Processes and Monitors in Mesa[edit source | edit]
- Butler W. Lampson, David D. Redell
- Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105–117.
- Online copy (PDF)
Description: This is the classic paper on synchronization techniques, including both alternate approaches and pitfalls.
Scheduling Techniques for Concurrent Systems[edit source | edit]
- J. K. Ousterhout
- Proceedings of Third International Conference on Distributed Computing Systems, 1982, 22—30.
Description: Algorithms for coscheduling of related processes were given
A Fast File System for UNIX[edit source | edit]
- Marshall Kirk Mckusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry
- IACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181–197.
- Online copy (PDF)
Description: The file system of UNIX. One of the first papers discussing how to manage disk storage for high-performance file systems. Most file-system research since this paper has been influenced by it, and most high-performance file systems of the last 20 years incorporate techniques from this paper.
The Design and Implementation of a Log-Structured File System[edit source | edit]
- Mendel Rosenblum, J. K. Ousterhout
- ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 26–52.
- Online version
Description: Log-structured file system.
Microkernel operating system architecture and Mach[edit source | edit]
- David L. Black, David B. Golub, Daniel P. Julin, Richard F. Rashid, Richard P. Draves, Randall W. Dean, Alessandro Forin, Joseph Barrera, Hideyuki Tokuda, Gerald Malan, David Bohman
- Proceedings of the USENIX Workshop on Microkernels and Other Kernel Architectures, pages 11–30, April 1992.
Description: This is a good paper discussing one particular microkernel architecture and contrasting it with monolithic kernel design. Mach underlies Mac OS X, and its layered architecture had a significant impact on the design of the Windows NT kernel and modern microkernels like L4. In addition, its memory-mapped files feature was added to many monolithic kernels.
An Implementation of a Log-Structured File System for UNIX[edit source | edit]
- Margo Seltzer, Keith Bostic, Marshall Kirk McKusick, Carl Staelin
- Proceedings of the Winter 1993 USENIX Conference, San Diego, CA, January 1993, 307-326
- Online version
Description: The paper was the first production-quality implementation of that idea which spawned much additional discussion of the viability and short-comings of log-structured filesystems. While "The Design and Implementation of a Log-Structured File System" was certainly the first, this one was important in bringing the research idea to a usable system.
Soft Updates: A Solution to the Metadata Update problem in File Systems[edit source | edit]
- G. Ganger, M. McKusick, C. Soules, Y. Patt
- ACM Transactions on Computer Systems 18, 2. pp 127–153, May 2000
- Online version
Description: A new way of maintaining filesystem consistency.
Programming languages[edit source | edit]
The FORTRAN Automatic Coding System[4][edit source | edit]
- John Backus et al.
- Proceedings of the WJCC (Western Joint Computer Conference), Los Angeles, California, February 1957.
- Online version(PDF)
Description: This paper describes the design and implementation of the first FORTRAN compiler by the IBM team. Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing.
Recursive functions of symbolic expressions and their computation by machine, part I[5][edit source | edit]
- John McCarthy.
- Communications of the ACM, 3(4):184–195, April 1960.
- Several online versions
Description: This paper introduced LISP, the first functional programming language, which was used heavily in many areas of computer science, especially in AI. LISP also has powerful features for manipulating LISP programs within the language.
ALGOL 60[edit source | edit]
- Revised Report on the Algorithmic Language Algol 60 by Peter Naur, et al. – The very influential ALGOL definition; with the first formally defined syntax.
- B. Randell and L.J. Russell, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer. Academic Press, 1964. The design of the Whetstone Compiler. One of the early published descriptions of implementing a compiler. See the related papers: Whetstone Algol Revisited, and The Whetstone KDF9 Algol Translator by B. Randell
- Edsger W. Dijkstra, Algol 60 translation: an Algol 60 translator for the x1 and making a translator for Algol 60, report MR 35/61. Mathematisch Centrum, Amsterdam, 1961. [6]
Description: Algol 60 introduced block structure.
Pascal[edit source | edit]
- Niklaus Wirth: The Programming Language Pascal. 35–63, Acta Informatica, Volume 1, 1971.
- Kathleen Jensen and Niklaus Wirth: PASCAL - User Manual and Report. Springer-Verlag, 1974, 1985, 1991, ISBN 0-387-97649-3 and ISBN 3-540-97649-3 [7]
- Niklaus Wirth: Algorithms + Data Structures = Programs. Prentice–Hall, 1975, ISBN 0-13-022418-9 [8]
Description: Pascal introduced good programming practices using structured programming and data structuring.
The next 700 programming languages[5][edit source | edit]
- Peter Landin
- Communications of the ACM 9(3):157–65, March 1966 [9]
Description: This seminal paper proposed an ideal language ISWIM, which without being ever implemented influenced the whole later development.
Fundamental Concepts in Programming Languages[edit source | edit]
Lambda Papers[edit source | edit]
- Gerald Jay Sussman and Guy L. Steele, Jr.
- AI Memos, 1975–1980
Description: This series of papers and reports first defined the influential Scheme programming language and questioned the prevailing practices in programming language design, employing lambda calculus extensively to model programming language concepts and guide efficient implementation without sacrificing expressive power.
Structure and Interpretation of Computer Programs[edit source | edit]
- Harold Abelson and Gerald Jay Sussman
- MIT Press, 1984, 1996
Description: This textbook explains core computer programming concepts, and is widely considered a classic text in computer science.
The C Programming Language[edit source | edit]
- Brian Kernighan and Dennis Ritchie
- Prentice Hall, 1978, 1988
Description: Co-authored by the man who designed the C programming language, the first edition of this book served for many years as the language's de facto standard. As such, the book is regarded by many to be the authoritative reference on C.
The C++ Programming Language[edit source | edit]
- Bjarne Stroustrup
- Addison–Wesley, 1986, 1997, 2000
Description: Written by the man who designed the C++ programming language, the first edition of this book served for many years as the language's de facto standard until the publication of the ISO/IEC 14882:1998: Programming Language C++ standard on 1 September 1998.
The Java Programming Language[edit source | edit]
- Ken Arnold, James Gosling, David Holmes, The Java Programming Language, Fourth Edition, Addison-Wesley Professional, 2005, ISBN 0-321-34980-6
Scientific computing[edit source | edit]
- Wilkinson, J. H.; Reinsch, C. (1971). Linear algebra, volume II of Handbook for Automatic Computation. Springer. ISBN 978-0-387-05414-8.
- Golub, Gene H.; van Loan, Charles F. (1996) [1983], Matrix Computations, 3rd edition, Johns Hopkins University Press;, ISBN 978-0-8018-5414-9
Computational linguistics[edit source | edit]
- Booth, T. L. (1969). "Probabilistic representation of formal languages". IEEE Conference Record of the 1969 Tenth Annual Symposium on Switching and Automata Theory. pp. 74–81.
- Contains the first presentation of stochastic context-free grammars.
- Koskenniemi, Kimmo (1983), Two-level morphology: A general computational model of word-form recognition and production, Department of General Linguistics, University of Helsinki
- The first published description of computational morphology using finite state transducers. (Kaplan and Kay had previously done work in this field and presented this at a conference; the linguist Johnson had remarked the possibility in 1972, but not produced any implementation.)
- Rabiner, Lawrence R. (1989). "A tutorial on hidden Markov models and selected applications in speech recognition". Proceedings of the IEEE 77 (2): 257–286.
- An overview of hidden Markov models geared toward speech recognition and other NLP fields, describing the Viterbi and forward-backward algorithms.
- Brill, Eric (1995). "Transformation-based error-driven learning and natural language processing: A case study in part-of-speech tagging". Computational Linguistics 21 (4): 543–566.
- Describes a now commonly used POS tagger based on transformation-based learning.
- Manning, Christopher D.; Schütze, Hinrich (1999), Foundation of Statistical Natural Language Processing, MIT Press
- Textbook on statistical and probabilistic methods in NLP.
- Frost, Richard A. (2006). "Realization of Natural-Language Interfaces Using Lazy Functional Programming". ACM Computing Surveys 38 (4).
- This survey documents relatively less researched importance of lazy functional programming languages (i.e. Haskell) to construct Natural Language Processors and to accommodated many linguistic theories.
Software engineering[edit source | edit]
Software engineering: Report of a conference sponsored by the NATO Science Committee[edit source | edit]
- Peter Naur, Brian Randell (eds.)
- Garmisch, Germany, 7–11 October 1968, Brussels, Scientific Affairs Division, NATO (1969) 231pp.
- Online copy (PDF)
Description: Conference of leading figures in software field c. 1968
The paper defined the field of Software engineering
Go To Statement Considered Harmful[5][edit source | edit]
- Dijkstra, E. W.
- Communications of the ACM, 11(3):147–148, March 1968
- Online copy (PDF)
Description: Don't use goto – the beginning of structured programming.
On the criteria to be used in decomposing systems into modules[edit source | edit]
- David Parnas
- Communications of the ACM, Volume 15, Issue 12:1053–1058, December 1972.
- Online copy (PDF)
Description: The importance of modularization and information hiding. Note that information hiding was first presented in a different paper of the same author – "Information Distributions Aspects of Design Methodology", Proceedings of IFIP Congress '71, 1971, Booklet TA-3, pp. 26–30
Hierarchical Program Structures[edit source | edit]
- Ole-Johan Dahl, C. A. R. Hoare
- in Dahl, Dijkstra and Hoare, Structured Programming, Academic Press, London and New York, pp. 175–220, 1972.
Description: The beginning of Object-oriented programming. This paper argued that programs should be decomposed to independent components with small and simple interfaces. They also argued that objects should have both data and related methods.
A technique for software module specification with examples[edit source | edit]
- David Parnas
- Comm. ACM 15, 5 (May 1972), 330–336.
- Online copy (PDF)
Description: software specification.
Structured Design[edit source | edit]
- Wayne Stevens, Glenford Myers, and Larry Constantine
- IBM Systems Journal, 13 (2), 115–139, 1974.
- On-line copy (PDF)
Description: Seminal paper on Structured Design, data flow diagram, coupling, and cohesion.
The Emperor's Old Clothes[edit source | edit]
- C.A.R. Hoare
- Communications of the ACM, Vol. 24, No. 2, February 1981, pp. 75–83.
- Archived copy (PDF)
Description: A lovely story of how large software projects can go right, and then wrong, and then right again, told with humility and humor. Illustrates the "second-system effect" and the importance of simplicity.
The Mythical Man-Month: Essays on Software Engineering[edit source | edit]
- Brooks, Jr., F. P.
- Addison Wesley Professional. 2nd edition, 1995.
Description: Throwing more people at the task will not speed its completion...
No Silver Bullet: Essence and Accidents of Software Engineering[edit source | edit]
- Brooks, Frederick. P., Jr. (April 1987). "No Silver Bullet: Essence and Accidents of Software Engineering". Computer 20 (4): 10–19. doi:10.1109/MC.1987.1663532.
Description: We will keep having problems with software...
The Cathedral and the Bazaar[edit source | edit]
- Raymond, E.S.
- First Monday, 3, 3 (March 1998)
- Online copy (HTML)
Description: Open source methodology.
Design Patterns: Elements of Reusable Object Oriented Software[edit source | edit]
- E. Gamma, R. Helm, R. Johnson, J. Vlissides
- Addison–Wesley, Reading, Massachusetts, 1995.
Description: This book was the first to define and list design patterns in computer science.
Statecharts: A Visual Formalism For Complex Systems[edit source | edit]
- David Harel
- D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8:231—274, 1987
- Online version
Description: Statecharts are a visual modeling method. They are an extension of state machine that might be exponentially more efficient. Therefore, statcharts enable formal modeling of applications that were too complex before. Statecharts are part of the UML diagrams.
Theoretical computer science[edit source | edit]
Topics covered: theoretical computer science, including computability theory, computational complexity theory, algorithms, algorithmic information theory, information theory and formal verification.
See also[edit source | edit]
- DBLP (Digital Bibliography & Library Project in computer science)
- List of open problems in computer science
- The Collection of Computer Science Bibliographies
- Paris Kanellakis Award, a prize given to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing.
References[edit source | edit]
- ^ Laplante 1996, p. 150
- ^ Laplante 1996, p. 208
- ^ The rendering equation
- ^ Laplante 1996, p. 62
- ^ a b c Pierce, Benjamin C. (2004). "Great works in programming languages". Penn Engineering.
- ^ http://www.cs.utexas.edu/users/EWD/MCReps/MR35.PDF
- ^ http://www.cs.inf.ethz.ch/~wirth/books/Pascal/
- ^ http://www.cs.inf.ethz.ch/~wirth/books/AlgorithmE0/
- ^ Google Академія
- Laplante, Phillip, ed. (1996). Great papers in computer science. New York: IEEE Press. ISBN 0-314-06365-X.
- Randell, Brian (ed). (1982). The Origins of Digital Computers: Selected Papers. 3rd ed. Berlin: Springer-Verlag. ISBN 0-387-11319-3.
- Turning Points in Computing: 1962–1999, Special Issue, IBM Systems Journal, 38 (2/3),1999.
- Yourdon, Edward (ed.) (1979) Classics in Software Engineering. New York: Yourdon Press. ISBN 0-917072-14-6
External links[edit source | edit]
- ACM Classic Books Series
- Most cited articles in Computer Science (CiteSeer Database)
- 50 most influential papers ACM SIGPLAN papers published in PLDI from 1979 through 1999; organized into a special SIGPLAN proceedings.
Academic Search Engines[edit source | edit]
|