離散数理工学

電気通信大学情報理工学域I類 (情報系)
2025年度後学期
火曜1限 (9:00-10:30)
教室：西8-132

岡本吉央

実施形態

この授業は次のように実施されます．

講義自体はオンデマンド講義動画で提供されます．
リアルタイム対面授業では，質疑応答と演習を行います．演習はグループで行うことを想定しています．

そのため，お薦めする受講形態は以下のとおりです．

授業日の前日まで：オンデマンド講義動画を視聴する → 質問やコメントをフォームから投稿する (18:00まで)
授業日：リアルタイム対面授業に出席する → オンデマンド講義に関する質疑応答を行う → リアルタイム授業で演習問題にグループで取り組む
授業日の後：自習で演習問題に取り組む → 演習問題をレポートで提出する

ただ，これを全部やるのは，かなり時間と労力を取られます．もし「最小限の勉強で済ませたい」という場合は「オンデマンド講義動画を視聴する」だけでも構いませんし，「スライドを閲覧する」だけでも構いません．受講形態によって成績評価が決められるということはありません (し，受講形態の記録も取りません)．成績評価はただ単に2回の試験のみで行われます (レポートに変更となる可能性もありますが)．ただ，理解のために時間や労力を使わなければ，勉強になりませんし，芳しい成績評価を得ることも難しくなるでしょう．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

演習シート (全回共通)
用語集 (全回共通)
10/21 第1回　低次元 (1)：多角形と三角形分割
10/7 第0回　ガイダンス

10/7 第0回　ガイダンス
- コメントをありがとうございます．皆さんのコメントとそれに対する返答は次のように掲載されます．次回 (第1回) からは，毎回授業前日の18:00頃までに投稿されたコメントが，授業日の回のコメントとしてここに掲載されます．
- (TAより) 後で今日の録画確認すれば分かりますが，スライド8ページの反復回数の期待値とかで分数が出てきていたとき，先生の読み方が全部逆だったような…（「AでBを割る」か「AをBで割る」か忘れちゃいましたけど，とにかくAとBが逆になっていた気がします）
  --ありがとうございます．たしかに間違って言っている部分がありました．文脈から訂正できるかと思いますので，みなさんご注意ください．
- よろしくお願いいたします。
  --こちらこそよろしくお願いいたします．
- よろしくお願いします。
  --こちらこそよろしくお願いします．
- 離散数理工学履修しようと思います。半年間よろしくお願いします。
  --半年間よろしくお願いします．
- 問題を解くことができたので良かった
  --よかったです．解けなくても考えることが重要なので，ぜひ励行してください．
- 授業が1限にあるので、毎回遅れないよう出席していきたい
  --遅れることに慣れてしまうと，遅れがちになるので，遅れないことに慣れていってください．
- 面白そうな授業だと感じました。次回の講義を受けて、履修しようか決めたいと思います。
  --はい，よく検討して決めてください．(なお，学修要覧によると，単位を取得することまで含めて「履修」と呼ぶようです．履修登録をするだけでは履修したことにならないので，ご注意ください．)
- 今年から幾何の内容になるとのことで、幾何学はどちらかといえば苦手で自信がないのですが、頑張ってついていきたいと思います。
  --はい，分からないことはどんどん質問してください．
- 成績の付け方や演習への取り組み方などが詳しく説明されていて良かった。学生に優しい授業そうで安心している。
  --学生に優しいかどうかは，私が判断することではないので，その判断は皆さんに委ねます．ただ，私としては，指示が明確になるように気をつけてはいるつもりです．うまくいっているかどうか，自信はないので，分からないことはどんどん聞いてください．
- よろしくおねがいします。初回なので、好きなことを話します。好きなことは音楽を聞くことです。特にドラムやベースが際立ってる曲や気持ち明るめな曲が好きです。最近ハマっている曲はTrySailの「Adrenaline!!!」という曲です。よかったら聞いてみてください。
  --The F1rst Takeで聞いてみました．元気のでる曲ですね．ベースに注目すると，メロディーとユニゾンになるところがあって，そこが気持ちよかったです．
- スライド内の矢印の記法について質問です。「→」と「↝」に何か違いはありますか？
  --スライド内では気分で使い分けていて，違いはありません．よくないですね．
- 演習問題の授業内問題 0.1において、アルゴリズムの観点から、2桁の数で10種類の数を使うような問題として1024通りを全探索することによって解くことができると考えました。しかし、これは拡張性に乏しいため、数学的に解く方法に感心しました。
  --1024とおりを全探索することによって解くことは，問題解決の手法としてはよいものです．問題ありませんし，他の数字でも同じ考えを適用できるので，その意味での拡張性は高いと思います．一方で，その方法に問題があるとすれば，説明が難しいということです．1024とおりを全部考えて，それを見せるという説明は，検証するのが大変です．検証が簡単な説明をできるように考えることは重要だと思います．その点で「数学的に解く方法」は，論理的な思考ができれば，簡単に説明できるものだと思います．
