情報処理Ⅲ

科目基礎情報

学校	北九州工業高等専門学校	開講年度	平成28年度 (2016年度)
授業科目	情報処理Ⅲ
科目番号	0061	科目区分	専門 / 必修
授業形態	授業	単位の種別と単位数	履修単位: 1
開設学科	電子制御工学科	対象学年	4
開設期	前期	週時間数	2
教科書/教材	データ構造とアルゴリズム（五十嵐 健夫）
担当教員	才田 聡子

到達目標

1. アルゴリズムとデータ構造の概念を理解できる。
2. 時間計算量などによってアルゴリズムを比較・評価できることを理解できる。
3. リスト構造についてその概念と操作方法、表現方法、計算量を説明できる。
4. 木構造についてその概念と操作方法、表現方法、計算量を理説明きる。
5. 代表的なソートについてその概念と計算量を理解できる。

ルーブリック

	理想的な到達レベルの目安	優れた到達レベルの目安(良)	最低限必要な到達レベルの目安(良)	未到達レベルの目安
アルゴリズムの概念	アルゴリズムについて、その概念を説明できる。与えられた問題を抽象化しアルゴリズムを適用できる。問題を解決するための手段としてプログラムを用いたアルゴリズムを実装し解決することができる。	アルゴリズムについて、その概念を説明できる。与えられた問題を抽象化しアルゴリズムを適用できる。	アルゴリズムについて、その概念を説明できる。	アルゴリズムについて、その概念を説明できない。
計算量の理解	計算量とは何かを説明できる。各種アルゴリズムにおける計算量を把握することができる。プログラムの記述から必要な計算量を見積もることができる。	計算量とは何かを説明できる。各種アルゴリズムにおける計算量を把握することができる。	計算量とは何かを説明できる。	計算量とは何かを説明できない。
データ構造	データ構造の概念を説明できる。データの並び方からデータ構造を推測できる。問題解決のためにどのようなデータ構造を用いればよいか説明できる。プログラムを用いてデータ構造を実現できる。	データ構造の概念を説明できる。データの並び方からデータ構造を推測できる。問題解決のためにどのようなデータ構造を用いればよいか説明できる。	データ構造の概念を説明できる。	データ構造の概念を説明できない。
集合	データの集合について様々な表現方法があることを理解し説明できる。問題を解決するためにどのような表現を用いればよいのかを理解している。プログラムを用いて集合を実現できる。	データの集合について様々な表現方法があることを理解し説明できる。問題を解決するためにどのような表現を用いればよいのかを理解している。	データの集合について様々な表現方法があることを理解している。	データの集合について様々な表現方法があることを理解していない。
整列	データを整列させるための様々なソートアルゴリズムを理解し説明できる。データの並びに適したソートアルゴリズムを選択することができる。プログラムを用いてソートアルゴリズムを実装することができる。	データを整列させるための様々なソートアルゴリズムを理解し説明できる。	データを整列させるための様々なソートアルゴリズムを理解している。	データを整列させるための様々なソートアルゴリズムを理解していない。

教育方法等

概要:

本授業では、プログラムを作成する際、どのような処理が多く行われるかを判断し、空間・時間計算量を考慮して適切なデータ構造とアルゴリズムを考えることができるようになることを目的とする。授業ではプログラムを作るために理解しておかなければならない必要知識の要ともいえる、データ構造とアルゴリズムについて、その特徴や利点を学ぶ。

授業の進め方・方法:

教科書を使った講義を中心に授業を進めるが、教科書の内容から離れることもあるので、各自学習ノートを充実させること。また、理解を深めるために適宜問題演習を行 い、アルゴリズムの実装法をプログラムによって理解する。

注意点:

ポインタや構造体などの C 言語の知識が必要である。各授業で学習するテーマと予習するポイントを事前に予告し、毎回簡単な小テストを実施して事前知識と授業の理解度を確認しながら進めていくため、講義前に教科書 などを読み、テーマの要点と疑問点を整理しておくことが望ましい。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス	授業の進め方の確認、評価方法について理解してもらう。
		2週	アルゴリズムと計算量１	ユークリッドの互除法、線形探索、２分探索を理解するとともに、計算量について学ぶ。
		3週	アルゴリズムと計算量２	ユークリッドの互除法、線形探索、２分探索をC言語プログラミングで実装してみる。
		4週	データ構造１	配列とリストの違い、スタックと待ち行列の違い、循環配列、木について概念を理解する。
		5週	データ構造２	配列、リスト、スタック、待ち行列、循環配列、木をC言語プログラミングで実装してみる。
		6週	集合の表現法１	ヒープ、２分探索木、2-3木による平衡木の実現について概念を理解する。
		7週	集合の表現法２	ヒープ、２分探索木、2-3木による平衡木の実現についてプログラミングによる実装を行う。
		8週	中間試験
	2ndQ
		9週	集合の表現法３	ハッシュ（チェイン法と開番地法）、集合群について概念を学ぶ
		10週	集合の表現法４	ハッシュ（チェイン法と開番地法）、集合群についてプログラミングによる実装を行う。
		11週	整列１	バブルソート、クイックソート、マージソートについて概念を学ぶ
		12週	整列２	バブルソート、クイックソート、マージソートについてプログラミングによる実装を行う。
		13週	整列３	ヒープソート、バケットソート、基数ソートについて概念を学ぶ。
		14週	整列３	ヒープソート、バケットソート、基数ソートについてプログラミングによる実装を行う。
		15週	プログラミング	アルゴリズムとデータ構造の実装に必要なプログラミングについて学ぶ
		16週	定期試験

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

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	プログラミング	変数とデータ型の概念を説明できる。	3
				代入や演算子の概念を理解し、式を記述できる。	3
				制御構造の概念を理解し、条件分岐や反復処理を記述できる。	3
				プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。	3
				与えられた問題に対して、それを解決するためのソースプログラムを記述できる。	3
				ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。	2
				主要な言語処理プロセッサの種類と特徴を説明できる。	2
				ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。	2
			ソフトウェア	アルゴリズムの概念を説明できる。	3
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	3
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	3
				時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。	3
				整列、探索など、基本的なアルゴリズムについて説明できる。	3
				コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。	3
				同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。	3
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。	3
				ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。	3
				同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。	3

評価割合

	定期試験	小テスト	取り組み姿勢	態度の良さ	態度の悪さ		合計
総合評価割合	60	25	15	40	-40	0	100
基礎的能力	60	25	15	40	-40	0	100
専門的能力	0	0	0	0	0	0	0
分野横断的能力	0	0	0	0	0	0	0