Theory of Computation by Kyle Burke
This pdf begins with an overview of resources, organization and motivation and preview of CS theory covering the Limits of Computation, the Undecidability of the Halting Problem.The Automata and Machines including Deterministic and Nondeterministic Finite-state Automata, Pushdown Automata, and Turing Machines and Language Classes. Finally focus shifts to Computational Complexity, discussing NP-Completeness, Approximation Algorithms, and the Hardness of Approximation.
Author(s): Kyle Burke
114 Pages
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
Introduction to Theory of Computation by Wikiversity
This note describes the following topics: Finite State Machines, Closure and Nondeterminism, The Pumping Lemma, Minimizing FSMs, Context Free Languages, CFLs and compilers, Recitation, Pushdown Machines, CFGs and NPDMs, CYK algorithm, Undecidability and CFLs, Turing Machines, Halting Problem, Decidability, Complexity Theory, Quantified Boolean Formula, Savitch's Theorem, Space Hierarchy, Recursion Theorem.
Author(s): Wikiversity
NA 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
Advanced Theory in Computation
This note covers the following topics: Analysis of Algorithms, String Matching, Amortized Analysis, Knuth-Morris-Pratt Algorithm, Pattern-Matching Machine, Boyer-Moore Algorithm, Horspool Algorithm, Suffix Trees, Dictionary Techniques, Ziv-Lempel Coding, Randomized Algorithms, Reservation-Price-Policy, Portfolio Selection, Statistical Adversaries.
Author(s): Seoul National University
NA Pages
Theory of Computation Lecture Notes
This note covers the following topics: Mathematical Perliminaries, Automata Theory, Combinatorics and Graph Theory, DFAs to Regular Expressions- Brzozowski’s Algebraic Method, Myhill-Nerode and DFA Minimization, Group Theory, Turing Machines and Computability Theory, Complexity Theory.
Author(s): Michael Levet
114 Pages
This note covers the following topics: A brief history of computing, Fundamentals, Formal languages and machine models, Computability and undecidability, NP-completeness, Generalized number systems and Cryptography mental poker.
Author(s): Dr. Gabriel Robins
NA Pages
Introduction to Theoretical Computer Science or Theory of Computation
This 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.
Author(s): Pavan Kumar Anumula, Andrea Di Fabio and Jia Zhu
NA Pages
ConstructiveComputation Theory
This is an executable course note implemented in Pidgin ML, which is a core subset of the Objective Caml programming language under the so-called revised syntax.
Author(s): Gerard Huet
NA Pages
