離散数理工学

実施形態

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

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

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

• 演習シート (全回共通)
• 11/10 第4回　低次元 (4)：距離とボロノイ図
  • スライド
  • 演習問題
  • 講義動画
• 10/27 第3回　低次元 (3)：近接グラフと交差グラフ
  • スライド
  • 演習問題
  • 講義動画
• 10/20 第2回　低次元 (2)：点配置と直線配置
  • スライド
  (10/19修正)
  • 演習問題
  • 講義動画
• 10/13 第1回　低次元 (1)：多角形と三角形分割
  • スライド
  • 演習問題
  • 講義動画
  • デモ：シェーンハルト多面体
• 10/6 第0回　ガイダンス
  • スライド
  • 演習問題
  • 講義動画

• 10/27 第3回　低次元 (3)：近接グラフと交差グラフ
• 掲載が遅くなり，すみません．
• BGMをリクエストしたいです。
  --ぜひどうぞ．ただ，お応えできるかどうかは不明ですので，その点はご了承ください．
• デローネグラフの英語名のくだりが面白かった。
  最近はDelaunay graph
  --人名というのはなかなか難しいもので，いろいろな都合により，本人でさえも，自分の名前を変えて呼ぶことがあります．例えば，(私の理解では) 香港の若い人は英語的なニックネームを持っていて，普段の会話ではそのニックネームで呼んだりします．
• 研究室配属が近いです。とにかく情報を集めていますが、そもそもどう優先順位をつけるのか、どのような基準を用いるのかで困ってしまいます。先生は研究室など何か将来を影響しうる選択をするとき、どう基準を決めていましたか。
  --基準の決め方はあまり定まっていないですが，あとで悔やまないことを自分に課している気がします．うまくいかないことはよくあるわけですが，そのときに後悔しないということだけは決めています．
• 講義を受け問題に挑む度、定義の大切さを痛感します。定義を過不足なく頭に入れなければ。
  --まず，何事も覚える必要はないと思ってください．これは重要です．忘れたら調べて思い出せればよいのです．ただ，それと理解していることは異なることだと認識することも重要です．文章というのは読めば理解できるというものではない気がします．それを理解するために考えることが重要で，いったん理解すれば，思い出すときにもその経験が活きると思います．それを踏まえて，とくに，用語や概念の定義を理解すること自体はとても重要です．それが理解できないと，その用語や概念を使っている文章はどれも理解できないことになります．すべての理解の出発点になるのが，定義の理解だと思っています．
• 個別の内容は特段難しいわけではないものの、内容が多めでまだ上手く頭の中で整理できていないので、自分なりに整理しておきたい。
  --自分なりの整理ができれば，理解ができていることになると思います．理解の仕方は人それぞれで異なりますから，自分なりの視点と方法を編み出すことが今後も活きると思います．
• 10/20 第2回　低次元 (2)：点配置と直線配置
• 授業内演習が終わった後は、演習問題のどの問題を優先的に解くべきですか。
  --私から何かを優先してほしいというものはありません．好きな問題に取り組んでください．教室では，他の学生と相談することになっているので，相談する甲斐のありそうな問題を選んでください．
• 写像などの問題が苦手なので、具体的な理解はできたが、抽象的に考えるのが難しかった。
  --抽象的な考え方に慣れる必要はあると思います．そのための具体例なので，授業で与えられている具体例で足りない場合は，自分でも具体例を作ってみるということをお薦めします．具体例をいくつか考えることで，抽象的な概念も理解しやすくなると思います．
• 今回の教訓の「ひとつの対象を様々な視点から眺める」は前期に学んだプログラム言語論(佐藤重幸先生)、言語処理系論(佐藤重幸先生)でも重要な考え方だった。色んな分野において多角的な視野は重要視されていると感じた。
  スライド24において、頂点は7個だと思う。最も小さい三角形を形成できる3点の内、右下の点が数えられてない。傾きが負の直線は他の4つの直線全てと交わっているので交点は4つできるはず
  --はい，頂点数は7です．失礼しました．スライドを修正しました．
  教訓として述べているものは，この授業の内容だけに関わるものではなくて，もっと一般的なことを述べているつもりです．そのため，他の授業や生活の中で現れるものにも適用できることを想定しています．
