アルゴリズム論第一(3クラス)

Google Classroomに資料掲載予定

情報の分野では, 対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために, アルゴリズムとデータ構造を学ぶことが最初になる. 本講義では, データ構造とアルゴリズムの基本と特性について, 理論的・直観的に理解し活用する技量を学び, コンピュータ上での実現方法を修得する. 単純なデータ構造から始めて, ハッシュ法, 木やグラフの定義, 諸性質, 制御するアルゴリズム, および, これらを用いた問題の構造の記述・理解と効率的処理技法を修得する.
本講義によって, 高校数学・大学初年次までに学んだ線形代数・確率統計・数列などの基礎数学と合わせ, 情報分野で必須な基本的な数学の知見を修得することも目標とする.

C言語によるプログラミングの履修が望ましい. 特に, プログラミング通論. 基礎プログラミングおよび演習.

同上.

資料は毎回独自のものを作成し配布しています. 毎年の講義資料はほぼ安定しているので今年度のGoogle Classroomには, 昨年度の授業資料を最初にまとめて掲載します. また, 毎回の授業資料はこのクラスルームに前の週には掲載します. 代表的な学部教科書15回に相当する入門的な教科書や専門的教科書は, 授業初回に紹介します.

参考書として, 最近出た学部2年・3年向け授業15回のために作られた以下の本をあげておきます:

西尾章治郎 監修, 原, 水田, 大川著,
「アルゴリズムとデータ構造」, (未来へつなぐデジタルシリーズ10),
共立出版 (2400円).

最近の講義内容を顧みると, 前半は上記の教科書にかなり近く, 後半の平衡探索木とグラフアルゴリズムは本講義のほうが広く・深く扱っていると言えます.

他に, アルゴリズムの専門的な授業で必須とされる教科書は, 以下の2種類です. 上記で載っていない項目については, これらが参考に, なります. 分厚いので, 項目を選んで調べるのに適す:

*1 (i) R.セジウィック著, 「アルゴリズムC」 第1巻～第3巻. 近代科学社,
(ii) R.セジウィック著/野下浩平・星守・佐藤創・田口東 共訳:アルゴリズムC・新版─基礎・データ構造・整列・探索, 近代科学社, 2004年. (内容は(i)と近く, こちらのほうが新しい本です).

*2 T.コルメン他著, 「アルゴリズムイントロダクション第3版」全3巻.
特に, 第1巻(計算量, ヒープ, 3章のデータ構造)と第2巻(VI.グラフ)
近代科学社, (2013年に, 1冊にまとめた統合版が出ています).
MITの標準教科書です.

専門書は分厚いので, 学部向け日本語教科書は断片的に話題をとりあげて編集されています. そのため一冊の学部向け入門書ではなかなかこの講義全体をカバーしきれません. 講義のうち特に後半の, 平衡探索木(2-3木), グラフのアルゴリズム, の紹介は, 下記の入門書も参考になります:

*「データ構造とアルゴリズム」(五十嵐建夫, 数理工学社)(サイエンス社).
(比較的最近の新しい入門書. 前半のうちハッシュやヒープ, 2分探索, 後半の平衡木以後, などの解説は簡潔にまとまっている. 疑似コードによる解説. 演習解答つき)

*「アルゴリズムとデータ構造」(岩波講座ソフトウェア科学3)(石畑清, 岩波書店)
(かなり古くて絶版に近いが図書館などにはある. 疑似コードがPascal. 内容は充実している)

です.

I類の2年後期科目として3クラスでの編成実施のうち第3クラス(昨年からクラスC)を新谷・大森で担当します. 扱う項目はクラス間でほぼ合わせてあります. 初回がガイダンス, 新谷が前半7回を担当し, 後半7回を大森が担当. 前半後半の回数は状況によって多少変動します.
-------------------------------
本授業の内容は, 下記を基本として行います. 項目ごとの講義の回数や順序は多少変更する可能性があります. 途中, 学生の理解度を調べるため, 復習まとめに相当する宿題を入れる場合があります.

