うつろぐ

文章

FMS生に向けた「ネットワーク理論」履修上のことについて

学科向けの記事です。
FMSB2で僕が履修したNDの「ネットワーク理論」について。
(この記事の内容は2017年度の「ネットワーク理論」に基づいたものです。来年度は担当教員、評価、講義の進行が異なる場合があります。)

基本情報

ネットワーク理論はNDの選択必修の2年次科目(2016年入学者用カリキュラム時点)で、MSとFMSの生徒は他学科履修科目として履修することができる。他学科履修科目なので他学部履修科目のような窓口の問い合わせは必要なく、履修登録画面から選択することができる。評価は授業中の演習30%、平常点10%(謎、たぶん出席)、期末考査60%。2単位。

科目の内容

ざっくり。
グラフ理論についての基礎(隣接行列によるグラフの表現など)をさらっとやって、そこから様々な有名な問題についてグラフ理論による解析の例を学ぶ。

まずグラフっていうのはこういうやつ。
f:id:Distorted_Unchi:20180131175115p:plain
点を要素、辺を関係として要素と要素の関係性を表現できるやつ。駅と駅を線路で繋ぐネットワークを表してもいいし、辺を矢印にして(有向グラフ)動物の捕食関係やワークフローを表してもいい。

でここからグラフ理論を活用した簡単な例を一部紹介すると、
f:id:Distorted_Unchi:20180131175152p:plainf:id:Distorted_Unchi:20180131175249p:plain
左のグラフは一筆書きできるけど右のグラフは何をどうやっても一筆書きできない。あと左のグラフは「一筆書きでかつ始点が終点と一致する」みたいなことができない。こういう内容が定理で証明できたり、
f:id:Distorted_Unchi:20180131175830p:plain
A~E駅を鉄道で繋ぐ際に線路整備コスト(各辺の数字)が最小になる繋ぎ方を求めるアルゴリズムがわかったりする。
他にも4つの立方体の問題(急性精神病問題)とか6人の会合(参考:ラムゼーの定理と6人の問題 | 高校数学の美しい物語)とか最大流問題とか色々やったけど今回は図が簡単に書けるやつだけ図を出しました。デジタルな図書くの意外としんどい。
6人の会合については一般化したラムゼーの定理には触れなかったので、そこまで踏み入ってくれればもっと面白かったのになあと思う。授業の傾向としては全体的に、色々なグラフ理論に関する問題に浅めに扱う感じ。

講義

(2017年度の「ネットワーク理論」に基づいたもの)
基本的に出席はない。が、抜き打ちで一回だけ出席取ってたり、宿題(演習課題)のプリントを講義の終わりに配ってたりしたし、講義資料のPDF配布がなくプリントなので基本的に出席しないと(特にアウェイなMSやFMSの人は)困ることが多い。講義はプリントの穴埋め形式で進むし進行もゆっくりめなのであんまり理解に困ることはない。説明もけっこう分かりやすい。教科書は全く使わなかったので来年も担当が同じ人なら買わなくていいけど、内容を深めるための参考書としては良質。
科目の内容の関係上、前提となる数学的スキルは殆どない。基本的な行列の演算や、高校レベルの数列、場合の数に関しての理解ができれば十分。
講義中に演習問題を解くけど、それを提出したりはしない。授業外課題に関しては、2回だけ宿題(演習課題)があったが、あまり負担は大きくない。

テスト

(2017年度)
この辺りの分野はいくらでも応用問題が作れるのでテストもそんな感じなのではとビクビクしていたが、意外にも講義で扱った問題そのままの出題が殆どだった。講義プリントを全て真面目に復習していれば確実に解けるものだった。とはいえ扱った内容の量自体が相当なものなので復習にはそれなりに時間がかかるんだけど。

単位

授業外の負担がかなり少なめなので、授業を受けて復習をそれなりにやってテストに臨めば楽な部類に入ると思う。ただ、当然のことかもしれないけど、内容に興味がないと講義とかテスト対策とかに対してモチベが出なさそうな科目だな~と思った。

所見

「この分野に関して興味があるけどグラフ理論真面目に学んだこと全くない」という人にはおすすめの科目。少し独学してる、みたいな人には講義内容は退屈になると思う。講義内容を踏まえて自分で更に発展させたい、みたいなことは比較的やりやすいと思う。また、グラフに関する問題を解決するアルゴリズムがけっこう出てくるので、FMSにありがちな「それをコンピューターにやらせるぞ~」みたいな動機も生まれやすいので、アルゴリズム実装オタクにもおすすめ。