この実習は, 離散手法に関する学習を行うことを目的とします. 日頃インターネット上の情報を閲覧していると思いますので, この インターネット上のページを題材に実習を行います.
実習では, ウェブページとリンクをそれぞれノード (節点) とエッジ (辺) とに 見立てた「ウェブグラフ」を扱います. この「ウェブグラフ」をJavaプログラム を使って解析し, グラフを扱う手法の修得を目指します.
1日目には, まず, 本実習で使用するソフトウェア (Java, Graphviz) のインストールを行います.
その後, 深さ優先探索を使って, Webを探索するプログラムの作成を行います.
サンプルプログラム2日目には, まず, 前回の深さ優先探索を行うプログラムを改良して, Web Graphの抽出を行うプログラムを作成してもらいます. また, 深さ優先探索に 利用したスタックを別のデータ構造のキューに変更することで, 幅優先探索を プログラムを作成します.
最後に, Graphvizを利用することで, 簡単なGraphを描画してみます.
サンプルプログラム3日目には, 強連結成分分解を行うプログラムを作成します. 強連結成分分解は, グラフの解析を行う上で重要な概念で, 他の解析の前処理としても 利用されます. 強連結成分分解のアルゴリズムについては, 実習の時間の中 で説明をしますが, 深さ優先探索のアルゴリズムを改良することで得られます.
なお, 希望者は, 他のグラフアルゴリズムの実装を行っても良いとします.
本実習の中で作成したプログラムを用いて, 計数工学科の研究室から1つ選択し, そのウェブグラフの構造について自分なりの考察を行って レポートにまとめてもらいます.
