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

課題の提出

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

課題１

• ★必修：課題１Ａ★

  授業で示した幅優先探索を行うプログラムについて、各ノードの深さを表示するように改良せよ。
  ただし最初のノードの深さを０とする。
  出力については、明白に読み取れるようになっていれば、特に表示形式は問わない。
  

  Graph G3

  #define N 8 int edge[N][N] = { /* 0 1 2 3 4 5 6 7 */ {0,1,0,0,1,0,0,0}, /* 0 */ {1,0,0,0,0,0,1,0}, /* 1 */ {0,0,0,1,0,0,1,0}, /* 2 */ {0,0,1,0,0,0,0,1}, /* 3 */ {1,0,0,0,0,1,0,0}, /* 4 */ {0,0,0,0,1,0,1,0}, /* 5 */ {0,1,1,0,0,1,0,1}, /* 6 */ {0,0,0,1,0,0,1,0} /* 7 */ };

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

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

  • 提出物〔1A-2〕：グラフG3に対して、出発点をノード０としたときの出力結果を保存したテキストファイル
    

  • 提出物〔1A-3〕：グラフG3に対して、出発点を「ノード７」としたときの出力結果を保存したテキストファイル
    

• ★必修：課題１Ｂ★

  深さ優先探索と幅優先探索の授業で示したアルゴリズムの其々について、 実行時に必要な書き込み可能メモリの空間計算量を見積もり、その違いを説明しなさい。
  ヒント：隣接行列は読み出して使うだけなので、この見積もりには入りません。
  

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

• ◆発展：課題１Ｘ◆

  課題１Ａのプログラム改良に加えて、全ノードについて、それぞれその深さを保証する経路を出発ノードから示すようにプログラムを改良しなさい。
  そのノードに同じ深さで到達できる経路が複数ある場合は、１つ示すだけで構いません。
  経路の表示方法は、それが読める形であれば形式は問いません。
  

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

  • 提出物〔1X-2〕：頂点０、頂点７を出発ノードとするグラフＧ３の処理結果を保存したテキストファイル