離散数理工学

岡本 吉央

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

実施形態

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

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

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

講義資料

• 1/31 (14) 離散確率論：マルコフ連鎖 (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 1/24 (13) 離散確率論：マルコフ連鎖 (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 1/17 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 1/10 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • スライド (1/10修正) | 印刷用スライド (1/10修正) | 演習問題 (1/10修正) | 用語集
  • オンデマンド講義動画
• 12/27 (10) 離散確率論：確率的離散システムの解析 (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 12/13 (9) 離散確率論：確率的離散システムの解析 (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 12/6 (8) 離散代数 (4)：対称性を考慮した数え上げ (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 11/29 (7) 離散代数 (3)：対称性を考慮した数え上げ (基礎)
  • スライド | 印刷用スライド | 演習問題 (11/29修正) | 用語集
  • オンデマンド講義動画
• 11/22 (6) 離散代数 (2)：部分群と軌道
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 11/15 (5) 離散代数 (1)：置換と置換群
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 11/8 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
  • スライド (11/13修正) | 印刷用スライド (11/13修正) | 演習問題 | 用語集
  • オンデマンド講義動画
• 11/1 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 10/25 (2) 数え上げの基礎 (2)：漸化式の立て方
  • スライド | 印刷用スライド | 演習問題 (10/25修正) | 用語集
  • オンデマンド講義動画
  • 演習問題を修正するなかで，2.2も変更となっています．現在のバージョンの演習問題が「正しい」2.2です．よろしくお願いします．
• 10/11 (1) 数え上げの基礎 (1)：二項係数と二項定理
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • オンデマンド講義動画
• 10/4 (0) ガイダンス
  • スライド | 印刷用スライド | 演習問題 | 用語集

• 1/31 (14) 離散確率論：マルコフ連鎖 (発展)
  • 離散確率論で、解析をすると直感とは違う結果になることが多かった。(今回のランダムウォークなど)　　離散数理工学の講義ありがとうございました。
    -- 確率に関する議論は直感に従うと間違えてしまうことがあるので，しっかりと計算をすることが重要だと思っています．この授業では，いろいろな計算を実際に行うことで正しい直感を養えるようにしてみたつもりでいます．今後の生活でぜひ活かしてください．
• 1/24 (13) 離散確率論：マルコフ連鎖 (基礎)
  • 今回はコメントが1つもありませんでした．次回はぜひコメントをお願いします．
• 1/17 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • コメントをありがとうございます．
  • 中央値トリックの出力が資料のように2値だけになることは、計算で求められるものですか？
    -- 2値になるとは限りません．資料 (スライド) で行った実験では2値になっていますが，他のパラメータで実験を行うと，2値にならない場合があります．
  • シミュレーションのお陰で、統計の授業で習った不偏推定量が望ましいという話が直感的に理解できたような気がします。不偏推定量でないと推定したい値を取らないような推定量を作ることもできるんですね…
    -- まさのそのとおりですね．もう一点重要な点としては，いろいろな目的でアルゴリズムやプログラムをつくるわけですが，その目的をはっきりさせないといけないということです．「誤差がεを超える確率をδ以下にする」という制約のもとで標本の数を少なくすることを目的としたのですが，「不偏推定量でなくてはならない」という暗に持っていた仮定をなくすことで，実際に標本の数を少なくできたのです．
  • log(1/δ)を作るために、底を逆数に変換して作る変形が一回でわからなかった。対数関数の性質をうまく使ってるなと感じた。
    -- 底が1未満である対数には注意してください．
• 1/10 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • コメントをありがとうございます．12月20日に行った中間試験の採点は終わっていますが，当日事情により試験を受けられなかった方の代替試験をまだ行えていませんので，結果などはそれが終わってからお知らせします．
  • 他の授業で差集合はA-BではなくA\B(\setminus)と書くようにと教わりました。先生は記号を正しく使うと言う意味で、この2つに違いがあると感じますか？
    -- 違いはないと思っています．ISOによると $A \setminus B$ を使う方がよいようにも見えますが，実際には $A-B$ を使うこともよくあります．
    ただ，「差集合」という用語はよくないと思っています．よくないというよりも，差集合と呼ばれるものは違うものを指します．$A \setminus B$ は $A$ と $B$ の差と呼ばれるべきもので，それを差集合と呼ぶべきではないと思っています．私たちは，実数 $a$ と $b$ に対して，$a-b$ を「差数」や「差実数」と呼ぶことはありません．なぜ，集合になった途端に「差集合」と呼びたくなってしまうのでしょうか．それが私には分かりませんし，実際，差集合というものは集合の差と違うものなので，そこは気を付けないといけないと思っています．
  • 乱数を使うと適切でない動きをする可能性があるから高速に動作しなそうという直感が裏切られて面白かった。同じくらい適切な動きをする可能性もあるということを見落としていたかもしれないと感じた。
    -- そのような学びがあるのはよかったです．確率を用いたり，乱数を用いると，自分の直感から外れた現象が見られることはよくあります．それだからこそ，数学をしっかりと使って理解することが重要なのだと思います．
  • クイックソートの比較回数で、塊の幅はnが大きくなるにつれて広がっているが形がくずれていないのが面白いと思った。
    -- 比較回数は約 $n \log_2 n$ と約 $n^2/2$ の間に必ずある (ことが分かる) ので，幅はだんだん広がっていくように見えると思います．実は約 $n^2/2$ 回の比較を行う場合はあまり発生しないので，図の「上の方」はだいぶすかすかに見えていると思います．そのせいもあって，期待値は $n \log_2 n$ に近い方に位置することになります．
• 12/27 (10) 離散確率論：確率的離散システムの解析 (発展)
  • 標示確率変数ありがとう
    -- まさに感謝です．演習問題を通して，恩恵を授かってください．
  • X=0またはX=2E[X] に変形するのが鮮やかすぎた
    -- 確かにそうだと思います．これはなかなか思いつきません．ただ，確率的システムの解析でチェビシェフの不等式をこのように用いるということはよくあります．その観点から言えば，授業で扱わないと思いつかないので，勉強した甲斐があると感じます．
  • 頂点集合があって，ある2つの頂点間に辺があるかどうかが「確率的」なのだと理解しましたが，もう1つの「確率的に生成された 1 つのグラフ」はイメージが浮かびませんでした．
    -- これは説明が不足していてすみません．別の例で雰囲気を説明します．例えば「乱数」という用語がありますが，これは2つの異なる意味を持つ可能性があります．少し具体的にするため「0から9までの整数の上での一様乱数」という用語に対する2つの異なる意味を考えます．1つは「{0, ..., 9}という集合の上の一様分布」という確率分布を指すという意味です．もう1つは「{0, ..., 9}から一様分布に従って実際に選ばれた1つの整数」という整数を指すという意味です．前者は確率分布であり，後者は整数なので，この2つの意味は異なります．C言語のイメージでいうと，前者はrand()という関数自体を指し，後者はrand()の返り値である数を指す，といったイメージです．
    これと同様に，「ランダム・グラフ」という用語は，確率分布を指す場合と1つのグラフを指す場合がある，ということになります．いかがでしょうか．
• 12/13 (9) 離散確率論：確率的離散システムの解析 (基礎)
  • 日本代表惜しかった
    -- 楽しませていただいたことに私は感謝しています．
  • チェルノフ上界の技法で定数cが2や3だと不適切な場合はありますか？
    -- 特別に不適切な場合はないと思ってよいはずです．cが1よりも真に大きければ，何かしら意味のある上界が得られます．ただ，「最もよい上界」を得ようとする場合は，慎重になる必要があります．演習問題9.12に取り組んでみてください．
  • 高校時代に1からなんらかの確率を引いて求める解法を用いるときに、「余事象」や「補集合」といった言葉を耳にした気がします。特に意識はしていませんでしたが、用語を正しく使う(使い分ける)という観点では気をつけなきゃなとふと思いました。
    -- そうですね．事象に対して「余事象」という用語を使います．数学的には「補集合」と同じです．用語を正しく使えるようになることは，この授業の目標の1つなので，ぜひ身に付けてください．
  • 今回出てきたシミュレーションのヒストグラムのようなものはあまり描いてこなかったので自分でシミュレーションしたあとに描いてみようかなと思った。先生視点でグラフを描く上で気をつけていることとかこのツールが便利みたいなおすすめとかありますか？
    -- 今回の授業の図はすべてExcelで描いています．何を使って描いてもよいとは思いますが，自分の目的に合ったツールを使えるとよいと思います．そのためには，どのようなツールがそもそも存在するのか調べる必要はあるかもしれません．私の場合，細かいことを行わないときにはExcelを使いますが，細かいことをするときにはgnuplotを使います．もっと込み入ったことを行うときには，pythonのmatplotlibもお薦めします．
    なお，シミュレーションなどを行うことはかなりお薦めします．そもそも楽しいです．今回の授業でご紹介したものはどれも難しくないはずですので，ぜひやってみてください．
• 12/6 (8) 離散代数 (4)：対称性を考慮した数え上げ (発展)
  • 手続きはできるけど理解できているわけではない
    -- まずは，手続きとして計算できることが大事なので，それが間違いなく行えるようにしてください．それだけでも割と大変で，重要だと思います．その次に原理を理解しようとしてみてください．
  • 正三角形とその重心ぐらいならすぐに巡回群C3の同型は思いつきますが、もっと難しい図形になると簡単に思いつく気はしません。何か置換群の同型を思いつくコツとかはありますか？
    -- 回転・鏡映対称性については，必ずその中心がどこかに位置します．まず，中心がどこにあるか見極めてください．
  • 立方体の中点をつないで切断すると六角形が現れるという話，中学受験を思い出しました．こういう立体を想像するのは昔から苦手なので，練習しながらできるようになれればいいなとおもった．
    -- そうですね．何事も練習が必要なのだと思います．
  • バーンサイドの補題を使うことで置換とその対応さえわかれば，同じ操作で立体の対称性も考えられる部分に強力さを感じました．ただ，置換とその対応を考えるのは，動画の説明の理解はできるものの自力で全列挙できる気はしなかったですね．テストでこれをやると考えると数え漏れとか軸を全列挙できなかったりしそうで怖いです...
    -- 試験では，その場で今まで見たことがない置換群が突然出てくることはないと思ってください．(90分で6問に取り組まなければならないので．) その点は安心してください．
  • 試験勉強を兼ねて復習を始めました．再提出の返却が試験前になるように頑張って早めに出したいと思っています．近似の不等式や公式などに対して先生は「覚える必要はない」とおっしゃっていたと思います．それゆえに持ち込み可なのでしょうが，色々勉強してきたためA4の紙に収まらなさそうだな...となってます．文字小さくするなどして対策してみようと思います．
    -- おそらく，要点だけをメモして，細かい部分はそこから導出することができれば，理想的だと思います．うまくまとめることも重要な能力だと思いますので，ぜひ培ってください．
• 11/29 (7) 離散代数 (3)：対称性を考慮した数え上げ (基礎)
  • 試験勉強は2週間前から始めることにした
    -- はい，しっかりと準備するようにしてください．
  • 動画は毎回見ていて，わかりやすく行間を埋めていただき助かっています．ただ，うまく質問の形にできなくて最近はコメントが減ってしまいました．質問の形になっていなくても，気づいたりしたことや感想を拙くても遠慮なくたくさんあげて行こうかなと思いました．せっかくやり取りができて勉強できるのでもっと活かしていきたいですね
    -- はい，雑談でも結構ですので，なにか書いていただけると私も励みになります ;-)
  • 恒等置換の場合で全ての着色のパターンを数えているのに、最終的には正しい総数が求められるのが不思議だと思った。
    -- 確かにそうですね．それがバーンサイドの補題の不思議なところで，威力だと思います．バーンサイドの補題の証明を思い出すと，そこで使っているのは二重の数え上げ (という基礎的な証明法) と軌道・固定部分群定理だけで，軌道・固定部分群定理の証明で使っているのは，ラグランジュの定理と全単射による証明 (という基礎的な証明法) だけで，ラグランジュの定理の証明は全単射による証明 (という基礎的な証明法) と置換 (全単射) に関する基本的な事項だけなので，結局すべて基礎的なことの組合せでできていることになります．基礎がいかに重要であるのか，ということが分かると思います．
  • G同値のお話についてです．ある着色を別の着色に置換を用いて写しているのに「同値」という言葉がでてきていて，今までの自分が扱ってきた「同値」と違うように感じた
    -- 数学において「同値」という用語は「本質的に同じ」ということを表すときに使われます．G同値性においては，「Gの要素であるような置換で写りあう着色どうしは本質的に同じである」ということを考えています．同値関係は「本質的に同じ」という考え方を数学的にちゃんと定義した概念だと思ってください．
    例えば，論理において「同値」ということばを使うことがあります．これは論理式 (あるいは命題) が本質的に同じであることを表す用語です．皆さんが『離散数学』や『論理設計学』という授業を受けたことがあるとき，もしかしたら，2つの論理式 $\varphi$ と $\psi$ に対して「$\varphi = \psi$」というような表記を用いることがあったかもしれませんが，そのとき，「そもそも $\varphi$ と $\psi$ が等しい」とはどういうことなのか，どのように定義されるのか，ということをしっかりと考える必要があります．例えば，論理変数 $x, y$ があるとき，「$\overline{x \vee y} = \overline{x} \wedge \overline{y}$」と書いたら，それは何を意味するのでしょうか？ 一方で，論理的な同値性の定義から，「$\overline{x \vee y} \leftrightarrow \overline{x} \wedge \overline{y}$」が正しいことは言えます．このように，見た目の違う「$\overline{x \vee y}$」と「$\overline{x} \wedge \overline{y}$」が「本質的に同じである」ということを同値の記号「$\leftrightarrow$」で表しているのです．
• 11/22 (6) 離散代数 (2)：部分群と軌道
  • この欄 (毎回のコメントや質問) の投稿が少なくなっています．この欄は皆さんが私と応対するとてもよい機会です．ぜひ活かしてください．
  • 今まであまりやったことのない頭の使い方をする
    -- それは勉強になっている証拠なので，よいことだと思います．ぜひ，このような論法にも慣れてください．
  • |G/H| = |G| / |H| の性質はラグランジュの定理として使って良いのですか？
    -- |G/H| = |G| / |H| をラグランジュの定理と呼ぶこともあるので，私は「使って良い」という立場です．
• 11/15 (5) 離散代数 (1)：置換と置換群
  • 2次の係数が1ではない2次式が分母にある関数の部分分数部展開で，2次の係数が1になる分解を書いてしまったり，解と係数の関係で2次の係数で割り忘れたりしてしまいました... 漸化式の解き発展とあるだけあって計算が煩雑で1問にすごく時間がかかりました．手計算はやっぱり苦手ですね．計算はやるしかないのはわかっているんですが，なかなか苦しいし合わなかったです...
    -- そうですね．ややこしいのは確かだと思います．一方で，一つの問題を様々な方法で取り組むことができれば，一つの計算法で出てきた結果の正しさを確認することもできます．そのような使い方もしてみてください．
  • 母関数を用いた方法で解ける漸化式は多いのだろうが，その分計算の煩雑さや，既知の形に結びつけるように変形する工夫が大変でした．煩雑な分数や無理数の手計算は時間がかかる上にミスを連発してしまうので嫌いですが，練習あるのみですね...
    -- 嫌いにならないでください ;-) 考え方は単純なので，まずその部分は慣れてください．細かい計算はミスをしないように慎重に進めてください．
  • 前回までの数列と違って，馴染みのない概念と高い抽象度のせいか，わかっているのかが自分でわからないような程度しか理解が進まなかったように感じた．丁寧に問題と向き合って解いたり質問したりする中で理解を深められればいいなと思った．
    -- はい，演習問題に取り組んで，分からない部分は質問してください．よろしくお願いします．
• 11/8 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
  • 母関数の計算、難しい
    -- そうですね．演習問題をとおして，しっかりと身に付けてください．
  • 母関数が収束するかどうかは毎回考えるべきですか？
    -- 実をいうと，母関数が収束するかどうか，考えないことが多いです．それを許すためには，母関数を「形式的べき級数 (formal power series)」と見なす，という方法を用います．ただ，これを行うためには，いろいろと準備が必要なので，授業ではそうせず，収束する場合のみ考えることにしました．
  • 対応できる範囲を広げれば広げるほど，手続きが増えていく感じがしたので，広い範囲をカバーできるもの一つだけを使うのではなく色々使い分けるのが大事なのかなと感じた
    -- そのとおりだと思います．一つ重要なことは，この授業で扱っていることは何も覚えるべきではないということです．覚えようと思わないでください．必要になったときに思い出せるように整理しておくことが重要です．それを念頭において，ぜひ使い分けてください．
• 11/1 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
  • 返却された答案のコメントがついていない✓はどのような意図で付けているのでしょうか．
    --コメントがついていようがいまいが，「そこまでチェックした」という確認のマークです．
  • anをλ^nに置き換える発想はどこから、、、
    --スライド9ページのプロットを見てください．このような観察 (実験) をすることが割と重要です．
  • <と≦ではどちらが制約として強いですか
    --場合によります．例えば，同じ数列$\{a_n\}$に対して「$a_n < 10n$」と「$a_n \leq 10n$」という不等式を比較するとき，「$a_n < 10n$」の方が多く情報を含んでいると言えます．なぜかといえば「$a_n < 10n$」の方は「$a_n = 10n$」となる可能性を排除しているからです．一方で，「$a_n < 10n$」と「$a_n \leq 9n$」という不等式を比較するとき，「$a_n \leq 9n$」の方が情報を多く含んでいると言えます．なぜかといえば，「$a_n \leq 9n$」の方が，「$9n < a_n < 10n$」となる可能性を排除しているからです．結論としては，記号の種類ではなく，そこから得られる情報に着目するとよいことになると思います．
  • 線形漸化式の解き方で、行列を使う方法の方が一般性があるということは、どの線形漸化式でも使える解法ということですか？
    --そのとおりです．例えば，スライド21ページにあるように，複数の数列が絡み合っているような線形漸化式でも使えます．
  • スライドp28の不等式の係数が「2で十分」とおっしゃっていましたが，どのような理由で2を設定したのでしょうか？(似たような状況に直面した時，何を考えて今回の「2」のような係数をみつければいいのでしょうか？)
    --いろいろな係数を試して，よさそうなものを見つけています．2である必要はありません．例えば，同じように証明を「係数が4である」として行っても，「係数が100万である」として行っても，問題なくできます．無理に小さいものを見つける必要はありませんが，小さい方が好まれるような気もします．(上にある「<と≦ではどちらが制約として強いですか」という質問の回答も参考にしてください．)
• 10/25 (2) 数え上げの基礎 (2)：漸化式の立て方
  • 過去回の質問や，質問が複数あった場合のFormの複数回答はしても大丈夫ですか？(このFormの使い方の話になります)
    -- はい，大丈夫です．ただ，過去回の質問の場合は，どの回の質問であるのか書いていただけると分かりやすいので，ぜひそうしてください．
  • レポートの問題が多いので復習問題だけやって出すことにした
    -- 皆さんの好きなように提出してください．
  • 問題の解説は提出以外でされますか
    -- 直接聞いていただいてもかまいません．
  • グラフGnの漸化式を立てるために、新たにグラフHnを考えるというような解き方を他の問題でも行うのは簡単ではないと感じました。
    -- そうですね．漸化式を立てようと思って進めていくと，そこで初めて，別のグラフを考えればよさそうであるということが分かります．そのため，はじめからHnというグラフを頭に思い浮かべているわけではありません．
  • "アルゴリズムをみて漸化式が成立すること証明する"ことがよく分からないのですが、各行で行われていることを説明すればそれは証明になるのでしょうか？例えば授業内問題2.2では、2行目が必ず実行されること、3行目の条件で4,5行目が再帰的に実行されることを説明すればそれは証明になりますか？
    -- はい，それで問題ありません．
  • 1.2年の復習の必要性を感じた。
    -- そうですね．しっかりと復習をしながら進めてください．
• 10/11 (1) 数え上げの基礎 (1)：二項係数と二項定理
  • どうしてこの演習問題を選択したのですか？
    -- 質問の投稿時間より，第0回に対するコメントだと判断します．
    2つ理由があります．1つ目は，すぐに解答が思いつきそうもないことです．2つ目は，特殊な知識を必要としないことです．
  • 次回の問題も楽しみにしています。
    -- はい，楽しみにしていてください．:-)
  • 式だけだと数式の意味が分かりませんでしたが，格子や点を用いた説明で理解できました
    -- そうですね．ひとつの事項を様々な角度から見ることができると，理解が深まると思います．
  • 証明を自分でやってみようとすると、スライドのように式変形が上手く進まず詰まったり、そもそも方針が立たなかったりしました。そこから1つの証明を論理的飛躍なしに書き上げることの難しさを感じました。そこを訓練するのがこの授業なのかなと思うので、講義スライドのマネから入って身につけていきたい(≠覚える)と思いました。
    -- はい，難しい部分もあると思いますが，ぜひ直接質問をしてください．よろしくお願いします．
  • 大学1年生のときに習ったような、、、みたいなうろ覚えの記憶がたくさん出てきて復習が必要だと思いました。
    -- うろ覚えで問題ありませんので，ぜひ復習してください．「必要となったときに復習できる」ことが今後大事になってくるはずです．
  • 授業内問題1.2.1で、rについての帰納法で求めようとしました。r=nが成立することを確かめ、任意の自然数k<=nで成立すると仮定し、k-1について成立するか確かめるため右項を展開していったところ、$\sum_{i=k-1}^{n}{\binom{i}{k-1} \frac{(k+1)(i-k+1)}{k(n-k+1)}}$ となり、目的である $\sum_{i=k-1}^{n}{\binom{i}{k-1}}$ に係数がつく形になりました。明らかに係数に n と i が含まれるのが問題となっていますが、どのように消せばいいか分かりません。wolframalpha に投げると取る値は同じではあるようです。
    -- 指摘されてる等式は正しいような気がします．ただ，その証明は元の等式と同程度の難しさだと思います．つまり，それによって，簡単になっているような気はあまりしません．
    また，別のことですが，数学的帰納法が正しく書けていないような気がします．証明すべきことは，「任意の自然数n, rに対して，『n≧rならば〇〇である』」という形の命題です．いま，rに関する数学的帰納法を使おうとするならば，各r = 0, 1, 2, ... に対して，「任意の自然数nに対して，『n≧rならば〇〇である』」ということを証明することになります．それを数学的帰納法で証明しようとしてみてください．
  • 今回は階乗の上界と下界は与えられていますが、その上界と下界をどのように導き出すのかが分からないです。
    -- 実際には，いろいろな推測を通して，上界や下界の予想をします．推測や予想をする部分は，かなり実験をすることになります．予想した上界や下界をプロットしてみて，正しそうか考えます．また，予想した上界や下界が正しいと証明できないといけないので，それができそうなぐらいシンプルな形であることも重要です．対面授業で補足します．
  • 特に質問が思いつなかったのでくだらない質問にはなりますが、二項定理の応用(3)で出てくる $(x+1)^{2n}$ のようなものはどこから思いつくものですか？問題を見て、$x^n$ の係数を2パターンで確認できないかなとなるわけですか？この手の突然出てきてそれをいじると問題の答えに辿り着くものの見つけ方がわかりません。
    -- くだらない質問というものはないので，気にせずになんでも聞いてください．
    二項係数の和に関する等式を考えるときには，二項定理を考えるとうまくいく場合が多いので，そこに着想が生まれるかもしれません．そのとき，$\binom{2n}{n}$ が $(x+1)^{2n}$ の展開式の中に現れることに気づくと，授業で紹介した証明に気づくかもしれません．演習問題には似たものもあるので，ぜひ取り組んでみてください．
  • 離散数学においても複素関数論や解析学などの知識が必要であることがよくわかりました。必要に応じて復習したいと思います。
    -- はい，ぜひ復習してください．「離散と連続」とか，「理論と応用」とか，「文系と理系」とか，何でも分類して，違いを気にしすぎることもありますが，本来，世界は一続きのものだと意識して，いろいろなものを見直してみてください．
• 10/4 (0) ガイダンス
  • コメントありがとうございます．いただいたコメントとその回答は以下のように掲載されます．
  • DFMWIN
    -- 知らなかったので調べました．;-) 授業中にゲームをするのは控えてください．
  • 少し暑かった、早く冬になって欲しい
    -- 季節の変わり目は体調を崩しやすいので，注意してください．
  • 1年の離散数学、準備してたら終わってたのですね...勉強していく上であれが離散数学？という違和感はおかしくなかったみたいですね。資料を見るに難しそうに見えますが、色々練習して離散数学を使えるように慣れればなと思います。半年間よろしくおねがいします！
    -- はい，ぜひ今まで勉強したことを使っていくんだ，という気持ちで臨んでください．
  • 誕生日がそろう確率は自信があるくらい高いのでしょうか? 何%くらいあれば成功するだろうと安心(?)できますか?
    -- 具体的な確率は，後半の「離散確率論」の部分で扱います．そして，安心はわりと主観的な感覚なのだろうと思います．一方で，主観と確率を結びつけるような考え方が古くから存在していて，いろいろな論争の的になっているようです．興味がありましたら「主観確率」で調べてみてください．
  • 演習問題は解くことができなかった。誕生日の問題が成功するとは思わなかった。8回中7回成功というのは意外と成功率が高いと感じた。
    -- これは案外成功します :-) こういうのは，実際にやってみるのが大事です．
  • この授業は嫌でも勉強する機会を与えてくださってうれしいです。
    -- 嫌にならないでください ;-)
  • 1限ですが半年間がんばります。。
    -- 1限でなくてもがんばってください
  • 離散数学には興味があるのでたのしみにしています
    -- はい，期待に応えられるようにしていきます．
  • 授業内容に関してはむしろ受けたいぐらいなんですが、特段簡単に単位が取れる訳ではなさそうで、自分はかなり寝付きが悪く、一限の対面授業のために朝早く起きるのは健康に悪いため受講はやめておきます。
    -- 9:00に間に合うために起きることで健康に支障がでるのは，今後さまざまな場面で問題となるかもしれません．例えば，電通大職員の始業時刻は8:30です．多くの企業も8:30や9:00に始業ということがあると思います．なにか対策を考えた方がよいように思いました．
  • グループワークだと自分でわからないこと、気づかないことが見えてくるのでとても面白い形式だと思いました。なんで一限なんですか？
    -- なんで一限なのか，ということについて私の選択はありません．「そこにコマがあるから」です．
  • 演習を行うことは試験対策には良いが、オンデマンドと対面授業を両方真面目にやると思うと重そう。
    -- 受講形態についてはこのページの一番はじめに書いてあるとおりです．自分にあった受講形態を考えていただければよいです．
  • 問題2解きたかったです
    -- 授業中にもいったとおり，できなくても悲観するようなものではないので，気にしないでください．
  • 授業内問題0.2が分かりませんでした
    -- 授業中にもいったとおり，できなくても悲観するようなものではないので，気にしないでください．
  • 演習問題の1は解けたが、2が難しくて解けなかった。
    -- 授業中にもいったとおり，できなくても悲観するようなものではないので，気にしないでください．
  • グループワーク、うまくできるか心配ですがなんとか頑張ります．
    -- はい，よろしくお願いします．
  • グループワーク楽しかったです、いい脳トレになりました^_^
    -- それはよかったです ^_^
  • 証明の方針がたっても、それを数学的に記述するのは容易ではなかった。　
    -- その点を訓練したいのです．その第一歩は何ができないのかに気づくことだと思うので，そこはクリアできたのかな，と思います．
  • 照明すべきであろうことはわかったが、証明するための手法や知識が足りなかった
    -- 重要な技術なので，ぜひ身につけてください．
  • 感覚的にできないことは想像できたが、それを論理的に証明する手立てを考えることが難しかった。
    -- そうですね．考えたことを他の人に伝える (説明する) というのが重要なプロセスなので，授業をとおして身につけていってください．
  • 相談しながら問題を解くのが面白かったです．
    -- ぜひ楽しんでください．:-)
  • 先生の話含め、演習問題を思考するのが非常に面白かったです。
    -- ありがとうございます．今後も楽しめるように努力します．

