Details

• Class Times
  • Tuesday/Thursday 10:00-11:20, 101 Volcanology
• Instructor: David Atkins
  • Office: Deschutes 358, phone 346-4413
  • Office Hours: Tuesday/Thursday 1:00 - 2:00 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, also 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
  • Alan Turing web site
  • Turing Machine Simulator
  • JFLAP - package for exploring automata
• Grading and Policy
  • Approximate weighting: Assignments 25%, Midterm 30%, Final 30%, Other 15% - "Other" will include quizzes and class participation
  • Students registered in 520 will have additional assignment problems and exam problems

Course Objectives

• 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.