文理学部シラバスTOP > 文理学部 > 情報科学科（情報システム解析学科） > アルゴリズム
日本大学ロゴ

アルゴリズム

このページを印刷する

令和元年度以前入学者 アルゴリズム
教員名 谷聖一
単位数    2 学年    3 開講区分 文理学部
（他学部生相互履修可）
科目群 情報科学科
学期 後期 履修区分 選択必修
授業の形態 主として同時双方向型授業（Zoom）
Blackboard ID: 20203271 （「2020アルゴリズム（谷聖一・後・月2）」）
授業概要 アルゴリズム論は，処理手順（アルゴリズム）の処理性能に対する評価方法の確立を第一の目的とし，様々な情報処理の問題に対する処理性能の良いアルゴリズムの開発を第二の目的としている．この授業では，これら二つの目的に関する基礎事項を解説する．まず，時間計算量（より一般的に，計算量）を解説しながら現在のアルゴリズム論が計算量概念を指標として性能評価を行っていること，ならびに計算量概念の実際的（工学的）な意味を解説する．さらに，時間計算量を実験的に解析する方法も解説する．次に，ソーティングとグラフ構造の処理をおもな題材として，様々なアルゴリズムを解説する．多様なアルゴリズムを比較検討することによって，情報処理の効率が，コンピュータシステム（ハードウェアやソフトウェア）の性能だけでなく，アルゴリズムの性能にも大きな影響を受けることを理解していく．
授業のねらい・到達目標 アルゴリズムの処理性能が情報処理の効率を決定づける大きな要因の一つであることを認識できるようになる．さらに，各種アルゴリズムの基本的な考え方を理解することによって，それらを柔軟に応用できるようになる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法 レポート課題として，C言語を用いたアルゴリズムの実現と性能評価実験を要求する．
・レポートの一部は自己評価・相互評価を行う．レポートには，総評することでフィードバックを行う．
履修条件 「データ構造」の内容を理解していることを前提に講義を行う．
授業計画
1 アルゴリズム論の概要
【事前学習】シラバスを事前に確認し、授業全体の流れを理解する. （2時間）
【事後学習】アルゴリズム論の基本的な方法論を理解する． （2時間）
2 理論的性能評価の方法
【事前学習】アルゴリズム論の基本的な方法論について復習する． （2時間）
【事後学習】計算量概念の定義と意図を理解する． （2時間）
3 基本的データ構造の復習（リスト・スタック・キュー）
【事前学習】計算量概念の定義を復習する． （2時間）
【事後学習】基本的データ構造の復習に関する簡単な実験課題を課す． （2時間）
4 二分探索法とその応用
【事前学習】実験的性能評価について復習する． （2時間）
【事後学習】応用例を通して二分探索法に関する理解を深める． （2時間）
5 選択ソート，挿入ソート，バブルソート
【事前学習】ソーティング問題について学習する． （2時間）
【事後学習】素朴なソーティングアルゴリズムを題材に時間計算量について理解を深める． （2時間）
6 マージソート
【事前学習】再帰呼び出し（再帰的定義）について復習する． （2時間）
【事後学習】再帰的な処理手順とマージ処理について理解を深める． （2時間）
7 クイックソート
【事前学習】再帰呼び出し（再帰的定義）について復習する． （2時間）
【事後学習】分割処理の処理手順について理解を深める． （2時間）
8 ヒープソート
【事前学習】木構造（グラフ理論）について復習する． （2時間）
【事後学習】ヒープの構成方法について理解を深める．各種ソーティングアルゴリズムを実現し，性能評価実験を試みる． （2時間）
9 第8回までのまとめと小テスト
【事前学習】ヒープの構成方法について復習する． （2時間）
【事後学習】選択問題に対する線形時間アルゴリズムを実現し，その性能評価実験を試みる．さらに，クイック選択アルゴリズムも実現し，両者の性能比較実験を試みる． （2時間）
10 グラフのデータ構造
【事前学習】グラフに関する基礎概念（グラフ理論），構造体，ポインタ，メモリの動的割り当て，データ構造について復習する． （2時間）
【事後学習】グラフのデータを入力したり，（適当な形式で）出力するプログラムを試作してみる． （2時間）
11 幅優先探索と深さ優先探索
【事前学習】グラフのデータ構造について復習する． （2時間）
【事後学習】幅優先探索と深さ優先探索のプログラムを実現してみる． （2時間）
12 幅優先探索・深さ優先探索の応用
【事前学習】幅優先探索と深さ優先探索について復習する． （2時間）
【事後学習】授業で解説したアルゴリズムを実現してみる． （2時間）
13 最小全域木問題のアルゴリズム
【事前学習】幅優先探索・深さ優先探索の応用について復習する． （2時間）
【事後学習】最小全域木問題に対する複数のアルゴリズムを実現して，性能比較実験を試みる． （2時間）
14 最短路問題のアルゴリズム
【事前学習】最小全域木問題のアルゴリズムについて復習する． （2時間）
【事後学習】最短路問題に対する複数のアルゴリズムを実現して，性能比較実験を試みる． （2時間）
15 まとめと小テスト
【事前学習】最短路問題に対する複数のアルゴリズムについて復習する． （2時間）
【事後学習】全15回の内容を復習する． （2時間）
その他
教科書 平田富夫 『アルゴリズムとデータ構造（第3版）』 森北出版 2018年 第3版
参考書 J. Kleinberg, E. Tardos 著  『アルゴリズムデザイン』 共立出版 2008年
大槻 兼資 著 『問題解決力を鍛える!アルゴリズムとデータ構造 （KS情報科学専門書）』 講談社 2020年
T.コルメン他著／浅野哲夫他訳 『アルゴリズムイントロダクション（第3版）第1巻，第2巻』 近代科学社 2012年 第3版
成績評価の方法及び基準 試験(40%)、レポート(30%)、授業参画度(30%)
・試験は2回の授業内試験で評価する．詳細は1回目の授業時に説明する．
・レポート課題は授業全体の前半と後半で２回課す予定である．いずれもC言語を用いた計算機実験を行う（C++, Ruby, Python も可）．
オフィスアワー 毎週月曜日 18:00 〜 19:00

↑このページのトップ