＝＝＝課題４＝＝＝ 受付開始日時 2015-05-19 12:00 受付終了日時 2015-05-26 18:00 閲覧設定 提出者本人と教員のみ閲覧・コメント可（個別指導） 学生による再提出の許可 再提出を許可する ●必須課題4-1[論述(pdf)] 最長経路問題 課題に関する説明 ・先頭に学籍番号・氏名・課題番号を示すこと。 ・授業で説明した最長経路問題を解くアルゴリズムについて、前提となるグラフは以下の通りとする。 (1) 辺の重みは正値のみ認める。 (2) 頂点には重みを設けない。 (3) グラフ中に有向閉路がない。 (4) 最長経路には、一つの頂点は高々１つまで含まれる（同じ頂点を２回通ることはない）。 4-1-1. 前提の重複 上記の条件には、重複が含まれると考えられる。 重複があると考えられる部分を考察し、どのように簡略化できるかを着論しなさい。 4-1-2. 計算量 最長経路問題を解くアルゴリズムについて、アルゴリズムを３段階に分けて説明し、それぞれで時間計算量と空間計算量をオーダー表現で示せ。、 ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ●必須課題4-2[プログラム(zip)] トポロジカルソートを実現するプログラム 課題に関する説明 ・授業で説明したトポロジカルソートを実現するプログラムを実装しなさい。 ・コンパイル方法などに注意がある場合はその説明文を含めること。 ・実行結果を示すテキストファイルを含めること。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・プログラムで工夫した部分について、何かしらの説明をコメントの形でプログラム中に書き込むこと ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・実行のテスト時には下記を利用しなさい。 // 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 ・実行結果がわかるようにすること。一例として下記を挙げるが、この通りでなくともよい。 === トポロジカルソーティングを開始します。 TP: 頂点 0 をとりあえず呼び出してスタート！ TP: 結果 4 TP: 結果 5 TP: 結果 0 TP: 頂点 1 をとりあえず呼び出してスタート！ TP: 結果 1 TP: 頂点 2 をとりあえず呼び出してスタート！ TP: 結果 6 TP: 結果 2 TP: 頂点 3 をとりあえず呼び出してスタート！ TP: 結果 3 TP: 頂点 7 をとりあえず呼び出してスタート！ TP: 結果 7 TP: 終了。 4 5 0 1 6 2 3 7 === ◇発展課題4-A[プログラム(zip)] 最長経路問題を解くプログラム 課題に関する説明 ・授業で説明した最長経路問題を解くプログラムを実装しなさい。 ・課題4-2で提出したコードを（できるだけ、可能ならファイル単位で）再利用すること。 ・コンパイル方法などに注意がある場合はその説明文を含めること。 ・実行結果を示すテキストファイルを含めること。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・プログラムで工夫した部分について、何かしらの説明をコメントの形でプログラム中に書き込むこと ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・実行のテスト時には下記を利用しなさい。 // 0 1 2 3 4 5 6 7 0,4,0,0,2,0,0,0, // 0 0,0,0,0,0,0,1,0, // 1 0,0,0,3,0,0,3,0, // 2 0,0,0,0,0,0,0,5, // 3 0,0,0,0,0,2,0,0, // 4 0,0,0,0,0,0,0,0, // 5 0,0,0,0,0,4,0,1, // 6 0,0,0,0,0,0,0,0 // 7 ・実行結果がわかるようにすること。一例として下記を挙げるが、この通りでなくともよい。 === TS: 5 7 6 1 4 0 3 2 Longest Path Value = 9 5 <- 6 <- 1 <- 0 <- Go === 以上