授業の目的 【日本語】
Goals of the Course(JPN) | | アルゴリズム1で学んだ基本的知識を踏まえ，グラフや文字列などのアルゴリズム，アルゴリズムの設計方法について講述する。情報関連の技術者・研究者として知っておくべきデータ構造とそのアルゴリズムとして，グラフ，文字列照合などのアルゴリズムとその計算量，さらにアルゴリズムの設計法について学ぶ。具体的には次の事項を達成することを目標とする。
1. グラフアルゴリズム，文字列照合のアルゴリズムを理解する。
2. 上述のアルゴリズムの計算量の導出過程を理解する。
3. アルゴリズムの設計法を理解する。 |
|
|
授業の目的 【英語】
Goals of the Course | | 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 |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | | アルゴリズム1で学んだ基本的知識を踏まえ，整列や，木やグラフなどの探索，アルゴリズムの設計方法について学習する。木やグラフなどの基礎的なアルゴリズムとその計算量・設計法・実現方法の理解を通じて，情報関連の技術者・研究者として知っておくべきアルゴリズムの基礎知識を学ぶ。 |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | アルゴリズム1で学んだ基本的知識をもとに，グラフ探索アルゴリズムの基本として幅優先探索および深さ優先探索，ソートアルゴリズムとしてマージソートやクイックソート，ダイクストラのアルゴリズムなど基本的なグラフアルゴリズムについて講じる。さらに，紹介したアルゴリズムをもとにアルゴリズムの設計法について講じる。
1. アルゴリズムの基本と計算量
2. 木・グラフの構造
3. 木探索
4. グラフ探索
5. ダイクストラのアルゴリズム
6. 整列
7. アルゴリズムの設計法
8. まとめと評価
毎授業後に宿題を課し，次回時にレポートとして提出する。 | |
|
|
履修条件・関連する科目
Course Prerequisites and Related Courses | | | プログラミング1,2およびアルゴリズム1を受講していることが望ましい。 | |
|
|
成績評価の方法と基準
Course Evaluation Method and Criteria | | | 講義中に与える演習課題，期末試験の結果を総合的に判断して，合計100点満点で60点以上を合格とする。アルゴリズムの基本的な設計技法を理解し，整列アルゴリズムの計算量の算出，グラフアルゴリズムなどの計算量の議論を理解できる知識を身に付いていることを合格の基準とする。 | |
|
|
教科書・参考書
Textbook/Reference book | | （教科書）平田富夫，アルゴリズム設計とデータ構造，サイエンス社，2015
（参考文献）平田富夫，Cによるアルゴリズムとデータ構造，科学技術出版，2002。他，必要に応じて指定する。
（履修条件等）アルゴリズム1の単位を取得済みであることが望ましい。 | |
|
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | | 講義において説明した理論を理解するために課題を与える。 | |
|
|
授業開講形態等
Lecture format, etc. | | | 対面授業を実施し，必要に応じてオンデマンドで視聴可能な講義ビデオを提供する。 |
|
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | |
|