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

科目基礎情報

学校	長野工業高等専門学校	開講年度	2017
授業科目	アルゴリズムとデータ構造
科目番号	0031	科目区分	専門 / 必修
授業形態	授業	単位の種別と単位数	履修単位: 2
開設学科	電子情報工学科	対象学年	3
開設期	通年	週時間数	2
教科書/教材	教科書：紀平拓男・春日伸弥「プログラミングの宝箱 アルゴリズムとデータ構造」ソフトバンククリエイティブ，教員が用意するテキスト
担当教員	伊藤 祥一

到達目標

各種アルゴリズムの計算量を計算できること，数値計算の誤差要因について説明できること，学習したアルゴリズムをC言語で実装できることで，学習・教育目標(D-1)および(D-2)の達成とする．

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
理論	各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができ，計算量の削減や計算誤差の縮小について述べることができる．	各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができる．	各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができない．
実装	学習したアルゴリズムのC言語による実装ができ，高速化などの工夫を盛り込める．	学習したアルゴリズムのC言語による実装が概ねできる．	学習したアルゴリズムのC言語による実装ができない．

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

(D-1)

(D-2)

教育方法等

概要:

優れたプログラムを作成するうえで必須の知識であるアルゴリズムとデータ構造について，計算量を中心にその基本概念を学習する．学習したアルゴリズムを実際にC言語により実装する．

授業の進め方・方法:

・授業方法は演習を中心とする．
・適宜，レポート課題を課すので，期限に遅れず提出すること．

注意点:

＜成績評価＞レポート(100%)の100点満点で(D-1)及び(D-2)を総合的に評価する．6割以上獲得した者をこの科目の合格者とする．
＜オフィスアワー＞月曜日16:00 ～ 17:00，電子情報工学科棟第4教員室．
＜先修科目・後修科目＞先修科目は情報処理，後修科目はシミュレーション・オブジェクト指向となる．
＜備考＞ノートPCを使用する．

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	アルゴリズムの基本概念	アルゴリズムにおける計算量を理解することができる．
		2週	データ構造の基本概念1	配列，リスト，スタック，キューを理解することができる．
		3週	データ構造の基本概念2	配列，リスト，スタック，キューを理解することができる．
		4週	木構造とヒープ1	木構造について理解し，その計算量が計算できる．
		5週	木構造とヒープ2	木構造について理解し，その計算量が計算できる．
		6週	演習1	ヒープを実装することができる．
		7週	ヒープソート	ヒープソートを実装することができる．
		8週	選択ソートとバブルソート	2つのアルゴリズムについて学習し，アルゴリズムの特徴が説明できる．
	2ndQ
		9週	挿入ソートとシェルソート1	2つのアルゴリズムについて学習し，アルゴリズムの特徴が説明できる．
		10週	挿入ソートとシェルソート2	2つのアルゴリズムについて学習し，アルゴリズムの特徴が説明できる．
		11週	クイックソート1	クイックソートを実装することができる．
		12週	クイックソート2	クイックソートを実装することができる．
		13週	文字列探索アルゴリズム1	文字列探索におけるKMP法とBM法について学習し，その違いが説明できる．
		14週	文字列探索アルゴリズム2	文字列探索におけるKMP法とBM法について学習し，その違いが説明できる．
		15週	演習2	Boyer-Moore法を実装することができる．
		16週	※15週以外で試験等を行う場合は入力ください．
後期
	3rdQ
		1週	数の内部表現	IEEE754による数の内部表現について理解することができる．
		2週	数値計算の誤差	種々の誤差要因について理解することができる．
		3週	数値計算の誤差	種々の誤差要因について理解することができる．
		4週	多倍長演算1	多倍長演算に必要なデータ構造を設計できる．
		5週	多倍長演算2	多倍長演算に必要な周辺ルーチンを作成できる．
		6週	多倍長演算3	多倍長演算に必要な周辺ルーチンを作成できる．
		7週	多倍長演算4	多倍長演算に必要な加算と減算のルーチンを作成できる．
		8週	多倍長演算5	多倍長演算に必要な加算と減算のルーチンを作成できる．
	4thQ
		9週	多倍長演算6	多倍長演算に必要な乗算と除算のルーチンを作成できる．
		10週	多倍長演算7	多倍長演算に必要な乗算と除算のルーチンを作成できる．
		11週	多倍長演算8	四則演算ルーチンを使って平方根や三角関数などの数学関数を作成できる．
		12週	Newton法と二分法1	方程式f(x)=0を反復解法によって解くことができる．
		13週	Newton法と二分法2	方程式f(x)=0を反復解法によって解くことができる．
		14週	無理数の多倍長計算と性能評価1	多倍長演算ルーチンによりeやπなどの値を計算し，精度や速度について評価することができる．
		15週	無理数の多倍長計算と性能評価2	多倍長演算ルーチンによりeやπなどの値を計算し，精度や速度について評価することができる．
		16週	※15週以外で試験等を行う場合は入力ください．

評価割合

	試験	小テスト	平常点	レポート	その他	合計
総合評価割合	0	0	0	100	0	100
配点	0	0	0	100	0	100