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

アルゴリズム

このページを印刷する

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

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法 講義ノートと配布資料だけで学習できるように授業を行う．
レポート課題として，C言語を用いたアルゴリズムの実現と性能評価実験を要求する．
本授業の事前・事後学習は,各2時間の学習を目安とする．
授業計画
1 アルゴリズム論の概要
【事前学習】シラバスを事前に確認すること
【事後学習】アルゴリズム論の基本的な方法論を理解する．
2 理論的性能評価の方法
【事前学習】前回の授業内容を復習する．
【事後学習】計算量概念の定義と意図を理解する．
3 実験的性能評価の方法
【事前学習】計算量概念の定義を復習する．
【事後学習】実験的性能評価に関する簡単な実験課題を課す．
4 二分探索法とその応用
【事前学習】前回までの授業内容を復習する．
【事後学習】応用例を通して二分探索法に関する理解を深める．
5 選択ソート，挿入ソート，バブルソート
【事前学習】ソーティング問題について学習する．
【事後学習】素朴なソーティングアルゴリズムを題材に時間計算量について理解を深める．
6 マージソート
【事前学習】再帰呼び出し（再帰的定義）について復習する．
【事後学習】再帰的な処理手順とマージ処理について理解を深める．
7 クイックソート
【事前学習】再帰呼び出し（再帰的定義）について復習する．
【事後学習】分割処理の処理手順について理解を深める．
8 ヒープソート
【事前学習】木構造（グラフ理論）について復習する．
【事後学習】ヒープの構成方法について理解を深める．各種ソーティングアルゴリズムを実現し，性能評価実験を試みる．
9 選択問題のアルゴリズム
【事前学習】前回までの授業内容を復習する．
【事後学習】選択問題に対する線形時間アルゴリズムを実現し，その性能評価実験を試みる．さらに，クイック選択アルゴリズムも実現し，両者の性能比較実験を試みる．
10 グラフのデータ構造
【事前学習】グラフに関する基礎概念（グラフ理論），構造体，ポインタ，メモリの動的割り当て，データ構造について復習する．
【事後学習】グラフのデータを入力したり，（適当な形式で）出力するプログラムを試作してみる．
11 幅優先探索
【事前学習】前回までの授業内容を復習する．
【事後学習】幅優先探索のプログラムを実現してみる．
12 深さ優先探索
【事前学習】前回までの授業内容を復習する．
【事後学習】深さ優先探索のプログラムを実現してみる．
13 幅優先探索・深さ優先探索の応用
【事前学習】前回までの授業内容を復習する．
【事後学習】授業で解説したアルゴリズムを実現してみる．
14 最短路問題のアルゴリズム
【事前学習】前回までの授業内容を復習する．
【事後学習】最短路問題に対する複数のアルゴリズムを実現して，性能比較実験を試みる．
15 最小全域木問題のアルゴリズム
【事前学習】前回までの授業内容を復習する．
【事後学習】最小全域木問題に対する複数のアルゴリズムを実現して，性能比較実験を試みる．
その他
教科書 使用しない
参考書 平田富夫 『アルゴリズムとデータ構造（第3版）』 森北出版 2018年 第3版
S.S.スキーナ著／平田富夫訳 『アルゴリズム設計マニュアル（上）』 丸善出版 2012年 第3版
T.コルメン他著／浅野哲夫他訳 『アルゴリズムイントロダクション（第3版）第1巻，第2巻』 近代科学社 2012年 第3版
『平田富夫著「アルゴリズムとデータ構造（第3版）」森北出版』が授業内容にとても近い．
成績評価の方法及び基準 試験(60%)、レポート(40%)
試験は期末試験1回で評価する．
レポート課題は授業全体の前半と後半で２回課す予定である．いずれもC言語を用いた計算機実験を行う．
オフィスアワー 毎週水曜日１２：１０〜１３：００

↑このページのトップ