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

課題の提出

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

課題２

• ★必修：課題２ａ★

  Dijkstraのアルゴリズム解法を実現するプログラムを作成し、コンパイルして実行せよ。
  このとき、グラフ中の指定頂点（ここでは頂点０）に対して、全ての頂点への最短経路コストと最短経路を標準出力に表示すること。
  ソースコードはグラフＢに対する実行時のものだけでよい。

  • グラフＢ（必須課題２ａの項参照）
  • グラフＣ（必須課題２ａの項参照）

  ※第一回課題では隣接行列をedge[][]の形にしていましたが、 今回は隣接行列をw[][]で表してます。

  • 提出物〔2a-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    Dijkstraのアルゴリズム本体については、授業中に示したものを使ってよい。元のプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
    

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

    プログラム先頭の様子

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

  • 提出物〔2a-2〕：プログラムのグラフＢに対する出力結果を保存したテキストファイル
    出力例をグラフＢに示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。

  • 提出物〔2a-3〕：プログラムのグラフＣに対する出力結果を保存したテキストファイル
    出力例をグラフＣに示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。

• ★必修：課題２ｂ★

  Dijkstraのアルゴリズムと、Floydのアルゴリズムについて、空間計算量と時間計算量をオーダーで表現せよ。プログラムソース（ないしアルゴリズム）のどの部分に注目してそのような結論に至ったかも述べよ。

  • 提出物〔2b-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で提出すること。
    なお、指数表示については、nの2乗であればn^2のように表記せよ。
    

• ◆発展：課題２ｐ◆

  Floydのアルゴリズム解法を実現するプログラムを作成し、コンパイルして実行せよ。
  このとき、グラフ中の全ての頂点の組み合わせに対して、それぞれの最短経路コストと最短経路を標準出力に表示すること。
  ソースコードはグラフＢに対する実行時のものだけでよい。

  • グラフＢ（発展課題２ｐの項参照）
  • グラフＣ（発展課題２ｐの項参照）
  • 提出物〔2p-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    Floydのアルゴリズム本体については、要したサンプルプログラムをベースにしてよい。
    元のプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
    他の注意点については〔2a-1〕に同じ。

  • 提出物〔2p-2〕：プログラムのグラフＢに対する出力結果を保存したテキストファイル
    出力例をグラフＢ（発展課題２ｐの部分を参照）に示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。

  • 提出物〔2p-3〕：プログラムのグラフＣに対する出力結果を保存したテキストファイル
    出力例をグラフＣ（発展課題２ｐの部分を参照）に示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。