|
Schedule of Topics
Class Information:
Textbook
Online resources
Our email addresses
Problem sessions
Grading
Evening exams
Website for
the book
Errata for
the book
Exams
Academic Integrity
|
|
Course Description
In this class, we will develop a single framework in which
all kinds of computational problems can be defined and analysed. The
framework is based on the idea of a language, and problems are defined as the
task of determining whether an input string is a member of some particular
language. Thus this area is often called formal language theory.
But a key idea is that all problems can be described as language
recognition tasks so this framework shouldn't be thought of as limiting.
Instead think of it as a simple mechanism by which problems that may
initially appear very different can be compared and analyzed to see whether
there can exist computational solutions to them at all, and, if there can,
what power those solutions must possess. We will discuss computational
models ranging from very simple (finite state machines) to pushdown automata
(with the power to recognize context free languages, including standard
programming languages) to Turing Machines, which are powerful enough to solve
any problem for which a solution exists, yet simple enough to describe that
we can prove theorems about what they can and cannot do.
Texts
I have written a text book for this class, Automata, Computability and Complexity:
Theory and Applications.
Prentice-Hall, 2008. It
should be available at the Coop or online from Amazon or Barnes and Noble.
There is a website that
goes along with the book. It is organized
into pages that correspond to the chapters of the book. On those pages, you will find links to
many other useful sites.
If you would like another book as a supplementary text, I recommend Introduction
to the Theory of Computation, Michael Sipser. Brooks/Cole, 1996.
Contact Information
Elaine Rich - ear@cs.utexas.edu
|