Course Name Year Term Period Faculty / Graduate School All Instructors Credits
34158:Data Science Ⅲ (T1) § 34159:Theory of Algorithms (X1) 2022 Spring Mon4 College　of　Science　and　Engineering ISHII HIDENORI 2

Campus

BKC

Class Venue

Co-learning106

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
1

導入、グラフの定義と基本概念、道、閉路

グラフと言っても、2次関数のグラフとはちと違う

2

グラフの連結性、オイラーグラフ

オイラーグラフは一筆書き

3

オイラーの定理と証明

オイラーがグラフ理論の創始者

4

グラフの同型と種々の例

何事にも同型がある。

5

木

木と言っても、庭に生えてる木とは違う。

6

ラベル付き木、根付木、グラフの生成木

さまざまな木

7

平面グラフ

平面に交叉なく実現できるグラフ

8

平面グラフに関するオイラーの公式と供給問題

多面体の位相幾何学と関連あり

9

隣接行列と隣接リスト

コンピュータでグラフを記憶

10

広さ優先探索と深さ優先探索

グラフアルゴリズムの基礎となる

11

深さ優先探索とトポロジー順序

応用例

12

重み付グラフと最小木問題．

ネットワークとも言う

13

クラスカルのアルゴリズムとプリムのアルゴリズム

最小木を求めるアルゴリズム

14

最短経路問題とダイクストラのアルゴリズム

最短路アルゴリズム。カーナビ

15

まとめとさらなるアルゴリズム

時間があれば、その他のアルゴリズムにも触れたいが・・・

Class Format

【BCPレベル1~2の場合 / In the case of BCP level 1-2】
・第２回～第９回は教室での対面授業。それ以外はWEB授業

【BCPレベル3~4の場合 / In the case of BCP level 3-4】
・WEB授業

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

日常的な課題等
なお、BCPレベルにより成績評価方法は変更しない。

Grade Evaluation Method （Note）

Advice to Students on Study and Research Methods

Textbooks

Textbooks （Frequency of Use, Note）

教科書は用いず、資料をpdfで配布する。

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)

Talk with Students

Other Comments


【科目ナンバリング・カリキュラムマップはこちらから/Click here to see the Curriculum-Map and Course-Numbering】
URL:http://www.ritsumei.ac.jp//students/pathways-future/course/curriculum.html