0. ガイダンス(第1回)
1. アルゴリズムと計算量、抽象データ型(第2回)
2. 基本データ構造(第3, 4回)
- 線形構造(1):リストと様々な操作
- 線形構造(2):スタック、キュー
3. 木(第5回)
- (1):基本概念、色々な木
- (2):実現法、応用

4. ハッシュ法, トライなど (第6回)
- 集合を扱うデータ構造

5. ヒープと優先度つき待ち行列 (第7回)
6. 2分探索木 (第8回)
---------------
6'. 基数探索とトライ (第9回)
7. 平衡探索木 (第10, 11回)
(1):平衡探索木の詳細(2-3木, AVL木)(第10回)
(2):その他の平衡探索木(2-3-4木, B木, 赤黒木) (第11回)

8. グラフのアルゴリズム (第12, 13, 14回)
(1):グラフの表現法、単一出発点最短経路問題 (第12回)
(2): 全頂点間の最短経路問題, グラフの深さ優先探索 (第13回)
(3):コスト最小極大木, 二重連結問題, など応用編 (第14回)

9. まとめと計算量・マスター定理など先進的な話題 (第15回)

(全15回).

離散系の数学とアルゴリズム論は一体であり, 情報系のシステムソフトウェア設計や問題解決法を考えるときの基本的な言語です. 微積分や確率とは異なるため, 情報やIT, ビッグデータなどに興味があって本学に入学したものの数学的な基本の違いに戸惑う学生諸君もおられるかもしれません. 履修学生がアルゴリズム系の教科書や解説を読み, そこに書かれた文章の意味を理解し, アルゴリズムや離散構造に関する内容を日本語で適切に記述するだけの言語能力を身に着け, 教員へ積極的に適切な日本語表現で質問できる, ようになってもらうと良いです.

以下の到達レベルをもって合格の最低基準とする.
(1) 各種線形構造の操作を理解しており, 具体的な実現法を説明できる.
(2) 木構造の基本的な概念と操作を理解しており, 実現法を説明できる.
(3) ハッシングの原理と実現法を理解している.
(4) 探索木の原理を説明でき, 操作法を理解し再現できる.
(5)グラフを用いた初等的な問題と解法アルゴリズムの理解と事例に適用できる.

成績評点は, 全15回にわたる宿題の得点をX, 期末筆記試験の得点率をY%としたとき, 総合点= X + (100-X)*Y を100点満点における最終的な成績点とする. 長年, 定期的に出す宿題は必須でなく提出自由としてきたが, 今年については最近の学生の学習様式を観察の上で変更するかもしれず, 初回に説明します. 期末試験の実施も, 長年, A4資料一枚のみ持ち込み可としてきたが, 今年度からは持ち込み不可とする(最近の学習の結果). その分, 宿題の質・量を工夫し, 平素の理解度や学生間の習熟度, などを, 宿題側の得点に反映するように検討します. これらは昨年から変更なので, 初回講義で解説予定.

平日午後なら6時までなら随時. 授業終了後にその場で質問いただいたり, 電子メールで時間を相談して居室(西10号館528号室)にて相談とします. 新谷・大森どちらでも対応します.

資料や授業の内容が, その解説に向き合ったとき, 言語として頭に入ってこない場合があるかもしれません. そのときは, 自分で読んでわかる, アルゴリズムの薄い教科書を探して, それを最初に通して読むことを勧めます. アルゴリズムの基本を理解することはCプログラミングを読み書きすることとも違う要因があり, Cで学ぶアルゴリズム, などのC言語主体のプログラミングの教科書とは違う視点から, アルゴリズムそのものの構成原理を理解して記述する講義として本講義を考えていただき, 毎回の授業や宿題などで疑問に感じた点を積極的に質問してください.

I類の3クラス体制の講義なので, 過年次の学生はどのクラスを選択しても良い. 現役学生については希望クラス担当教員の了解をとってもらえば他クラスを履修して良い. この点は初回講義で説明する. 履修登録締め切り後のクラス変更は採点システムの違いのため, お断りしています.