検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
アルゴリズム
| 令和元年度以前入学者 | アルゴリズム | ||||
|---|---|---|---|---|---|
| 教員名 | 谷聖一 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 |
文理学部
（他学部生相互履修可） |
| 科目群 | 情報科学科 | ||||
| 学期 | 後期 | 履修区分 | 選択必修 | ||
| 授業の形態 | 同時双方向型授業（Zoom）実施する．（全15回同時双方向型授業（Zoom）の予定であるが，状況に応じて一部の回で希望者は対面で参加できる場合があるかもしれない．） ただし，試験は対面で実施する．（対面での試験を受験できない事情がある場合は，1対1あるいは少人数での面接試験・オンライン試験・レポートの組み合わせで試験に代えるなどの配慮を行う．） Blackboard コースID: 月曜2限→20213032 |
|---|---|
| 授業概要 | アルゴリズム論は，処理手順（アルゴリズム）の処理性能に対する評価方法の確立を第一の目的とし，様々な情報処理の問題に対する処理性能の良いアルゴリズムの開発を第二の目的としている．この授業では，これら二つの目的に関する基礎事項を解説する．まず，時間計算量（より一般的に，計算量）を解説しながら現在のアルゴリズム論が計算量概念を指標として性能評価を行っていること，ならびに計算量概念の実際的（工学的）な意味を解説する．さらに，時間計算量を実験的に解析する方法も解説する．次に，ソーティングとグラフ構造の処理をおもな題材として，様々なアルゴリズムを解説する．多様なアルゴリズムを比較検討することによって，情報処理の効率が，コンピュータシステム（ハードウェアやソフトウェア）の性能だけでなく，アルゴリズムの性能にも大きな影響を受けることを理解していく． |
| 授業のねらい・到達目標 | アルゴリズムの処理性能が情報処理の効率を決定づける大きな要因の一つであることを認識できるようになる．さらに，各種アルゴリズムの基本的な考え方を理解することによって，それらを柔軟に応用できるようになる． この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。 |
| 授業の方法 | 授業の形式：【講義】 ・基本的に Blackboard, Google Classroom, OneDrive, Google Drive, Slack でコミュニケーション行う． ・事前学習・事後学習の一環として，C言語/C++, Ruby, あるい Python を用いたアルゴリズムの実現と性能評価実験を課題として出題する． ・課題の一部は自己評価・相互評価を行う場合がある．レポートには，総評することでフィードバックを行う． |
| 履修条件 | 「データ構造」の内容を理解していることを前提に講義を行う． また，文理学部教育用アカウント (stu アカウント) と NU-Apps G アカウントを適切に使い分けられることを前提とする． |
| 授業計画 | |
|---|---|
| 1 |
アルゴリズム論の概要
【事前学習】シラバスを事前に確認し、授業全体の流れを理解する. （2時間） 【事後学習】アルゴリズム論の基本的な方法論を理解する． （2時間） |
| 2 |
理論的性能評価の方法
【事前学習】アルゴリズム論の基本的な方法論について復習する． （2時間） 【事後学習】計算量概念の定義と意図を理解する． （2時間） |
| 3 |
基本的データ構造の復習（リスト・スタック・キュー） 二分探索法とその応用 【事前学習】計算量概念の定義を復習する． （2時間） 【事後学習】基本的データ構造の復習に関する簡単な実験課題を課す． （2時間） |
| 4 |
選択ソート，挿入ソート，バブルソート
【事前学習】ソーティング問題について学習する． （2時間） 【事後学習】素朴なソーティングアルゴリズムとマージソートを題材に時間計算量について理解を深める． （2時間） |
| 5 |
マージソート クイックソート 【事前学習】再帰呼び出し（再帰的定義）について復習する． （2時間） 【事後学習】再帰的な処理手順とマージ処理及びクイックソートのアルゴリズムについて理解を深める． （2時間） |
| 6 |
クイックソートの計算量解析 ヒープソート 【事前学習】クイックソートの計算量解析について学習する． （2時間） 【事後学習】クイックソートの計算量解析とヒープソートについて復習する． （2時間） |
| 7 |
第6回までのまとめと小テスト
【事前学習】第６回までに内容について復習する． （2時間） 【事後学習】グラフ理論について復習する． （2時間） |
| 8 |
グラフのデータ構造
【事前学習】グラフに関する基礎概念（グラフ理論），構造体，ポインタ，メモリの動的割り当て，データ構造について復習する． （2時間） 【事後学習】ヒープの構成方法について理解を深める．各種ソーティングアルゴリズムを実現し，性能評価実験を試みる． （2時間） |
| 9 |
幅優先探索と深さ優先探索
【事前学習】グラフのデータ構造について復習する． （2時間） 【事後学習】幅優先探索と深さ優先探索のプログラムを実現してみる． （2時間） |
| 10 |
幅優先探索・深さ優先探索の応用 最小全域木問題のアルゴリズム 【事前学習】幅優先探索・深さ優先探索の応用について復習する． （2時間） 【事後学習】グラフのデータを入力したり，（適当な形式で）出力するプログラムを試作してみる． （2時間） |
| 11 |
最小全域木問題のアルゴリズムの応用
【事前学習】最小全域木問題のアルゴリズムについて復習する． （2時間） 【事後学習】最小全域木問題に対する複数のアルゴリズムを実現して，性能比較実験を試みる． （2時間） |
| 12 |
最短路問題のアルゴリズム
【事前学習】最小全域木問題に対する応用について復習する． （2時間） 【事後学習】最小全域木問題に対する複数のアルゴリズムを実現して，性能比較実験を試みる． （2時間） |
| 13 |
動的計画法
【事前学習】最短路問題に対する複数のアルゴリズムについて復習する． （2時間） 【事後学習】動的計画法について復習する． （2時間） |
| 14 |
動的計画法の応用
【事前学習】動的計画法について応用を検討する． （2時間） 【事後学習】動的計画法の典型手法について，性能比較実験を試みる． （2時間） |
| 15 |
まとめと小テスト
【事前学習】動的計画法について復習する． （2時間） 【事後学習】全15回の内容を復習する． （2時間） |
| その他 | |
|---|---|
| 教科書 | 大槻 兼資 著 『問題解決力を鍛える!アルゴリズムとデータ構造 （KS情報科学専門書）』 講談社 2020年 第3版 |
| 参考書 | J. Kleinberg, E. Tardos 著 『アルゴリズムデザイン』 共立出版 2008年 平田富夫 『アルゴリズムとデータ構造』 森北出版 2018年 第3版 T.コルメン他著／浅野哲夫他訳 『アルゴリズムイントロダクション（第3版）第1巻，第2巻』 近代科学社 2012年 第3版 |
| 成績評価の方法及び基準 | 試験(60%)、授業内テスト(20%)、授業参画度(20%) ・試験は対面で実施する．（対面での試験を受験できない事情がある場合は，1対1あるいは少人数での面接試験・オンライン試験・レポートの組み合わせで試験に代えるなどの配慮を行う．） ・授業内テストは2回実施する．詳細は1回目の授業時に説明する． ・10回前後の事前学習あるいは事後学習の一環として課題提出を課す．この評価が授業参画度の中核をなす．一部の課題ではC言語を用いた計算機実験を行う（C++, Ruby, Python も可）． このシラバスで提示している成績評価に関する記述は，対面による試験が実施できることを前提にしたものである． 状況よって対面による試験が実施できない場合の評価方法は，そのような事態になった場合に提示する． ・基本的に Blackboard, Google Classroom, OneDrive, Google Drive, Slack でコミュニケーション行う． |
| オフィスアワー | 随時受け付ける。原則、事前にメールで予約すること。（Google Chat または Google Meet） |