科目名 データ構造とアルゴリズムⅡ
単位数 2.0
担当者 情報工学専攻 准教授 市原 英行(A,B,C,Dクラス担当)
知能工学専攻 准教授 黒木 進(E,F,G,Hクラス担当)
システム工学専攻 准教授 双紙 正和(I,J,K,Lクラス担当)
履修時期 前期
履修対象 2年次
概要 授業形態:講義

コンピュータによる高度なデータ処理を実現するために必要な基本概念である、データ構造とアルゴリズムについて学ぶ。特に、グラフや文字列に対する探索や照合のアルゴリズムや、基本的な最適化問題について学ぶ。
科目の到達目標 効率のよいアルゴリズムを作成する方法や、既存のアルゴリズムを分析する方法を身につける。
受講要件 講義科目「離散数学」、「データ構造とアルゴリズムⅠ」を履修していることが望ましい。
事前・事後学修の内容 教科書の演習問題に積極的に取り組んで、アルゴリズムの動作や特性を説明できるように自習する。また、講義で習った内容をプログラムにして実行する。
講義内容 1. 数学的基礎
2. ハッシュ表
3. 二分探索木(基本)
4. 二分探索木(応用)
5. 文字列照合
6. トライ
7. トポロジカルソート
8. 中間まとめ
9. グラフの連結成分
10. 最小木
11. 最短経路問題
12. バックトラック法
13. 分枝限定法
14. 動的計画法
15. まとめ
評価方法 テストの結果をもとにして総合的に評価する。評価基準は以下のとおりである。
合格(評価「可」):グラフや文字列に対するデータ構造およびアルゴリズムを説明できること。基本的な最適化問題について理解していること。
合格(評価「良」):合格(評価「可」)に加えて以下の条件1、2のいずれかを満たすこと。
合格(評価「優」):合格(評価「可」)に加えて以下の条件1、2の両方を満たすこと。
合格(評価「秀」):合格(評価「可」)に加えて以下の条件1、2の両方を高いレベルで満たすこと。
条件1 アルゴリズムおよびデータ構造の計算量とその根拠を説明できること。
条件2 アルゴリズムの正しさを説明できること。
教科書等 教科書:茨木俊秀著「Cによるアルゴリズムとデータ構造」(オーム社)
参考書:平田富夫著「アルゴリズムとデータ構造(改訂C言語版)」(森北出版)
     石畑清著「アルゴリズムとデータ構造」(岩波書店)
     浅野哲夫著「アルゴリズム・サイエンス:入口からの超入門」(共立出版)
     岩間一雄著「アルゴリズム・サイエンス:出口からの超入門」(共立出版)
     T.コルメンほか著「アルゴリズムイントロダクション」(近代科学社)
担当者プロフィール 授業内容に関する、学生の個別学習相談を随時受け付けています。
教員の所在は、学内サイネージ等に掲示されていますので、確認の上、研究室を訪ねてみてください。

市原:コンピュータの設計・テスト、フォールトトレランスの研究に従事。
黒木:マルチメディアデータベースの研究に従事。
双紙:セキュリティに関する研究に従事。
備考