対象年度	年度	2017	期	(週1ｺﾏ)秋期	開講時限	金2
開講学部・学科等	理工
科目コード	640034100		科目ナンバー	SES03102
授業名	アルゴリズム論
英文授業名	Theory of Algorithm
担当教員	守谷　哲夫

授業形態	講義
	e-learning利用		その他：
担当形態	単独
関連する授業
	当科目履修前に履修して おくことが望ましい科目	数理情報入門 情報数学
	後続関連授業
教職課程科目	教科に関する科目
テーマ・キーワード	効率のよいアルゴリズムを設計するための基本的な考え方と技法

授業の概要・ねらい	授業のねらい：アルゴリズム論は、情報処理、計算を効率良く行う方法について研究する学問分野である。(効率の)よいアルゴリズムを設計するための基本的な考え方と技法を学ぶことによって論理的思考力や表現力をみにつけることを目的とする。グラフアルゴリズム、探索問題、ソーティングの問題を中心に講義をすすめる。 系統的な基礎知識とともに、論理的思考力を修得することを目指す。
到達目標	アルゴリズムの設計と解析に対する基礎 効率のよいアルゴリズムに関する基礎知識を身につける。 授業で学んだグラフのアルゴリズムやソーティングのアルゴリズムを用いた計算過程が正しく記述できる。
教科書と準備するもの	使用しない
参考書	授業中に指示
評価の基準	効率の良いアルゴリズムに関する 基礎知識が習得できている。時間計算量と領域計算量の概念が説明できる。 与えられたグラフに対して、クラスカルやプリムのアルゴリズムを用いて最小全域木を求める計算過程を記述できる。 選択法、バブルソートに関する知識が身についている。 ヒープソートの方法を用いてソーチングを行う方法を記述できる。 KMPのアルゴリズムを用いてパターンマッチングの問題を解くための計算過程を記述できる。 以上の点について、その到達度によって評価を行う。
具体的評価方法	試験80% レポート20%

授業評価アンケート フィードバック・ 受講生へメッセージ	説明の仕方を検討し、受講生の興味を引くものになるよう工夫を したいと思います。
単位互換
特記

第1回	内容	アルゴリズムの基本的概念について説明し、 アルゴリズムの定義とチューリング機械の関連性について述べる。
	授業時間外における学修（予習・復習等）	(予習)事前にシラバスを読んでおくこと。 (復習)授業で理解できなかった点をA4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第2回	内容	アルゴリズムと計算量の関連について述べ、 時間計算量と領域計算量の概念を例を挙げて説明する。
	授業時間外における学修（予習・復習等）	(予習)情報数学で学んだ基礎知識、特に集合、論理、関係について復習しておき、 要点をA4のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点をA4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第3回	内容	グラフ理論の基礎 グラフの定義をのべ,有向グラフと無向グラフの相違点について、具体例を通して説明する。
	授業時間外における学修（予習・復習等）	(予習)有向グラフおよび無向グラフについてその定義・概念を、例を挙げてA４のレポート用紙1枚程度にまとめておくこと。　 (復習)授業でよく理解できなかった点をまとめてA４のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第4回	内容	オイラーグラフの定義をのべ、具体例を挙げて示す。 オイラー閉路を求めるアルゴリズムについて説明する。
	授業時間外における学修（予習・復習等）	(予習)グラフに関する用語を整理して、A４のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A４のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第5回	内容	グラフと木。 木と2分木の概念について述べ、具体例を示す。 木構造について、その特徴などを説明する。
	授業時間外における学修（予習・復習等）	(予習)グラフと木、２分木について調べ、A4のレポート用紙１枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第6回	内容	全域部分グラフと最小全域木 全域部分グラフの概念を述べ、最小全域木について、具体例を挙げて説明する。
	授業時間外における学修（予習・復習等）	(予習)全域部分グラフと最小全域木について調べ、A4のレポート用紙１枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと
	授業実施特記
第7回	内容	最小全域木を求めるアルゴリズム クラスカルのアルゴリズムと プリムのアルゴリズムについて、具体例を挙げながら説明し、2つのアルゴリズム の特徴、相違点について述べる。
	授業時間外における学修（予習・復習等）	(予習)最小全域木の定義を確認し、クラスカルのアルゴリズム並びにプリムのアルゴリズム について調べ、A4のレポート用紙１枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第8回	内容	最短経路を求めるアルゴリズム ダイクストラ法について、具体例を挙げながら説明する。 フロイド法について、具体例を挙げながら説明する。
	授業時間外における学修（予習・復習等）	(予習)ダイクストラ法並びにフロイド法について調べ、A4のレポート用紙１枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第9回	内容	2分木の探索 深さ優先探索の概念を具体例を挙げながら説明し、そののちプッシュダウンスタックを使う手法について説明する。
	授業時間外における学修（予習・復習等）	(予習)２分木について、その定義及び性質について確認して、A4のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第10回	内容	２分探索木（BST）の概念について具体例を挙げながら説明し、 BSTの基本操作である、探索、挿入、削除などについて説明する。
	授業時間外における学修（予習・復習等）	(予習)２分探索木について、その定義及び性質について確認して、A4のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第11回	内容	ソーティングのアルゴリズム 単純選択法およびバブルソートについて具体例を用いて説明し、これらのアルゴリズムの 最悪時間計算量についてしめす。
	授業時間外における学修（予習・復習等）	(予習)整列（ソーティング）についてあらかじめ調べておき、A4のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第12回	内容	ヒープソート ヒープの定義を具体例を通して説明し、そののちヒープを用いたソーティング の手順を述べる。
	授業時間外における学修（予習・復習等）	(ヒープ)　ヒープについてあらかじめ調べておき、A4のレポート用紙1枚程度にまとめておくこと。 （復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第13回	内容	マージソートならびにクイックソートについて具体例を用いて説明し、これらのアルゴリズムの最悪時間計算量についてしめす。
	授業時間外における学修（予習・復習等）	(予習)マージソート、クイックソートについてあらかじめ調べておき、A4のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第14回	内容	パターンマッチング 素朴な方法と クヌースモーリスプラット(KMP)法について説明し、これらの特徴ならびに相違点に着目して説明する。
	授業時間外における学修（予習・復習等）	(予習)パターンマッチングについてあらかじめ調べておき、A4のレポート用紙1枚程度にまとめておくこと。 (復習)授業で理解できなかった点を整理して、A4のレポート用紙1枚程度にまとめておくこと。
	授業実施特記
第15回	内容	まとめと総合演習
	授業時間外における学修（予習・復習等）	(予習)講義内容全般にわたって総復習をしておくこと。 (復習)授業で解決できなかった点を質問事項として各自A4のレポート用紙1枚程度にまとめ、自ら学修する。
	授業実施特記