離散数理工学

岡本 吉央

ショートカット： 講義資料 | コメント | 試験・成績評価 | 公式シラバス | スケジュール | 参考書 | 過去の講義 | 過去の試験・レポート問題

実施形態

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

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

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

講義資料

• 演習シート (全回共通)
• 用語集 (全回共通)
• 11/18 第5回　低次元 (5)：多角形内の距離
  • スライド
  • 演習問題
  • 講義動画
• 11/11 第4回　低次元 (4)：距離とボロノイ図
  • スライド
  • 演習問題 (11/11更新)
  • 講義動画
• 11/4 第3回　低次元 (3)：近接グラフと交差グラフ
  • スライド (11/3更新)
  • 演習問題
  • 講義動画
• 10/28 第2回　低次元 (2)：点配置と直線配置
  • スライド
  • 演習問題 (10/28更新)
  • 講義動画
• 10/21 第1回　低次元 (1)：多角形と三角形分割
  • スライド (10/20更新)
  • 演習問題
  • 講義動画
• 10/7 第0回　ガイダンス
  • スライド
  • 演習問題
  • 講義動画

• 11/11 第4回　低次元 (4)：距離とボロノイ図
  • 勝手にお悩み相談させてもらいます。
    3年生に入ってからコンピュータサイエンス実験が始まり、プログラムを書く機会が増えました。その中で、アルゴリズムを実装することが当然あるのですが、どうもAIにばかり頼ることが多くなったなと感じました。もちろん、このご時世ですからAIに頼るというのが決して悪ということではないとは思います。ですが、このまま基本的なアルゴリズムの実装すらAIに頼ってしまうというのは果たして良いことなのかという疑問が湧いてきました。
    先生はAIとの向き合い方についてどう考えていますか？また、いわゆるプログラミング力といいますか、アルゴリズムを実装する力を鍛えるおすすめの方法などがあればぜひおしえてほしいです。
    --質問は2つあるので分けて答えます．まず，1つめの方ですが，私は回答を3つ持っています．
    (1-1) 使える道具を上手に使うことは重要だと思っています．ポイントは「上手に」という部分です．「上手に」のここでの意味は私にとって「目的に合うように」ということです．そのためには目的をしっかりと理解することが重要です．
    この時点で「授業や課題でAIを使う」という文脈において2つの問題がでています．1つ目は教えている方が目的を分かっていないことがあることです．そんな状況では，教わっている方が目的を理解できるわけありません．2つ目は，教えている方の目的と教わっている方の目的が異なっていることがあることです．そのため，教えている方の目的に合うようにAIが使われるとは限らないことになります．
    授業や課題でAIを上手に使うためには，まず教えている方の目的を理解しようとしてください．つまり，何のためにそれを学ばなければならないことになっているのか理解するということです．そして，教わる方の目的を教える方の目的と同じにするようにしてください．
    (1-2) 電通大では「学修におけるAI利用に関する注意事項」をお知らせしています．そちらをしっかりと読んで理解して，AIを使うようにしてください．
    (1-3) 新しい技術が現れたときに，社会が混乱するのはよくあることです．よくあることですから，あまり気にしないほうがよいように思います．
    2つ目の質問に答えます．私の回答は2つあります．
    (2-1) プログラミングやアルゴリズムを学ぶことで，何をしたいのか，という目的をはっきりとさせられるとよいと思います．例えば，ソフトウェアやアプリを1つ作るという目的をもって，そのために必要な技術を学んで実装していくとよいと思います．
    (2-2) 何かを作るという目的が思い浮かばないときは，プログラミングやアルゴリズムを学ぶこと，そして，実装すること自体を目的とするとよいと思います．そのためのよい手段のひとつは競技プログラミングに取り組むことです．たとえば，AtCoderとかProject EulerとかCodinGameに入会して取り組んでみてください．どれも無料です．AtCoderの場合は，コンテストに出なくても，過去問を解くだけでよいと思います．
  • 逐次添加法が，どのような順番で点集合から点を選んでも正しく動くのは分かるのですが，点を選ぶ順番について，何らかの意味で良い順番が存在するって話が研究されていたりしますか（計算機上で逐次添加法を実行する際に，入出力の形式と1ステップで行える操作を定めれば，平均時間計算量や最悪時間計算量が小さくなるような選び方が議論できる気はなんとなーくしますが，設定の固め方，議論の方向や使う道具，結論の形まで全然想像ができないです）．
    --回答は2つあります．なお，どちらの回答でも点を付け加えたときに描く辺の数の総和が小さいほど，その順番はよいものであるとして，n は母点の数を表すものとします．
    (1) 最適な順序を求めるという問題は研究されていないような気がします．ただ，ある順序で，それに沿って逐次添加法を実行すると付け加える辺の総数がO(n)になるものが存在することが知られています (Snoeyink, van Kreveld '97)．
    (2) 実際にボロノイ図を逐次添加法で作るために，「一様ランダムに選んだ順序を使う」という手法が提案されています．これは乱択逐次添加法 (randomized incremental construction) と呼ばれていて，計算幾何における他の問題のも適用できます．逐次添加法では，変な順序を使うと，最悪の場合，辺の追加をn² に比例する回数だけ行うことになってしまうことがあるのですが，乱択逐次添加法を使うと，追加する辺の総数が期待値で O(n log n) になることが証明できます．乱択逐次添加法は1980年代に提案され (Clarkson, Shor '89)，1990年代には多くの研究者がこれを理解しようとして，いまでは一般的な手法になっています．
  • 動画で「コンパスと定規で作図」というワードを聴いて，Euclideaってゲームを思い出しました．120個の問題が，アルファからオミクロンまで15個のレベルに分けられていて，単に指定の作図をするだけでなく，少ない手数で作図する方法を見つけないと先に進めないのですが，序盤からこれがめちゃくちゃ難しくて，未だにアルファレベルすら突破できてないです．
    --はい，私もEuclideaはインストールしています．私はβで止まっています．(βまですべてクリアしてるのですが，点数が足りなくて次に進めません．)
  • 動画でちょくちょく $q$ って言いながら $g$ って書いてません…？
    --$q$ を書いているつもりなのですが，下のセリフ (横棒) の書き方がよくなくて$g$ に見えるのかもしれません．下のセリフを書こうとするのではなく，右にはねるように矯正していきます．
• 11/4 第3回　低次元 (3)：近接グラフと交差グラフ
  • 11/3に好きなゲームの音楽のコンサートに行くのですが、先生は好きなゲーム音楽はありますか？
    --ゲーム音楽には詳しくないですが，東京オリンピックの開会式でドラゴンクエストの序曲が流れたときにはなんか心を動かされました．
  • スライド33/36 (4枚目) を見ると，同じ点集合 $P$ に対して，ガブリエル・グラフの辺ではないが，デローネ・グラフの辺であるものが見て確認できます．そのようなもののうち，$P$ の凸包の境界に含まれないものがあると，本当にデローネ・グラフの辺として適当であるのか（定義に書かれた円盤が存在するのか）気になりますね．いくつかの辺（特に，スライド33/36 (3枚目) の赤点線の右端点とその右下の頂点を結んだ辺）はとてもそのような円板があるように思えないのですが，スライド18/36 (3枚目)のようにギリギリで円板が存在するケースなんだと思います．
    --どの3点も1直線上にないとき，凸包の辺は必ずデローネ・グラフの辺になります．円板の中心を限りなく遠くにもっていければ，うまく円板をつくることが必ずできます．
  • スライド21/36で紹介されている性質は，「デローネ・グラフは非交差であること」ではなく，「デローネ・グラフの全ての有界面が三角形である条件」を言っていると思うので，ブロックのタイトルもそのような意味を表す文言に変えた方が良いと思います（あるいはスライド見出しの「デローネ・グラフの面」にそろえるとか）．
    --ご指摘のとおりだと思います．修正しました．
  • 「定義 (非形式) : 近接グラフ」とあったのですが，形式的な近接グラフのよく知られた定義があったりするのでしょうか．数学で近さというと，位相や距離関数を考えたくなりますが，デローネ・グラフ，ガブリエル・グラフ，最近点グラフの3つから，位相や距離関数に関する言葉を使って，簡潔に表現できる共通の特徴を見出すことが，自分にはできませんでした．
    --形式的な定義は私の知る限りないと思います．デローネ・グラフ，ガブリエル・グラフ，最近点グラフが持つ共通の特徴は「ある種の図形で，辺となるべき2点のみを含むものが存在する」ということです．ただ，近さ (proximity) としてその特徴に従わないものもあるので，形式的に定義するのは難しいように思います．
• 10/28 第2回　低次元 (2)：点配置と直線配置
  • コメントが長くなって，段落を変えて表示させたい場合，どう書いたらコメントに反映されますか．
    --長文回答ができるように設定を変えました．設定を変えたので，回答の中でEnterを入力すれば改行ができると思います．試してみてください．
  • 授業時間は授業内問題を解いて、時間が余ったら復習問題なども解いて、紙で提出しなかったその他の問題はClassroomで別に提出すれば別々に採点していただけるということでよろしいでしょうか。それと、補足問題と追加問題という名称の違いに何か意図はあるのでしょうか。
    --採点はしません (点はつきません) が，別に提出すれば別々に拝見します．補足問題は「問題自体が授業内で『これは演習問題』と述べられているもの」で，追加問題はそうではないものです．
  • 授業内問題1.1の3について、「内部に点を打ち続ける」という自分とは異なる解き方をしている方がいて、「なるほどそっちの方が簡単そうだな」と思いました。でも、考えてみたら内部ならどこでもいいという訳ではどうやら無さそうで、内部のどこにある点を追加すればいいのか定義するのは意外と大変なような気もしました。
    --1つの問題の解答は複数ありえます．どのような解答であっても，自分の考えをわかりやすく伝えようとすることが重要です．
  • 第一回レポートの補足問題1.4で、座標系に図形を落とし込んで証明をしたのですが、その際に計算をする必要がありました。この時、どこまで計算過程を書いた方がいいのか分からないのですが、どこまで書くかの考え方はありますか。
    --主観的で申し訳ないですが，私が導出を追えるように書いてください．
  • 先生が口癖だと自認している「でー」が該当するかは判断しかねますが，「あー」とか「えー」のような音を発さずに話をするのは，私にとって非常に難しいです（最近知りましたが，こういう，話し終えていなかったり，考え中であることを示すために発する音をフィラーワード (filler word) って言うらしいですね）．
    --難しいですね．こういうものは癖なので，やめようとするならば，意識をしてやめようとしないといけないと思います．
  • $L$ を$\mathbb{R}^2$ 上の直線全体からなる集合，$V$ を $\mathbb{R}^2$ 上の直線で $y$ 軸と平行なもの全体からなる集合とすると，今回の講義で紹介された双対変換は $\mathbb{R}^2$ と $L \setminus V$ の間に存在する全単射であると理解しました．そこで気になったのですが，$\mathbb{R}^2$ と $L$ の間には全単射は存在しないのでしょうか．全単射が存在してかつ，構成や使い方もよくわかっているのあれば，直線の傾きを気にしないで良い分，今回の講義で紹介された双対変換より便利かもしれないと思いました． …と，思っていたのですが，有限個（本）の点（直線）を考える場合は，座標を回転させればどの直線も $y$ 軸と平行にならないようにできるから，有限の範囲で事が済むのであれば，今回の双対変換でも困ることはなさそうです．非可算無限個（本）本の点（直線）を扱うときに，初めて困りそうな気がします．
    --$\mathbb{R}^2$ と $L$ の間の全単射は存在します．(次の段落で示します．) ただ，それが有用であるかどうかは全単射の性質に依存します．例えば，授業で扱った双対変換は接続関係を保存したり，上下関係を保存します．これは重要な性質です．一方で，次の段落で示す全単射はそのような性質を持ちません．
    では，全単射の存在を示します．授業で扱った双対変換によって，単射 $\mathbb{R}^2 \to L$ の存在が分かります．一方で，単射 $f\colon L \to \mathbb{R}^3$ を次のようにつくります．直線 $y = ax + b$ を $f$ は点 $(a,b,0)$ にうつします．また，直線 $x=c$ を $f$ は点 $(c,0,1)$ にうつします．また，$\mathbb{R}^3$ から $\mathbb{R}^2$ への全単射の存在はよく知られています．この全単射を $g$ とすると，$g \circ f \colon L \to \mathbb{R}^2$ は単射となります．これで，$L$ から $\mathbb{R}^2$ への単射と $\mathbb{R}^2$ から $L$ への単射が存在することが分かったので，カントール・シュレーダー・ベルンシュタインの定理から，$L$ と $\mathbb{R}^2$ の間に全単射が存在することが分かります．
  • $\mathbb{R}^2$ の点からなる（有限）集合 $S$ と，$\mathbb{R}^2$ の点 $p$ が与えられたときに，$p$ を $S$ に属するいくつかの点の凸結合として表せる場合が何通りあるか（ただし，足し算の順番を入れ替えたら等しくなる場合は同じものとして数え上げる）という問題を思いつきました．「点 $p$ は，$S$ の点をいくつか使った凸多角形上に属する点である」を満たす凸多角形がいくつあるかを（おおよそ）数え上げる（正確には，今回の講義では凸多角形として扱っていない頂点や辺，対角線も考えている）という意味で，図と結び付けた解釈はできていると思いますが，何の役に立つのかはよく分からないです．$p$ が $S$ の凸包に属さないことが分かれば $0$と，$p$ が $S$ の凸包の境界点であることが分かれば $1$ と答えられると思います（冗長な点があってもこの辺りは大丈夫な気がします）．ただ，$p$ が $S$ の凸包の内点であることが分かったときに，$S$ に属するいくつかの点の凸包をしらみつぶしに試して数え上げる以外に方法が思いつかなくて，面白そうだと思いました．
    --よい発想ですね．「$S$の点をいくつか使った凸多角形」ではなく「$S$の点をいくつか使った三角形」とする場合はよく調べられていて，simplicial depthという名前がついています．
  • シャンパングラスで乾杯する時に何人と同時に乾杯できるかという問題があるのですが、最近同時に乾杯できる人数の上限を更新した日本人の方がyoutubeで動画を出していて驚きました。証明には幾何的なベクトルやグラフの定理などを使っていて面白かったです。
    --こちらの論文ですね．この手の問題は離散幾何において典型的なものです．多くの問題が未解決です．この授業では扱いませんが，例えば参考書に挙げている『離散幾何学講義』ではこれに似た問題をいくつか議論しています．
• 10/21 第1回　低次元 (1)：多角形と三角形分割
  • うどんを食べに行っていたのでコメントの締め切りが過ぎてしまいました。演習中に流す曲にこだわりはありますか？
    --コメントの締切を過ぎた場合は次の回のところに掲載されることになります．ご了承ください．
    演習中に流す曲にこだわりはありませんが，演習がはかどりそうなものを考えています．
  • (TAより) 実は，TAは今期の講義でどのような内容を扱うのか詳細まで知らないです．前回，この離散数理工学の講義で計算幾何を軸に講義を構成するのは(2014年以来)初めてであると先生は仰ってましたが，TAも「計算幾何を軸に講義する」と宣言された形で先生から教わるのは初めてです．そもそも，先生は計算幾何の専門家であると自他共に認められているので，演習問題について的を得たヒントが欲しい場合は，TAより先生に質問をした方が，良いアドバイスが得られるかもしれません．一方で，TA自身も一緒に考えるのは好きですし，演習問題に対しても考えを用意したうえで教室には居るので，是非TAにも声を掛けてくれると嬉しいです．よろしくお願いします．
    --ということですので，皆さんもよろしくお願いします．
  • (TAより) 別のコメントでも類することを書きましたが，今期の内容はTAも初めて学ぶことが多くあります．そのため，TAも遠慮なくコメントを出すつもりです (今後は，TAのものであると明示したほうがよさそうなものだけ「TAより」と書くつもりです)．TAは数学的な側面には割と興味がある一方で，面白い人間ではないので，このコメント欄も講義内容の数学的側面に関するものが多くなるかもしれません．ただ，初回で先生が説明されたように，コメントの内容は本当に自由なので (前回のコメントで，某アニメのエンディングテーマをおすすめしている方がいましたが，数学的内容と同じくらい (あるいはそれ以上に) 求められている気がします)，返信をするのはTAじゃないですが，どんどんコメントしてください．先生の返信を含めてTAも楽しみにしていますので．
    --ということですので，皆さんよろしくお願いします．
  • 　動画の15分くらいのところで，円周や円板の定義で用いる$r$について，$r \geq 0$を$r > 0$に訂正していたところを見て「半径$0$の円周 (円板) ってどう思うのが自然か，意識して考えた記憶がないな」と思いました． 　試しに考えてみると，「半径$0$の円周 (円板) 」という言葉からはそのような対象は空集合であってほしいように私は思いましたが，動画の定義に$r=0$を代入すると，点$c$が入ってしまいます．確かに，点の「大きさ」を$0$とするならば (物理学でしばしば扱う「質点」はそのように考えるので，設定の一つとして悪くはなさそう)，半径$0$の円周 (円板) は円周 (円板) の中心$1$点からなる図形であるとしても良いような気もしてきました．一方で，このように半径$0$の円周 (円板) を定義することが，数学的な議論の上で都合が良いかということも考える必要があります．この講義では，$r>0$として考えることにしたので，$r=0$だと都合が悪いことが起こるのかなと思いました．今後の講義でどのように話が進むのか，詳細は知らないのですが，半径$0$の円周 (円板) は集合として非空なのに，それ以外の円周や円板と違って「長さ」や「広がり」を持たないのは，議論を一般化する上で色々と不都合がありそうに思えます． 　と，動画の15分くらいまでを見てこれを書いていたわけですが，28分くらいで開集合の定義が出てきて，早速$r=0$だと困ったことが発生しました．上で述べたような$r=0$の円板を考えると，どんな集合も開集合かつ閉集合になってしまうし，集合に属する全ての点は内点になってしまい，色々な議論がおかしくなります．だから，円周 (円板) において半径が$0$より大きいことは重要なんですね．
    --はい，スライドを作ったときに，開集合の定義のところでよくないことが起きることに気づいておらず，動画ではr>0であることを補足することになりました．ただ，場合によっては，半径が0の閉円板を考えることもあります．その場合，それは中心だけからなる1点の集合になります．
  • 平面上の集合で，開集合でも閉集合でもないものは，定義を見ずに開集合と閉集合 (あるいは境界) のイメージを基に考えても作れそうに思えますが，開集合かつ閉集合であるものは，定義をよく理解しないとなかなか作れないように思えます．
    --はい，演習問題になっているので，ぜひ取り組んでください．
  • 開集合の定義について質問です。ある集合Xが開集合であるとは、「任意の点についてその点を中心とした開円板で、Xの部分集合であるものが存在する」だと思います。この定義だと開集合の定義に開集合である開円板を用いてしまっているように思います。定義の中で定義されていない用語を用いていると感じたのですが、その認識で間違いないでしょうか？また、問題は無いのでしょうか？
    --「開円板の定義」には開集合を使っていないので，問題はないことになります．
  • スライド21/41の多角形領域の頂点 (辺) は$46$個だと思います…
    --ありがとうございます，確かに46個でした．訂正します．
  • スライド29/41で，回転を許せば，単純多角形$P$の左端の頂点が一意になることを仮定すると説明されていました( し，動画内の説明でも十分理解はできたつもりです )が，きちんと証明しようとすると「$P$に凸頂点が少なくとも$1$つ存在すること (演習問題が解ければそれどころか少なくとも$3$つ存在することまで言えますが)」「任意の正実数$\varepsilon$に対して，$\varepsilon$より真に小さい正実数として$\varepsilon/2$が存在すること」辺りが鍵になっている気がします．
    --詳しく証明しようとすると，ご指摘のとおりです．(ただ，ε/2である必要性はあまりありません．) 凸頂点が少なくとも1つ存在することは，x座標がもっとも小さい頂点はどれも凸頂点であることからわかります．εについては，あまり使わないように議論をしようと思って授業を進めています．いわゆる解析学では「任意のεに対して，あるδが存在して…」という言い回しがよく登場して，それは重要なのですが，この授業ではその言い回しをあまり使わないようにして，それに代わる部分は直感的な理解に留めるようにしています．
  • スライド29の三角形分割:証明(2)の、「複数ある場合は、少し回転させて左端を頂点を一意にする」っていうのは、実際証明をする際はどのような書きますか。このままの表記でいいのですか。
    --1つ前のコメントにも関係しますが，この授業ではこの書き方で十分ですし，論文などでもこのような書き方はよくします．
  • スライド32/41で，単純多角形$P$を線分$ps$で分けて，一方を頂点数$m$の単純多角形$P_1$としたときに，$m \leq n-1$が成り立つのは，$p$か$s$を一方の端点とし，他方の端点$w$は$p$でも$s$でもないような辺で，$w$が$P_2$の頂点でもあるものが$P$に存在するからですか．
    --正しいです．ただ，動画内での口頭説明では違う方法で示しています．それを繰り返すと，下の方の単純多角形の頂点数がn-m+2で，単純多角形の頂点数は3以上なので，n-m+2≧3となり，ここから，m≦n-1が導かれます．
  • 極大な線分ということがよくわからなかったのでもう少しこれについて聞きたい
    --一応，ここでも説明しますが，分からない場合は教室で直接聞いてください．
    辺は「境界上にある線分」ですが，「境界上にある線分」を不注意に持ってくると，それが辺であるとは限りません．辺であるためには，「『境界上にある』という性質を保ったまま，伸ばせるだけ伸ばした線分」である必要があります．この「『○○』という性質を保ったまま，伸ばせるだけ伸ばす」というのが「極大」の意味だと思って下さい．
    以下，もう少し詳しく説明しますが，この説明は理解できなくてもよいですし，理解できたからといって，この授業の理解が深まるわけでもありません．
    一般的に，半順序集合(X,≦)があって，その各要素が性質Qを持つか持たないか決められるとします．このとき，Xの中で性質Qを持つもの全体 (つまり {x∈X | Q(x)} という集合) の≦に関する極大元を「Qに関して極大な元」と呼びます．この場合は，Xが平面上の線分全体の集合，≦が集合の包含関係 (つまり，線分I, J に対して，I⊆JであることをI≦Jと定義するもの)，Qが「多角形Pの境界上にある」という性質だとすると，Pの辺は，Xにおいて性質Qに関して極大な元となります．
  • 三角形の内角が\piであることを許さなければならない理由を理解することができませんでした。
    --これはスライド33ページの例のとおりですが，いまいちど説明します．
    三角形分割は単に三角形に分ければよいということではなく，2つの三角形の共通部分が空集合か共通の頂点か共通の辺でなくてはなりません．33ページの例では，三角形に分かれていますが，その2つの三角形の共通部分が左の三角形の辺ではありますが，右の三角形の辺ではないので，「共通の辺である」という性質が満たされないのです．そのため，共通部分になる部分に頂点を挿入して，うまく共通部分が共通の辺になるようにする必要があるのです．
• 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 期末試験

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

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