＝＝＝課題２＝＝＝ 受付開始日時 2015-04-28 16:00 受付終了日時 2015-05-12 18:00 【変則】 閲覧設定 提出者本人と教員のみ閲覧・コメント可（個別指導） 学生による再提出の許可 再提出を許可する ●必須課題2-1[論述(pdf)] 幅優先探索の説明 課題に関する説明 授業(3.1.節)で説明した、幅優先探索アルゴリズムを日本語で書き下しなさい。 ・先頭に学籍番号・氏名・課題番号を示すこと。 ・曖昧性のないよう、明確に記述すること。 ・小学生にもわかる記述を心がけること。 ・簡潔な記述のほうがよい。（しかし舌足らずな表現は減点するので注意すること） ・Step-X や繰り返しなどの指示(プログラム構造)は適宜用いてよい。 ・授業内での説明に準じない説明は減点します。 ●必須課題2-2[プログラ(zip)] 幅優先探索の実装 課題に関する説明 授業(3.1.節)で説明した、幅優先探索プログラムの標準出力表示がわかりやすくなるよう、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 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・プログラムで工夫した部分があれば、何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・提出はkadai2-2.zipの形で出すこと。 ・ソースファイルはkadai2-2-1.c ・実行結果を収めたテキストファイルはkadai2-2-2.txt ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ●必須課題2-3[論述(pdf)] 幅優先探索の計算量 課題に関する説明 授業(3.1.節)で説明した、幅優先探索プログラムについて、空間計算量と時間計算量とを入力量（頂点数Ｎ）に対するオーダー表現で示しなさい。その導出過程も説明しなさい。 ・必要があればプログラムソースの一部を示すこと。 ・空間計算量については、メモリ使用量の観点から論じること。 ・時間計算量については、最もよく訪れる文を訪れる回数で論じること。 ●必須課題2-4[論述(pdf)] 幅優先探索の適用性 課題に関する説明 授業(3.1.節)で説明した、幅優先探索のアルゴリズムは、一般に有向グラフに適用可能ですか。はい・いいえで答え、その理由を説明しなさい。 ・本問では、頂点間の移動はアルゴリズムに沿って行うものとします。 ◇発展課題2-A[プログラム(zip)] 幅優先探索の計算量確認 課題に関する説明 課題2-3に合わせて、時間計算量を実際に調べるプログラムを作成し、結果を議論しなさい。 ・課題2-2のグラフG2-2において、開始点を頂点０から頂点７まで、それぞれで実行した場合の結果を示すこと。 ・課題2-3のオーダー表現と結果がどれほど一致しているか議論し、異なる場合はその理由を考察しなさい。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・グラフは授業中で説明したものを利用すること。 ・プログラムで工夫した部分があれば、何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ・提出はkadai2-A.zipの形で出すこと。 ・ソースファイルはkadai2-A-1.c ・実行結果を収めたテキストファイルはkadai2-A-2.txt ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。