アルゴリズム論

https://y-ishigami.github.io/index.html
または, 遠隔授業に関する情報の欄を参照

●2年後期までに、必修科目で(アルゴリズムの正確な定義無しに)クイックソートや二分探索のようないくつかの具体的なアルゴリズムの構造(及びその計算量を少し)を学習した。
●3年前期のこの科目では, これらをふまえ、アルゴリズムの最も広汎的で正確な定義を学ぶ。
そして、その土台のもと良いアルゴリズムとしての基準を計算量などの観点で学び、アルゴリズムの設計において, どの手法を選択するか, またそれぞれの手法の利点と限界の理解し, アルゴリズムの記述などが出来るようになることを目標とする.

離散数学
(必修ではなくとも事実上ほとんど全員が単位取得している。言語として記法などを使用する。難しい演習問題は解ける必要無いが、例えば、講義で、定義なしに単射、全射などと言ったとき、すぐに定義を思い出すか、教科書で該当ページを調べられるようにしておくこと。もっとも高校を超える必要予備知識は初回講義で1-2ページ程度のプリントにして配布する予定なので心配は無いと思う。)

・本講義で論理的に必要な科目は、上の離散数学だけです。

・プログラミング経験があったほうが分かり易いという意味で、次は望ましいが前提とはしない。
●アルゴリズムとデータ構造およびプログラミング演習(2年後期必修)、
(プログラミングの経験があったほうが理解しやすい。2分探索木など。ソートなどの具体的なアルゴリズムを覚えている必要はない。)

・前もってというわけではないが、平行して
離散数学応用(3年前期)
もあわせて受講すると、更に効果的です。(アルゴリズム論も広い意味で離散数学の応用と考えることが可能であり、離散数学応用でもアルゴリズムを扱う。)

参考書・参考資料等
★有川・宮野著:オートマトンと計算可能性、培風館ISBN4-563-00789-7(主要参考書)
●Michael Sipser著Introduction to the Theory of Computation
(邦訳版あり。計算理論の基礎)
○岩間著 アルゴリズム理論入門 昭晃堂 (2001/05)
○Wilf著(西関・高橋訳)アルゴリズムと計算量入門・総研出版

★遠隔授業についての詳細は、上記、授業関連WebページのURLへ行くこと。
●まずは定義が簡単で能力がよく分かっている低機能計算機モデル(オートマトン)からはじめ、万能計算機であるチューリング機械へと進む。
計算機モデルとアルゴリズムの定義を正確にする。具体なアルゴリズムを例にして計算量の定義と評価法を説明する。そして効率的なアルゴリズムの定義とともにその限界性をNP完全性の概念を通して学ぶ。そして典型的な例題アルゴリズムを基本として, アルゴリズムの基本的設計技法を解説する.
授業計画
第1回:導入、背景。計算機で出来ることと出来ないこと。
第2回:オートマトンの理論(1)定義と基礎
第3回:オートマトンの理論(2)全体の概観
第4回:帰納的関数の理論(再帰的アルゴリズム)
第5回:チューリング機械(1)定義(決定性と非決定性)
第6回:チューリング機械(2)計算可能性・万能Turing機械・第一不完全性定理
第7回:チューリング機械(3)コルモゴロフ複雑度
第8回:計算量理論(1);基礎
第9回:計算量理論(2);線型圧縮定理
第10回;計算量理論(3);線型加速定理
第11回;計算量理論(4);NP完全性
第12回;近似アルゴリズム
第13回:確率アルゴリズム
第14回: 回路計算量の理論
第15回:期末試験とその解説・復習

講義での疑問点は上にあげた参考書を読むと理解が深まります。離散数学の講義で説明されていないことは全て説明しますので、説明されていない疑問点があった場合には、離散数学の復習プリント(初回講義に配布)にあたって定義から立ち戻ってください。担当教員への質問も歓迎します。

主に期末試験によって成績評価をする。
オートマトン・チューリング機械など基本的計算機モデルを厳密に表現し扱える.
各種基本的アルゴリズム・計算クラスを正確に表現し扱える.

水曜5限。

●他人の出来と比較するよりも、学問を楽しんでください。離散数学(2年前期)で学んだことが役に立つはずです。講義だけで理解できる内容は、もともと知っていたか、よほど薄っぺらいものかのどちらかです。本を読んでください。
過去において、この科目で期末試験受験後不可の学生は(例外なく)全員が、離散数学(2年前期)の理解が不足していました。
●良いアルゴリズムを設計すること(首尾よく問題を解決すること)も重要であるが、アルゴリズムの限界(問題が難しいこと)を理解することも重要である。暗号や擬似乱数などでは、敵の解読アルゴリズムの計算量が膨大になってしまうこと(敵の抱えている問題が難しいこと)を利用する。

★遠隔授業についての詳細は、
(学務情報システムの)シラバスの"遠隔授業に関する情報"欄参照