計算機数学・講義内容と予定

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

期末試験のお知らせ

期日：7月29日（月）
時間：10:55～11:55（60分）
教室：6-203教室（四谷キャンパスなので注意）
内容：7/22までに講義した範囲

レポート提出について

期日：8月5日（月）20時頃まで
内容：配布プリントのレポート問題の例のような内容、及び授業に関連する内容で、授業内容の理解または発展的な取組みをアピールできるようなもの。
提出方法：
- 紙媒体：授業時に手渡し、または市谷本館106室前のメイルポストに提出。科目名・学生番号・氏名を明記した表紙を付けること。その他、レポートとして常識的な体裁を整えること。
- 電子メイル：電子メイルでの提出が適切な課題は電子メイルでも良い。初回の授業で配布したプリントに記載したメイルアドレス宛に、 メディアセンターの自分のアカウントから 提出すること(そうでないとスパムメイルと誤認して消してしまう可能性が高い)。質問などのメイルも歓迎する。
プリントの課題例を全て提出する必要はない。写して沢山出すくらいなら、少しでも自分でちゃんとやって出せ。

お知らせ

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

講義概要

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

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

講義計画

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

「計算」の定式化
計算のモデル化：有限オートマトン・プッシュダウンオートマトン・チューリング機械など
言語と文法：正規言語・生成文法・文脈自由言語など
計算可能性の理論の入門まで：普遍チューリング機械と対角線論法
計算量の理論の入門まで
基礎的な数理アルゴリズムの例
- ユークリッドの互除法
- 素数判定・素因数分解
- 並べ替え(ソーティング)
- 高速フーリエ変換
などなど

主な参考書

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）

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