| 授業の目的 【日本語】 | | アルゴリズム1で学んだ基本的知識を踏まえ，グラフや文字列などのアルゴリズム，アルゴリズムの設計方法について講述する。情報関連の技術者・研究者として知っておくべきデータ構造とそのアルゴリズムとして，グラフ，文字列照合などのアルゴリズムとその計算量，さらにアルゴリズムの設計法について学ぶ。具体的には次の事項を達成することを目標とする。
1. グラフアルゴリズム，文字列照合のアルゴリズムを理解する。
2. 上述のアルゴリズムの計算量の導出過程を理解する。
3. アルゴリズムの設計法を理解する。 |
|
|
| 授業の目的 【英語】 | | In addition to knowledges learned at Algorithm 1, throughout lectures on algorithms for graphs and strings and algorithm design. we learn graph algorithms, string matching, their complexity, and paradigm of algorithm design, as basic algorithms and data structures that technicians and researchers of informatics should be familiar with. We aim at acquiring the following topics:
1. graph algorithms and string matching
2. how to derive complexity of the above algorithms
3. paradigm of algorithm design |
|
|
| 到達目標 【日本語】 | | | アルゴリズム1で学んだ基本的知識を踏まえ，整列や，木やグラフなどの探索，アルゴリズムの設計方法について講義を実施する。木やグラフなどの基礎的なアルゴリズムとその計算量・設計法・実現方法の理解を通じて，情報関連の技術者・研究者として知っておくべきアルゴリズムの基礎知識を学ぶ。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | アルゴリズム1で学んだ基本的知識をもとに，グラフ探索アルゴリズムの基本として幅優先探索および深さ優先探索，ソートアルゴリズムとしてマージソートやクイックソート，ダイクストラのアルゴリズムなど基本的なグラフアルゴリズムについて講じる。さらに，紹介したアルゴリズムをもとにアルゴリズムの設計法について講じる。
1. アルゴリズムの基本と計算量
2. 木・グラフの構造
3. 木探索
4. グラフ探索
5. ダイクストラのアルゴリズム
6. 整列
7. アルゴリズムの設計法
8. 総括 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に与える演習課題，期末試験の結果を総合的に判断して，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | （教科書）平田富夫，アルゴリズム設計とデータ構造，サイエンス社，2015
（参考文献）平田富夫，Cによるアルゴリズムとデータ構造，科学技術出版，2002。他，必要に応じて指定する。
（履修条件等）アルゴリズム1の単位を取得済みであることが望ましい。 | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|