Course Title : Theory of Algorithms

Code 90551
Course Year 3rd year
Term
Class day & Period
Location
Credits 2
Restriction No Restriction
Lecture Form(s) Lecture
Language Japanese
Instructor

Course Description

We introduce a computation model suitable for discussing both time and space complexities of algorithms and problems, then study basic ideas and issues of computational complecity theory.

Grading

Two reports and a final exam.

Course Goals

Course Topics

Theme Class number of times Description
review of language and automata theory 2
Turing machines 4 Basic properites of Turing machites including their computation power and several equivalent machines.
Decidability and Undecidability 3 The notion of decidability of problems and examples of undecidable problems.
Introduction of complexity theory 6 Decidable but intractable problems and NP-completeness. Discussion to check the achievements of students

Textbook

Iwama, Introduction to theory of algorithms, Shoko-do, 2001 .

Textbook(supplemental)

Prerequisite(s)

91040

Web Sites

Additional Information