応用プログラムの作成

この授業の最後の課題として、これまで学んだデータ構造とアルゴリズム、 およびさまざまなクラスライブラリを活用する、 応用(application)プログラムを作成しましょう。

問題の選択・提出方法

問題の選択方法

学籍番号の末尾3桁の数字を4で割った余り = 問題番号

提出先

• ホスト: earth.mlab.im.dendai.ac.jp
• ディレクトリ: /home/submit/JavaLib/application/[学籍番号]/[所定のディレクトリ]

提出期限

• 1/17(木) 20:30

クラス名

提出する際に作成する問題ごとのディレクトリ名を、 main メソッドのあるクラス名にも用いること。

問題

問題0 [スレッド・正規表現]

UNIX系の OS には、指定したファイル群から正規表現にマッチする行を抜き出して表示する grep というコマンドがある。例えば、

  $ grep 東京電機大学 foo.txt bar.txt

とすると、foo.txt と bar.txt の中身をチェックし、「東京電機大学」を含む行を表示する。また、その行だけだとわかりにくい場合には、--context オプションをつけることにより、前後数行をあわせて表示することもできる。

  $ grep --context=2 東京電機大学 foo.txt bar.txt

さて、このWeb対応版を作成したい。

  $ java WebGrep HTML5 http://www.w3.org/ http://www.itmedia.co.jp/

とすると、指定された複数の URL を起点とし、何階層かリンクをたどってページを収集し、そのページ群の中から HTML5 という文字列を含む行、および前後の行を表示する。その行がどこのページで発見されたのかも示す (URLもしくは独自にふったIDなどで示す)。

提出にあたっては、所定の提出ディレクトリの下にディレクトリ "WebGrep" を作成し、プログラムの実行に必要なファイルをすべてまとめること。

以下の条件のうち、任意に設定できるものをどのようにしたか、 および他の工夫した点について、ファイルの先頭にコメントとして記述しておくこと。

[条件]

• Webページの取得にはマルチスレッドを用いる。
  • スレッドの用意のしかたは任意とする。起点の数だけ、1サイト1スレッド、1URLリスト1スレッド、など。
• リンクをたどるときに、以下の点について工夫をする。
  • なんらかの終了条件を定める。階層ではなくてよい。見つかった個数など。
  • 同一ページを複数回取得しない。ループを防止する。
  • HTML以外のリンク先をHTMLだと思ってたどらない。
  • 目的に合わせてたどる範囲を設定する。同一サイト内など。
  • 同一サーバに接続する際には1秒以上間隔を開ける(ことが望ましい)。

[参考]

• スレッドの週の演習問題の解答例: URLExtractor.java

[備考]

• 通常のリストやキューは、要素を取り出したいときに要素がなければ取れなくて終わるが、別のスレッドが要素を追加するまで待っていることができるものもある。必要があれば、java.util.concurrent パッケージの LinkedBlockingQueue などを調べてみるとよい。

問題1 [スレッド・正規表現]

ある特定のサイトのページからリンクの張ってある mp3 を集めたい、pdf を集めたい、などといった要求に応えるプログラムを作りたい。画像ファイルを集めたいことも想定し、a 要素の href 属性だけでなく、img 要素の src 属性からも参照先 URL を取得することにする。

  $ java ResourceFinder pdf http://www.w3.org/

とすると、引数で指定された正規表現にマッチする参照先 URL、この場合 pdf を含む URL を表示するものとする。正規表現を用いることにより、拡張子以外の部分についても条件を設定することができる。

このプログラムではリンクをたどってページを収集することになるが、同一のサイト内のみリンクをたどるか、外部のサイトへのリンクもたどるかは、選べるようにすること。

提出にあたっては、所定の提出ディレクトリの下にディレクトリ "ResourceFinder" を作成し、プログラムの実行に必要なファイルをすべてまとめること。

以下の条件のうち、任意に設定できるものをどのようにしたか、 および他の工夫した点について、ファイルの先頭にコメントとして記述しておくこと。

[条件]

• 問題0と同じ

問題2 [リスト]

線形リストのデータ構造を用い、メニュー形式でデータの追加、削除、検索、 一覧などが可能な簡単なデータベースシステムを作成しなさい。メニュー の選択やデータの入力はテキスト形式でも良いし、GUIのようなインタフェース を工夫しても良い。

以下の機能を備えること。

• リスト先頭への追加
• リスト末尾への追加
• 削除
• 検索
• リストの内容を表示

すべての機能が正常に動作するか十分にテストすること。例えば、すべての機 能において先頭、中間、末尾の3種類のノードが正しく扱えるか確認すること。 また、エラー処理も考慮すること。エラー処理とは、例えば削除や検索で見つ からなかった場合に適切なメッセージを表示することなどである。問題文に示 されていない仕様は、自分で決めること。

提出にあたっては、所定の提出ディレクトリの下にディレクトリ "TinyDB" を 作成し、プログラムの実行に必要なファイルをすべてまとめること。

問題3 [2分探索木]

2分探索木と木の中に存在しないキーxが与えられたとき、 xより大きなノード を除去し、xより小さなノードのみからなる2分探索木を得るアルゴリズムを考 え、プログラムとして実現しなさい。直接処理対象の木の構造を組み替えるよ うにし、元の木を残す必要はない。

木が完全2分木に近い形をしているときに O(log n) に近い計算量とする方法を 工夫すること。 (完全2分木のとき、木の高さは log n に比例する)

最も単純な方法は、木のノードを1つ1つすべて調べてxと比較するやり方である が、この方法はO(n)、すなわち木のノードの数に比例するという大きな計算量 を要するため不正解とする。木の高さにほぼ比例する計算量で済む方法を工夫 すること。

すべての機能が正常に動作するか十分にテストすること。少なくとも、対象の 木が空であった場合、抽出した結果の木が空であった場合、1つまたは複数個の ノードからなる木であった場合について正常動作を確認すること。

提出にあたっては、所定の提出ディレクトリの下にディレクトリ "BSTMinDistiller" を作成し、プログラムの実行に必要なファイルをすべてま とめること。

[ ヒントのスライド ]