Introduction to the Theory of Computation |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
References: (Japanese Version Available in the Hibikino library) Sipser, Michael, Introduction to the Theory of Computation (2nd edition)「計算理論の基礎」, Thomson Course Technology. J. Matousek and J. Nesetril, Invitation to Descrete Mathematics 「離散数学への招待」, Springer 2002. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecture Time: Wednesday: 16:30-18:00 「水曜日 第５時限 16：30ー18：00」 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Office Hours: Tuesday (15:30 ~ 17:00)「火曜日 15：30－17：00」, or send your questions to me. (chensong@aoni.waseda.jp) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Place「場所」: N318 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Note: The notes are downloadable inside the campus (ダウンロードすることは学内のみ). | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecture | Date | Topic | Availabe | Due | 1 | April 11 | Guidance and Introduction 「案内と序論」 | ppt pdf | 2 | April 18 | Set 「集合」 | ppt pdf solution | 3 | April 25 | Counting 「数え上げ」 | ppt pdf solution | May 2 | No Lecture | 4 | May 9 | Recurrence Relation I 「漸化式Ｉ」 | ppt pdf | 5 | May 16 | Recurrence Relation II 「漸化式ＩＩ」 | ppt pdf Proof.of.Master.Theorem HowToMultiply ProblemSet01(doc) ProblemSet01-Solution | 6 | May 23 | Finite Automat and Regular Language 「有限オートマトン＆正規言語」I | ppt pdf solution | 7 | May 30 | Finite Automat and Regular Language 「有限オートマトン＆正規言語」II | ppt pdf solution | 8 | June 6 | Turing Machine and Algorithms 「Turing 機械とアルゴリズム」 | ppt pdf solution | 9 | June 13 | Decidability： Halting problem 「判定可能性：停止問題」 | ppt pdf solution | 10 | June 20 | Reducibility 「帰着可能性」 | ppt pdf ProblemSet02 ProblemSet02-Solution | 11 | June 27 | Time Complexity: P Class and NP Class 「時間複雑さ：ＰとＮＰ」 | ppt pdf | 12 | July 4 | Polynomial Time Reducibility and NP-Completeness 「多項式時間帰着可能性とＮＰ－完全性」 | ppt pdf | 13 | July 11 | Proving NP-Completeness 「ＮＰ－完全性の証明」 | ppt pdf ProblemSet03 | 14 | July 18 | NP-Hardness 「ＮＰ－困難性」 | ppt pdf | 15 | July 25 | 理解度の確認 | ppt pdf Reading |