アルゴリズム

科目基礎情報

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

到達目標

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

ルーブリック

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

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

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

教育方法等

概要:

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

授業の進め方・方法:

授業はペアワークやグループワークを含んだ講義および実習形式で進める。
各回の授業の冒頭で前回の内容に関する小テストを実施する。
各回の授業の前にあらかじめ教科書を読み、不明なところは調べるなどしてある程度理解しておくこと。
適宜、プログラミングの実習課題を宿題として課す。

注意点:

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

授業計画

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

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

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

評価割合

	中間試験	定期試験	小テスト	実習課題	合計
総合評価割合	35	35	10	20	100
基礎的能力	0	0	0	0	0
専門的能力	35	35	10	20	100
分野横断的能力	0	0	0	0	0