• 全然話は変わるんですが、教育実習(高校,数1)で、最短経路の総数の自作問題(往復の最短経路であって、かつ行きと帰りが非交差な経路の総数)を扱いました。だいぶ時間をかけて準備したはずなのですが、教員からは難しすぎると酷評を受け、なんだかやるせない気持ちになりました。生徒への申し訳ない気持ちと、高校での授業はゼミの発表とは違う(自明)ということを知りました。
  --こういうものは力を入れすぎると空回りしてしまう可能性があります．よい経験だったと思って，今後に活かしていってください．
• 会話の空気を読むのは得意な方ですが、問題の誘導に乗るのは苦手です。
  --問題の誘導に乗る必要はないので，あまり気にしないでください．;-)
• シンプルな変換なのに都合が良い性質が色々あって面白かった。
  --そうですね．こういうものは自分で思いつこうとしても，なかなか思いつかないと思います．そういうものは勉強する価値があると思います．
• 講義内容は理解できたと思うんですが、いざ問題を解くってなると頭がこんがらがりそうな気がした。演習をいくつかやって慣れたい。
  --はい，演習は慣れるためにあるものなので，ぜひ積極的に取り組んでください．
• 双対変換の特徴は理解できましたが実際に証明するとなるとスライドを見ないと出来なかったので復習をちゃんとしようと思いました。
  --覚える必要はないので，使えるようになってください．(試験でもA4用紙両面に自筆で書いたものは持ち込めます．第0回で説明したとおりです．)
• 上側半平面はy軸正の側、上側凸包は負の側と定義されており、直感的でないように思います。直線を無限個の点の集合と見た場合、その集合の上側半平面と下側凸包が等しいということになりますか。
  --「直線を無限個の点の集合と見た場合…」の部分は，そのとおりで正しいです．用語が直感的でないことは確かだと思いますが，伝統的に用いられているものに従うべきですので，授業でもそうしています．ご了承ください．
• 10/13 第1回　低次元 (1)：多角形と三角形分割
• 前期で単位３つ落としました。お手柔らかにお願いします。
  --はい，しっかりと勉強してください．
• BGMの程よい音量がグループ内の会話を活性化しているように感じて良かった。
  --音量は調整できますので，言ってください．
• 第2回からは出席してグループ課題を解いていきたいと思います。
  --演習問題はぜひグループで相談しながら取り組んでください．
• 講義動画が分かりやすかった。前期の実験で三角形分割をやったせいもあると思うが、個人的には特に理解に困らなかった。
  --ありがとうございます．分からないところがでてきたら，ぜひ質問をしてください．
• 多角形の頂点としてπを考える理由が最初はなぜ？となっていたけど、説明を聞いてとても納得できた。
  --内角がπである頂点を考えるのは多くの教科書で行われておらず，むしろ，そのような教科書に書いてある証明は正しくないと思っています．注意深さが必要だと思います．
• 開集合と閉集合について定義になぜ開円板をもちいて定義するのが適切なのかわからなかった。円形である必要が分からなかった。
  --円である必要があるかといわれると，そうである必要はありません．例えば，正方形でもよいです．重要なのは，xに十分近い部分をすべて含むような集合をとることです．そのためにここでは「ユークリッド距離が近い」という考えを使ったため，円になっています．また，開円板でなくて閉円板を使っても同じように定義できます．一方で，開円板を使って定義することは標準的なので，授業でもそうしています．
