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

課題の提出

• 提出期限
  2010/07/01 (Fri), 18:00 JST 【予定：正確にはmoodleで確認してください】
• 提出方法
  筑波大学e-learningポータル(moodle)から提出
• 条件
  「必修」課題は全て提出してください。
  「発展」課題の提出は任意です。
  （「発展」課題を出さなくともＡ評価になる可能性はありますが、確実に目指すのなら「発展」課題をするほうがよいでしょう）
  

課題５

• ★必修：課題５Ａ★

  授業中に説明した重複を許すナップサック問題について、
  (1) バックトラック法
  (2) 動的計画法
  の両解法をプログラム中のmain関数から呼び出し、それぞれ最適解を表示するプログラムを作成すること。
  このとき、それぞれの時間計算量の目安となる実行ステップ数を計り、最適解と併せて表示すること。
  最適解の表示方法は、その内容が分かれば形式は問わないが、(1)(2)でそれぞれ出力すること。
  (特に(2)は表示方法は授業中に明示していないことに注意)。
  

  SAMPLE_K300
  

  ID	0	1	2	3	4	5	6	7
  value	15	100	90	60	40	15	10	3
  weight	6	20	25	30	40	30	60	10

  制限重量を112とすると、ID0が2個、ID1が5個の組み合わせで、最大価値は530となる。

  SAMPLE_K310
  

  ID	0	1	2	3	4
  value	4	5	10	11	13
  weight	3	4	7	8	9

  制限重量を17とすると、ID0が1個、ID2が2個の組み合わせで、最大価値は24となる。

  • 提出物〔5A-1〕：Ｃソースファイル（コメント必須）
    SAMPLE_K300の動作確認ができる状態で提出すること。
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    プログラムで工夫した行があれば、必ず何かしらの説明をコメントの形でプログラム中に書き込むこと。
    

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

  • 提出物〔5A-2〕：(1)バックトラック法(2)動的計画法の実行結果（最大価値、それを与える物品の組み合わせ、計算に要したステップ数)）。
    

• ★必修：課題５Ｂ★

  (1) 上記の重複を許すナップサック問題の解法(1)(2)について、時間計算量、空間計算量をオーダーで述べよ。
  このとき、物品の種類の数Nだけでは表現できないことがあることに注意すること。
  (2) 課題５Ａの実行ステップ数と、オーダーによる時間計算量予想とが必ずしも一致しない原因を考察せよ。
  

  • 提出物〔5B-1,5B-2〕：テキスト。上記(1)-(2)に対応
    moodle上で編集して提出してください。バックアップを各個人で別に持っておくことを薦めます。
    

• ◆発展：課題５Ｘ◆

  授業で示した有限オートマトンを実行するプログラムに関して、受理状態に入った時点でその受理状態を表示して実行を終了するようにプログラムを改良せよ。

  • 提出物〔5X-1〕：Ｃソースファイル（コメント必須）
    有限オートマトンは講義で示したものでよい。
    （より複雑な有限オートマトンを用意した場合は、その内容に応じて加点対象とする）。
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    元のプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
    教えた・教わった場合には、課題５Ａと同様に明記すること。
    

  • 提出物〔5X-2〕：出力結果のファイル。