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

春学期・月曜5時限・8-409教室紀-104教室に変更

本講義は、理工学部情報理工学科「計算機数学」・ 理工学部数学科「電子計算機概論I」の合併講義であるが、 数学科の「計算機数学I・II」とは別の講義である。

上智大学の学部シラバス内の本授業のページ [計算機数学 |電子計算機概論I ]

期末試験のお知らせ

レポート提出について

お知らせ

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

講義概要

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

講義計画

計算機におけるデータの取扱いや計算の原理について軽く説明した後、 計算の理論の入門として、計算モデルによる「計算」の定式化・ 計算可能性の理論・計算量の理論の初歩を紹介し、 幾つかの基礎的な数理アルゴリズムについても触れる。

主な参考書

講義内容

4/16

配ったプリント [page 0(pdf,15KB) |アンケート(情報理工学科向け)(pdf,6KB) ] ・プロジェクタ資料 [4/16授業時(pdf,83KB) |4/16印刷用(pdf,62KB) ]

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

4/23

配ったプリント [演習(1)(pdf,13KB) ] ・プロジェクタ資料 [4/23授業時(pdf,55KB) |4/23印刷用(pdf,42KB) ]

計算の理論入門まで。コンピュータが行なっていることの定式化。 有限オートマトン。

4/30

振替休日でお休み。

5/7

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

計算の理論入門まで。有限オートマトン。 語・言語の演算。正規言語・正規表現。 集合・写像などの言葉を用いた概念記述の練習。

5/14

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

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

5/21

プロジェクタ資料 [5/21授業時(pdf,57KB) |5/21印刷用(pdf,56KB) ](誤記訂正済)

計算の理論入門まで。 決定性有限オートマトンと非決定性有限オートマトンとの同等性。 有限オートマトンによる計算可能性。

5/28

配ったプリント [page 1(有限オートマトン)(pdf,28KB) |演習(3)(pdf,7KB) ] ・プロジェクタ資料 [5/28授業時(pdf,48KB) |5/28印刷用(pdf,39KB) ](誤記訂正済)

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

6/4

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

計算の理論入門まで。 生成文法による言語の記述。文脈自由言語。 生成文法・文脈自由言語とプッシュダウンオートマトン。 スタックマシンの例: 逆ポーランド記法。

6/11

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

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

6/18

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

計算の理論入門まで。文脈自由言語に対する Pumping Lemma。 チューリング機械。

6/25

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

計算の理論入門まで。 チューリング機械。計算可能性。Church-Turingの提唱。 万能チューリング機械。対角線論法。

7/2

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

万能チューリング機械と対角線論法(補足)。冪集合の濃度。

計算量の理論入門まで。計算量とは。

7/9

配ったプリント [page 2,3(計算モデル・言語)(pdf,34KB) ] ・プロジェクタ資料 [7/9授業時(pdf,44KB) |7/9印刷用(pdf,33KB) ]

計算量の理論入門まで。計算量とは。LandauのO-記法。 多項式時間・指数時間。例: 互除法。

7/16

配ったプリント [page 4(計算量)(pdf,24KB) ] ・プロジェクタ資料 [7/16授業時(pdf,82KB) |7/16印刷用(pdf,59KB) ]

「海の日」であるが授業実施日である。

計算量の理論入門まで。色々な数理アルゴリズムの計算量。 例: 素数判定・素因数分解・並べ替えなど。

7/23

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

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

7/30(予定)

期末試験を行なう。