• 10/6 第0回　ガイダンス
  • コメントをありがとうございます．皆さんのコメントとそれに対する返答は次のように掲載されます．次回 (第1回) からは，毎回授業前日の18:00頃までに投稿されたコメントが，授業日の回のコメントとしてここに掲載されます．
  • 本日は中間発表の練習で都合がつきませんでしたが次回からぜひ対面で参加したいと思います。
    --はい，よろしくお願いします．
  • mod9に着目して考えた。
    --考え方はよいと思います．その考え方に沿って，解答を文章として書けるようにしてみてください．
  • 導入の内容が非常に面白かったのですが、そのアルゴリズムが気になりました。先生の研究室ではその研究をしているのですか？
    --私はアルゴリズムの研究をしていますが，「そのアルゴリズム」の研究はしていません．知られているアルゴリズムの研究をするということはほぼありません．解かなくてはいけない問題は世の中に山ほどあるのですが，それらに対して新しいアルゴリズムを考えることをしています．
  • 演習問題は自分では全く分からなかった解法をグループメンバーが提案してくれてとても参考になった。
    今年で学部を卒業する必要があるのでなんとしても単位を取る。
    --はい，積極的に勉強をしていってください．
  • 授業内演習01が一見簡単そうに見えたけど、実際解いてみたら難しかった
    --「一見簡単そうに見えたけど，実際は難しい」ということはよくあると思います．見た目だけで判断するのではなくて，実際に取り組むということが重要だと思います．これからも演習問題は出てきますので，しっかりと取り組んでいってください．
  • 頭の体操になりました
    --そうですね．考えることが重要だと私は思っていますので，演習問題を通して考える訓練をしていってください．
  • 0.1はただプログラミングで2^10通りを全て調べることが可能ですが、それだと0.2のような問題には歯が立ちません。また、全てを文字で置くようなやり方で示すことができそうな気がしますが、簡潔な解法を探したくなってしまいます。
    --いろいろな考え方はあると思います．「プログラムを使ってすべて調べる」というのは問題解決の方法として汎用的であり，そういう考えができることはとても重要です．
  • ちょい早口でした。事前に予習？授業受けて行くという今まであまり経験したことないタイプでちょっとびっくりしてます。
    このコメントは個人個人に返信する形なんでしょうか。それともクラスルームに匿名でコメントフィードバックみたいな形になるのでしょうか
    先生の研究室が第一志望です！木村先輩に色々聞いててとても興味があります！後日面談のメールを送ります｡
    --フィードバックはこのような形でひとつひとつのコメントに対してこのページでお伝えします．実は，このコメント返答は業界視聴率が割とあり，Classroomに閉じ込めておきたくないのです．;-)
    面談等に関する情報は後日卒研配属のページからたどれるようになると思いますので，そちらを参照してください．
  • 講義への取り組み方や雰囲気が分かった。過去の講義のページを見た感じでは質問対応が丁寧そうだったので安心した。自分も質問があれば積極的に聞きたい。
    --はい，質問は大歓迎していますので，どしどしお寄せください．
  • サイコロの問題について、解法自体は習っているはずでもどれを使うべきかが考えさせられた
    --いろいろな考え方があると思います．ひとつの考え方にとらわれる必要はないので，自由に考えてください．授業の中でも言いましたが，私には「模範解答」や「想定解答」というものはありません．皆さんが自由に考えて，自由に結論にたどり着くことだけを想定しています．

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

• こちらをご覧ください

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

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

• 離散数理工学 (2025年度後学期，I類 (情報系))
• 離散数理工学 (2024年度後学期，I類 (情報系))
• 離散数理工学 (2023年度後学期，I類 (情報系))
• 離散数理工学 (2022年度後学期，I類 (情報系))
• 離散数理工学 (2021年度後学期，I類 (情報系))
• 離散数理工学 (2020年度後学期，I類 (情報系))
• 離散数理工学 (2019年度後学期，I類 (情報系))
• 離散数理工学 (2018年度後学期，I類 (情報系))
• 離散数理工学 (2017年度後学期，情報・通信工学科)
• 離散数理工学 (2016年度後学期，情報・通信工学科)
• 離散数理工学 (2015年度後学期，情報・通信工学科)
• 離散数理工学 (2014年度後学期，情報・通信工学科)

• 2025年度： 中間試験 | 期末試験
• 2024年度： 中間試験 | 期末試験
• 2023年度： 中間試験 | 期末試験
• 2022年度： 中間試験 | 期末試験
• 2021年度： レポート1 | レポート2
• 2020年度： レポート1 | レポート2
• 2019年度： 中間試験 | 期末試験
• 2018年度： 中間試験 | 期末試験
• 2017年度： 中間試験 | 期末試験
• 2016年度： 中間試験 | 期末試験
• 2015年度： 中間試験 | 期末試験
• 2014年度： 中間試験 | 期末試験