第五回課題：データ構造とアルゴリズム（２００９）

課題の提出

• 提出期限
  2009/06/30 (Tue), 08:30 JST
• 提出方法
  Web CTから提出
• 条件
  「必修」課題は全て提出してください。
  「発展」課題の提出は任意です。
  （「発展」課題を出さなくともＡ評価になる可能性はありますが、確実に目指すのなら「発展」課題をするほうがよいでしょう）
  

課題５

• ★必修：課題５ａ★

  授業中に説明した重複を許すKnapsack問題について、最大価値とその最大価値を実現する物体の選択状況を表示するプログラムを作成し、実行結果を示せ。

  ＜問題例＞ N = 10, W_LIMIT = 199 0: v = 5, w = 56 1: v = 83, w = 46 2: v = 56, w = 20 3: v = 19, w = 99 4: v = 75, w = 49 5: v = 35, w = 65 6: v = 14, w = 25 7: v = 95, w = 32 8: v = 58, w = 37 9: v = 80, w = 31

  ＜出力例＞ ID=9 x 1, ID=7 x 4, ID=2 x 2 total max value = 572, weight = 199

  以下のものを提出してください。

  • 提出物〔5a-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
    

    【注意】
    誰かに教えてもらった場合：	その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
    誰かに教えてあげた場合：	その学生（氏名・学籍番号）をプログラム先頭に記すこと。
    お互いに相談した場合：	教えてもらった・教えてあげたの例に準拠して提出してください。

    プログラム先頭の様子

    // 課題3 (3a-1) // 提出者 012345678 筑波 薫 【←学籍番号、氏名】 // 教わりました： 112233445 優秀 秀雄, 554433221 秋葉原 命 // 教えてあげた： 998877665 学園 友近 // #include <stdio.h> #define N 8 ...

  • 提出物〔5a-2〕：プログラムの出力結果を保存したテキストファイル
    上記に例を示したが、形式についてはその通りに出力する必要はない。
    

  • 提出物〔5a-3〕：時間計算量についての考察を述べたテキストファイル
    5a-1のＣプログラムについて、時間計算量について、ビッグオー表現を用いて見積もりをせよ。
    必要なら、物品数N、ナップサックの重量制限値W_LIMITを用いること。
    

• ★必修：課題５ｂ★

  授業中に説明した「問題の置換」において、ナップサック問題を最長経路問題における重み付き有向グラフに変換して問題を解くことを考える。
  ここで、物品数をN、ナップサックの重量制限を値W_LIMITとする。
  (1) 重み付き有向グラフに変換するための作業量を、空間作業量・時間計算量の両方についてビッグオー表現で見積もること。
  (2) 変換した重み付き有向グラフを最長経路問題用のアルゴリズムで解いた場合の空間作業量・時間計算量を、ビッグオー表現で見積もること。
  (3) ナップサック問題を全解探索で解いた場合の時間計算量 O(2&supN;) に対して、問題の置換を適用した場合の計算量の得失を論ぜよ。
  (O()の中が表記逆転してました:2009/06/29修正)

  • 提出物〔5b-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で十分であるが、必要があればpdfで提出してもよい。
    このファイルの中で、(1)-(3)について回答すること。
    

• ◆発展：課題５ｐ◆

  Knapsack問題に対して、FPTASアルゴリズムに基づくＣプログラムを実装せよ。また、εの値をいろいろと変えて（３種類以上）、時間計算量（プログラム中の特定行の通過回数で評価）がどのように変化するかを調べよ。

  • 提出物〔5p-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
    

  • 提出物〔5p-2〕：プログラムの出力結果を保存したテキストファイル
    εを３種類以上変えて、時間計算量（プログラム中の特定行の通過回数で評価）がどのように変化するかを調べ、その結果について近似精度と時間計算量とがどのように交換されているか考察せよ。