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

科目基礎情報

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

到達目標

1. 再帰を用いたソートアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。
2. 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。
3. 二分木のデータ構造の概念と操作を説明し、実装することができる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	再帰を用いたソートアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを、その特徴を踏まえて説明できる。	再帰を用いたソートアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	再帰を用いたソートアルゴリズムについて、同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できない。
評価項目2	同じ問題を解決する複数のプログラムを計算量等の観点から比較・説明できる。	同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。	同じ問題を解決する複数のプログラムを計算量等の観点から比較できない。
評価項目3	二分木のデータ構造の概念と操作を説明し、実装と共に説明することができる。	二分木のデータ構造の概念と操作を説明し、実装することができる。	二分木のデータ構造の概念と操作を説明し、実装することができない。

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

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

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

教育方法等

概要:

時間計算量について効率的なアルゴリズムとデータ構造に関して、実際にプログラムを作成し動作を確認しながら学習する。

授業の進め方・方法:

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

注意点:

前期のアルゴリズムとデータ構造Ⅰを理解していることが前提条件となる。C言語について特に再帰関数、構造体、ポインタの知識が要求される。

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

ICT 利用

遠隔授業対応

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	再帰関数	再帰関数の概念を理解し、プログラムを実装することができる。
		2週	分割統治法	分割統治法の概念を理解し、プログラムを実装することができる。
		3週	全探索	再帰を用いて全探索を行うプログラムを実装することができる。
		4週	マージソート	マージソートのアルゴリズムを説明し、実装することができる。
		5週	パーティション	パーティションのアルゴリズムを説明し、実装することができる。
		6週	クイックソート	クイックソートのアルゴリズムを説明し、実装することができる。
		7週	計数ソート	計数ソートのアルゴリズムを説明し、実装することができる。
		8週	中間試験
	4thQ
		9週	二分木	二分木のデータ構造を説明し、実装することができる。
		10週	二分木の巡回	二分木の巡回のアルゴリズムを理解し、実装することができる。
		11週	二分木探索木：挿入	二分木探索木に新しいノードを挿入するアルゴリズムを理解し、実装することができる。
		12週	二分木探索木：探索	二分木探索木に含まれるノードを探索するアルゴリズムを理解し、実装することができる。
		13週	二分木探索木：削除	二分木探索木に含まれるノードを削除するアルゴリズムを理解し、実装することができる。
		14週	木構造	木構造のデータ構造を説明し、実装することができる。
		15週	9〜14週目までの振り返り演習	9〜14週目までの内容で、不十分なところをなくす。
		16週	定期試験

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

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