- 授業内問題0.1に関しては、考えようとしていたところに隣の人が答えを言っているのが聞こえてきてしまって、自分の力では考えられませんでした。こういうことがあるから、答えが分かっていてもすぐにネタバレをするのではなく、ひとまず待つということを心掛けようと思いました。「書けるだろうか」と問われて、例を一つ見つけなければいけないのだと思い込んでいましたが、「そうか、書けないという選択肢もあるのか」となりました。でも、今回の場合100だから書けないということでそれを証明してすぐ終わりでしたが、逆に108など9の倍数だったら書けない場合よりも一苦労ありそうだと感じました。最小が45で、そこから1なら9、2なら18、3なら27と増えていくので、それら9の倍数の和で108-45=63を作るという、何か別の問題に置き換わるような気がします。もちろん全部9の倍数なので9で割れば多少は簡単というか分かりやすくなる気もしますが。でも、授業内問題0.1のような問題は数学では見たことがありませんでしたが、こういう風に9や18や27から選んで63を作る(1や2や3から選んで7を作る)という問題は数学であってもおかしくないような問題に思えるので、受験数学的な観点で見れば「習っていない問題を習ったことのある問題に落とし込む」ということができているのではないかと思います。この科目では多次元の問題について扱うとのことでしたが、我々が生きているのはもちろん三次元(空間だけでなく時間も含めれば四次元？)なので、図などを描いて考えるのは多少無理があるように感じます。ですが、数学では立方体の投影図や見取図を描いたり、斜影ベクトルを考えたりするように、低次元に落とし込むということはできるのではないかと感じました。どんな立体も影を落とせば二次元になりますが、その影を作り出すために光をどこから当てるのかが腕の見せ所なのかもしれないです。そういった意味で、数学者は一種の照明係と言ってもよいかもしれないと感じました。
  --数学というのは「無限」とか「高次元」といった目に見えないものをいかに扱うかということに苦心してきました．それらを扱うための記号や図式，論理を編み出してきたわけです．これは，ご指摘のとおり，数学的な対象に照明をうまくあてて，影を見ていると考えられます．これは数学だけではなくて，一般の言語活動についても同じことがいえるように思います．考えていることや想像していることを表現することは，その思考や想像のすべてを尽くすことができるとは限りません．そうであっても，考えを伝えるために，考えに照明をうまくあてて，できた影を言葉として表現しているのだと思います．
- 演習問題で頭を動かせてスッキリした朝を過ごせた。
  --それはよかったです :-)
- 今日の演習問題面白かったです。サイコロはわかりませんでした、、、
  --まずは考えることが重要です．分からないことについて，あまり悲観的にならないでください．考えてみて分からない場合は，ヒントを出しますので，聞いてください．
- 専門科目で先生からグループワークを推奨されることが無かったので、新鮮でした。
  --演習問題にグループで取り組むことを推奨しています．本当は強制にしたいぐらいですが，各自の事情もあるでしょうから推奨にとどめています．他の学生と協同できることが大学のよいところですから，その環境をぜひ活かしてください．
- 演習問題は少し捻った高校入試を解いてるような感覚で楽しかった。
  --今後の演習問題もぜひ楽しんでください．

試験・成績評価

各回の授業内演習と2回の試験により，成績の評価を行う予定です．
成績の計算方法
- 授業内演習の配点：1点×12回 = 12点満点
  - 授業内演習は9:20までに教室へ入らないと1点が与えられません．9:20を越える場合は理由 (公共交通機関の遅延証明書など) を添えてください．
- 試験の配点：50点×2回 = 100点満点
- 成績 = min{授業内演習の素点+試験の素点, 100}

公式シラバス

こちらをご覧ください

スケジュール (予定)

以下は仮の予定です．変更もありえます．

10/7 第0回　ガイダンス
10/14 休み (体育祭)
10/21 第1回　低次元 (1)：多角形と三角形分割
10/28 第2回　低次元 (2)：点配置と直線配置
11/4 第3回　低次元 (3)：近接グラフと交差グラフ
11/11 第4回　低次元 (4)：距離とボロノイ図
11/18 第5回　低次元 (5)：多角形内の距離
11/25 第6回　低次元 (6)：二次曲線と楕円
12/2 休み (秋ターム試験)
12/9 中間試験
12/16 第7回　高次元 (1)：高次元の物体の取り扱い方
12/23 第8回　高次元 (2)：凸集合と凸包
12/30 休み (冬季休業)
1/6 第9回　高次元 (3)：凸多面体の面構造
1/13 第10回　高次元 (4)：点配置と超平面配置
1/20 第11回　高次元 (5)：点配置と次元削減
1/27 第12回　高次元 (6)：距離とボロノイ図
2/3 休み (修士論文発表会)
2/10 期末試験

参考書

生協には次の本をお願いしました．ただし，これらに書かれていることをすべて授業で扱うわけではありませんし，ここに書かれていないことも授業で扱います．他にも「計算幾何」や「離散幾何」に関する本は参考になるかもしれません．

M. ドバーグ，O. チョン，M. ファンクリベルド，M. オーバーマーズ，『コンピュータ・ジオメトリ (計算幾何学：アルゴリズムと応用) 第3版』，2010年，近代科学社．
杉原厚吉，『計算幾何学』，朝倉書店，2013年．
福田公明，森山園子，『凸多面体と計算』，共立出版，2025年．
J. マトウシェク，『離散幾何学講義』，丸善出版，2012年．