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

科目基礎情報

学校	小山工業高等専門学校	開講年度	令和04年度 (2022年度)
授業科目	アルゴリズムとデータ構造
科目番号	0055	科目区分	専門 / 必修
授業形態	講義	単位の種別と単位数	学修単位: 2
開設学科	電気電子創造工学科	対象学年	3
開設期	前期	週時間数	2
教科書/教材	データ構造とアルゴリズム、インフォテック・サーブ（2014）
担当教員	平田 克己

到達目標

1．構造化プログラミングにおける基本制御構造（順次・選択・反復）を理解し、擬似言語で表現できる。
2．基本的な探索や整列のアルゴリズムを理解し、擬似言語で表現できる。
3．基本的な探索や整列を実現するプログラムをC言語で記述できる。
4．基本的なデータ構造（スタック、キュー、リスト、木構造）を説明できる。
5．スタックやキューを用いた簡単なデータ入出力アルゴリズムを擬似言語で表現できる。
6．音声や画像、動画などのメディア情報の表現形式やディジタル化（離散化）の基礎について説明できる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
1．基本制御構造を含む簡単なアルゴリズムを擬似言語で書き表せる。 （小テスト、中間試験および定期試験で評価）	極めて正確に書き表せる。	少しの誤りはあるものの、ほぼ正確に書き表せる。	まったく書き表せないか書き表せても誤りが多い。
2．基本的な探索や整列のアルゴリズムを擬似言語で書き表せる。 （小テスト、中間試験および定期試験で評価）	極めて正確に書き表せる。	少しの誤りはあるものの、ほぼ正確に書き表せる。	まったく書き表せないか書き表せても誤りが多い。
3．基本的な探索や整列を実現するC言語プログラムを作成できる。 （実習課題で評価）	仕様どおりに作成できる。	おおむね仕様どおりに作成できる。	作成できないか、作成できても仕様をほとんど満たしていない。
4．基本的なデータ構造について説明できる。 （小テスト、中間試験および定期試験で評価）	極めて正確に説明できる。	おおむね説明できる。	まったくまたはほとんど説明できない。
5．スタックやキューを用いた簡単なデータ入出力アルゴリズムを擬似言語で書き表せる。 （小テスト、中間試験および定期試験で評価）	与えられた仕様どおりに極めて正確に書き表せる。	少しの誤りはあったり、一部仕様を満たしていない部分があるものの、ほぼ正確に書き表せる。	まったく書き表せないか書き表せても誤りが多い。
6．音声や画像、動画などのメディア情報の表現形式やディジタル化（離散化）の基礎について説明できる。 （小テスト、中間試験および定期試験で評価）	極めて正確に説明できる。	おおむね説明できる。	まったくまたはほとんど説明できない。

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

学習・教育到達度目標 ⑤ （情報技術力の向上）

教育方法等

概要:

この授業ではプログラミングにおいて重要であるアルゴリズムとデータ構造について学習する。
まずアルゴリズムの重要性やその良し悪しについて理解した上で、データの探索や整列などの典型的なアルゴリズムについて学習する。
また、アルゴリズムの実現においてデータ構造が重要であることを理解し、種々の基本的なデータ構造について学習する。
キーワード：　プログラミング、擬似言語、C言語、アルゴリズム、探索、ソート、データ構造

授業の進め方・方法:

授業は講義、演習および実習形式で進める。
各回の授業の冒頭で前回の内容に関する小テストを実施する。
各回の授業の前にあらかじめ教科書を読み、不明なところは調べるなどしてある程度理解しておくこと。
この科目は学修単位科目のため、以下の事前および事後学習を最低限求める。
事前学習：　教科書に目を通しておく。
事後学習：　授業内容を復習する（→小テストで評価）。与えられたプログラミング課題に取り組んで提出する。

注意点:

わからないことがあればその都度質問するなどしてその場で解決することを心がけること。授業中や教員室への訪問以外に、Microsoft Teamsでの質問も受け付ける。
実習課題は学生同士で教え合うなど協力して取り組んでも良いが、誰かが作ったプログラム（インターネット上の情報も含む）をそのままコピーして提出することは不可とする。（不正が発覚した場合には課題点を0とする。）

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

ICT 利用

