Tony Shaska

Tony Shaska

Associate Professor
Department of Mathematics and Statistics
Oakland University
146 Library Drive
Rochester, MI. 48309

Office: 546 Mathematics Science Center
E-mail: shaska[at]oakland.edu


APM 5881: Theory of Computation

Description

A study of what kinds of computation can, in principle, be accomplished by what kinds of computing devices, and how efficiently such computations can be done. Finite automata, pushdown automata, Turing machines, languages, grammars, undecidability, complexity theory, intractability.

Prerequisites

Required background: a course in discrete mathematics.

Textbook

  • John Martin, Introduction to languages and the theory of computation (third addition)
  • Course policies

    For all the problems and concerns you might have you must talk to me. No makeups will be given other then in case of documented emergencies. Cellular phones or any electronic equipment is NOT allowed during lecture. No calculators of any kind are allowed. Further, I do not tolerate any kind of academic dishonesty. Appropriate measures according to Oakland University regulations will be take for any case of cheating or breaking other rules. Attendance is mandatory!

    Detailed Syllabus

    Software that will be used

    Other readings

  • Separating words by automata
  • Godel's lost letter and P=NP