2012年後期 データ構造とアルゴリズム&プログラミング演習Ⅲ



  • 期末試験
    • 2月13日(水)3限。場所は後日公表。
    • 教科書、ノート、メモなどの持ちこみは不可。
    • 携帯、スマホなど、ネットにアクセスできる機器の持ちこみも不可。
    • 不正行為には厳罰をもって対処します。
    • 問題は、教科書からの穴埋め問題のみ。
      • 例題:次の()内を埋めよ。「「(    )法」は(中略)再帰を利用して“試行錯誤”をもれなく行うアルゴリズムです。(中略)ひたすら突き進み、処理が行き詰ってうまくいかなくなったら、別の選択肢に進むためにあと戻りしてやり直す、という猪突猛進的な方法です。」

  • 出席

  • 単位の取り方=実演チェック (自分がどの問題を残しているかはここで。2013年1月23日用に更新。)
    • シラバスにある参考書を入手する⇒プログラミングの宝箱 アルゴリズムとデータ構造 第2版external image 51w7xEA33iL.jpg
    • 各回、参考書にある以下のコードについて、「コードを表示し、それをコンパイルして、動作確認する」という一連の動作を目の前で実演してもらう。
      • その際、各コードの上部に指定した変更をコードに加え、それをコンパイルして、動作確認する、という一連の動作も目の前で実演してもらう。
      • 実演チェックは、一つのコードあたり、一人3分以内で終わらせる。3分で終わらない場合は、やりなおし。
    • 全てのコードについて実演チェックを受けないと、単位は出ない。
    • 教科書にあるすべてのソースコードはここからダウンロードできるが、この講義用に改変したコードもあるので、注意。
    • プログラミング演習Ⅲを受講していない人から順に、実演チェックする。


データ構造とアルゴリズム履修者の実演チェック

プログラミング演習Ⅲ履修者の実演チェック
(*印は難しい。それ以外は必ずチェックを受ける。)
もの足りない人のために(実演チェック不要)
1
バブルソート
List 1-1, List 1-2
1
クイックソート
List 1-3, List 1-4
コームソート
List 1-6
2
リニアサーチ
List 2-1
2
マージソート
List 1-5
挿入ソート
List 1-7, List 1-8
3
バイナリサーチ
List 2-3
3
構造体のサーチ
List 2-5
自己組織化探索
List 2-7
4
動的配列
List 3-3
4
--
(遅れている人の実演チェック or 自習)


5
リスト
List 3-4
5
リストのサーチ
List 3-5
リストを用いた自己組織化探索
List 3-7
6
スタック
List 4-1
6
キュー
List 4-5
スタックによる式の計算
List 4-3
7
再帰呼び出し
List 5-4
7
フィボナッチ数を求める
(ソースコード無し)
アッカーマン関数の計算
(ソースコード無し)
8
2分木
List 6-4
8
2分木と「マップ」(追加資料
List 6-5
逆ポーランド記法
List 12-1,List 12-2
9
ハッシュ関数
List 7-1, List 7-2
9
ハッシュマップ
List 7-3
テンパズル
List 12-3
10
誤差
List 8-1 ~ 8-4
10
複雑な方程式を解く
List 8-8
ニュートン法
(ソースコード無し)
11
文字列検索(追加資料
List 9-1
11
BM法(追加資料
List 9-3
KMP法
List 9-2
12
バックトラック
List 10-1
12
--
List 10-1(午前中の続き)
11パズル
List 10-2
13
動的計画法
List 11-1
13
11パズル
List 10-2
--
--
14
グラフの表現方法
List 13-3, List 13-4
14
ダイクストラ法
List 13-6
長崎電気軌道の最短路
(長崎駅より南の範囲で)
15
--
(遅れている人のチェック)
15
長崎電気軌道の最短路
(長崎駅より南の範囲で)
--
--

  • 欠席レポート
    • 欠席6回以上は不合格。
    • 欠席1回につき、ここにあるPDFファイルの中から任意の1ページを日本語に訳して masada (a) outlook.com にメールで提出。