離散数学特論 ガイダンス資料
担当 松田 晴英，研究室は
4
号館5
階の4501-3
オフィスアワー 火
5
限(この時間以外でも研究室在室中であれば，原則的には対応します)メールアドレス
[email protected]
教科書 離散数学入門
[
改訂版]
，秋山仁，R.L.Graham
著，朝倉書店評価方法と基準 数回にわたるレポート報告により評価する。各評価の合計が
60%
以上を合格とする。授業サポート
web http://www.sic.shibaura-it.ac.jp/~hmatsuda/
授業の概要 コンピューターの発展に伴って，無限ではないけれど，天文学的な数でしか表現できな いような多くの場合を考慮しない限り，真実にたどり着かない問題を扱う機会が増えています。
本講義では，こうした巨大な数で表現される対象を効率よく解く手法について学びます。例え ば，離散的な問題の例として，カーナビゲーションシステムに代表されるような，順列や組合 せをしらみつぶしに調べる問題があります。このような問題はコンピューターを用いて解くと よいのですが，その効率的な解法の設計や研究は重要です。というのは，ある問題を解く
(
コン ピューターに解かせる)
のに要する時間は解法の設計に大きく依存するからです。設計が悪いた めに，解けるはずの問題が現実的な時間内に解けなくなることさえあります。この講義では離散数学のうち，特に，組合せ幾何／可視性問題／最短ネットワーク／詰込み／
スケジュール作成／コンピューターの限界などを学びます。
達成目標
1.
組合せ幾何の代表的な結果を理解する。2.
可視性問題とその応用について理解する。3.
最短ネットワークの基礎事項を学び，社会への応用について理解する。4.
詰め込み問題の基礎事項を学び，社会への応用について理解する。授業計画
