

This section contains free ebooks and guides on Computation Theory, some of the resources in this section can be viewed online and some of them can be downloaded.




Theory of Computation Lecture NotesMichael LevetPDF  114 Pages  EnglishThis note covers the
following topics: Mathematical Perliminaries, Automata Theory, Combinatorics
and Graph Theory, DFAs to Regular Expressions Brzozowski’s Algebraic Method,
MyhillNerode and DFA Minimization, Group Theory, Turing Machines and
Computability Theory, Complexity Theory.
 Introduction to the Theory of ComputationProf. Sofya RaskhodnikovaOnline  NA Pages  EnglishThis note
explains the following topics: Automata and Language Theory, Finite automata,
regular expressions, pushdown automata, contextfree grammars, pumping
lemmas, Computability Theory, Turing machines, ChurchTuring thesis,
decidability, halting problem, reducibility, recursion theorem, Complexity
Theory, Time and space measures, hierarchy theorems, complexity classes P, NP,
PSPACE, complete problems, P versus NP conjecture, quantifiers and games,
provably hard problems, probabilistic computation.
 Notes on Computation TheoryKonrad SlindPDF  231 Pages  EnglishThis course is an introduction to
the Theory of Computation. Topics covered includes: Background Mathematics,
Models of Computation, ContextFree Grammars, Automata, The Chomsky
Hierarchy.
 Notes on Computational Complexity TheoryJames AspnesPDF  180 Pages  EnglishThis note provides
an introduction to the theory of computational complexity. Topics covered
includes: Models of computation, Time and space complexity classes,
Nonterminism and NP, Diagonalization, Oracles and relativization, Alternation,
Space complexity, Natural proofs, Randomized classes, Counting classes,
Descriptive complexity and Interactive proofs.
 Introduction to theory of computation by Tom CarterTom
CarterPDF  76 Pages  EnglishThis note explains the following topics: Symbols, strings and
languages, Finite automata, Regular expressions and languages, Markov models,
Context free languages, Language recognizers and generators, The Chomsky
hierarchy, Turing machines, Computability and actability, Computational
complexity.
 The Theory of Languages and ComputationJean Gallier and Andrew HicksPDF  109 Pages  EnglishThis note
covers the following topics: Automata, Set Theory, The Natural numbers and
Induction, Foundations of Language Theory, Operations on Languages,
Deterministic Finite Automata, Formal Languages, Computability, Computations
of Turing Machines, The Primitive Recursive Functions, The Partial Recursive
Functions, DNA Computing, Analog Computing and Scientific Computing.
 Introduction to Theory of ComputationAnil
Maheshwari and ichiel SmidPDF  246 Pages  EnglishThis is a free textbook for an undergraduate course
on the Theory of Computation, which have been teaching at Carleton University
since 2002.Topics covered includes: Finite Automata and Regular Languages,
ContextFree Languages, Turing Machines and the ChurchTuring Thesis,
Decidable and Undecidable Languages and Complexity Theory.
 Theory of Computation by S. Arun KumarS. Arun KumarPDF  83 Pages  EnglishThis book covers the
following topics: The RAM Model, The Primitive Recursive Functions, The
Partial Recursive Functions, Coding and Godelization, The Hierarchy of
Primitive Recursive Functions, Universality and Parametrisation, The typefree
lambda calculus.
 Theory of ComputationDr.
Gabriel RobinsOnline  NA Pages  EnglishThis note covers the following topics: A brief history of
computing, Fundamentals, Formal languages and machine models, Computability
and undecidability, NPcompleteness, Generalized number systems and
Cryptography mental poker.
 Great Ideas in Theoretical Computer Science Lecture NotesProf. Scott
AaronsonOnline  NA Pages  EnglishThis course note provides a challenging introduction to some of the
central ideas of theoretical computer science. It attempts to present a vision
of computer science beyond computers: that is, CS as a set of mathematical
tools for understanding complex systems such as universes and minds.
 Introduction to Theoretical Computer Science or Theory of ComputationPavan
Kumar Anumula, Andrea Di Fabio and Jia Zhu Online  NA Pages  EnglishThis note covers the following
topics: introduction to theoretical computer science, language, regular
language, finite automata, language accepted by dfa, nondeterministic finite
automata, equivalence of nfa, regular language and fa, application of fa,
nonregular languages, context free languages, turing machines, computability
and complexity.
 Computation Theory Lecture notesProf Anuj DawarOnline  93 Pages  EnglishThe aim of this course note
is to introduce several apparently different formalisations of the informal
notion of algorithm; to show that they are equivalent; and to use them to
demonstrate that there are incomputable functions and algorithmically
undecidable problems.
 ConstructiveComputation TheoryGerard HuetOnline  NA Pages  EnglishThis is an executable course note
implemented in Pidgin ML, which is a core subset of the Objective Caml
programming language under the socalled revised syntax.
 A Computational Introduction to Number Theory and Algebra (V. Shoup)Victor
ShoupOnline  NA Pages  EnglishThis book introduces the basic concepts from computational number theory
and algebra, including all the necessary mathematical background. Covered topics
are: Basic properties of the integers, Congruences, Computing with large
integers, Euclid’s algorithm, The distribution of primes, Abelian groups, Rings,
Finite and discrete probability distributions, Probabilistic algorithms,
Probabilistic primality testing, Finding generators and discrete logarithms in
Zp, Quadratic reciprocity and computing modular square roots, Modules and vector
spaces, Matrices, Subexponentialtime discrete logarithms and factoring,
Polynomial arithmetic and applications.









