Automata, Computability, and Complexity

Automata, Computability, and Complexity

Course Number
CIS 2620 910
Course Code
CIS2620910
Course Key
79261
Day(s)
Friday
Monday
Wednesday
Time
12:00pm-2:30pm
12:00pm-2:30pm
12:00pm-2:30pm
Instructor
Course 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). The topics covered include finite automata and regular languages, context-free languages, Turing machines, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness.