Introduction to Computational Theory Lecture Notes

Theory of Computation by Jim Hefferon

This PDF covers the following topics related to Theory of Computation : Mechanical Computation, Background, Languages and graphs, Automata, Computational Complexity.

Author(s): Jim Hefferon

439 Pages

Models of Computation by John E. Savage

This PDF Models of Computation by John E. Savage covers the following topics related to Computation Theory : The Role of Theory in Computer Science, General Computational Models, Logic Circuits, Machines with Memory, Finite-State Machines and Pushdown Automata, Computability, Algebraic and Combinatorial Circuits, Parallel Computation, Computational Complexity, Complexity Classes, Circuit Complexity, Space–Time Tradeoffs, Memory-Hierarchy Tradeoffs, VLSI Models of Computation.

Author(s): John E. Savage, Brown University

698 Pages

Lecture Notes Theory of Computation

This note covers the following topics: Properties of binary operations, Concantenation properties, Finite automata, Formal Languages, Pumping Lemma.

Author(s): S R Engineering College

155 Pages

Introduction to Computational Theory Lecture Notes

This note covers the following topics: Languages, Finite Automata, Regular Languages and Sets, Context-Free Grammars, Pushdown Automata and Context-Free Languages, Turing Machines, The Chomsky Hierarchy, P and NP.

Author(s): BYU Computer Science Department

NA Pages

Theory of Computation Tutorials

This note explains the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include: regular and context-free languages, finite automata and pushdown automata, Turing machines, Church's thesis, computability - halting problem, solvable and unsolvable problems, space and time complexity, classes P, NP and PSPACE, NP-Completenes.

Author(s): The Australian National University, Canberra

NA Pages

Notes on Computation Theory

This course is an introduction to the Theory of Computation. Topics covered includes: Background Mathematics, Models of Computation, Context-Free Grammars, Automata, The Chomsky Hierarchy.

Author(s): Konrad Slind

231 Pages

Notes on Computational Complexity Theory

This 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.

Author(s): James Aspnes

180 Pages

Theory of Computation by S. Arun Kumar

This 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 type-free lambda calculus.

Author(s): S. Arun Kumar

83 Pages

Great Ideas in Theoretical Computer Science Lecture Notes

This 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.

Author(s): Prof. Scott Aaronson

NA Pages

A Computational Introduction to Number Theory and Algebra (V. Shoup)

This 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, Subexponential-time discrete logarithms and factoring, Polynomial arithmetic and applications.

Author(s): Victor Shoup

NA Pages