This note covers the following topics: Sets,
functions and other preliminaries, Formal Languages, Finite Automata ,
Regular Expressions, Turing Machines, Context-Free Languages, Rice's Theorem,
Time complexity, NP-Completeness, Space Complexity , Log Space, Oracle
machines and Turing Reducibility, Probabilistic Complexity, Approximation and
Optimisation, Complexity Hierarchy Theorems.
These
are lecture notes from the University of Toronto, giving a very brief
introduction to some of the basic ideas in the theory of computation. We start
with some basic topics: induction and recursion; the correctness of programs,
that must be understood if more advanced computational theories are to be
enlightened. Then we go on to develop the topics of regular languages and finite
automata, giving the basic models and techniques used in analysing and
recognising regular languages. The coverage is designed to provide students with
a reasonably solid grounding in the basic ideas of the theory of computation and
to render a clear and thorough exposition of the fundamental concepts underlying
more advanced topics.
Introduction
to the Theory of Computing is a course that undertakes
an intensive study of the underpinnings of the theory of computation. Beginning
with mathematical foundations, the course moves into regular operations and
expressions, and then into proofs on languages being nonregular and other
further treatments on regular languages. Other important topics include parse
trees, ambiguity, Chomsky normal form, pushdown automata, and Turing machines.
Further, the PDF discusses various types of Turing machines, the stack machine
model, and undecidable languages, making it a great starting point in the topic
of computability.
This
book surveys some of the most relevant theoretical concepts with computational
models. The limits of computation, undecidability of the Halting Problem,
several automata models, including both deterministic and nondeterministic
finite-state automata, pushdown automata, and Turing machines, are introduced.
The ending is dedicated to computational complexity, with NP-Completeness,
approximation algorithms, and hardness of approximation.
This book, written for graduates, covers
general subjects on computational models, logic circuits, and memory machines,
with advanced subjects being parallel computation, circuit complexity, and
space-time trade-offs; therefore, it's a very thorough course on computational
models and their complexities.
These
lecture notes give an introduction to the more fundamental parts of the theory
of computation and begin by presenting finite automata: starting with
deterministic and nondeterministic finite automata, their equivalence, and
practical implications of these concepts. The lecture notes include sections
on regular expressions and their relationship to finite automata, non-regular
languages, and the Pumping Lemma to prove non-regularity. Myhill-Nerode
Theorem: For understanding recognition of languages. The notes go further to
present context-free languages, including their ambiguity and properties of
closure. The pumping lemma for context-free languages is also discussed, while
decidable and recognizable languages are informed by a deep underpinning in
computational theory.
This
is an advanced set of notes on the analysis of algorithms and their
complexity. Of interest in these notes are the topics on string matching
algorithms, such as Knuth-Morris-Pratt and Boyer-Moore. Suffix trees and
dictionary techniques are also part of the discussion here. Among the methods
to be shown in a way of analyzing algorithm efficiency are amortized analysis
and randomized algorithms. It also treats the pairing technique, Ziv-Lempel
coding; further topics on statistical adversaries, portfolio selection, and
reservation-price policies that are objects of other techniques discussed
herein.