データ構造とアルゴリズムⅡ

科目基礎情報

学校	茨城工業高等専門学校	開講年度	令和03年度 (2021年度)
授業科目	データ構造とアルゴリズムⅡ
科目番号	0086	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	履修単位: 1
開設学科	国際創造工学科　情報系	対象学年	4
開設期	前期	週時間数	2
教科書/教材
担当教員	蓬莱 尚幸

到達目標

1. アルゴリズムを分類することで、複数のアルゴリズムを体系的に説明できる。
2. 高速に検索するために発明された様々なデータ構造を説明できる。
3. 最適化で用いられる線形計画法と動的計画法を説明できる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
アルゴリズムの体系的な分類に関する説明・比較・評価	アルゴリズムの分類を用いて複数のアルゴリズムを体系的に説明できるとともに、それらを比較・実装・評価できる	アルゴリズムの分類を用いて複数のアルゴリズムを体系的に説明できる	アルゴリズムの分類を用いてアルゴリズムを体系的に説明できない
複数の平衡二分探索木に関する説明・比較・評価	複数の平衡二分探索木を説明できるとともに、それらを比較・実装・評価できる	平衡二分探索木を説明できる	平衡二分探索木を説明できない
最適化アルゴリズムjに関する説明・比較・評価	最適化アルゴリズムについて説明できるとともに、それらを比較・実装・評価できる	最適化アルゴリズムについて説明できる	組合せ最適化アルゴリズムについて説明できない

学科の到達目標項目との関係

学習・教育到達度目標 (A)

教育方法等

概要:

3年次「データ構造とアルゴリズムI」で学んだデータ構造とアルゴリズムの基礎の上に、より高度なデータ構造とアルゴリズムについて学ぶ。

授業の進め方・方法:

様々な問題に対するアルゴリズムを設計するためには、アルゴリズムを分類し体系的に理解することが重要になります。また、3年次では二分木を用いた探索について学びましたが、高速な探索を実行するためには木構造を平衡に保つ必要があります。さらに、最適化問題を解くための線形計画法と動的計画法についても学びます。これらの計画法はオペレーションズリサーチにおける1940～50年代の研究成果ですが、いまでも広く使われていおり、人工知能の研究へとつながりました。講義と演習をとおして様々なデータ構造とアルゴリズムを身につけましょう。

注意点:

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	分割統治法	マージソート、クイックソート、ストラッセンのアルゴリズム、最大部分配列問題を題材に分割統治法を学ぶ。
		2週	貪欲法	ダイクストラ法、アクティビティ選択問題を題材に貪欲法について学ぶ。
		3週	演習①	分割統治法と貪欲法のプログラムを作成する。
		4週	平衡二分探索木 (1)	赤黒木について学ぶ。
		5週	平衡二分探索木 (2)	AVL木について学ぶ。
		6週	演習②	赤黒木とAVL木のプログラムを作成する。
		7週	（中間試験）
		8週	平衡二分探索木 (3)	2-3木とB木について学ぶ。
	2ndQ
		9週	語彙のための探索木	トライ木とパトリシア木について学ぶ。
		10週	演習③	2-3木、B木、トライ木、パトリシア木のプログラムを作成する。
		11週	線形計画法	ダイエット問題、シンプレックス法を題材に線形計画法について学ぶ。
		12週	演習④	線形計画法のプログラムを作成する。
		13週	動的計画法	ロッド切り出し問題、最長共通部分列問題を題材に動的計画法について学ぶ。
		14週	演習⑤	動的計画法のプログラムを作成する。
		15週	（期末試験）
		16週	総復習

評価割合

	試験	レポート	相互評価	態度	ポートフォリオ	その他	合計
総合評価割合	70	30	0	0	0	0	100
基礎的能力	0	0	0	0	0	0	0
専門的能力	70	30	0	0	0	0	100
分野横断的能力	0	0	0	0	0	0	0