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

アルゴリズム

このページを印刷する

令和２年度以降入学者 アルゴリズム
令和元年度以前入学者 アルゴリズム
教員名 谷聖一
単位数    2 学年    3 開講区分 文理学部
科目群 情報科学科
学期 後期 履修区分 選択必修
授業の形態 対面授業

Blackboard コースID: 20224416
授業概要 アルゴリズム論は，処理手順（アルゴリズム）の処理性能に対する評価方法の確立を第一の目的とし，様々な情報処理の問題に対する処理性能の良いアルゴリズムの開発を第二の目的としている．この授業では，これら二つの目的に関する基礎事項を解説する．まず，時間計算量（より一般的に，計算量）を解説しながら現在のアルゴリズム論が計算量概念を指標として性能評価を行っていること，ならびに計算量概念の実際的（工学的）な意味を解説する．さらに，時間計算量を実験的に解析する方法も解説する．次に，ソーティングとグラフ構造の処理をおもな題材として，様々なアルゴリズムを解説する．多様なアルゴリズムを比較検討することによって，情報処理の効率が，コンピュータシステム（ハードウェアやソフトウェア）の性能だけでなく，アルゴリズムの性能にも大きな影響を受けることを理解していく．
授業のねらい・到達目標 アルゴリズムの処理性能が情報処理の効率を決定づける大きな要因の一つであることを認識できるようになる．さらに，各種アルゴリズムの基本的な考え方を理解することによって，それらを柔軟に応用できるようになる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している．

なお，新カリキュラム（令和2年度以降入学者対象）では，この科目は文理学部（学士(理学)）のディプロマポリシー DP3-5及びカリキュラムポリシー CP3-5に対応している．

・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる．(A-3-3)
・問題を分析し，複数の解決策を提示した上で，問題を解決することができる．(A-4-3)
・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる．(A-5-3)
授業の方法 授業の形式：【講義】
・基本的に Google Classroom, OneDrive, Google Drive, Google Chat でコミュニケーション行う．（Blackboard や Slack は利用しない．）
・事前学習・事後学習の一環として，C言語/C++, Ruby, あるい Python を用いたアルゴリズムの実現と性能評価実験を課題として出題する．
・課題の一部は自己評価・相互評価を行う場合がある．レポートには，総評することでフィードバックを行う．
・学部の指示により遠隔形式で実施することになった場合は，同時双方向型授業（Zoom）とする．

対面参加できない学生の要件は，学部の方針に従う．
学部が定める要件を満たし，オンライン参加が認められた場合の受講方法：
・授業時間帯にZoomにて授業に参加する．
履修条件 「データ構造」の内容を理解していることを前提に講義を行う．
また，文理学部教育用アカウント (stu アカウント) と NU-Apps G アカウントを適切に使い分けられることを前提とする．
授業計画
1 アルゴリズム論の概要
【事前学習】シラバスを事前に確認し、授業全体の流れを理解する. （2時間）
【事後学習】アルゴリズム論の基本的な方法論を理解する． （2時間）
2 理論的性能評価の方法
【事前学習】アルゴリズム論の基本的な方法論について復習する． （2時間）
【事後学習】計算量概念の定義と意図を理解する． （2時間）
3 基本的データ構造の復習（リスト・スタック・キュー）
二分探索法とその応用
【事前学習】計算量概念の定義を復習する． （2時間）
【事後学習】基本的データ構造の復習に関する簡単な実験課題を課す． （2時間）
4 選択ソート，挿入ソート，バブルソート
【事前学習】ソーティング問題について学習する． （2時間）
【事後学習】素朴なソーティングアルゴリズムとマージソートを題材に時間計算量について理解を深める． （2時間）
5 マージソートとクイックソート
【事前学習】再帰呼び出し（再帰的定義）について復習する． （2時間）
【事後学習】再帰的な処理手順とマージ処理及びクイックソートのアルゴリズムについて理解を深める． （2時間）
6 クイックソートの計算量解析とヒープソート
【事前学習】クイックソートの計算量解析とヒープソートついて事前に学習する． （2時間）
【事後学習】クイックソートの計算量解析とヒープソートについて復習する． （2時間）
7 ヒープソートの計算量解析
【事前学習】各種ソートアルゴリズムについて復習する． （2時間）
【事後学習】各種ソートアルゴリズムに関する性能比較計算機実験に取り組む… （2時間）
8 第7回までのまとめと小テスト (1)
【事前学習】第1〜第7回の内容を復習する． （2時間）
【事後学習】第1〜第8回の内容を復習する． （2時間）
9 グラフのデータ構造と幅優先探索と深さ優先探索の復習
【事前学習】グラフに関する基礎概念（グラフ理論），構造体，ポインタ，メモリの動的割り当て，データ構造について復習する． （2時間）
【事後学習】幅優先探索と深さ優先探索に関する課題に取り組む． （2時間）
10 最小全域木問題のアルゴリズム
【事前学習】幅優先探索・深さ優先最小全域木問題のアルゴリズムについて事前に学習する．探索の応用について復習する． （2時間）
【事後学習】最小全域木問題のアルゴリズムについて復習する． （2時間）
11 最小全域木問題のアルゴリズムの正当性の証明と時間量解析
【事前学習】最小全域木問題のアルゴリズムの正当性について事前に学習する． （2時間）
【事後学習】最小全域木問題に関する課題に取り組む． （2時間）
12 最短路問題のアルゴリズム
【事前学習】最短路問題のアルゴリズムについて事前に学習する． （2時間）
【事後学習】最短路問題のアルゴリズムについて復習する． （2時間）
13 動的計画法
【事前学習】動的計画法について事前に学習する． （2時間）
【事後学習】動的計画法について復習する． （2時間）
14 動的計画法の応用
【事前学習】動的計画法について応用を検討する． （2時間）
【事後学習】動的計画法の典型手法について，性能比較実験を試みる． （2時間）
15 まとめと小テスト (2)
【事前学習】第1〜第14回の内容を復習する． （2時間）
【事後学習】全15回の内容を復習する． （2時間）
その他
教科書 大槻 兼資 著 『問題解決力を鍛える!アルゴリズムとデータ構造 （KS情報科学専門書）』 講談社 2020年
参考書 平田富夫 『アルゴリズムとデータ構造』 森北出版 2018年 第3版
米田 優峻 著 『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』 技術評論社 2021年
T.コルメン他著／浅野哲夫他訳 『アルゴリズムイントロダクション（第3版）第1巻，第2巻』 近代科学社 2012年 第3版
成績評価の方法及び基準 試験(60%)、授業内テスト(20%)、授業参画度(20%)
・試験は対面で実施する．（対面での試験を受験できない事情がある場合は，1対1あるいは少人数での面接試験・オンライン試験・レポートの組み合わせで試験に代えるなどの配慮を行う．）
・授業内テストは2回実施する．詳細は1回目の授業時に説明する．
・10回前後の事前学習あるいは事後学習の一環として課題提出を課す．この評価が授業参画度の中核をなす．一部の課題ではC言語を用いた計算機実験を行う（C++, Ruby, Python も可）．

このシラバスで提示している成績評価に関する記述は，対面による試験が実施できることを前提にしたものである．
状況よって対面による試験が実施できない場合の評価方法は，そのような事態になった場合に提示する．

・基本的対面出席者も Zoom 参加者も Blackboard, Google Classroom, OneDrive, Google Drive, Google Chat でコミュニケーション行う．
オフィスアワー 随時受け付ける．Google Chat にてアポイントを取ること．

↑このページのトップ