Server: Netscape-Communications/1.1 Date: Wednesday, 20-Nov-96 23:24:19 GMT Last-modified: Friday, 30-Aug-96 20:11:20 GMT Content-length: 5025 Content-type: text/html CIS 511 Handout 1

CIS 511, Summer 1, 96

Introduction to the Theory of Computation
Course Information
May 17

Coordinates:

Moore 223, 2:00-5:00

Instructor:

Jean H. Gallier, MRE 176, 8-4405, jean@saul

Office Hours:

11:00-noon Monday, Wednesday, 11:00-noon, Tuesday

Teaching Assistant:

Shiann-Liang Chern, slchern@saul.cis.upenn.edu

Office Hours:

Tuesday-Thursday, 2:00-4:00

Newsgroup:

upenn.cis.cis511

Textbook (required):

Introduction to Automata Theory, Languages and Computation , J.E. Hopcroft and J.D. Ullman, Addison Wesley

Also recommended:

Theory of Computation, D. Wood, Wiley

Grades: homework assignments and take home final

Problem Sets (3 of them)

Some Course Notes

Brief description:

The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) computability and recursive function theory; (3) complexity theory. The course will focus mostly on (1) and (2). Applications of (1) to programming (and natural) language specification and parsing (top-down and bottom-up parsing), will be emphasized.

Topics will include:

published by:

Jean Gallier