計算機数学・講義内容と予定
秋学期3Q・月曜2時限＋木曜2時限・紀-503教室
講義概要
「この問題は計算機でも計算できないなぁ」
「君は実に…計算が下手なんだなぁ」
「そうじゃなくて計算できないことが証明できるんだよ」
「え？どゆこと？」
「計算」とは何か、「計算できるか／できないか」というような問いに対して、
数学では、「計算機が行なうこと」を「計算」と考え、
計算機が行なえることを「計算モデル」として定式化することによって
「計算」を定義し、明確に答えることを可能にしてきた。
本講義では、代表的な計算モデルを取り上げながら、
計算の理論・アルゴリズムの概念・計算量の理論の初歩を紹介し、
計算の可能性・効率について論ずると共に、
具体的な例として幾つかの基礎的な数理アルゴリズムについて触れる。
講義計画
計算の理論の入門として、計算モデルによる「計算」の定式化・
計算可能性の理論・計算量の理論の初歩を紹介し、
幾つかの基礎的な数理アルゴリズムについても触れる。
- 「計算」の定式化
- 計算のモデル化：有限オートマトン・プッシュダウンオートマトン・チューリング機械など
- 言語と文法：正規言語・生成文法・文脈自由言語など
- 計算可能性の理論の入門まで：普遍チューリング機械と対角線論法
- 計算量の理論の入門まで
- 基礎的な数理アルゴリズムの例
- ユークリッドの互除法
- 素数判定・素因数分解
- 並べ替え(ソーティング)
- 高速フーリエ変換
- などなど
主な参考書
- Micheal Sipser "Introduction to the Theory of Computation" (PWS Publishing Company, ISBN: 978-0534950972), 太田和夫・田中圭介・阿部正幸・植田広樹・藤岡淳・渡辺治（共訳）による和訳あり
- 「計算理論の基礎 [原著第2版] 1.オートマトンと言語」（共立出版・ISBN: 978-4320122079）
- 「計算理論の基礎 [原著第2版] 2.計算可能性の理論」（共立出版・ISBN: 978-4320122086）
- 「計算理論の基礎 [原著第2版] 3.複雑さの理論」（共立出版・ISBN: 978-4320122093）
近年出版された次の冒険小説も、本講義の受講者には楽しく読めるだろう。
- 川添愛「白と黒のとびら」（東京大学出版会・ISBN: 978-4130633574）
- 川添愛「精霊の箱（上・下）」（東京大学出版会・ISBN: 978-4130633635, 978-4130633642）
講義内容
準備中