CmpE 415 - Theory of Computation

Fall Semester 2009  

  Announcements

·         Note the slight change in the midterm results as a result of objections.

·         The results of the first midterm are:

OSMAN 

CELEP 

 

SAİD TAHSİN 

DANE 

69

METİN 

ESER 

25

MUSTAFA ERAY 

KOÇAK 

97

MEHMET MURAT 

SEVİM 

 

MAX- FREDERIC 

WEULE 

 

ERTAN 

YAVUZ 

 

GÖKHAN REMZİ 

YAVUZ 

60

EMRE 

YILMAZ 

85

·         The extra lecture hour will be held right after our Friday lecture (October 9) this week, in the room currently announced in the Schedule.

·         The midterm dates are announced below.

·         Our lectures on Friday will be held at 13:00 from now on. (We'll discuss when to hold the single extra hour that we missed on Oct. 2 when we meet on Oct. 7.)

·         The “F2” lecture hour will be changed. We will hold an extra lecture hour to compensate for the one we missed today (October 2). See you on Wednesday.

·         New announcements will be added to the top as they arrive. Please follow this announcements page frequently.

Catalog Data:

Basic concepts of computation. The theory and representation of algorithms and models of computation. Computability and recursive functions. Formal specification and proofs of programs. Automata theory.

Textbook:

Michael Sipser. Introduction to the theory of Computation, 2nd ed.

Instructor:

Cem Say

 

 

 

Prerequisite:

CMPE220 , CmpE 350

Topics (subject to change):

1. The Church-Turing Thesis
2. Decidability
3. Reducibility
4. Advanced Topics in Computability Theory
5. Complexity Theory

Exams:

Computer Usage:

None

Laboratory projects:

None.

 Mathematics:

A lot of proofs and hard work.