Theory of Computation

A branch of computer science that deals with whether and how efficiently problems can be solved on a computer. It is divided into two major sub-branches: computability theory and complexity theory, but both sub-branches deal with formal models of computation.

All categories

Books under this sub-category (24 books)

Foundations of Computation, Second Edition

Post date: 28 Oct 2016
A free textbook for a one-semester course in theoretical computer science. It has been used for several years in a course at Hobart and William Smith Colleges. The course has no prerequisites other than introductory computer programming.
Publication date: 31 Dec 2011
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported
Document Type: Textbook
 
Foundations of Computation, Second Edition

Foundations of Computation, Second Edition

Post date: 28 Oct 2016
A free textbook for a one-semester course in theoretical computer science. It has been used for several years in a course at Hobart and William Smith Colleges. The course has no prerequisites other than introductory computer programming.
Publication date: 31 Dec 2011
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported Document Type: Textbook


Introduction to Complexity Theory

Post date: 02 Apr 2007
The notes are aimed at exposing the students to the basic results and research directions in the field of Complexity Theory. The focus was on concepts and ideas, and complex technical proofs were avoided.
Publication date: 31 Dec 1999
 
Introduction to Complexity Theory

Introduction to Complexity Theory

Post date: 02 Apr 2007
The notes are aimed at exposing the students to the basic results and research directions in the field of Complexity Theory. The focus was on concepts and ideas, and complex technical proofs were avoided.
Publication date: 31 Dec 1999


Introduction to Computational Complexity

Post date: 15 Feb 2007
Adopts some unconventional approaches, in which alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases, in order to simplify many proofs.
Publication date: 31 Dec 1991
 
Introduction to Computational Complexity

Introduction to Computational Complexity

Post date: 15 Feb 2007
Adopts some unconventional approaches, in which alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases, in order to simplify many proofs.
Publication date: 31 Dec 1991


Lecture Notes on Algorithm Analysis and Computational Complexity (4th Edition)

Post date: 22 Feb 2005
Tranparency materials used in Algorithm Analysis and Complexity Theory course at the University of North Texas.
Publication date: 30 Nov -0001
 
Lecture Notes on Algorithm Analysis and Computational Complexity (4th Edition)

Lecture Notes on Algorithm Analysis and Computational Complexity (4th Edition)

Post date: 22 Feb 2005
Tranparency materials used in Algorithm Analysis and Complexity Theory course at the University of North Texas.
Publication date: 30 Nov -0001


Lecture Notes on Approximation Algorithms

Post date: 25 Feb 2007
Attempt to classify all hard optimization problems as one of the possibilities for relaxing the requirements, from the point of view of approximability: easy, intermediate and hard.
Publication date: 31 Dec 1992
 
Lecture Notes on Approximation Algorithms

Lecture Notes on Approximation Algorithms

Post date: 25 Feb 2007
Attempt to classify all hard optimization problems as one of the possibilities for relaxing the requirements, from the point of view of approximability: easy, intermediate and hard.
Publication date: 31 Dec 1992


Models of Computation Exploring the Power of Computing

Post date: 10 May 2016
This book re-examines theoretical computer science, offering a fresh approach that gives priority to resource tradeoffs and complexity classifications over the structure of machines and their relationships to languages.
 
Models of Computation Exploring the Power of Computing

Models of Computation Exploring the Power of Computing

Post date: 10 May 2016
This book re-examines theoretical computer science, offering a fresh approach that gives priority to resource tradeoffs and complexity classifications over the structure of machines and their relationships to languages.

Parallel Complexity Theory

Post date: 22 Feb 2005
The study of resource-bounded aimed at advanced graduate students or researchers in theoretical Computer Science.
Publication date: 30 Nov -0001
 
Parallel Complexity Theory

Parallel Complexity Theory

Post date: 22 Feb 2005
The study of resource-bounded aimed at advanced graduate students or researchers in theoretical Computer Science.
Publication date: 30 Nov -0001


The Complexity of Boolean Functions

Post date: 26 Jul 2006
Presents a large number of research results on the complexity of Boolean functions in non-uniform computation models. It has a direct relevance to practical problems in the computer aided design of digital circuits.
Publisher: John Wiley & Sons
Publication date: 01 Jan 1991
 
The Complexity of Boolean Functions

The Complexity of Boolean Functions

Post date: 26 Jul 2006
Presents a large number of research results on the complexity of Boolean functions in non-uniform computation models. It has a direct relevance to practical problems in the computer aided design of digital circuits.
Publisher: John Wiley & Sons
Publication date: 01 Jan 1991


The Design of Approximation Algorithms

Post date: 16 Mar 2011
This book is designed to be a textbook for graduate-level courses in approximation algorithms. It assumes familiarity with algorithms, mathematical proofs about the correctness of algorithms, probability theory and NP-completeness.
Publisher: Cambridge University Press
Publication date: 26 Apr 2011
 
The Design of Approximation Algorithms

The Design of Approximation Algorithms

Post date: 16 Mar 2011
This book is designed to be a textbook for graduate-level courses in approximation algorithms. It assumes familiarity with algorithms, mathematical proofs about the correctness of algorithms, probability theory and NP-completeness.
Publisher: Cambridge University Press
Publication date: 26 Apr 2011


Book Categories
Sponsors
Icons8, a free icon pack