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

科目基礎情報

学校	新居浜工業高等専門学校	開講年度	平成29年度 (2017年度)
授業科目	アルゴリズムとデータ構造
科目番号	121433	科目区分	専門 / 必修
授業形態	講義	単位の種別と単位数	履修単位: 2
開設学科	電気情報工学科	対象学年	4
開設期	通年	週時間数	2
教科書/教材	アルゴリズムとデータ構造　　湯田 幸八・伊原 充博　共著　（コロナ社）
担当教員	先山 卓朗

到達目標

1. ポインタを利用したリストについて、その概念や実現方法が理解できること。
2. スタックとキューについて、その概念や違いを理解できること。
3. 木の構造や走査について、その概念や各種手法を理解できること。
4. いろいろな探索手法について、その概念や実現方法が理解できること。
5. いろいろなソート手法について、その概念や実現方法が理解できること。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
ポインタを利用したリストについて、その概念や実現方法が理解できる	ポインタを利用したリストについて、その概念や実現方法を理解し、実装することができる。	ポインタを利用したリストについて、その概念や実現方法が理解できる。	ポインタを利用したリストについて、その概念や実現方法が理解できない。
スタックとキューについて、その概念や違いを理解できる	ポインタを利用したリストについて、その概念や実現方法を理解し、使い分けることができる。	スタックとキューについて、その概念や違いを理解できる。	スタックとキューについて、その概念や違いを理解できない。
木の構造や走査について、その概念や各種手法を理解できる	木の構造や走査について、その概念や各種手法を理解でき、使い分けることができる。	木の構造や走査について、その概念や各種手法を理解できる。	木の構造や走査について、その概念や各種手法を理解できない。
いろいろな探索手法について、その概念や実現方法が理解できる	いろいろな探索手法について、その概念や実現方法、効率の違いを理解できる。	いろいろな探索手法について、その概念や実現方法が理解できる。	いろいろな探索手法について、その概念や実現方法が理解できない。
いろいろなソート手法について、その概念や実現方法が理解できる	いろいろなソート手法について、その概念や実現方法、効率の違いを理解できる。	いろいろなソート手法について、その概念や実現方法が理解できる。	いろいろなソート手法について、その概念や実現方法が理解できない。

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

工学基礎知識 (A)

教育方法等

概要:

基本的なデータ構造であるリスト、キュー、木について修得し、さらにこれらのデータ構造を利用して実現できる探索や整列のアルゴリズムについて学ぶ。

授業の進め方・方法:

プログラミング１・プログラミング２で学んできたＣ言語の文法的知識をもとに、より高度なデータ構造やアルゴリズムの実現方法について勉強することになります。
授業を一方的に聞くだけでなく、その概念や動作を自分で理解できるよう頑張ってください。特に、教科書で省略されているＣプログラムを自分で考えることは非常に重要です。

注意点:

事前学習：プログラミング１・プログラミング２の知識が必要となるので、よく復習しておいてください。
自己学習：授業でいろいろなプログラムの学習をしますが、実際にパソコンで動かすことはしないので、各自実施してみてください。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	アルゴリズムの計算量の評価	1
		2週	データ構造と表現法　配列による順配置	1,2
		3週	ポインタ・構造体の復習	1,3
		4週	ポインタによるリンク配置	1,3
		5週	順配置によるリストの実現	1
		6週	ポインタによるリンク配置の実現１	1
		7週	ポインタによるリンク配置の実現２	1
		8週	中間試験
	2ndQ
		9週	双方向連結リスト	1
		10週	スタック	2
		11週	キュー	2
		12週	木の概念	3
		13週	２分木	3
		14週	２分木の走査	3
		15週	２分木と数式	3
		16週	期末試験
後期
	3rdQ
		1週	線形探索・２分探索	4
		2週	ハッシュ法探索	4
		3週	文字列の探索１	4
		4週	文字列の探索２	4
		5週	２分木の探索１	4
		6週	２分木の探索２	4
		7週	Ｂ木	4
		8週	中間試験
	4thQ
		9週	選択によるソート	5
		10週	交換によるソート１	5
		11週	交換によるソート２	5
		12週	クイックソート１	5
		13週	クイックソート２	5
		14週	挿入によるソート	5
		15週	いろいろなソート	5
		16週	期末試験

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

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

評価割合

	試験	レポート・小テスト	相互評価	態度	ポートフォリオ	その他	合計
総合評価割合	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