• Title: Computability and Complexity: From a Programming Perspective
• Author(s) Neil Deaton Jones
• Publisher: The MIT Press (January 15, 1997); eBook (Revised version, 2007)
• Hardcover: 466 pages
• eBook: PDF (487 pages, 1.7 MB)
• Language: English
• ISBN-10: 0262100649
• ISBN-13: 978-0262100649
• Share This:  

Book Description

This book is an introduction to the basic concepts of computability, complex, and the theory of programming languages.

This book has two very clear and distinct aims: to present the theory of computability and complexity in a different didactic way, namely as motivated by programming; and to modify notions of complexity theory so that they are more natural. As to the first aim, there is not really much literature in this direction.

This places the text in the category 'highly welcome textbook for computer science students.' The second aim places this text in the category 'research monograph.' Since both parts of the book are presented well, I strongly recommend it. either section alone would be a substantial contribution.

Computability and complexity theory should be of central concern to practitioners as well as theorists. Unfortunately, however, the field is known for its impenetrability. Neil Jones's goal as an educator and author is to build a bridge between computability and complexity theory and other areas of computer science, especially programming.

In a shift away from the Turing machine- and Godel number-oriented classical approaches, Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists and more applicable to practical programming problems.

• Neil D. Jones is Professor of Computer Science at the University of Copenhagen.

• Amazon

• Computational Complexity
• Computer Programming
• Algorithms and Data Structures
• Computational and Algorithmic Mathematics
• Parallel Computing and Programming

• Computability and Complexity: From a Programming Perspective (Neil Deaton Jones)
• The Mirror Site (1) - PDF
• Book Homepage (PDF Files, etc.)

• Mathematics and Computation (Avi Wigderson)

  This book provides a broad, conceptual overview of computational complexity theory - the mathematical study of efficient computation. With important practical applications to computer science and industry, computational complexity theory, etc.

• Think Complexity: Science and Modeling, 2nd Ed. (Allen Downey)

  This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. It presents features that make Python such a simple and powerful language. Code with a solution for each exercise.

• Complexity Theory: A Modern Approach (Sanjeev Arora, et al)

  This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation.

• Quantum Computing Since Democritus (Scott Aaronson)

  This book takes readers on a tour through some of the deepest ideas of maths, computer science and physics. Full of insights, arguments and philosophical perspectives, the book covers an amazing array of topics.

• Traveling Salesman Problem, Theory and Applications

  This book is a collection of current research in the application of evolutionary algorithms and other optimal algorithms to solving the TSP problem, including Artificial Immune Systems, Genetic Algorithms, Neural Networks and Differential Evolution Algorithm.

• The Complexity of Boolean Functions (Ingo Wegener)

  Initially deals with the wee-known computation models, and goes on to special types of circuits, parallel computers, and branching programs. It presents a large number of recent research results f Boolean functions previously unavailable in book form.

• Computational Complexity (Wikibooks)

  This book contains material that should be core knowledge in the theory of computation for all graduates in computer science. It starts with classical computability theory which forms the basis for complexity theory.

• Computational Complexity: A Conceptual Perspective (Goldreich)

  This book offers a conceptual introduction to the study of the intrinsic complexity of computational tasks. It is intended to serve advanced undergraduate and graduate students, either as a textbook or for self-study.

• Algorithms and Complexity (Herbert S. Wilf)

  This is an introductory book on the design and analysis of algorithms. The author uses a careful selection of a few topics to illustrate the tools for algorithm analysis.