離散数学
講義要項
自然科学概論 I(離散・組合せ幾何入門)
- 講義の内容・授業スケジュール
- 離散幾何学とは点や図形の配置の(ある意味での)最適化問題、極値問題に関する幾何学です。離散幾何学の中でも有限個の点や図形の配置などを扱う場合は組合せ幾何と呼ばれます。
- 自然科学概論 Iでは可視性問題を扱います。次のような問題が可視性問題です。
- 「美術館の内部すべてを監視するために必要な防犯カメラの最小台数はいくつか?」(美術館問題)
- 「すべての壁が鏡になっている部屋の勝手に選んだ1点で電灯を灯すと部屋全体に明かりが行き渡る。」(ミラー・ルーム予想)
- 他の可視性問題として要塞問題/刑務所問題/警備問題/照明問題などがあります。
これらの問題を学び、数学的直観性と論理性を身に付けることを目標とします。
- 成績評価の方法
- 筆記試験。出欠席とレポートを考慮します。
- 教科書
- 秋山仁/R.L.Graham『離散数学入門』[改訂版]朝倉書店
自然科学概論 II(離散・組合せ幾何入門)
- 講義の内容・授業スケジュール
- 離散幾何学とは点や図形の配置の(ある意味での)最適化問題、極値問題に関する幾何学です。離散幾何学の中でも有限個の点や図形の配置などを扱う場合は組合せ幾何と呼ばれます。
- 自然科学概論 IIでは最短ネットワーク問題と詰め込み問題を扱います。
次のような問題が最短ネットワーク問題です。
- 「n個の都市に、どの2つの都市も往来可能となるように高速道路を設計しようと思う。ただし、道路の長さが1km違っただけで工事にかかるコストには大きな差が生じるので、高速道路をどのように設計すればよいだろうか?」
- 詰め込み問題では次のような問題を考えます。
- 「2×1000の長方形内に単位円を出来るだけ詰め込みたい。いくつまで詰め込むことが出来るか?」
- これらの問題を学び、数学的直観性と論理性を身に付けることを目標とします。
- 成績評価の方法
- 筆記試験。出欠席とレポートを考慮します。
- 教科書
- 秋山仁/R.L.Graham『離散数学入門』[改訂版]朝倉書店
期末テスト
Copyright (C) Makoto Ozawa. All Rights Reserved.