|
授業科目名
|
担当教員
|
|||||||||||||||||
|
アルゴリズムとデータ構造I演習
|
美濃 英俊／山本 泰生
|
|||||||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||||||
| 263115 A | 1 | CS | 2 | 前期 | 木 | IV | ||||||||||||
| ［概要］ | ||||||||||||||||||
| 本演習では，講義「アルゴリズムとデータ構造I」で学ぶ内容に関して，コンピュータを用いた演習を行うことを目的とする．幾つかの重要で具体的なアルゴリズムやデータ構造，及びアルゴリズムに関する一般的な技術を理解した上で，C++によって実際にプログラミングすることによって理解を深めさせる． | ||||||||||||||||||
| ［具体的な達成目標］ | ||||||||||||||||||
| 以下の4つの項目について学習し，それらのコーディング手法を習得する<BR>1. 2分木，ハッシュ表<BR>2. 最小スパニング木やトポロジカルソート等のグラフ探索<BR>3. Boyer-Moore法による文字列照合<BR>4. 動的プログラミング | ||||||||||||||||||
| ［必要知識・準備］ | ||||||||||||||||||
| 「プログラミング基礎」および「同演習」ならびに「プログラミング応用」および「同演習」を履修済みで (単位取得が望ましい)，C++言語の基本的知識とプログラミング技術を修得していること．履修にあたっては，上記の先行科目で学習した内容を必ず復習しておくこと． | ||||||||||||||||||
| ［評価方法・評価基準］ | ||||||||||||||||||
|
||||||||||||||||||
| ［教科書］ | ||||||||||||||||||
| ［参考書］ | ||||||||||||||||||
| ［講義項目］ | ||||||||||||||||||
| 第１回：二分木の応用（１）（プライオリティキュー）<BR>第２回：二分木の応用（２）（平衡探索木）<BR>第３回：中間評価１（二分木の復習とまとめ）<BR>第４回：標準テンプレートライブラリの利用<BR>第５回：ハッシュ表（１）（分離チェイン法，ハッシュ関数の設計）<BR>第６回：ハッシュ表（２）（開番地法，ハッシュ表の拡大） <BR>第７回：中間評価２ (ハッシュ表の復習とまとめ)<BR>第８回：グラフの探索と最小スパニング木<BR>第９回：最短経路問題<BR>第10回：トポロジカルソートとクリティカルパス問題<BR>第11回：期末評価１（探索アルゴリズムの復習とまとめ）<BR>第12回：文字列照合（１）力任せアルゴリズム <BR>第13回：文字列照合（２）Boyer-Moore法，レポート課題１<BR>第14回：動的プログラミング，レポート課題２<BR>第15回：期末評価２（文字列照合と動的プログラミングの復習および演習のまとめ） | ||||||||||||||||||
| ［教育方法］ | ||||||||||||||||||
| 演習課題は，授業のMoodleページに掲示する． | ||||||||||||||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||||||||||||||
| (未登録) | ||||||||||||||||||
| ［その他］ | ||||||||||||||||||
| (未登録) | ||||||||||||||||||