| On Computable Numbers |
Article Index for On |
Website Links For List |
Information AboutOn Computable Numbers |
|
COMPUTABILITY ''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''
Description: The Chomsky Hierarchy , a Containment Hierarchy of classes of Formal Grammars that generate Formal Languages was introduced. 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 COMPUTATIONAL COMPLEXITY THEORY ''On the computational complexity of algorithms''
Description: This paper gave Computational Complexity its name and seed. Importance: Topic creator, Breakthrough, Influence ''The complexity of theorem proving procedures''
Description: This paper introduced the concept of NP-Complete ness and proved that Boolean Satisfiability Problem (SAT) is NP-Complete . Importance: Topic creator, Breakthrough, Influence ''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 Function s ''
Description: This paper introduced the concept of Trapdoor Function s and described some of its application, like in Cryptography . 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''
Description: This paper showed that the existence of One Way Functions leads to Computational Randomness . Importance: Topic creator, Breakthrough, Latest and greatest, Influence '' IP = PSPACE ''
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 '' Interactive Proofs And The Hardness Of Approximating Cliques ''
'' ''
'' 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 ''
Description: This book provides a very good introduction to Computational Complexity Importance: Introduction ALGORITHMS ''A machine program for theorem proving''
Description: The DLL algorithm. The basic algorithm for SAT and other NP-Complete problems. Importance: Breakthrough, Influence ''A Machine-Oriented Logic Based on the Resolution Principle''
Description: First description of resolution and unification used in theorem proving; used in Prolog & Logic Programming . Importance: Topic Creator, Breakthrough, Influence ''Optimization by simulated annealing''
Description: 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 ''Why''s 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 SEE ALSO ''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 ALGORITHMIC INFORMATION THEORY ''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''
Description: A good introduction to Algorithmic Information Theory by one of the important people in the area. Importance: Introduction INFORMATION THEORY '' 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''
Description: A good and popular introduction to information theory. Importance: Influence, Introduction OPERATING SYSTEM ''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 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''
Description: Algorithms for coscheduling of related processes were given Importance: Influence DATABASE S ''A relational model for large shared data bank''
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 CRYPTOGRAPHY '' 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 ARTIFICIAL INTELLIGENCE ''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 ''''
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 UNFORMATTED LIST OF READING CONSIDERED AS SEMINAL WORKS IN THE FIELD OF ARTIFICIAL INTELLIGENCE
TechBookReport MACHINE LEARNING '' 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 ''
Description: Proving negative results for PAC Learning . Importance: Influence '' The strength of weak learnability ''
Description: Proving that weak and strong learnability are equivalent in the noise free PAC Framework . Importance: Breakthrough, Influence '' Learning in the presence of malicious errors ''
Description: Proving possibility and imposibility result in the malicious errors framework. Importance: Breakthrough, Influence COMPUTER VISION '' The Phase Correlation Image Alignment Method ''
Description: A correlation method based upon the inverse Fourier Transform Importance: Influence '' An Iterative Image Registration Technique with an Application to 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 : Active contour models ''
Description: An interactive variational technique for image segmentation and visual tracking Importance: Influence, topic creator '' Condensation -- conditional density propagation for visual tracking ''
Description: A technique for Visual Tracking Importance: Influence COMPILERS ''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 FORMAL VERIFICATION '' Assigning meanings to programs ''
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, Influence, Introduction '' An axiomatic basis for computer programming ''
Description: Axiomatic foundation for program correctness proofs was laid. The importance of the use of formal methods is explained. Importance: Topic creator, Breakthrough, Influence, Introduction ''The temporal logic of programs''
Description: The use of Temporal Logic was suggested as a method for formal verification. Importance: Topic creator, Influence ''Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints''
Description: Introducing Abstract Interpretation for the verification of computer programs by sound approximations. Importance: Topic creator, Influence. ''Model Checking''
Description: An overview of Model Checking , an automatic formal verification technique Importance: Introduction HISTORY OF COMPUTATION ''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 '' Science Committee''
Description: Conference of leading figures in software field circa 1968 Importance: Defined the field of Software Engineering '' Go To Statement 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 Pattern s in computer science Importance: Topic creator, Influence PARALLEL COMPUTING ''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 ''
Description: Requirements that guarantee the correct execution of multi process programs were defined. 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 COMPUTER NETWORK S ''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 DISTRIBUTED COMPUTING ''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 achievve Consensus in Asynchronous Systems if one process is faulty . Importance: Influence, Breakthrough SEE ALSO
EXTERNAL LINKS
Academic Search Engines |
|
|