Error: no such theme PatternSkinTheme

You are here: Foswiki>Faculty Web>CourseGoalsAndObjectives>CSC341:Automata,FormalLanguages,AndComputationalComplexity (2011-02-02, JohnDavidStone)EditAttach

- to develop an exact understanding of the powers and limitations of the kinds of automata that we discuss;
- to acquire facility in applying the proof techniques that we study and in recognizing cases in which it is appropriate to use them;
- more generally, to distinguish rigorous mathematical argumentation from casual presentation of a line of reasoning, and to write clearly and accurately in either mode;
- to recognize commonly encountered problems that are either insoluble or intractable and to be able to demonstrate their insolubility or intractability.

- the ability to determine whether certain formal languages are regular, context-free, or recursively enumerable, by applying relevant lemmas and theorems developed in the course, and to prove that one's determinations are correct;
- the ability to propose automata that accept certain formal languages, or grammars that generate them;
- the ability to transform and combine automata in certain specified ways, adapting them to the solution of different (but equally well-defined) problems;
- the ability to prove the equivalence of certain models of computation, by systematically correlating elements of the models and demonstrating that each step in a computation carried out under one model can be emulated by the other;
- the knowledge of certain properties of models of computation, specifically:
- the existence and construction of a universal Turing machine;
- the undecidability of the halting problem for Turing machines, and of certain problems that are reducible to that problem;
- the existence and construction of a Turing machine that prints out its own description, and of certain related machines that use their own descriptions for computational purposes;
- the uncomputability of minimal descriptions of Turing machines; and
- the undecidability of the arithmetic of natural numbers under addition and multiplication;

- the knowledge of the nature and composition of some complexity classes of problems, including
**P**and**NP**; and - the knowledge of the existence and structure of several
**NP**-complete problems, including*3SAT*(the satisfiability or unsatisfiability of Boolean formulas in conjunctive normal form having exactly three literals in each clause).

- mathematical induction, including course-of-values induction
- deterministic and nondeterministic finite automata;
- regular expressions and regular languages;
- context-free grammars;
- pushdown automata;
- deterministic and nondeterministic Turing machines;
- multitape Turing machines and other variations in Turing-machine design;
- cardinalities of infinite sets;
- diagonalization arguments;
- decidability;
- Turing reducibility;
- mapping reducibilty;
- the recursion theorem;
- the parameter theorem;
- definitions of computational complexity;
- the
**P**and**NP**complexity classes; -
**NP**-completeness; and - the Cook-Levin theorem.

- semi-Thue production systems;
- the Post correspondence problem;
- recursive function theory;
- oracle machines;
- information and compressibility;
- the
**PSPACE**complexity class; -
**PSPACE**-completeness; - the
**L**and**NL**complexity classes; - approximation algorithms;
- probabilistic algorithms; and
- cryptography.

Edit | Attach | Print version | History: r4 < r3 < r2 < r1 | Backlinks | View wiki text | Edit wiki text | More topic actions

Topic revision: r4 - 2011-02-02, JohnDavidStone

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding Foswiki? Send feedback

Ideas, requests, problems regarding Foswiki? Send feedback