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

課題の提出

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

課題３

• ★必修：課題３ａ★

  授業で示したFloydのアルゴリズムに従って、全ての頂点対についての最短経路値とその経路を表示するプログラムを、Ｃ言語で書いて実行せよ。
  実行例となる処理対象のグラフG50dash0は隣接行列で下記のように与える。
  

  Graph G6-A

  Graph G6-B

  #define NC 9999 #define N 6 int edge[N][N] = { /* src: 0 1 2 3 4 5 ...dst */ /* 0 */ { 0, NC, NC, 8, 15, NC}, /* 1 */ { 10, 0, 24, NC, 8, NC}, /* 2 */ { NC, NC, 0, NC, NC, 6}, /* 3 */ { NC, NC, NC, 0, 5, NC}, /* 4 */ { NC, NC, 12, NC, 0, 7}, /* 5 */ { NC, NC, 3, NC, NC, 0} };

  #define NC 9999 #define N 12 int edge[N][N] = { /* 0 1 2 3 4 5 6 7 8 9 10 11*/ /* 0 */ { 0, 4,NC,NC, 3,NC,NC,NC,NC,NC,NC,NC}, /* 1 */ { 4, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC,NC}, /* 2 */ {NC, 1, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC}, /* 3 */ {NC,NC, 1, 0,NC,NC,NC,NC,NC,NC,NC,NC}, /* 4 */ { 3,NC,NC,NC, 0, 1,NC,NC, 1,NC,NC,NC}, /* 5 */ {NC,NC,NC,NC, 1, 0, 2,NC,NC, 2, 3,NC}, /* 6 */ {NC, 2,NC,NC,NC, 2, 0,NC,NC,NC, 3,NC}, /* 7 */ {NC,NC, 2,NC,NC,NC,NC, 0,NC,NC,NC,NC}, /* 8 */ {NC,NC,NC,NC, 1,NC,NC,NC, 0,NC,NC,NC}, /* 9 */ {NC,NC,NC,NC,NC, 2,NC,NC,NC, 0,NC,NC}, /*10 */ {NC,NC,NC,NC,NC, 3, 3,NC,NC,NC, 0, 1}, /*11 */ {NC,NC,NC,NC,NC,NC,NC,NC,NC,NC, 1, 0} };

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

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

  • 提出物〔3a-2〕：プログラムのグラフG6-Aに対して、全頂点対の最短経路値とその経路を出力したテキストファイル
    各頂点対について、１行ずつ使って経路値と経路を示すこと。
    最短経路は始点⇒終点の順でなくともよいが、その場合は経路出力結果の読み方を示すこと。
    最短経路値がNCの場合は表示する必要はない。始点と終点が同じ場合も同様（表示しても構わない）。
    

  • 提出物〔3a-3〕：プログラムのグラフG6-Bに対して、全頂点対の最短経路値とその経路を出力したテキストファイル
    諸注意は3a-2に準ずる。
    

• ★必修：課題３ｂ★

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

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

• ★必修：課題３ｃ★

  ※課題３ｃが間違って２ｃのままでした(5/27a版)。5/28a版以降は訂正済です。
  安定結婚問題を解くための授業で紹介した「求婚アルゴリズム」について、男性数をNとしたときの時間計算量をビッグオーによるオーダー表現で示せ。その理由も説明せよ。また、時間計算量が最悪になるケースを説明せよ。
  

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

• ◆発展：課題３ｐ◆

  課題３ａのプログラムにおいて、頂点に頂点名(文字列)を関連付け、最短経路の表示時に頂点番号ではなく頂点名を表示するようにせよ。
  必要な文字列情報は配列の形で格納せよ。
  発展課題においては、経路は必ず始点から終点の順に表示すること。
  以下は例である。この通りに行う必要はない。隣接行列も独自に与えてよい。
  

  Graph G6-A / 名前
  0	Tokyo
  1	Shinjuku
  2	Tsukuba
  3	Yokohama
  4	Utsunomiya
  5	Ohmiya

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

  • 提出物〔3p-2〕：3p-1のプログラムの実行結果（頂点対の最短経路値と、始点〜終点を名前で表示した結果）を保存したテキストファイル