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

課題の提出

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

課題１

• ★必修：課題１ａ★

  トポロジカルソートを行うプログラムを作成し、コンパイルして実行せよ。
  ただし、ソーティングを行うグラフは下記の２つを用意するので、どちらについても実行結果を示すこと。
  ソースコードはGraphAに対する実行時のものだけでよい。
  

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

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

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

    プログラム先頭の様子

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

  • 提出物〔1a-2〕：プログラムのグラフAに対する出力結果を保存したテキストファイル
    

  • 提出物〔1a-3〕：プログラムのグラフBに対する出力結果を保存したテキストファイル
    

• ★必修：課題１ｂ★

  有向グラフに対してトポロジカルソーティングを行う場合、そのグラフはどのような性質を満たす必要があるか考察せよ。

  • 提出物〔1b-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で提出すること。
    

• ◆発展：課題１ｐ◆

  連結無向グラフである隣接行列が与えられたときに、そのグラフ中に少なくとも１つの閉路があることを検出できるプログラムを作成せよ。
  ＜ヒント：閉路がないグラフは何と呼ばれるか？＞
  

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

  • 提出物〔1p-2〕：プログラムの出力結果を保存したテキストファイル
    閉路を含むグラフと閉路を含まないグラフの両方の隣接行列と実行結果を示すこと。
    与えるグラフは各自で用意してください。