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

科目基礎情報

学校	北九州工業高等専門学校	開講年度	令和04年度 (2022年度)
授業科目	アルゴリズムとデータ構造Ⅰ
科目番号	0082	科目区分	専門 / 必修
授業形態		単位の種別と単位数	履修単位: 1
開設学科	生産デザイン工学科（情報システムコース）	対象学年	3
開設期	前期	週時間数	2
教科書/教材	渡部 有隆、プログラミングコンテスト攻略のためのアルゴリズムとデータ構造、マイナビ出版/AIZU ONLINE JUDGE
担当教員	白濵 成希

到達目標

1. アルゴリズムの概念、及びアルゴリズムが問題を解決していく過程を説明できる。
2. 整列、探索など、基本的なアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。
3. 時間計算量・領域計算量によってアルゴリズムを比較・評価できることを説明できる。
4. リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明・実装できる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	アルゴリズムの概念、及びアルゴリズムが問題を解決していく過程を特徴を踏まえて説明できる。	アルゴリズムの概念、及びアルゴリズムが問題を解決していく過程を説明できる。	アルゴリズムの概念、及びアルゴリズムが問題を解決していく過程を説明できない。
評価項目2	整列、探索など、基本的なアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを特徴を踏まえて説明できる。	整列、探索など、基本的なアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	整列、探索など、基本的なアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できない。
評価項目3	時間計算量・領域計算量によってアルゴリズムを比較・評価できることを具体例を挙げて説明できる。	時間計算量・領域計算量によってアルゴリズムを比較・評価できることを説明できる。	時間計算量・領域計算量によってアルゴリズムを比較・評価できることを説明できない。
評価項目4	リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作について実装とともに説明することができる。	リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明し、実装することができる。	リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明し、実装することができない。

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

学習・教育到達度目標 B① 専門分野における工学の基礎を理解できる。

学習・教育到達度目標 B② 自主的・継続的な学習を通じて、専門工学の基礎科目に関する問題を解くことができる。

教育方法等

概要:

アルゴリズムの概要と計算効率の概念を理解し、汎用的なアルゴリズムとデータ構造に関して、実際にプログラムを作成し動作を確認しながら学習する。

授業の進め方・方法:

解説の後、実際にプログラムを作成し動作を確認する。その後オンラインジャッジの課題のプログラムを作成する。

注意点:

C言語の基本的な知識が要求されるので、復習しておくこと。

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

ICT 利用

遠隔授業対応

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス（ソースプログラム記述、実行、オンラインジャッジ） アルゴリズムの概念	ソースプログラムを記述・コンパイル・実行できる。 オンラインジャッジにプログラムを提出できる。 アルゴリズムの概念を説明できる。
		2週	時間計算量・領域計算量の評価と比較	時間計算量・領域計算量によってアルゴリズムを比較・評価できることを説明できる。
		3週	挿入ソート	挿入ソートのアルゴリズムを説明し、実装することができる。
		4週	バブルソート	バブルソートのアルゴリズムを説明し、実装することができる。
		5週	選択ソート	選択ソートのアルゴリズムを説明し、実装することができる。
		6週	安定なソート	ソートについて、複数のアルゴリズムが存在することを説明できる。 ソートについて、安定なソートと不安定なソートがあることを説明できる。
		7週	1〜6週目までの振り返り演習	1〜6週目までの内容で、不十分なところをなくす。
		8週	中間試験
	2ndQ
		9週	スタック	スタックのデータ構造を説明し、実装することができる。
		10週	キュー	キューのデータ構造を説明し、実装することができる。
		11週	連結リスト	連結リストのデータ構造を説明し、実装することができる。
		12週	線形探索	線形探索のアルゴリズムを説明し、実装することができる。
		13週	二分探索	二分探索のアルゴリズムを説明し、実装することができる。
		14週	ハッシュ	ハッシュのアルゴリズムを説明し、実装することができる。
		15週	9〜14週目までの振り返り演習	9〜14週目までの内容で、不十分なところをなくす。
		16週	定期試験

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

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

評価割合

	試験	小テスト等	演習・レポート	発表	相互評価	合計
総合評価割合	70	0	30	0	0	100
基礎的能力	0	0	0	0	0	0
専門的能力	70	0	30	0	0	100
分野横断的能力	0	0	0	0	0	0