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

科目基礎情報

学校	苫小牧工業高等専門学校	開講年度	令和07年度 (2025年度)
授業科目	データ構造とアルゴリズム
科目番号	0031	科目区分	専門 / 必修
授業形態	授業	単位の種別と単位数	学修単位: 2
開設学科	創造工学科（情報科学・工学系共通科目）	対象学年	4
開設期	前期	週時間数	2
教科書/教材	教科書： 柴田望洋「新・明解　Javaで学ぶデータ構造とアルゴリズム　第2版」SBクリエイティブ／参考図書：紀平 拓男、春日 伸弥「プログラミングの宝箱アルゴリズムとデータ構造」SBクリエイティブ，ジョン ベントリー「珠玉のプログラミング: 本質を見抜いたアルゴリズムとデータ構造」桐原書店，T.コルメン他「アルゴリズムイントロダクション　第3版　第1巻」近代科学社，石田 保輝「アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム」翔泳社
担当教員	原田 恵雨

到達目標

1) 与えられたプログラムの読解，要求仕様を満たすプログラムの作成ができる．
2) 再帰的アルゴリズムについて，実装を通して理解できる．
3) 代表的な探索アルゴリズムについて，実装を通して理解できる．
4) 代表的なソートアルゴリズムについて，実装を通して理解できる．
5) スタックとキューについて，実装を通して理解できる．
6) 配列，リスト構造，木構造について，実装を通して理解できる．
7) アルゴリズム，データ構造について，計算量，安定性等の面から性能を評価できる．

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	与えられたプログラムの読解，要求仕様を満たすプログラムの作成ができる．	与えられたプログラムの読解，要求仕様を満たすプログラムの基本的な作成ができる．	与えられたプログラムの読解，要求仕様を満たすプログラムの作成ができない．
評価項目2	再帰的アルゴリズムについて，実装を通して理解できる．	再帰的アルゴリズムについて，実装を通して基本的な理解ができる．	再帰的アルゴリズムについて，実装を通して理解できない。
評価項目3	探索アルゴリズムについて，実装を通して理解できる．	探索アルゴリズムについて，実装を通して基本的な理解ができる．	探索アルゴリズムについて，実装を通して理解できない。
評価項目4	ソートアルゴリズムについて，実装を通して理解できる．	ソートアルゴリズムについて，実装を通して基本的な理解ができる．	ソートアルゴリズムについて，実装を通して理解できない。
評価項目5	計算量について，理解と計算ができる．	計算量について，理解と基本的な計算ができる．	計算量について，理解と計算ができない。
評価項目6	スタックとキューについて，実装を通して理解できる．	スタックとキューについて，実装を通して基本的な理解ができる．	スタックとキューについて，実装を通して理解できない。
評価項目7	リスト構造，木構造，グラフ構造について，実装を通して理解できる。	リスト構造，木構造，グラフ構造について，実装を通して基本的な理解ができる。	リスト構造，木構造，グラフ構造について，実装を通して理解できない。
評価項目8	分枝限定法について，実装を通して理解できる．	分枝限定法について，実装を通して基本的な理解ができる．	分枝限定法について，実装を通して理解できない。

教育方法等

概要:

データ構造とアルゴリズムについて学ぶ。
具体的には，配列，リスト構造，木構造といったデータ構造，および探索，キュー／スタック，再帰，ソートなどのアルゴリズムを取り上げる。
これらと密接に関係する概念として，計算量の考え方についても理解を深める。
ソフトウェアによる問題解決の場面では，プログラミング言語を問わず，これらの知識が不可欠である。
本講義では，それらを活用した普遍的な問題解決の力を養うことを目的とする。

授業の進め方・方法:

短期的な目標は，各データ構造とアルゴリズムの理解，実装，評価ができることを目指す。
長期的な目標は，実際に業務で直面しうる場面において，どのデータ構造，どのアルゴリズムが良いか判断できるようになることを目指す。
授業は原則実習室で実施する。授業時間前に実習室でPCにログインしていること。
資料は事前にWebで閲覧できるようにするが，口頭で補足することもあるため，ノートをとることを勧める。
わからないことはすぐに解決することが望ましいため，いつでも質問を歓迎する。
各授業は講義＋演習形式で実施し，各データ構造とアルゴリズムは，全てまたは一部を自分で考えて実装する。
適宜課される課題を提出すること。また，定期試験はないが，小テストを適宜実施する。
評価は課題70％，小テスト30％とする。課題は締切を遅れると大幅に減点する。

注意点:

データ構造とアルゴリズムはプログラミング言語に依存しないが，この授業では，Javaを主に利用する。まれに他の言語を使うこともある。
計算量の単元では，数学（総和，等差数列，等比数列，対数，など）の知識が必要であるため，復習をしておくこと。
この授業は学修単位であるため，授業時間外に60時間の自習が必要である。
課題のほか，自分でなるべく見ないで実装できるか確認したり，参考書を読んだり，"VisuAlgo.net"，"一週間で身につくアルゴリズムとデータ構造"，"paizaラーニング"などのWebサイトで自習すること。
AtCoderなどの競技プログラミングの過去問を解いたり，実際にコンテストに出てみるのもよい。
アルゴリズムがわかる，組めるということは，手順を曖昧性なく具体的に言語化することでもある。説明力向上のために，学生同士または言語系生成AIと説明し合うのもよい。

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

ICT 利用

遠隔授業対応

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	時間計算量・空間計算量	計算量，ビッグオー記法を理解できる。
		2週	配列とリスト構造，線形探索	配列，リスト構造について実装を通して理解できる。線形探索O(n)について実装できる。
		3週	スタックとキュー	スタックとキューの基礎を理解し，その応用例を知る。
		4週	素数判定	エラトステネスのふるいを理解，実装する。
		5週	再帰とメモ化	再帰の考え方を理解し，階乗，フィボナッチ数を実装できる。メモ化を導入し，計算量を改善できる。
		6週	単純ソート	基本的なソート（交換，選択，挿入）を理解し，実装できる。単純ソートの非効率性を理解する。
		7週	単純文字列検索	単純な文字列探索について理解，実装できる。
		8週	二分探索，リングバッファ	二分探索（O(log n)）を理解し，ソート済み列に対する実装ができる。キューの効率的な実装ができる。
	2ndQ
		9週	シェルソート	挿入ソートの改良としてのシェルソートを理解，実装できる。
		10週	グラフ探索（再帰）	グラフの基本概念を理解し，深さ優先探索，幅優先探索のアルゴリズムを理解，実装できる。
		11週	分枝限定法・グラフ探索（非再帰）	再帰的アルゴリズムの非再帰化を理解，実装できる。分枝限定法について理解，実装できる。
		12週	クイックソート	クイックソートのアルゴリズムを理解，実装できる。
		13週	KMP法	KMP法を理解，実装できる。
		14週	二分探索木	二分探索木（BST）の概念を理解，実装できる。
		15週	総合演習	これまで学んだアルゴリズムを組み合わせた実践的な問題を解く。
		16週

評価割合

	課題	小テスト	合計
総合評価割合	70	30	100
基礎的能力	10	0	10
専門的能力	60	30	90
分野横断的能力	0	0	0