|
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 analyzed. 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.
In this
class, you will:
- Acquire a set of useful
computational tools, including finite state machines, context-free
grammars, and a way to identify undecidable problems,
- Develop your intuitions about
when to use each of those tools as you design and implement real applications,
- Hone your skill at reading and
writing formal logical descriptions of computational properties, and
- Become proficient at creating formal
proofs of claims about problems and programs.
This class is an honors
version of the standard CS341 class. The structure will be very similar to
that class. But we will cover more material and we will cover material in
greater depth. I will expect students to do more proofs.
If you are
a Turing Scholar, you will be able to register for this class. If you are not
a Turing Scholar and you want to take this class, please send me a copy of
your transcript, along with a note about why you want to take the class.
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
|