''Degree of difficulty of computing a function and a partial ordering of recursive sets''
*
Description: This technical report was the first publication talking about what later was renamed ''Arora & Barak's ''Computational Complexity'' and Goldreich's ''Computational Complexity'' (both Cambridge)''
* Sanjeev Arora and Boaz Barak (2009) "Computational Complexity: A Modern Approach," Cambridge University Press, 579 pages, Hardcover
* Oded Goldreich (2008) "Computational Complexity: A Conceptual Perspective, Cambridge University Press, 606 pages, Hardcover
Besides the estimable press bringing these recent texts forward, they are very positively reviewed in ''ACM's SIGACT News'' by Daniel Apon of the University of Arkansas,[
]
''Paths, trees, and flowers''
*
Description: There is a polynomial time algorithm to find a maximum matching in a graph that is not bipartite and another step toward the idea of computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
. For more information se
''Theory and applications of trapdoor functions''
*
Description: This paper creates a theoretical framework for trapdoor function
In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trap ...
s and described some of their applications, like in cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. Note that the concept of trapdoor functions was brought at "New directions in cryptography" six years earlier (See section V "Problem Interrelationships and Trap Doors.").
''Computational Complexity''
* C.H. Papadimitriou
* Addison-Wesley
Addison-Wesley is an American publisher of textbooks and computer literature. It is an imprint of Pearson PLC, a global publishing and education company. In addition to publishing books, Addison-Wesley also distributes its technical titles through ...
, 1994,
Description: An introduction to computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the book explains its author's characterization of P-SPACE and other results.
''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. See PCP theorem.
Algorithms
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
"A machine program for theorem proving"
*
Description: The DPLL algorithm
In logic and computer science, the Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a complete, backtracking-based search algorithm for deciding the satisfiability of propositional logic formulae in conjunctive normal form, i.e. for solvi ...
. The basic algorithm for SAT and other NP-Complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problems.
"A machine-oriented logic based on the resolution principle"
*
Description: First description of resolution
Resolution(s) may refer to:
Common meanings
* Resolution (debate), the statement which is debated in policy debate
* Resolution (law), a written motion adopted by a deliberative body
* New Year's resolution, a commitment that an individual mak ...
and unification used in automated theorem proving
Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a maj ...
; used in Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily ...
and logic programming
Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic prog ...
.
"The traveling-salesman problem and minimum spanning trees"
*
Description: The use of an algorithm for minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
as an approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
for the NP-Complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
. Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
s became a common method for coping with NP-Complete problems.
"A polynomial algorithm in linear programming"
* L. G. Khachiyan (1979)
* '' Soviet Mathematics - Doklady'', vol. 20, pp. 191–194, 1979
Description: For long, there was no provably polynomial time algorithm for the linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
problem. Khachiyan was the first to provide an algorithm that was polynomial (and not just was fast enough most of the time as previous algorithms). Later, Narendra Karmarkar
Narendra Krishna Karmarkar (born Circa 1956) is an Indian Mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.
He invented one of the first provably polynomial time algorithms for linear p ...
presented a faster algorithm at: Narendra Karmarkar, "A new polynomial time algorithm for linear programming", Combinatorica
''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorar ...
, vol 4, no. 4, p. 373–395, 1984.
"Probabilistic algorithm for testing primality"
*
Description: The paper presented the Miller–Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...
and outlined the program of randomized algorithms
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
.
"Optimization by simulated annealing"
*
Description: This article described simulated annealing
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It ...
, which is now a very common heuristic for NP-Complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problems.
''The Art of Computer Programming''
* Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
Description: This monograph
A monograph is a specialist work of writing (in contrast to reference works) or exhibition on a single subject or an aspect of a subject, often by a single author or artist, and usually on a scholarly subject.
In library cataloging, ''monograph ...
has four volumes covering popular algorithms. The algorithms are written in both English and MIX assembly language (or MMIX
MMIX (pronounced ''em-mix'') is a 64-bit reduced instruction set computing (RISC) architecture designed by Donald Knuth, with significant contributions by John L. Hennessy (who contributed to the design of the MIPS architecture) and Richard L. S ...
assembly language in more recent fascicles). This makes algorithms both understandable and precise. However, the use of a low-level programming language
A low-level programming language is a programming language that provides little or no abstraction from a computer's instruction set architecture—commands or functions in the language map that are structurally similar to processor's instructions ...
frustrates some programmers more familiar with modern structured programming
Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection ( if/then/else) and repetition ( ...
languages
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
.
''Algorithms + Data Structures = Programs''
* Niklaus Wirth
Niklaus Emil Wirth (born 15 February 1934) is a Swiss computer scientist. He has designed several programming languages, including Pascal (programming language), Pascal, and pioneered several classic topics in software engineering. In 1984, he w ...
* Prentice Hall, 1976,
Description: An early, influential book on algorithms and data structures, with implementations in Pascal.
''The Design and Analysis of Computer Algorithms''
* Alfred V. Aho, John E. Hopcroft
John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is the IBM P ...
, and Jeffrey D. Ullman
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the ...
* Addison-Wesley, 1974,
Description: One of the standard texts on algorithms for the period of approximately 1975–1985.
''How to Solve It By Computer''
*
Description: Explains the ''Why''s of algorithms and data-structures. Explains the ''Creative Process'', the ''Line of Reasoning'', the ''Design Factors'' behind innovative solutions.
''Algorithms''
* Robert Sedgewick
* Addison-Wesley, 1983,
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.
''Introduction to Algorithms''
* Thomas H. Cormen
Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...
, Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...
, Ronald L. Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
, and Clifford Stein
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Scien ...
* 3rd Edition, MIT Press, 2009, .
Description: This textbook has become so popular that it is almost the de facto standard for teaching basic algorithms. The 1st edition (with first three authors) was published in 1990, the 2nd edition in 2001, and the 3rd in 2009.
Algorithmic information theory
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as st ...
"On Tables of Random Numbers"
*
*
Description: Proposed a computational and combinatorial approach to probability.
"A formal theory of inductive inference"
* Ray Solomonoff
Ray Solomonoff (July 25, 1926 – December 7, 2009) was the inventor of algorithmic probability, his General Theory of Inductive Inference (also known as Universal Inductive Inference),Samuel Rathmanner and Marcus Hutter. A philosophical treatise ...
* ''Information and Control
''Information and Computation'' is a closed-access computer science journal published by Elsevier (formerly Academic Press). The journal was founded in 1957 under its former name ''Information and Control'' and given its current title in 1987. , t ...
'', vol. 7, pp. 1–22 and 224–254, 1964
* Online copy
part Ipart II
Description: This was the beginning of algorithmic information theory
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as st ...
and Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
. Note that though Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
is named after Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
, he said that the seeds of that idea are due to Ray Solomonoff
Ray Solomonoff (July 25, 1926 – December 7, 2009) was the inventor of algorithmic probability, his General Theory of Inductive Inference (also known as Universal Inductive Inference),Samuel Rathmanner and Marcus Hutter. A philosophical treatise ...
. Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
contributed a lot to this area but in later articles.
"Algorithmic information theory"
*
Description: An introduction to algorithmic information theory
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as st ...
by one of the important people in the area.
Information theory
Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
"A mathematical theory of communication"
*
Description: This paper created the field of information theory
Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
.
"Error detecting and error correcting codes"
*
Description: In this paper, Hamming introduced the idea of error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
. He created the Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...
and the Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
and developed methods for code optimality proofs.
"A method for the construction of minimum redundancy codes"
*
Description: The Huffman coding
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algori ...
.
"A universal algorithm for sequential data compression"
*
Description: The LZ77
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.
They are also known as LZ1 and LZ2 respectively. These two algorithms form the basis for many variations includin ...
compression algorithm.
''Elements of Information Theory''
*
Description: A popular introduction to information theory.
Formal verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal metho ...
Assigning meaning to programs
*
Description: Floyd's landmark paper introduces the method of inductive assertions and describes how a program (presented as a flow chart
A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.
The flowchart shows the steps as boxes of va ...
) annotated with first-order assertions may be shown to satisfy a pre- and post-condition specification. The paper also introduces the concepts of loop invariant
In computer science, a loop invariant is a property of a program loop that is true before (and after) each iteration. It is a logical assertion, sometimes checked within the code by an assertion call. Knowing its invariant(s) is essential in und ...
and verification condition.
An axiomatic basis for computer programming
*
Description: Hoare's paper gives a set of logical rules for reasoning rigorously about the correctness of computer programs
In theoretical computer science, an algorithm is correct with respect to a specification if it behaves as specified. Best explored is ''functional'' correctness, which refers to the input-output behavior of the algorithm (i.e., for each input it p ...
. It defines an Algol-like programming language using what are now called Hoare triple
Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and lo ...
s. It has been used as the basis for most later work in the field, rather than Floyd's paper "Assigning meaning to programs", which did the same in terms of flow chart
A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.
The flowchart shows the steps as boxes of va ...
s.
Guarded Commands, Nondeterminacy and Formal Derivation of Programs
*
Description: Dijkstra's paper proposes (for the first time) that, instead of formally verifying a program after it has been written (i.e. post facto), programs and their formal proofs should be developed hand-in-hand (using predicate transformers to progressively refine weakest pre-conditions), a method known as program (or formal) refinement (or derivation), or sometimes "correctness-by-construction".
''Proving Assertions about Parallel Programs''
* Ashcroft, Edward A. (1975) J. Comput. Syst. Sci. 10(1): 110–135
Description: The paper introduced invariance proofs of concurrent programs. It did not receive much attention because it discussed programs in terms of flow charts
A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.
The flowchart shows the steps as boxes of v ...
and was not written clearly enough.
''An Axiomatic Proof Technique for Parallel Programs I''
*
Description: This paper, along with the same authors' paper extends the axiomatic approach to parallel-program verification with the notion of Interference freedom.
''A Discipline of Programming''
* Dijkstra, Edsger W. (1976)
Description: Dijkstra's classic postgraduate-level textbook extends his earlier paper ''Guarded commands, nondeterminacy and formal derivation of programs'' and firmly establishes the principle of formally deriving programs and their proofs hand-in-hand from their specifications.
The Temporal Logic of Programs
*
Description: Pnueli suggests temporal logic In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am ''always'' hungry", "I will ''eventually'' be hungry", or "I will be hungry ''until'' I ...
for formal verification in which the basic concept is the time dependence of events.
''Communicating Sequential Processes''
*
Description: Hoare's paper introduces the idea of concurrent processes (i.e. programs) that do not share variables but instead cooperate solely by exchanging synchronous messages. This has spurred great deal of research and advances, which are detailed in communicating sequential processes
In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or pro ...
''Characterizing correctness properties of parallel programs using fixpoints''
Description: Introduces model checking as a procedure to check correctness of concurrent programs.
''A Calculus of Communicating Systems''
Description: Milner's book describes a process algebra, called CCS, that permits systems of concurrent processes to be reasoned about formally, something that has not been possible for earlier models of concurrency (semaphores, critical sections, original CSP).
''Software Development: A Rigorous Approach''
Description: Jones' book is the first full-length exposition of the Vienna Development Method (VDM), which had evolved (principally) at IBM's Vienna research lab over the previous decade and which combines the idea of program refinement as per Dijkstra with that of data refinement (or reification) whereby algebraically defined abstract data types are formally transformed into progressively more "concrete" representations.
''The Science of Programming''
*
Description: This textbook describes Dijkstra's weakest precondition method of formal program derivation, except in a very much more accessible manner than Dijkstra's earlier ''A Discipline of Programming''. It has jokingly been called "Dijkstra for the masses". The emphasis is on developing program and proof hand-in-hand, with the proof ideas leading the way.
The examples in the book are small-scale, emphasizing basic algorithms, such as sorting, merging, and string manipulation. Subroutines (functions) are included, but not object-oriented and functional programming environments.
''Denotational Semantics''
* Stoy, Joe (1981)
Description: This book is the first postgraduate-level book-length exposition of the mathematical (or functional) approach to the formal semantics of programming languages (in contrast to the operational and algebraic approaches).
''Communicating Sequential Processes''
Hoare, Tony (1985). ''Communicating Sequential Processes
In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or pro ...
''. Prentice Hall
Prentice Hall was an American major educational publisher owned by Savvas Learning Company. Prentice Hall publishes print and digital content for the 6–12 and higher-education market, and distributes its technical titles through the Safari B ...
International Series in Computer Science. (hardback) or (paperback). (PDF available at http://www.usingcsp.com/)
Description: Hoare's book (currently the third most cited computer science reference of all time) presents an updated CSP model in which cooperating processes do not even have program variables and which, like CCS, permits systems of processes to be reasoned about formally.
''Linear logic''
*
Description: Girard's linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also be ...
was a breakthrough in designing typing systems for sequential and concurrent computation, especially for resource conscious typing systems.
''A Calculus of Mobile Processes''
Description: This paper introduces the Pi-Calculus, a generalisation of CCS that allows process mobility. This extremely simple calculus has become the dominant paradigm in the theoretical study of programming languages, typing systems, and program logics. A second paper, which completes the work, can be downloade
here
''Communication and Concurrency''
Description: Milner's text is a more accessible, although still technically advanced, exposition of his earlier CCS work.
''The Z Notation: A Reference Manual''
*
Description: Spivey's classic text summarises the formal specification language Z notation
The Z notation is a formal specification language used for describing and modelling computing systems. It is targeted at the clear specification of computer programs and computer-based systems in general.
History
In 1974, Jean-Raymond Abrial ...
, which, although originated by Jean-Raymond Abrial, had evolved (principally) at Oxford University over the previous decade.
''a Practical Theory of Programming''
Description: the up-to-date version of Predicative programming Predicative programming is the original name of a formal method for program specification language, specification and program refinement, refinement, more recently called a Practical Theory of Programming, invented by Eric Hehner. The central idea i ...
. The basis for C.A.R. Hoare's UTP. The simplest and most comprehensive formal methods. The latest online edition can be downloade
here
References
*
{{DEFAULTSORT:Important Publications In Theoretical Computer Science
History of computer science
Theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...