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

課題の提出

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

課題２

• ★必修：課題２ａ★

  最長経路問題を解くプログラムを、Ｃ言語で書いて実行せよ。
  実行例となる処理対象のグラフG5dash0は隣接行列で下記のように与える。
  

  Graph G5-dash0	Graph G5-dash1
  #define N 8 int edgea[N][N] = { /* 0 1 2 3 4 5 6 7 */ /* 0 */ {0,4,0,0,2,0,0,0}, /* 1 */ {0,0,0,0,0,0,1,0}, /* 2 */ {0,0,0,3,0,0,3,0}, /* 3 */ {0,0,0,0,0,0,0,5}, /* 4 */ {0,0,0,0,0,2,0,0}, /* 5 */ {0,0,0,0,0,0,2,0}, /* 6 */ {0,0,0,0,0,0,0,1}, /* 7 */ {0,0,0,0,0,0,0,0} };	#define N 8 int edge[N][N] = { /* 0 1 2 3 4 5 6 7 */ /* 0 */ {0,4,0,0,2,0,0,0}, /* 1 */ {0,0,0,0,0,0,1,0}, /* 2 */ {0,0,0,3,0,0,3,0}, /* 3 */ {0,0,0,0,0,0,0,5}, /* 4 */ {0,0,0,0,0,2,0,0}, /* 5 */ {0,0,0,0,0,0,0,0}, /* 6 */ {0,0,0,0,0,4,0,1}, /* 7 */ {0,0,0,0,0,0,0,0} };

  • 提出物〔2a-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    プログラムで工夫した行について、必ず何かしらの説明をコメントの形でプログラム中に書き込むこと。
    コメントがないようなプログラムは提出とはみなさないので注意すること。
    隣接行列にG5-dash0を用いた形のプログラムを提出すること。
    

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

  • 提出物〔2a-2〕：プログラムのグラフG5-dash0に対して、最長経路値を保存したテキストファイル
    

  • 提出物〔2a-3〕：プログラムのグラフG5-dash1に対して、最長経路値を保存したテキストファイル
    

• ★必修：課題２ｂ★

  課題２ａで提出した最長経路問題を解くプログラムにおいて、空間計算量と時間計算量をビッグオーによるオーダー表現で示せ。その理由も説明せよ。 　　必要ならば課題２ａで提出した最長経路問題を解くプログラムを適宜引用すること。

  • 提出物〔2b-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で十分であるが、必要があればpdfで提出してもよい。
    

• ★必修：課題２ｃ★

  ある頂点から全ての頂点への最短経路を求めるDijkstraのアルゴリズムを実現するプログラムにおいて、
  　　頂点数Ｎ、辺の数Ｅに対して空間計算量と時間計算量をビッグオーによるオーダー表現で示せ。その理由も説明せよ。
  　　必要ならば授業で提示した最短経路問題を解くプログラムを適宜引用すること。

  • 提出物〔2c-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で十分であるが、必要があればpdfで提出してもよい。
    

• ◆発展：課題２ｐ◆

  課題２ａのプログラムにおいて、最長経路を与える経路（始点〜途中の全ての点〜終点）を表示するように改良し、実行せよ。
  

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

  • 提出物〔2p-2〕：G5-Dash0, G5-Dash1のそれぞれの最長経路値とその経路を出力した結果を保存したテキストファイル