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

アルゴリズム

このページを印刷する

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

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

・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる．(A-3-3)
・問題を分析し，複数の解決策を提示した上で，問題を解決することができる．(A-4-3)
・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる．(A-5-3)
授業の形式 講義
授業の方法 第1回目授業までに，本授業の Google Classroom 及び本授業用 Google Chat スペースに参加すること．
参加方法は Blackboard にて告知する．なお，Blackboard をこの目的以外に使用することはない．

・本授業では，Google Classroom, Google Drive, Google Chat でコミュニケーション行う．（Blackboard や Slack は利用しない．）
・講義内では，基本的に，アルゴリズムの計算量評価やアルゴリズム正当性の証明を扱う．
事前学習・事後学習の一環として，C言語/C++, Python, あるいは RUby を用いたアルゴリズムの実現と性能評価実験を課題として出題する．
・課題の一部は自己評価・相互評価を行う場合がある．レポートには，総評することでフィードバックを行う．
・学部の指示により遠隔形式で実施することになった場合は，同時双方向型授業（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%)、授業内テスト:小テスト (1) の得点．小テスト (2) の得点は，試験の一部とする．(20%)、授業参画度(20%)
・小テストを2回実施するが，小テスト (1) のみ授業内テスト扱いとする．小テスト (2) は試験の一部とする．
・8回前後の事前学習あるいは事後学習の一環として課題提出を課す．この評価が授業参画度の中核をなす．一部の課題では実装を伴う計算機実験を行う（実装に用いるプログラミング言語は，C, C++, Python, Ruby のいずれかとする）．
・Google Classroom, Google Drive, Google Chat でコミュニケーション行う．この授業では，Blackboard や Slack は使用しない．．
オフィスアワー 随時，Google Chat で受け付ける．
なお，対面を希望する場合は事前に Google Chat でで予約すること．

↑このページのトップ