Indeholder "Preface", "Acknowledgements", "Part One. Preliminaries", "1. Introduction and Historical Review - or, What's It All About?", " Some Gastronomy", " Algorithmics versus Computer Science", " Some History", " A Strange Dichotomy", " Some Limitations of Computers", " A Recipe", " Levels of Detail", " Short Algorithms for Long Processes", " The Algorithmic Problem", " Bounds on Basic Actions", " The Problem and Its Solution: Summary", "2. Algorithms and Data - or, Getting It Done", " Control Structures", " Combined Control Structures", " Bubblesort: An Example", " The 'Goto' Statement", " Diagrams for Algorithms", " Subroutines, or Procedures", " The Virtues of Subroutines", " Recursion", " The Towers of Hanoi: An Example", " The Expressive Power of Control Structures", " Variables, or Little Boxes", " Vectors, or Lists", " Arrays, or Tables", " Queues and Stacks", " Trees, or Hierarchies", " Treesort: An Example", " Databases and Knowledge Bases", "3. Programming Languages - or, Getting It Done by Computer", " Programs Require Precise Syntax", " Programs Require Precise Semantics", " Routines as Parameters: An Example", " From High-Level Languages to Bit Manipulation", " Compilation and Assembly Languages", " Interpreters and Immediate Execution", " Why Not an Algorithmic Esperanto?", " FORTRAN: A Language for Science and Engineering", " COBOL: A Language for Business and Commerce", " PASCAL: A General-Purpose Language", " SNOBOL: A Language for String and Text Manipulation", " LISP: An Applicative Language Based on List Processing", " PROLOG: A Language Based on Clausal Logic", " APL: The Quintessentially Compact Language", " Research on Programming Languages", "Part Two. Methods and Analysis", "4. Algorithmic Methods - or, Getting It Done Methodically", " Searches and Traversals", " Maximal Polygonal Distance: An Example", " Divide-and-Conquer", " Greedy Algorithms and Railroad Contractors", " Dynamic Planning and Weary Travelers", " Research on Algorithmic Methods", "5. The Correctness of Algorithms - or, Getting It Done Right", " Language Errors", " Logical Errors", " Computers Do Not Err", " Testing and Debugging", " Infinite Loops", " Partial and Total Correctness", " The Need for Proving Correctness", " Invariants and Convergents", " Reversing a Symbol String: An Example", " What's in a Proof?", " The Towers of Hanoi: An Example", " More on the Towers of Hanoi: A Simple Iterative Solution", " After-the-Fact versus As-You-Go Verification", " Interactive Verification and Proof Checking", " Research on Algorithmic Correctness", " The Four-Color Theorem", "6. The Efficiency of Algorithms - or, Getting It Done Cheaply", " Improvements Are Needed", " After-the-Fact Improvements", " Linear Search: An Example", " Order-of-Magnitude Improvements", " Binary Search: An Example", " Why Is It Enough to Count Comparisons?", " The Robustness of the Big-O Notation", " Time Analysis of Nested Loops", " Time Analysis of Recursion", " Average-Case Complexity", " Upper and Lower Bounds", " A Lower Bound for Telephone Book Search", " Closed Problems and Algorithmic Gaps", " Barricading Sleeping Tigers: An Example", " Research on the Efficiency of Algorithms", "Part Three. Limitations and Robustness", "7. Inefficiency and Intractability - or, You Can't Always Get It Done Cheaply", " The Towers of Hanoi Revisited", " The Monkey Puzzle Problem: An Example", " Reasonable versus Unreasonable Time", " More on the Monkey Puzzle Problem", " Two-Dimensional Arrangement Problems", " Path-Finding Problems", " Scheduling and Matching Problems", " Determining Logical Truth", " Coloring Maps and Graphs", " Short Certificates and Magic Coins", " NP-Completeness: Standing or Falling Together", " Reducing Oranges to Apples", " Is P Equal to NP?", " Imperfect Solutions to NP-complete Problems", " Provably Intractable Problems", " A Provably Intractable Satisfiability Problem", " Proving Exponential-Time Lower Bounds", " Problems that Are Even Harder!", " Unreasonable Amounts of Memory Space", " Research on Complexity Classes and Intractability", "8. Noncomputability and Undecidability - or, Sometimes You Can't Get It Done At all!", " The Rules of the Game", " The Tiling Problem: An Example", " Unboundedness Can Be Misleading", " Word Correspondence and Syntactical Equivalence", " Problems with Outputs Are No Better", " Algorithmic Program Verification", " The Halting Problem", " Proving Undecidability", " Proving the Undecidability of the Halting Problem", " Finite Certificates for Undecidable Problems", " Problems with Two-Way Certificates are Decidable", " Problems tha Are Even Less Decidable!", " Highly Undecidable Problems", " The Four Fundamental Levels of Algorithmic Behavior", " Research on Undecidability", "9. Algorithmic Universality and Its Robustness - or, The Simplest Machines that Get It Done", " An Exercise in Simplifying Data", " An Exercise in Simplifying Control", " Simplifying the Basic Operations", " The Turing Machine", " Detecting Palindromes: An Example", " Turing Machines versus Algorithms", " The Church/Turing Thesis", " Evidence for the Church/Turing Thesis", " Computability Is Robust", " Variants of the Turing Machine Model", " Folding Over an Infinite Tape: An Example", " Counter Programs: Another Very Primitive Model", " Turing Machines versus Counter Programs", " Universal Algorithms", " Simulations as Reductions", " A Slight Modification of Counter Programs", " Tractability Is also Robust", " Turing Machines and the P versus NP Problem", " Using Turing Machines for Lower Bound Proofs", " Proving Lower Bounds by Diagonalization", " One-Way Turing Machines, or Finite-State Automata", " On the Power of Finite Automata", " Research on Abstract Models of Computation", "Part Four. Relaxing the Rules", "10. Parallelism and Concurrency - or, Getting It Done by Cooperating", " Fixed versus Expanding Parallelism", " Sorting in Parallel", " The Product Complexity: Time x Size", " Networks: Fixed-Connection Parallelism", " The Odd-Even Sorting Network", " More About Networks: Computing Weighted Averages", " Can Parallelism Be Used to Solve the Unsolvable?", " The Parallel Computation Thesis", " Nick's Class: Towards Reasonable Parallelism", " Distributed and Ongoing Concurrency", " Solving Hotel Shower Problems", " Things Are Trickier than They Seem", " A Solution to the N-Processor Mutual Exclusion Problem", " Safety and Liveness Properties", " Temporal Logic", " Fairness and Real-Time Systems", " The Dining Philosophers Problem", " Concurrent Programming Languages", " Semaphores and Monitors", " Direct Communication Rendezvous", " Specifying Large and Complex Reactive Systems", " Statecharts: Visualizing Reactive Behavior", " Research on Parallelism and Concurrency", "11. Probabilistic Algorithms - or, Getting It Done by Tossing Coins", " More on the Dining Philosophers", " Probabilistic Algorithms for Conventional Algorithmic Problems", " Generating Large Primes", " Probabilistic Algorithms for Testing Primality", " Fast Probabilistic Pattern Matching", " Probabilistic Complexity Classes", " Cryptography", " Public-Key Cryptography", " The RSA Cryptosystem", " Playing Poker Over the Phone", " Research on Probabilistic Algorithms and Their Applications", " Theorems that Are Almost True?", "12. Algorithmics and Intelligence - or, Are They Better at It Than Us?", " Algorithmic Intelligence?", " The Turing Test", " Playing Games", " More About Heuristics", " Evaluating and Searching", " Knowledge Representation", " Expert Systems", " Knowledge in Learning, Planning, and Deduction", " Understanding Natural Language", "Postscript", "Bibliographic notes", "Index".

Ganske velskrevet bog. ( )