| 授業科目名 | 年度 | 学期 | 開講曜日・時限 | 学部・研究科 | 全担当教員 | 単位数 |
|---|---|---|---|---|---|---|
| 31829:データサイエンスⅢ (T1) § 31830:アルゴリズム論(X1) | 2023 | 春セメスター | 月4 | 理工学部 | 石井 秀則 | 2 |
キャンパス
授業施設
授業で利用する言語
授業の概要と方法
この授業ではアルゴリズムの中でも特にグラフやネットワークに関わるアルゴリズムを紹介します。
例えば、ある場所から、ある場所に車で移動する場合にどの経路を通るのが一番早いかという問題は最短経路問題と言われます。このような問題を解決するために、まず、道路の地図を数理モデル化することから始める。すると、重み付グラフ（ネットワーク）という数学的概念が出てきます。その上で、2地点間のすべての経路を調べていたら、とんでもなく時間がかかるので、うまいアルゴリズムが必要となります。本授業では、重み付グラフに関するいくつかのアルゴリズムを学びます。そのために、グラフ理論の基礎から始めます。グラフ理論の創始者はかの有名なオイラー（1707-1783）で、グラフ理論に関する最初の論文(1736年)は「ケーニヒスべルクの橋の問題」に端を発している。グラフに関する基本概念やさまざまな例を学んだうえで、グラフをコンピュータで扱うために、グラフの記憶方法と、それをもとにしたグラフの探索について学びます。これは、その後に続く、グラフに関するアルゴリズムの基本となります。
最後に、重み付グラフに関して、最小木問題、最短経路問題のアルゴリズムを学びます。時間があれば、さらなる話題も扱いたいと思っています。
受講生の到達目標
２）グラフに関するアルゴリズム、とりわけ、広さ優先探索、深さ優先探索を理解し、応用できる。
３）重み付グラフが現実社会のどのような問題についての数理モデルか説明できる。
４）重み付グラフに関する最小木や最短木を求めるアルゴリズムが理解できていて、具体的に求めることができる。
事前に履修しておくことが望まれる科目
授業スケジュール
| 授業回数/ 担当教員（複数担当の場合） |
テーマ |
|---|---|
| キーワード・文献・補足事項等 | |
| 1 | 導入、グラフの定義と基本概念、道、閉路 |
グラフと言っても、2次関数のグラフとはちと違う |
|
| 2 | グラフの連結性、オイラーグラフ |
オイラーグラフは一筆書き |
|
| 3 | オイラーの定理と証明 |
オイラーがグラフ理論の創始者 |
|
| 4 | グラフの同型と種々の例 |
何事にも同型がある。 |
|
| 5 | 木 |
木と言っても、庭に生えてる木とは違う。 |
|
| 6 | ラベル付き木、根付木、グラフの生成木 |
さまざまな木 |
|
| 7 | 平面グラフ |
平面に交叉なく実現できるグラフ |
|
| 8 | 平面グラフに関するオイラーの公式と供給問題 |
多面体の位相幾何学と関連あり |
|
| 9 | 隣接行列と隣接リスト |
コンピュータでグラフを記憶 |
|
| 10 | 広さ優先探索と深さ優先探索 |
グラフアルゴリズムの基礎となる |
|
| 11 | 深さ優先探索とトポロジー順序 |
応用例 |
|
| 12 | 重み付グラフと最小木問題． |
ネットワークとも言う |
|
| 13 | クラスカルのアルゴリズムとプリムのアルゴリズム |
最小木を求めるアルゴリズム |
|
| 14 | 最短経路問題とダイクストラのアルゴリズム |
最短路アルゴリズム。カーナビ |
|
| 15 | まとめとさらなるアルゴリズム |
時間があれば、その他のアルゴリズムにも触れたいが・・・ |
授業実施形態
During the suspension period of BCP, classes will be as described in BCP levels 0-2.
【BCPレベル1~2の場合 / In the case of BCP level 1-2】
・第２回～第９回は教室での対面授業。それ以外はWEB授業
【BCPレベル3~4の場合 / In the case of BCP level 3-4】
・WEB授業
授業外学習の指示
成績評価方法
| 種別 | 割合(%) | 評価基準等 |
|---|---|---|
| 定期試験（筆記） | 0 | |
| レポート試験 （統一締切日を締切とするレポート） |
0 | |
| 上記以外の試験・レポート、平常点評価 （日常的な授業における取組状況の評価） |
100 | 日常的な課題等
|
成績評価方法(備考)
受講および研究に関するアドバイス
教科書
教科書(使用頻度、その他補足)
参考書
| 書名 | 著者 | 出版社 | ISBNコード | 備考 |
|---|---|---|---|---|
| Introductory Graph Theory | Gary Chartrand | Dover | ||
| グラフ理論入門 | ウイルソン | 近代科学社 |
参考書(使用頻度、その他補足)
参考になるwwwページ
授業内外における学生・教員間のコミュニケーションの方法
備考
URL:https://secure.ritsumei.ac.jp/students/pathways-future/course/curriculum.html/