計算機数学(情報理工学科)・講義内容と予定

春学期・月曜2時限・市谷本館102教室

期末試験のお知らせ

レポート提出について

お知らせ

授業時のプロジェクタ資料を掲載する予定です。 各授業日の項から見て下さい。 但し、各授業中の前回の復習部分を含んでいるので、内容に重複があります。 印刷時には必要なページだけ印刷するなどして下さい。

講義概要

「この問題は計算機でも計算できないなぁ」 「君は実に…計算が下手なんだなぁ」 「そうじゃなくて計算できないことが証明できるんだよ」 「え？どゆこと？」

「計算」とは何か、「計算できるか／できないか」というような問いに対して、 数学では、「計算機が行なうこと」を「計算」と考え、 計算機が行なえることを「計算モデル」として定式化することによって 「計算」を定義し、明確に答えることを可能にしてきた。 本講義では、代表的な計算モデルを取り上げながら、 計算の理論・アルゴリズムの概念・計算量の理論の初歩を紹介し、 計算の可能性・効率について論ずると共に、 具体的な例として幾つかの基礎的な数理アルゴリズムについて触れる。

講義計画

計算の理論の入門として、計算モデルによる「計算」の定式化・ 計算可能性の理論・計算量の理論の初歩を紹介し、 幾つかの基礎的な数理アルゴリズムについても触れる。

主な参考書

近年出版された次の冒険小説も、本講義の受講者には楽しく読めるだろう。

講義内容

第1回：4/13

配ったプリント [page 0(pdf,14KB) |アンケート(pdf,6KB) ] ・プロジェクタ資料 [4/13授業時(pdf,64KB) |4/13印刷用(pdf,41KB) ](途中までしか話せなかったが、予定の最後までの分を掲載しておきます)

本授業の概要・予定。半期の講義内容全般の概観・予告。

第2回：4/20

配ったプリント [演習(1)(pdf,13KB) ] ・プロジェクタ資料 [4/20授業時(pdf,50KB) |4/20印刷用(pdf,44KB) ](機材トラブルで見せられなかったが、用意してきたものを掲載しておきます)

計算の理論入門まで。有限オートマトン（状態遷移図・形式的定義）。

第3回：4/27

配る予定だったプリント（次回配ります） [演習(2)(pdf,17KB) ]・ プロジェクタ資料 [4/27授業時(pdf,49KB) |4/27印刷用(pdf,44KB) ]

計算の理論入門まで。有限オートマトン。 語・言語の演算。正規言語・正規表現。

5/04

「みどりの日」で本授業なし。

第4回：5/11

配ったプリント（前回掲載したのと同じもの） [演習(2)(pdf,17KB) ]・ プロジェクタ資料 [5/11授業時(pdf,58KB) |5/11印刷用(pdf,57KB) ]

計算の理論入門まで。有限オートマトンと正規言語・正規表現。 集合・写像などの言葉を用いた概念記述の練習。 非決定性有限オートマトン。 正規言語⇔非決定性有限オートマトンで認識可能（途中まで）。

第5回：5/18

配ったプリント [演習(3)(pdf,10KB) ]・ プロジェクタ資料 [5/18授業時(pdf,42KB) |5/18印刷用(pdf,39KB) ]

計算の理論入門まで。 非決定性有限オートマトン。 正規言語⇔非決定性有限オートマトンで認識可能（続き）。 模式的な状態遷移図で表わしたことを形式的な5つ組の言葉で書き下す。 決定性有限オートマトンと非決定性有限オートマトンとの同等性（途中まで）。

第6回：5/25

プロジェクタ資料 [5/25授業時(pdf,38KB) |5/25印刷用(pdf,33KB) ]

計算の理論入門まで。 集合・写像などの言葉を用いた概念記述の練習（解答）。 決定性有限オートマトンと非決定性有限オートマトンとの同等性（続き）。 有限オートマトンによる計算可能性。 有限オートマトンで認識できない言語の例。

第7回：6/01

配ったプリント [page 1(有限オートマトン)(pdf,28KB)(前回配る予定だったので「5/25配布」と書いてあります) |演習(4)(pdf,7KB) ] ・プロジェクタ資料 [6/01授業時(pdf,62KB) |6/01印刷用(pdf,45KB) ]

計算の理論入門まで。 有限オートマトンによる計算可能性。 Pumping Lemma (注入補題・反復補題)。 プッシュダウンオートマトン。生成文法による言語の記述。

第8回：6/08

プロジェクタ資料 [6/08授業時(pdf,70KB) |6/08印刷用(pdf,63KB) ]

計算の理論入門まで。 プッシュダウンオートマトン。 生成文法による言語の記述。文脈自由言語。 演算木と式の記法。

第9回：6/15

配ったプリント [演習(5)(pdf,7KB) ] ・プロジェクタ資料 [6/15授業時(pdf,58KB) |6/15印刷用(pdf,52KB) ]

計算の理論入門まで。 生成文法・文脈自由言語とプッシュダウンオートマトン。 スタックマシンの例: 逆ポーランド記法・PostScript。 演算木と式の記法。文脈自由言語と再帰。 正規言語を生成規則で記述する際に現れる再帰は 所謂"末尾再帰"であって除去できる。

第10回：6/22

プロジェクタ資料 [6/22授業時(pdf,55KB) |6/22印刷用(pdf,48KB) ]

計算の理論入門まで。 生成文法・文脈自由言語とプッシュダウンオートマトン。 構文解析木。文脈自由言語に対する Pumping Lemma。

チューリング機械。計算可能性。Church-Turingの提唱。

第11回：6/29

プロジェクタ資料 [6/29授業時(pdf,44KB) |6/29印刷用(pdf,35KB) ]

チューリング機械。計算可能性。Church-Turingの提唱。 万能チューリング機械。対角線論法。集合の濃度。

第12回：7/06

配ったプリント [page 2〜4(期末レポートの例)(pdf,45KB) ] ・プロジェクタ資料 [7/06授業時(pdf,36KB) |7/06印刷用(pdf,31KB) ]

対角線論法。冪集合の濃度。

計算量の理論入門まで。計算量とは。LandauのO-記法。

第13回：7/13

プロジェクタ資料 [7/13授業時(pdf,100KB) |7/13印刷用(pdf,62KB) ]

計算量の理論入門まで。多項式時間・指数時間。 色々な数理アルゴリズムの計算量。 例: 互除法・素数判定・素因数分解・並べ替え・繰返し二乗法による冪の計算など。

第14回：7/20

プロジェクタ資料 [7/20授業時(pdf,52KB) |7/20印刷用(pdf,43KB) ]

授業アンケート。

計算量の理論入門まで。非決定性計算量。 "P vs NP" 問題。NP完全性。

7/27(予定)

期末試験を行なう。