＝＝＝課題３＝＝＝ 受付開始日時 2015-05-12 12:00 受付終了日時 2015-05-18 18:00 閲覧設定 提出者本人と教員のみ閲覧・コメント可（個別指導） 学生による再提出の許可 再提出を許可する ●必須課題3-1[論述(pdf)] 深さ優先探索の説明 課題に関する説明 授業(3.2.節)で説明した、深さ優先探索アルゴリズムを日本語で書き下しなさい。 ・先頭に学籍番号・氏名・課題番号を示すこと。 ・曖昧性のないよう、明確に記述すること。 ・小学生にもわかる記述を心がけること。 ・簡潔な記述のほうがよい。（しかし舌足らずな表現は減点するので注意すること） ・Step-X や繰り返しなどの指示(プログラム構造)は適宜用いてよい。 ・授業内での説明に準じない説明は減点します。 ●必須課題3-2[プログラ(zip)] 深さ優先探索の実装 課題に関する説明 授業(3.2.節)で説明した、深さ優先探索プログラムの標準出力表示がわかりやすくなるよう、printfを適宜埋め込みなさい。 ・新しく数え上げる頂点については、数え上げ時に開始頂点（入口頂点）からの辺数を自動的に求めて表示すること。 ・注目する頂点が変わるたびにスタックの変化の様子が分かるように表示を工夫すること。 ・printfの表示が他人と同一・酷使の場合は減点対象。（ある程度似るのはやむを得ないと判断します） ・可能であれば、コマンドラインから開始頂点を指定できるようにすること。 ・以下のグラフG2-2(隣接行列)において、開始点を頂点０にした場合と、頂点６にした場合の結果をそれぞれ示すこと。 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・プログラムで工夫した部分があれば、何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・提出はkadai3-2.zipの形で出すこと。 ・ソースファイルはkadai3-2-1.c ・実行結果を収めたテキストファイルはkadai3-2-2.txt ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ●必須課題3-3[論述(pdf)] スタックとキューの説明 課題に関する説明 スタックとキューの概念を説明しなさい。 ・先頭に学籍番号・氏名・課題番号を示すこと。 ・スタックとキューはそれぞれ動作の様子を図示すること。 ・スタックとキューの違いが際立つように説明すること。 ●必須課題3-4[論述(pdf)] トポロジカルソートの説明 課題に関する説明 授業(3.3.節)で説明した、トポロジカルソートのアルゴリズムを日本語で書き下しなさい。 ・先頭に学籍番号・氏名・課題番号を示すこと。 ・曖昧性のないよう、明確に記述すること。 ・小学生にもわかる記述を心がけること。 ・簡潔な記述のほうがよい。（しかし舌足らずな表現は減点するので注意すること） ・Step-X や繰り返しなどの指示(プログラム構造)は適宜用いてよい。 ・授業内での説明に準じない説明は減点します。 ◇発展課題3-A[プログラム(zip)] グラフの深さ 課題に関する説明 あるグラフ（無向・連結）が与えられたとき、一つの頂点を根(root)とすると、そのグラフの「深さ」を、根からの辺数がもっともかかる頂点への辺数として考えることができます。 ・ある一つの頂点を根に指定された場合の、与えられたグラフの深さを求めるプログラムを作成しなさい。 ・さらに、あるグラフが与えられて、根をどの頂点にしてもよい場合、そのグラフの深さの最小値と最大値を求めるプログラムを作成しなさい。 ・以下のグラフG2-2(隣接行列)において、実行結果を示しなさい。 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 ・作成したプログラムの時間計算量をオーダー表現で示しなさい。その理由も記述すること。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・プログラムで工夫した部分があれば、何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・提出はkadai3-A.zipの形で出すこと。 ・ソースファイルはkadai3-A-1.c ・実行結果を収めたテキストファイルはkadai3-A-2.txt ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ◇発展課題3-B[プログラム(zip)] 有向無向と連結の判定 課題に関する説明 あるグラフが隣接行列で与えられたとします。そのグラフの有向無向と連結性について判定するプログラムを書きなさい。 ・すべての辺が無向である場合のみ、無向グラフと判定します。 ・無向グラフであるときのみ、連結性の判定をさらにします。 ・任意に２つの頂点を取り上げ、他の頂点を通過してもよいと考えて一つからもう一方に必ず移動できるとき、そのグラフは連結であるとします。 ・時間計算量のオーダーがＮの２乗内に収まるように工夫することが望ましいです。 ・以下のグラフG3-B-1(隣接行列)は有向です。実行結果を確認しなさい。 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 ・以下のグラフG3-B-3(隣接行列)は無向で非連結です。実行結果を確認しなさい。 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 ・作成したプログラムの時間計算量をオーダー表現で示しなさい。その理由も記述すること。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・プログラムで工夫した部分があれば、何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・提出はkadai3-B.zipの形で出すこと。 ・ソースファイルはkadai3-B-1.c ・実行結果を収めたテキストファイルはkadai3-B-2.txt 【補足】 ・以前(rev1)で掲載していたグラフG3-B-2(隣接行列)は無向で連結でした。すみません。 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 以上