CIS 420/520 Automata Theory, Fall 2006
CRN 13247/13260
[
Details |
Objectives |
Schedule |
Assignments
]
Last updated 2006/11/16 08:29:14
- Class Times
-
Instructor: David Atkins
- Office: Deschutes 358, phone 346-4413
- Office Hours: MWF 3:30 - 4:30 and by appointment
- Email:
datkins@uoregon.edu
- Reference Material
- Required Text:
Introduction to the Theory of Computation, Second Edition, by Michael Sipser, Thomson Course Technology, 2005.
[Available at the bookstore, first edition on reserve in the Science Library]
- Other Texts:
An Introduction to Formal Languages and Automata, by P. Linz, Jones & Bartlett, 2006.
Introduction to Automata Theory, Languages, and Computing, by J. Hopcroft, R. Motwani, J.Ullman, Addison Wesley, 2001.
Elements of the Theory of Computation, by H. Lewis and C. Papadimitriou, Prentice Hall, 1998.
Languages and Machines, by Thomas Sudkamp, Addison Wesley, 2005.
Theory of Computing - A Gentle Introduction, by E. Kinber and C. Smith, Prentice Hall, 2001.
- Interesting links
- Grading and Policy
- Approximate weighting: Assignments 20%, Midterm 30%, Final 35%, Other 15% - "Other" will include
quizzes and class participation
- Students registered in 520 will have additional assignment problems and exam problems
- This course will introduce you to the theoretical basis of computation.
In a sense, we will see the origin of the computer as we know it today.
We will see mathematical models for computing and how they can be formally
described and reasoned about. We will cover the basic models of state
machines and Turing machines and see the differences in computational
power and how the concept of computing relates to formal languages.
We will discuss deterministic and nondeterministic models of machines
and how these compare to each other. We will see how the computers and
programming we take for granted came from formal reasoning about what
computation really is, and understand what computers can and cannot do.
We will see Alan Turing's fundamental contributions to computer science.
This course provides the basis for more advanced reasoning
about algorithms and complexity.
-
Have fun gaining an appreciation for what makes computing tick.
Last updated 2006/11/16 08:29:14