| Course Name | Year | Term | Period | Faculty / Graduate School | All Instructors | Credits |
|---|---|---|---|---|---|---|
| 32589:[2025 Spring]Data Science Ⅲ (T1) § 32590:Theory of Algorithms (X1) | 2025 | Spring | Mon4 | College of Science and Engineering | ISHII HIDENORI | 2 |
Campus
Class Venue
Language
Course Outline and Method
この授業ではアルゴリズムの中でも特にグラフやネットワークに関わるアルゴリズムを紹介します。
例えば、ある場所から、ある場所に車で移動する場合にどの経路を通るのが一番早いかという問題は最短経路問題と言われます。このような問題を解決するために、まず、道路の地図を数理モデル化することから始める。すると、重み付グラフ（ネットワーク）という数学的概念が出てきます。その上で、2地点間のすべての経路を調べていたら、とんでもなく時間がかかるので、うまいアルゴリズムが必要となります。本授業では、重み付グラフに関するいくつかのアルゴリズムを学びます。そのために、グラフ理論の基礎から始めます。グラフ理論の創始者はかの有名なオイラー（1707-1783）で、グラフ理論に関する最初の論文(1736年)は「ケーニヒスべルクの橋の問題」に端を発している。グラフに関する基本概念やさまざまな例を学んだうえで、グラフをコンピュータで扱うために、グラフの記憶方法と、それをもとにしたグラフの探索について学びます。これは、その後に続く、グラフに関するアルゴリズムの基本となります。
最後に、重み付グラフに関して、最小木問題、最短経路問題のアルゴリズムを学びます。時間があれば、さらなる話題も扱いたいと思っています。
Student Attainment Objectives
２）グラフに関するアルゴリズム、とりわけ、広さ優先探索、深さ優先探索を理解し、応用できる。
３）重み付グラフが現実社会のどのような問題についての数理モデルか説明できる。
４）重み付グラフに関する最小木や最短木を求めるアルゴリズムが理解できていて、具体的に求めることができる。
Recommended Preparatory Course
Course Schedule
| Lecture/Instructor（When there are multiple instructors) | Theme |
|---|---|
| Keyword, References and Supplementary Information | |
| - | +R授業対象科目。第7回に+R授業を実施。詳細はmanaba+Rを参照。 |
|
|
| 1 | 導入、グラフの定義と基本概念、道、閉路 |
グラフと言っても、2次関数のグラフとはちと違う |
|
| 2 | グラフの連結性、オイラーグラフ |
オイラーグラフは一筆書き |
|
| 3 | オイラーの定理と証明 |
オイラーがグラフ理論の創始者 |
|
| 4 | グラフの同型と種々の例 |
何事にも同型がある。 |
|
| 5 | 木 |
木と言っても、庭に生えてる木とは違う。 |
|
| 6 | ラベル付き木、根付木、グラフの生成木 |
さまざまな木 |
|
| 7 | 平面グラフ |
平面に交叉なく実現できるグラフ |
|
| 8 | 平面グラフに関するオイラーの公式と供給問題 |
多面体の位相幾何学と関連あり |
|
| 9 | 隣接行列と隣接リスト |
コンピュータでグラフを記憶 |
|
| 10 | 広さ優先探索と深さ優先探索 |
グラフアルゴリズムの基礎となる |
|
| 11 | 深さ優先探索とトポロジー順序 |
応用例 |
|
| 12 | 重み付グラフと最小木問題． |
ネットワークとも言う |
|
| 13 | クラスカルのアルゴリズムとプリムのアルゴリズム |
最小木を求めるアルゴリズム |
|
| 14 | 最短経路問題とダイクストラのアルゴリズム |
最短路アルゴリズム。カーナビ
|
Class Format
Recommendations for Private Study
Grade Evaluation Method
| Kind | Percentage | Grading Criteria etc. |
|---|---|---|
| Final Examination (Written) | 0 | |
| Report Examination (A report to be submitted by the unified deadline) |
0 | |
| Exams and/or Reports other than those stated above, and Continuous Assessment (Evaluation of Everyday Performance in Class) |
100 | 日常的な課題等 |
Grade Evaluation Method （Note）
Advice to Students on Study and Research Methods
Textbooks
Textbooks （Frequency of Use, Note）
Reference Books
| Title | Author | Publisher | ISBN Code | Comment |
|---|---|---|---|---|
| Introductory Graph Theory | Gary Chartrand | Dover | ||
| グラフ理論入門 | ウイルソン | 近代科学社 |
Reference Books （Frequency of Use, Note）
Web Pages for Reference
How to Communicate with the Instructor In and Out of Class(Including Instructor Contact Information)
Other Comments
URL:https://secure.ritsumei.ac.jp/students/pathways-future/course/curriculum.html/