データ構造

学校	弓削商船高等専門学校	開講年度	令和03年度 (2021年度)
授業科目	データ構造
科目番号	0018	科目区分	専門 / 選択
授業形態	授業	単位の種別と単位数	学修単位: 2
開設学科	生産システム工学専攻	対象学年	専1
開設期	前期	週時間数	2
教科書/教材	E-learning サイト：http://moodle2021.center.yuge.ac.jp
担当教員	長尾和彦

プログラミングは計算機による問題解決の唯一の手段である。本講義は、プログラミング作業を形式化したオブジェクト指向プログラミング、デザインパターンの概念について解説し、問題解決法の習得を目標とする。

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
アルゴリズムと計算量	アルゴリズムの計算量を増加率で算出できる	アルゴリズムの計算量の定義を理解できる	計算量の定義が理解できない
基本的データ構造	リスト・スタック・キューのデータ構造の特徴と実現方法を示すことができる	リスト・スタック・キューのデータ構造の特徴を示すことができる	リスト・スタック・キューのデータ構造の用途を説明できない
順序つき集合	優先順序付き待ち行列・２分探索木が実装できる	優先順序付き待ち行列・２分探索木が説明できる	優先順序付き待ち行列・２分探索木が説明できない
ソート	バブル・バケット・ヒープ・クイックのアルゴリズムが実装できる	バブル・バケット・ヒープ・クイックのアルゴリズムが利用できる	バブル・バケット・ヒープ・クイックのアルゴリズムが理解できない
アルゴリズムの設計手法	力ずく法、欲張り法、分割統治法、動的計画法のアルゴリズムによる実装ができる	力ずく法、欲張り法、分割統治法、動的計画法のアルゴリズムの説明ができる	力ずく法、欲張り法、分割統治法、動的計画法の説明ができない

専門 A1 説明

専門 A2 説明

教養 B2 説明

教養 D1 説明

教養 D2 説明

専門 E1 説明

専門 E2 説明

概要:

授業の進め方・方法:

演習のプログラム言語として、Java・Processing などを用いる。
本講義は豊橋技術科学大学の対応科目の遠隔受講により、オンデマンド形式で学習を進めること。
学習記録をmoodleに残す。

注意点:

達成目標全体の達成度を総合的に評価する最終試験により評価する．
最終試験では，データ構造やアルゴリズムの仕組み（メカニズム）を理解しているかどうかに重点を置く．

参考書：平田富夫，「アルゴリズムとデータ構造―改訂C言語版」森北出版，2002

アクティブラーニング	ICT 利用	遠隔授業対応	実務経験のある教員による授業

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス・受講登録	授業目的を理解し、moodleの使い方について体験する。自習課題：遠隔授業の方法に習熟する
		2週	アルゴリズムとその計算量（問題と問題例/計算量の評価/オーダー表記）	豊橋技科大の資料に基づき自主学習を行う
		3週
		4週	基本的なデータ構造（リスト，スタック，キュー）
		5週
		6週	グラフと木，木の用語，木のデータ構造，動的木，木の高さの解析
		7週
		8週	探索のためのデータ構造（順序つき集合）：2分探索，2分探索木，平衡探索木，ハッシング（辞書）
	2ndQ
		9週
		10週	整列（ソーティング）：バケットソート（基数ソート)，ヒープソート，分割統治法(クイックソート，マージソート)，クイックソートの平均計算量，計算量の下界
		11週
		12週	その他，発展的話題：順序統計量，Union-Find問題，最小全域木問題など
		13週
		14週
		15週	達成度テスト	プリントによる試験実施を予定
		16週	試験問題の解説