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

科目基礎情報

学校	津山工業高等専門学校	開講年度	令和03年度 (2021年度)
授業科目	アルゴリズムとデータ構造
科目番号	0018	科目区分	専門 / 必修
授業形態	講義	単位の種別と単位数	学修単位: 4
開設学科	情報工学科	対象学年	4
開設期	通年	週時間数	2
教科書/教材	教科書：茨木俊秀「Cによるアルゴリズムとデータ構造(改訂2版)」（オーム社）, 参考書：J. ホップクロフト他「オートマトン言語理論 計算論〈1〉」
担当教員	菊地 洋右

到達目標

学習目的：代表的なアルゴリズムやデータ構造の仕組みについて説明できる，または説明を読めばその名称が答えられる。アルゴリズムの効率を考える際に重要となる時間計算量などの基本的概念や用語を説明できる。

到達目標
１．アルゴリズムとは何かを説明できる。
２．ソート，探索に関する代表的なアルゴリズムを説明できる。
３．スタック，キュー，二分木などのデータ構造を説明できる。
４．情報のグラフ表現を使える。
５．文字列検索アルゴリズムを説明できる。
６．形式言語とオートマトンについて説明できる。

ルーブリック

	優	良	可	不可
評価項目1	計算量の表記とその定義を何も見ずに書くことができ，その意味を説明できる。	計算量の表記とその定義を，ノートを見ながら書くことができ，その意味を説明できる。	計算量の表記とその定義を，ノートを見ながら書くことができる。	計算量の表記とその定義を知らない。
評価項目2	ソート，探索のアルゴリズムを実装できる。かつそのプログラムに不備があった場合に修正できる。	ソート，探索のアルゴリズムを実装できる。	ソート，探索に関する代表的なアルゴリズムを説明できる。	ソート，探索に関する代表的なアルゴリズムを説明できない。
評価項目3	スタック，キュー，２分木などのデータ構造を必要に応じて利用したプログラムが実装できる。	スタック，キュー，２分木などのデータ構造を利用したプログラムが実装できる。	スタック，キュー，２分岐などのデータ構造を説明できる。	スタック，キュー，２分岐などのデータ構造を説明できない。
評価項目4	グラフ構造を用いたアルゴリズムを説明でき，その計算量を求めることができる。	グラフ構造を用いたアルゴリズムを説明できる。	情報のグラフ表現を使える。	グラフ構造を知らない。
評価項目5	文字列検索アルゴリズムを3つ以上知っていて、それらについて説明できる。	文字列検索アルゴリズムを２つ以上知っていて，それらについて説明できる。	文字列検索アルゴリズムを１つ以上知っていて，それらについて説明できる。	文字列検索アルゴリズムを知らない。
評価項目6	ポンプ補題を使って正規言語でないことを証明できる。	正規言語に対して、それを受理するオートマトンが図示できる。	文字列がオートマトンで受理されるかどうか判定できる。	文字列がオートマトンで受理されるかどうか判定できない。

教育方法等

概要:

一般・専門の別：専門
学習の分野：情報システム・プログラミング・ネットワーク

基礎となる学問分野：総合系／情報学／計算基盤／ソフトウェア

学習教育目標との関連：本科目は総合理工学科学習・学習教育目標「③基盤となる専門性の深化」に相当する科目である。

MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), データ構造(4), プログラム解析(4), V-D-5 システムプログラミングのコンパイラ(4) V-D-7 情報数学・情報理論の離散数学応用(4) が設定されている。

技術者教育プログラムとの関連：本科目が主体とする学習・教育目標は「（Ａ）技術に関する基礎知識の深化，Ａ－２:｢電気・電子｣，｢情報・制御｣に関する専門技術分野の知識を修得し，説明できること」である。

授業の概要：コンピュータを使って問題解決をする場合，使用するアルゴリズムとデータ構造が異なると問題解決の効率が違ってくる。本科目では，これらの選択能力や設計能力の基礎を修得するため，代表的なアルゴリズムとデータ構造を題材にそれらの仕組み等を学習する。

授業の進め方・方法:

授業の方法：板書を中心に授業を進めるが，できるだけ学生に質問し，学生の理解度を確かめながら授業を進める。また学生による発表も取り入れる。理解が深まるよう，演習などを課す。

成績評価方法：4回の定期試験の結果に重みを付け評価する。再試験は原則行わない。ただし，定期試験の結果をもって単位認定を正当に結論できないと判断した場合には再試験を行う。ルーブリックに基づいて定期試験を作成するが，定期試験がルーブリックの評価項目を必ずしも網羅しているとは限らない。

注意点:

履修のアドバイス：本科目はこれまでに履修してきた数学やプログラミングに関する科目と深く関連している。本科目で学習した内容を積極的に活用したプログラムを書くことでより理解が深まる。事前に行う準備学習としてBlackboardで告知されるテーマについて教科書で確認しておくこと。

履修上の注意：学年の課程修了のためには履修（欠席時間数が所定授業時間数の３分の１以下）が必須である。

基礎科目：総合理工基礎（１年），プログラミング基礎（2）

関連科目：データベース（５年），プログラミング応用（4），情報数理（4）

受講上のアドバイス：授業開始前に行う出席確認に遅れた者は遅刻として扱う。遅刻は1時限分の欠課として扱う。授業開始から５０分を経過しての遅刻については2時限分の欠課として扱う。BlackBoardに授業の進行状況を適宜掲載するので参考にすること。

