Algorithmics: The Spirit of Computing

by David Harel

Paperback, 1987

Status

Available

Call number

004

Library's review

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 Improvemnts", " 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.
… (more)

Publication

Addison Wesley (1987), Paperback, 437 pages

Description

The best selling 'Algorithmics' presents the most important, concepts, methods and results that are fundamental to the science of computing.  It starts by introducing the basic ideas of algorithms, including their structures and methods of data manipulation.  It then goes on to demonstrate how to design accurate and efficient algorithms, and discusses their inherent limitations.  As the author himself says in the preface to the book; 'This book attempts to present a readable account of some of the most important and basic topics of computer science, stressing the fundamental and robust nature of the science in a form that is virtually independent of the details of specific computers, languages and formalisms'.

User reviews

LibraryThing member danrk
The organization of this book is fantastic. It really breaks up the subject of computer science into functional parts that answer specific fundamental questions about computation. Read the table of contents and you'll see what I mean. The writing is also fairly concise, albeit worded awkwardly at times. I don't find the religious quotes distracting as other reviewers even though it's not important to me; they can be comical at times.… (more)

Language

Original language

English

Original publication date

1987

Physical description

437 p.; 23.1 cm

ISBN

0201192403 / 9780201192407

Local notes

Omslag: John Gibbs
Omslaget viser en sky og noget programtekst, der hænger sammen med et stort, måske uendeligt stort, puslespil
Indskannet omslag - N650U - 150 dpi
Page: 0.2857 seconds