|
[an error occurred while processing this directive]
| |
Teaching
[Top] [Prog Lang (2005, Tsuda)] [B3 enshu (2004)] [B4 enshu A (2004)] [B3 jikken (2004)] [B4 enshu B (2004)]
|
数理情報工学演習第一 数理実習（ 3年生2004年冬学期）
離散手法：ウェブグラフを用いたグラフ探索アルゴリズムの実験
場所，日程
工学部6号64講義室にて．
第二回：10月21日（木），25日（月），28日（木）．レポート締切は11月10日．
第四回：11月11日（木），15日（月），18日（木）．レポート締切は12月 1日．
概要
この実験は，離散手法に関する学習を行なうことを目的とします．日頃ウェブブラウザを用いてインターネット上の情報を閲覧していることと思います．実験では，ウェブページとリンクとをそれぞれ節点（ノード）と辺（エッジ）とに見立てた「ウェブグラフ」を題材とし，主にJavaでのプログラム作成を行ないます．
実験は以下のように進みます．
- ウェブグラフの取得
- 節点の持つ深さの計算
- 強連結成分分解
- Graphvizを用いたグラフ描画（発展課題）
レポート（第二回および第四回該当者）
以下のものを電子メールで筧宛（kaz _at_mark_ mist.i.u-tokyo.ac.jp）に提出して下さい．
- 自分で作成したプログラムとその実行結果
- （外部に迷惑をおかけしないよう）学内のサイトをひとつ選んで，下記の完成版（に必要に応じて自分で手を加えたもの）で実行した結果（画面出力，Graphviz用ファイルおよび可能であればその描画結果）
※注意※ スレッドを使ったウェイト（Thread.sleep(msec)）を忘れずに入れ，javacでコンパイルしなおすこと！
- 上記学内サイトのページ構成に関する簡単な考察（深さや強連結成分の構成のされ方について）
- 強連結成分分解アルゴリズムの正当性について調べたもの（もしくは自分自身で証明したもの）
提出の際は，文章はMicrosoft Word形式もしくはPDF（LaTeXで作成した際にどうPDFに変換すれば良いのかわからない場合は，別途連絡して下さい）で，プログラムや出力，画像はそのまま個別のファイルで，電子メールへの添付として提出して下さい．
資料
- サンプルグラフ 1 （http://www.ipl.t.u-tokyo.ac.jp/~kaz/test1/a.html）
- サンプルグラフ 2 （http://www.ipl.t.u-tokyo.ac.jp/~kaz/test2/a.html）
- 配布資料
|
First written: Thursday, October 21, 2004
Final revision: Apr 6, 2005, 12:24:27 JST
|