• 2回の試験により，成績の評価を行う予定です．
• 期末試験
  • 日時：2月14日(火) 第1時限 (9:00--10:30)
  • 教室：西8号館132中講義室 (普段，この授業を行っている教室と同じ)
  • 内容：第9回講義から第14回講義の内容に関する問題6つに答える．各10点で60点満点．
  • 注意：A4用紙1枚の両面に自筆記入したノートのみ持ち込み可．その他，不正行為に関する事項は学修要覧に従う．
  • 試験問題
  • 得点掲示 (辞書順に並べています)

    akstn	54
    ALTF4	52.5
    cdabe	60
    cdefg	55
    dbgn5	40
    dme_lover	50
    katou	28.5
    key10	57.5
    ncysk	42.5
    T0313	59
    wanchang	45
    神裂　火織	45

• 中間試験
  • 日時：12月20日(火) 第1時限 (9:00--10:30)
  • 教室：西8号館132中講義室 (普段，この授業を行っている教室と同じ)
  • 内容：第1回講義から第8回講義の内容に関する問題6つに答える．各10点で60点満点．
  • 注意：A4用紙1枚の両面に自筆記入したノートのみ持ち込み可．その他，不正行為に関する事項は学修要覧に従う．
  • 試験問題
  • 得点掲示 (辞書順に並べています)

    01130	13
    19191	15.5
    acefp	8
    ATORS	10
    bacde	50.5
    dbgns	29
    dme_lover	53.5
    key10	47
    kstuv	37
    mathvalo	40.5
    ncysk	20
    nekochan	37
    nyrsn	32
    TXXXI	47
    ZUNDA	44
    神裂火織	25

