| CS4124 Theory of Computation MWF 10:10--11:00 McBryde 216 | |
| Instructor: L. T. Watson, 630
McBryde,
231-7540,ltw@cs.vt.edu Office Hours: 11:00--12:00 MWF, and by appointment. Prerequisites: Math 3134 or Math 3034. |
 |
| Text: J. E. Savage, Models of Computation Addison-Wesley, 1998. | |
| Topics Covered: Logic circuits, Boolean function normal forms, prefix computations, arithmetic, circuit complexity, finite-state machines, random-access machines, Turing machines, simulation, pushdown automata, regular and context-free languages, models of computability, reducibility and insolvability, recursive function theory, parallel computation, space-time tradeoffs. | |
| Grading: FINAL GRADE will be the
average of two in-class exams (50%), a final examination (25%), and homework and class participation (25%). |
|
|
Final Exam: 07:45--9:45am Wednesday, December 13, 2000. |
|
| References: Clark and Cowell, Programs, Machines, and Computation, McGraw Hill, 1976. D. I. A. Cohen, Introduction to Computer Theory, 2nd Ed., Wiley, 1997. Davis, Sigal, and Weyuker, Computability, Complexity, and Languages, 2nd Ed., Academic Press, 1994. Denning, Dennis, Qualitz, Machines, Languages, and Computation, Prentice-Hall, 1978. Gill, Introduction to the Theory of Finite State Machines, McGraw-Hill, 1962. Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Kain, Automata Theory, Machines, and Languages, McGraw-Hill, 1972. Kfoury, Moll, Arbib, A Programming Approach to Computability, Springer-Verlag, 1982. Manna, Mathematical Theory of Computation, McGraw-Hill, 1974. McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967. B. M. Moret, The Theory of Computation, Addison-Wesley, 1998. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. R. G. Taylor, Models and Computation and Formal Languages, Oxford, 1998. |
|