2015/06/21(日) da3 授業準備

●ltp 授業準備（集計用紙システムの改修）
受講者が記入した内容をWebページとして閲覧するための機能を追加した。

●ltp 授業準備
各受講者の集計用紙への記入内容を点検し、奇妙なところのあるものについてはその受講者の学籍番号をメモにひかえた。

第10回のスライド資料を準備し、Dropboxにコピーを置いて、その旨を関係の先生方に連絡した。

●lt 授業準備
第10回の授業で使用する第9回小テストの用紙を3クラス分印刷し、2クラス分は他の先生方に渡した。

●da3 授業準備
第12回・第13回の資料の準備を行った。この2回のテーマは最小全域木である。いつもなら回の順に資料を作っていくところであるが、今度は第13回のプログラミング演習の素材となるプリム(Prim)のアルゴリズムおよびクラスカル(Kruskal)のアルゴリズムそれぞれの実装を先に検討し、これにつながるように逆算して第12回の資料を用意することにした。

★クラスカルのアルゴリズムの実装
毎年プリムのアルゴリズムは穴埋めプログラミングの問題として出していたが、クラスカルのアルゴリズムはこれまでJavaプログラムとして実装しておらず、出題もしていなかった。それがずっと気になっていたので、今年度は必須問題ではなく上級問題としてでもいいので出そうと考えて、今回初めて実装した。
この実装にあたっては、自分の腕試しを兼ねて、まずは処理の大まかな流れだけを念頭に置いて書籍を見ずにコードを書いてみた。次に動作を確認し、その上で複数の書籍と照合して、クラスカルのアルゴリズムの実装として間違っていないことを確認した。処理の大まかな流れは次の通りである。

1. 隣接行列から辺を見つけ出す。
2. これらの辺をヒープに入れる。
3. ヒープから辺を重みの小さい順に取り出しながら頂点の集合を結合していく。

一つ一つの辺をオブジェクトとして扱う必要があるので GraphEdge というクラスを作成した。グラフのインタフェース Graph に GraphEdge の配列を吐くメソッドを追加することも検討した。しかし、複数の回にわたって使う Graph に第13回でしか使わない GraphEdge を付けると、受講者への配布が無駄に面倒臭くなることに思い至ったのでやめた。

ヒープとしては java.util.PriorityQueue を使用した。このクラスを使うのも初めてであったので、最初は for-each 構文で要素を取り出すというコードを書いてしまい、この方法では優先度付きキューとしては働かないと気付くまでに時間がかかった。for-eachをやめてメソッドpollを使うことで解決した。
しかし、このヒープを使う部分を書きあげたあとで気付いたが、その部分の時間計算量が O(e log e) であったとしても、その前の隣接行列から辺を見つけ出す処理が O(n^2) であるから、実行効率の点ではあまり意味がない。「専門書でヒープを使っているからヒープを使った」というだけのことである（ただし、単にソートするとしか書いていない書籍も珍しくない）。
大方の受講者にとっては、これまで使用頻度の低かったヒープや、突然出てきたクラス PriorityQueue や、これを使うためのメソッド compareTo などは解りづらいであろう。クイックソートか何かの適当な整列アルゴリズムを使う形に書きかえるほうがよいかもしれない。そうかといって、ソートならヒープよりも劇的に解りやすいかと問われるとこれも疑わしい。
ヒープのままにしておくか、それともソートで書き換えるかについて悩んだが、とりあえずはヒープのままにしておいた。

また、頂点の集合を結合していく処理については、互いに素な集合の森 (disjoint set forest) だの同値類の問題だのunion-findアルゴリズムだのを調べたものの、結局最初に書いたままの工夫がなくて簡単なコードを採用した。頂点の集合全体を管理するためのクラス名前はIntGroupsとした。クラス名に複数形のsが付いているのが気に入らなくて、IntForestなど他の名前も考えたが、結局受講者にとっての解りやすさを考えてIntGroupsに据え置いた。

とにかくあれこれやってこの実装を完成させた。主要な処理部分のほかに補助的なクラスをいくつか要したので、プリムのアルゴリズムの実装と比べてコードの行数がかなり膨らんだが、なるだけ解りやすさを優先させた。しかし、前述の通り部分的には専門書からあまり離れないようにするために解りやすさを犠牲にしているので、全体としては中途半端な感じがする。

それにしても石畑清先生の「アルゴリズムとデータ構造」（岩波書店）は頼りになるとあらためて実感した。私が思いつく程度の疑問に対する答えは大抵これに載っていた。他のネタ本もWikipediaもその他のネット情報も活用したが、今回最も参照する頻度が高かったのはこの本であった。

★プリムのアルゴリズムの実装の見直し
昨年度までのJavaプログラムを見直した。
根本的な変更を行わず、第11回のダイクストラのアルゴリズムの実装に準拠するように軽微な変更を行ったのみで済ませた。

★第12回の講義資料
昨年度までのスライド資料の説明は簡潔であった。今年度はこれを大幅に変更し、多少ややこしくはなるが第13回のJavaプログラムにつながるよう実行手順の詳しい説明で置き換えた。スライド資料の枚数が増えた。資料を書いているうちに例題のグラフの変更すべき点に気付くことが何度かあり、そのたびに最初のスライドから全て見直しながら変更した。手間はかかったがそれなりの資料が出来上がった。

★第12回の小テスト
第11回のダイクストラのアルゴリズムの実装に関する小テスト問題を作成した。第11回の変更に併せてあちこちに変更を加え、正解プログラムの動作をEclipseで確認した。

★第12回の演習・実習用紙
未作成。前項までの時点で日付が変わって午前5時にもなろうかという頃であったので、この用紙の準備作業だけは後日に残した。
ここまでで完成したものを所定の場所に置いて、その旨をYo先生にメールで連絡した。

●進路指導Webサイトの更新
学外の合同企業説明会の日程を調べ、Webサイトに掲載した。