• こちらをご覧ください

• 10/4 (0) ガイダンス
• 10/11 (1) 数え上げの基礎 (1)：二項係数と二項定理
• 10/18 休み (体育祭)
• 10/25 (2) 数え上げの基礎 (2)：漸化式の立て方
• 11/1 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
• 11/8 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
• 11/15 (5) 離散代数 (1)：置換と置換群
• 11/22 (6) 離散代数 (2)：部分群と軌道
• 11/29 (7) 離散代数 (3)：対称性を考慮した数え上げ (基礎)
• 12/6 (8) 離散代数 (4)：対称性を考慮した数え上げ (発展)
• 12/13 (9) 離散確率論 (1)：確率的離散システムの解析 (基礎)
• 12/20 中間試験
• 12/27 (10) 離散確率論 (2)：確率的離散システムの解析 (発展) (対面授業は自習)
• 1/3 休み (冬期休業)
• 1/10 (11) 離散確率論 (3)：乱択データ構造とアルゴリズム (基礎)
• 1/17 (12) 離散確率論 (4)：乱択データ構造とアルゴリズム (発展)
• 1/24 (13) 離散確率論 (5)：マルコフ連鎖 (基礎)
• 1/31 (14) 離散確率論 (6)：マルコフ連鎖 (発展)

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

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