授業の属性・履修上の区分

ICT 利用

遠隔授業対応

実務経験のある教員による授業

必履修

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス〔科目の概要，目的，評価方法，注意事項等〕	本科目の位置づけを理解する。
		2週	アルゴリズムと計算量	実社会の問題を数理モデルとして定式化できる例を挙げられる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), V-D-7 情報数学・情報理論の離散数学応用(4)
		3週	基本的なデータ構造　１	問題を数理モデルとして定式化するときにデータ構造を2つ以上候補として挙げられる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのデータ構造(4)
		4週	基本的なデータ構造　２	問題を数理モデルとして定式化するときに適切なデータ構造を設計できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのデータ構造(4)
		5週	ソート・アルゴリズム　１	バブルソート、インサーションソートを説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4) V-D-7 情報数学・情報理論の離散数学応用(4)
		6週	ソート・アルゴリズム　２	クイックソート、マージソートなどを説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4) V-D-7 情報数学・情報理論の離散数学応用(4)
		7週	ソート・アルゴリズム　３	バケットソートを説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4) V-D-7 情報数学・情報理論の離散数学応用(4)
		8週	ソートの計算量	ソートの計算量について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4) V-D-7 情報数学・情報理論の離散数学応用(4)
	2ndQ
		9週	（前期中間試験）	自分の知識を確認する。
		10週	答案返却と解説，演習	自分の知識で不足している箇所を認識し、改善する。
		11週	木のデータ構造　１	2分探索木，平衡木について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのデータ構造(4)
		12週	木のデータ構造　２	B木について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのデータ構造(4)
		13週	グラフ・アルゴリズム　１	グラフを数理モデルとして使うことができる。グラフのデータ構造を説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのデータ構造(4) , V-D-7 情報数学・情報理論の離散数学応用(4)
		14週	グラフ・アルゴリズム　２	深さ優先探索，幅優先探索について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4), V-D-7 情報数学・情報理論の離散数学応用(4)
		15週	（前期末試験）	自分の知識を確認する。
		16週	前期末試験の答案返却と試験解説	自分の知識で不足している箇所を認識し、改善する。
後期
	3rdQ
		1週	グラフ・アルゴリズム　３	最短経路問題を解くアルゴリズムを利用できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4), V-D-7 情報数学・情報理論の離散数学応用(4)
		2週	グラフ・アルゴリズム　４	ネットワークフローを解くアルゴリズムを利用できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4) , V-D-7 情報数学・情報理論の離散数学応用(4)
		3週	文字列検索アルゴリズム　１	ラビン-カープ法について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4)
		4週	文字列検索アルゴリズム　２	クヌース-モリス-プラッツ法について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4)
		5週	文字列検索アルゴリズム　３	ボイヤー-ムーア法について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), プログラム解析(4)
		6週	貪欲算法と動的計画法　１	貪欲算法を説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4), V-D-7 情報数学・情報理論の離散数学応用(4)
		7週	貪欲算法と動的計画法　２	動的計画法を説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-2 ソフトウェアのアルゴリズム(4) V-D-7 情報数学・情報理論の離散数学応用(4)
		8週	計算可能性	計算不可能な問題の存在を知っている。
	4thQ
		9週	（後期中間試験）	自分の知識を確認する。
		10週	答案返却と解説	自分の知識で不足している箇所を認識し、改善する。
		11週	形式言語	形式言語の概念について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-5 システムプログラミングのコンパイラ(4)
		12週	オートマトン	オートマトンの概念について説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-5 システムプログラミングのコンパイラ(4)
		13週	正規表現とオートマトン	正規表現と有限オートマトンの関係を説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-5 システムプログラミングのコンパイラ(4)
		14週	コンパイラ	コンパイラの役割と仕組みについて説明できる。 MCC到達目標(平成29年4月28日ガイドライン準拠、カッコ内はレベル)：V-D-5 システムプログラミングのコンパイラ(4)
		15週	（後期末試験）	自分の知識を確認する。
		16週	後期末試験の答案返却と試験解説	自分の知識で不足している箇所を認識し、改善する。

モデルコアカリキュラムの学習内容と到達目標

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	ソフトウェア	アルゴリズムの概念を説明できる。	4
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	4
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	4
				時間計算量によってアルゴリズムを比較・評価できることを説明できる。	4
				領域計算量などによってアルゴリズムを比較・評価できることを説明できる。	4
				整列、探索など、基本的なアルゴリズムについて説明できる。	4
				コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。	4
				同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。	4
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。	4
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。	4
				ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。	4
				同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。	4
			システムプログラム	形式言語の概念について説明できる。	4
				形式言語が制限の多さにしたがって分類されることを説明できる。	4
				オートマトンの概念について説明できる。	4
				正規表現と有限オートマトンの関係を説明できる。	4
				コンパイラの役割と仕組みについて説明できる。	4
			情報数学・情報理論	離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。	4

評価割合

	試験	発表	相互評価	自己評価	課題	小テスト	合計
総合評価割合	100	0	0	0	0	0	100
基礎的能力	0	0	0	0	0	0	0
専門的能力	100	0	0	0	0	0	100
分野横断的能力	0	0	0	0	0	0	0