Home > Store > Programming > Algorithms

Elements of the Theory of Computation, 2nd Edition

Register your product to gain access to bonus material or receive a coupon.

Elements of the Theory of Computation, 2nd Edition

Book

  • Your Price: $155.89
  • List Price: $183.40
  • Usually ships in 24 hours.

About

Features

  • Offers a mathematically sound introduction to the classical and contemporary theory of computation, and provide deep insights into the fundamental paradigms of computer science.

Would you like a theory of computation text that provides a solid, specialized introduction to algorithms?

  • Informally introduces algorithms, complexity analysis, and algorithmic ideas in Ch. 1 (in connection to transitive and other closures), and explores them throughout the book.
    • Introduces asymptotic analysis and O- notation.

  • Features a more “student-friendly” approach.
    • Truncates long proofs and presents them as exercises.

    • Provides problems after each section to check student comprehension.

  • Considers automata in the context of their applications.
    • Includes extensive discussion of state minimization, the Myhill-Nerode Theorem, string matching, and parsing.

  • Complexity starts with a proof that P = EXP.
    • Many combinatorial problems are introduced and analyzed (including variants of satisfiability), and their apparent complexity contrasted.

Would you like to teach NP—completeness, as well as ways of coping with it, in your course?

  • Features a separate chapter on NP-completeness.
    • Extensive section on coping with NP - completeness that covers special cases, approximation algorithms, backtracking, and local search heuristics.

    • Covers NP - completeness including state minimization problem of nondeterministic finite automata.

    • Logic coverage has been limited to propositional logic in relation to NP - completeness.

    • Considers Cook's Theorem again via the tiling problem.

    • Discusses approximation and its complexity.

  • Introduces the Turing machine notation more informally.
    • Uses the terms recursive and recursively innumerably.

    • Quantitatively analyzes simulations between machine models.

    • Introduces and analyzes a model of random access Turing machines, similar to RAMs.

  • Offers a more succinct treatment of general grammars and …¿¿-recursive functions.
    • Uses random access Turing machines to bridge the “credibility gap” between Turing machine model and the empirical concept of an algorithm.

    • Includes some recursion theory (up to Rice's theorem).

    • Provides an informal, concise development of A-recursive functions.

  • Explores Chomsky normal form and the resulting dynamic programming algorithm.

Description

  • Copyright 1998
  • Dimensions: 7" x 9-1/4"
  • Pages: 361
  • Edition: 2nd
  • Book
  • ISBN-10: 0-13-262478-8
  • ISBN-13: 978-0-13-262478-7

Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. KEY TOPICS: In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems.

Sample Content

Table of Contents



1. Sets, Relations, and Languages.


2. Finite Automata.


3. Context-free Languages.


4. Turing Machines.


5. Undecidability.


6. Computational Complexity.


7. NP-completeness.


Index.

Updates

New To This Edition

Would you like a theory of computation text that provides a solid, specialized introduction to algorithms?

  • NEWInformally introduces algorithms, complexity analysis, and algorithmic ideas in Ch. 1 (in connection to transitive and other closures), and explores them throughout the book.
    • Introduces asymptotic analysis and O- notation.
  • NEW—Features a more “student-friendly” approach.
    • Truncates long proofs and presents them as exercises.
    • Provides problems after each section to check student comprehension.
  • NEW—Considers automata in the context of their applications.
    • Includes extensive discussion of state minimization, the Myhill-Nerode Theorem, string matching, and parsing.
  • NEWComplexity starts with a proof that P = EXP.
    • Many combinatorial problems are introduced and analyzed (including variants of satisfiability), and their apparent complexity contrasted.

Would you like to teach NP—completeness, as well as ways of coping with it, in your course?

  • NEW—Features a separate chapter on NP-completeness.
    • Extensive section on coping with NP - completeness that covers special cases, approximation algorithms, backtracking, and local search heuristics.
    • Covers NP - completeness including state minimization problem of nondeterministic finite automata.
    • Logic coverage has been limited to propositional logic in relation to NP - completeness.
    • Considers Cook's Theorem again via the tiling problem.
    • Discusses approximation and its complexity.
  • NEW—Introduces the Turing machine notation more informally.
    • Uses the terms recursive and recursively innumerably.
    • Quantitatively analyzes simulations between machine models.
    • Introduces and analyzes a model of random access Turing machines, similar to RAMs.
  • NEW—Offers a more succinct treatment of general grammars and …m-recursive functions.
    • Uses random access Turing machines to bridge the “credibility gap” between Turing machine model and the empirical concept of an algorithm.
    • Includes some recursion theory (up to Rice's theorem).
    • Provides an informal, concise development of A-recursive functions.
  • NEW—Explores Chomsky normal form and the resulting dynamic programming algorithm.

Submit Errata

More Information

Unlimited one-month access with your purchase
Free Safari Membership