遠隔授業対応

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス、アルゴリズムとは、問題分析	アルゴリズムとは何かを説明できる。
		2週	流れ図（フローチャート）、基本制御構造	基本制御構造を含む簡単な処理をフローチャートで表せる。
		3週	擬似言語、アルゴリズムの評価基準	基本制御構造を含む簡単な処理を擬似言語で表せる。 アルゴリズムの評価基準を挙げ、それぞれについて説明できる。
		4週	配列、ハッシュ表	配列やハッシュ表を用いた簡単な処理を擬似言語で表せる。
		5週	連結リスト	連結リストを用いた簡単な処理を擬似言語で表せる。
		6週	スタックとキュー	スタックとキューについて説明できる。 スタックやキューを用いた簡単な処理を擬似言語で表せる。
		7週	木構造	木構造について説明できる。 木構造を用いた簡単な処理を擬似言語で表せる。
		8週	（中間試験）
	2ndQ
		9週	メディア情報の表現と処理	音声や画像、動画などのメディア情報の表現形式やディジタル化（離散化）の基礎について説明できる。
		10週	線形探索	線形探索について説明できる。 線形探索のアルゴリズムを擬似言語で表せるとともに、簡単なプログラムをC言語で作成することができる。
		11週	2分探索、探索の計算量	2分探索と探索アルゴリズムの計算量について説明できる。 2分探索アルゴリズムを擬似言語で表せるともに、簡単なプログラムをC言語で作成することができる。
		12週	選択ソート	選択ソートについて説明できる。 選択ソートのアルゴリズムを擬似言語で表せるとともに、簡単なC言語プログラムを作成することができる。
		13週	交換ソート	交換ソートについて説明できる。 交換ソートのアルゴリズムを擬似言語で表せるとともに、簡単なC言語プログラムを作成することができる。
		14週	挿入ソート	挿入ソートについて説明できる。 挿入ソートのアルゴリズムを擬似言語で表せるとともに、簡単なC言語プログラムを作成することができる。
		15週	マージソートとクイックソート	マージソートとクイックソートについて説明できる。 マージソートとクイックソートのアルゴリズムを擬似言語で表せるとともに、簡単なC言語プログラムを作成することができる。
		16週

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

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
基礎的能力	工学基礎	情報リテラシー	情報リテラシー	コンピュータのハードウェアに関する基礎的な知識を活用できる。	3	前9
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。	3	前1,前2,前10,前11,前12,前13,前14,前15
				与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。	3	前2,前10,前11,前12,前13,前14,前15
				任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。	3	前10,前11,前12,前13,前14,前15
専門的能力	分野別の専門工学	情報系分野	プログラミング	代入や演算子の概念を理解し、式を記述できる。	4	前4,前5,前6,前10,前11,前12,前13,前14,前15
				プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。	4	前10,前11,前12,前13,前14,前15
				変数の概念を説明できる。	4	前4,前5,前6,前10,前11,前12,前13,前14
				データ型の概念を説明できる。	4	前4,前6,前7,前10,前11,前12,前13,前14
				制御構造の概念を理解し、条件分岐を記述できる。	4	前2,前3,前5,前6,前10,前11,前12,前13,前14,前15
				制御構造の概念を理解し、反復処理を記述できる。	4	前2,前3,前5,前6,前10,前11,前12,前13,前14,前15
				与えられた問題に対して、それを解決するためのソースプログラムを記述できる。	4	前5,前6,前10,前11,前12,前13,前14,前15
				ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。	4	前5,前6,前10,前11,前12,前13,前14,前15
				与えられたソースプログラムを解析し、プログラムの動作を予測することができる。	4	前5,前6,前10,前11,前12,前13,前14,前15
			ソフトウェア	アルゴリズムの概念を説明できる。	3	前1,前10,前11,前12,前13,前14,前15
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	3	前2,前3,前10,前11,前12,前13,前14,前15
				整列、探索など、基本的なアルゴリズムについて説明できる。	3	前10,前11,前12,前13,前14,前15
			その他の学習内容	少なくとも一つの具体的なコンピュータシステムについて、起動・終了やファイル操作など、基本的操作が行える。	3	前8,前10,前11,前12,前13,前14,前15
				メディア情報の主要な表現形式や処理技法について説明できる。	2	前9
				ディジタル信号とアナログ信号の特性について説明できる。	2	前9
				情報を離散化する際に必要な技術ならびに生じる現象について説明できる。	2	前9
	分野別の工学実験・実習能力	情報系分野【実験・実習能力】	情報系【実験・実習】	与えられた問題に対してそれを解決するためのソースプログラムを、標準的な開発ツールや開発環境を利用して記述できる。	3	前8,前10,前11,前12,前13,前14,前15
				ソフトウェア生成に利用される標準的なツールや環境を使い、ソースプログラムをロードモジュールに変換して実行できる。	3	前8,前10,前11,前12,前13,前14,前15
				ソフトウェア開発の現場において標準的とされるツールを使い、生成したロードモジュールの動作を確認できる。	3	前8,前10,前11,前12,前13,前14,前15
				フローチャートなどを用いて、作成するプログラムの設計図を作成することができる。	3	前2
				問題を解決するために、与えられたアルゴリズムを用いてソースプログラムを記述し、得られた実行結果を確認できる。	3	前8,前9,前10,前11,前12,前13,前14,前15

評価割合

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