離散数理工学

http://dopal.cs.uec.ac.jp/okamotoy/lect/2025/dme/

離散幾何・計算幾何に関する基礎概念を習得し, 諸分野における問題をそれらによってモデル化および解決するための方法論を学習する. 達成目標は次の3項目である. (1) 離散幾何・計算幾何における用語を正しく使うことができる. (2) 離散幾何・計算幾何における基本的な概念について, 具体例の計算ができる. (3) 離散幾何・計算幾何における典型的な論法を用いて, 証明を書くことができる.

離散数学, プログラミング通論, 線形代数学第一, 線形代数学第二, アルゴリズム論第一

アルゴリズム論第二, グラフとネットワーク

教科書:指定しない. 講義資料を毎回用意するので, 講義webページより各自入手すること.

参考書:マトウシェク著『離散幾何学講義』丸善出版, など.

授業内容
第1回:低次元 (1) 多角形と三角形分割
第2回:低次元 (2) 点配置と直線配置
第3回:低次元 (3) 近接グラフと交差グラフ
第4回:低次元 (4) 距離とボロノイ図
第5回:低次元 (5) 多角形内の距離
第6回:低次元 (6) 二次曲線と楕円
第7回:前半のまとめ
第8回:高次元 (1) 高次元の物体の取り扱い方
第9回:高次元 (2) 凸集合と凸包
第10回:高次元 (3) 凸多面体の面構造
第11回:高次元 (4) 点配置と超平面配置
第12回:高次元 (5) 点配置と次元削減
第13回:高次元 (6) 距離とボロノイ図
第14回:最近の話題
第15回:後半のまとめ

進め方
対面授業とオンデマンド教材を併用する. 詳しくは「授業関連webページ」http://dopal.cs.uec.ac.jp/okamotoy/lect/2025/dme/ を参照すること. また, 「遠隔授業に関する情報」に記載されているGoogle Classroomのコードを参照して, クラスルームに参加すること.

講義動画と演習問題, プログラミングを用いて, 予習・復習を励行するように.

評価方法:次の2つによって評価を行う
(1) 毎回行う演習問題 (約10%)
(2) 2回の定期試験 (約90%)
評価基準:以下の到達レベルをもって合格の最低基準とする.
(1) 離散幾何・計算幾何における用語を正しく使うことができる.
(2) 離散幾何・計算幾何における基本的な概念について, 具体例の計算ができる.
(3) 離散幾何・計算幾何における典型的な論法を用いて, 証明を書くことができる.
ただし, 用語や概念を暗記する必要はない.

アポイントメントによる.

離散幾何・計算幾何は, 低次元の場合にコンピュータ・グラフィックス, 地理情報システム, センサ・ネットワークなど, 高次元の場合に最適化, 機械学習, データサイエンスなど, 多くの応用に対する基盤となります. また, それ自体が数学的にも面白い対象であり, 古くから研究されてきました. 皆さんが知らない離散数学の一面に触れてみてください.

他類, 他プログラムの学生も歓迎する.