計算機数学・講義内容と予定
春学期・月曜2時限・2-B212教室6-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）
事前準備など
- 講義資料提示・課題提出はmoodleコースを通じて行なうので、
履修登録後にLoyola授業掲示板に掲示される情報により、
本授業のmoodleコースに登録のこと。
- 初回の授業に先立ち、
moodleコースに掲載した動画「導入と概観」（全4編・計約23分）を視聴のこと。
（2020年度に作成したものなので、冒頭で「2020年度春学期」と表示されるが、
今年度も動画内容に変更ないので、気にしないこと。）
- オンラインでの受講が認められた受講生がいる場合や、
状況の変化により全学的にオンライン授業に移行した場合には、
オンライン会議ソフトウェアZoomを用いて講義を配信するので、
履修登録後にLoyola授業掲示板に掲示される情報により、
本授業のZoom会議室に参加のこと。
- 事前提示資料：
講義内容
第1回：4/18
計算の理論入門まで。有限オートマトン（状態遷移図・形式的定義）。
語・言語。
第2回：4/25
計算の理論入門まで。有限オートマトン。
語・言語の演算。正規言語・正規表現。
集合・写像などの言葉を用いた概念記述の練習。
第3回：5/02
集合・写像などの言葉を用いた概念記述の練習。
非決定性有限オートマトン。
正規言語⇔非決定性有限オートマトンで認識可能⇔決定性有限オートマトンで認識可能。
模式的な状態遷移図で表わしたことを形式的な5つ組の言葉で書き下す。
第4回：5/09
計算の理論入門まで。
非決定性有限オートマトン。
正規言語⇔非決定性有限オートマトンで認識可能⇔決定性有限オートマトンで認識可能(（続き）。
一般化された非決定性有限オートマトン。
第5回：5/16（予定）
計算の理論入門まで。
正規言語⇔非決定性有限オートマトンで認識可能⇔決定性有限オートマトンで認識可能(（続き）。
有限オートマトンによる計算可能性。
有限オートマトンで認識できる言語の特徴づけ
（"待ち"の種類が有限）。
有限オートマトンで認識できない言語の例。