離散数理工学

電気通信大学情報理工学域I類 (情報系)
2021年度後学期
火曜1限 (9:00-10:30)
教室：ZOOM (ミーティングIDとパスワードはGoogle Classroomを見て下さい)

岡本吉央

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

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

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

講義資料

1/25 (13) 離散確率論 (6)：マルコフ連鎖 (発展)
1/18 (12) 離散確率論 (5)：マルコフ連鎖 (基礎)
1/11 (11) 離散確率論 (4)：乱択データ構造とアルゴリズム (発展)
1/4 (10) 離散確率論 (3)：乱択データ構造とアルゴリズム (基礎)
12/21 (9) 離散確率論 (2)：確率的離散システムの解析 (発展)
12/14 (8) 離散確率論 (1)：確率的離散システムの解析 (基礎)
11/30 (7) 離散代数 (3)：有限群の応用
11/16 (6) 離散代数 (2)：有限群
11/9 (5) 離散代数 (1)：対称群と置換群
11/2 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
10/26 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
10/19 (2) 数え上げの基礎 (2)：漸化式の立て方
10/12 (1) 数え上げの基礎 (1)：二項係数と二項定理
- スライド | 印刷用スライド | 演習問題 (10/5改訂) | 用語集
- オンデマンド講義動画 (オンデマンド)
- 復習動画 (リアルタイム授業の録画)：質問がなかったため，録画はありません
10/5 (0) ガイダンスと離散数学の復習
- スライド (10/5改訂) | 印刷用スライド (10/5改訂) | 演習問題 (10/5改訂) | 用語集
- 離散確率論の復習
- 復習動画 (リアルタイム授業の録画)

1/25 (13) 離散確率論 (6)：マルコフ連鎖 (発展)
- コメントをありがとうございました．
- 第13回の用語集のリンク先が「404 Not Found」で閲覧できない状態なので, 直していただけると助かります.
  -- すみません，ファイル転送がうまくいっていませんでした．いまは見られると思います．
- 半年間ありがとうございました。期末レポート、頑張ります。
  -- こちらこそありがとうございました．
- スライドの単純ランダムウォークの到達時刻の期待値の計算結果は、現実の色々な状況に示唆を与えそうな結果でとても面白いと思いました。(現実の問題をランダムウォークでモデル化することが適当かどうかに注意する必要はありますが)
  -- ランダムウォークは拡散現象を確率的にモデル化したものであると考えることができ，ランダムウォークから拡散方程式を導くこともできます．リアルタイム授業で補足します．
- 色々なグラフの単純ランダムウォークの到達時刻の期待値を計算するだけでも、非自明な結果がたくさんありそうで面白そうだと思いました。
  -- そうですね．到達時刻以外にもいろいろな時刻や時間が調べられています．リアルタイム授業で「被覆時間」(cover time) について補足します．
1/18 (12) 離散確率論 (5)：マルコフ連鎖 (基礎)
- コメントをありがとうございました．
- 今回の講義で扱っていたマルコフ連鎖は、「斉次　離散時間　有限状態　マルコフ連鎖」と呼ばれるものという説明がありました。この場合の、斉次というのはどういう意味でしょうか？
  また、「斉次　離散時間　有限状態　マルコフ連鎖」以外ではどのようなマルコフ連鎖が考えられるのでしょうか？
  -- 斉次というのは (マルコフ連鎖に対して使われるときは) 推移確率が時刻に依存しないことを意味します．推移確率が時刻に依存する場合，マルコフ連鎖は非斉次といわれます．リアルタイム授業で補足します．
- 確率行列のt乗の極限(t→∞)について扱いましたが,
  ・任意の確率行列同士の積もまた確率行列となること(これ自体は確率行列の性質(定義?)から示せるはず)
  ・確率行列の任意の要素p_{ij}は0 <= p_{ij} <= 1を満たすため, 確率行列同士の積もまた確率行列となる(はずである)ことを考えると確率行列のt乗の任意の要素は∞や-∞には発散しないこと
  から確率行列のt乗の極限が収束しないとき, 確率行列のt乗は「周期的(P^tは2以上のある自然数でP^t=Pが成立する)」である(逆はスライドの例から成り立たない…)ように思えるのですが, これを満たさない場合はあるのでしょうか?
  -- 最後の質問だけに答えると，収束もせず，P^t=Pを満たす2以上のtが存在しない場合はあります．リアルタイム授業で補足します．
- 12月に出題された必須レポート課題について, いずれ採点されたものが返却されたりはするのでしょうか?
  -- すみません，まだ全然レポートを見ることができていません．採点されたものかどうかは分かりませんが，何かしらのものは返却される予定です．
- 気が付いたら次回で最終回なんですね. 前期の「グラフとネットワーク」と違って, 今のところ任意レポートは欠かさず出せているのですが, 今度は間違った問題の再提出が全然できていないです…(最低限ですが, 放置はしないでここがまずかったのだろうという反省はしています！)
  -- こちらの返却も遅くなっていましてすみません．
1/11 (11) 離散確率論 (4)：乱択データ構造とアルゴリズム (発展)
- コメントをありがとうございました．
- どうにかして多項式の同一性判定問題に帰着することができれば, 決定的ではないが間違える確率が十分低い上に, 決定的なアルゴリズムに比べて高速なアルゴリズムを作ることができるということは, とても役に立つ考え方だと思いました. 決定的ではないが問題を早く解くための帰着先として, 多項式の同一性判定問題以外にもよく利用されるものはあるのでしょうか.
  -- よく利用されるものはあります．例えば，「凸体の体積計算」というものがあります．これはある種の積分計算なのですが，高次元 (多変数) の問題なので，計算は非常に難しいです．リアルタイム授業で補足します．
- 確率増幅の話は, 測定を伴う実験の時に複数回測定することで不確かさを小さくする話に似ているなと思いました.
  -- 確かにそうですね．その場合，測定自体にランダム性があることになります．簡単な例を使って，リアルタイム授業で補足します．
1/4 (10) 離散確率論 (3)：乱択データ構造とアルゴリズム (基礎)
- コメントをありがとうございました．
- よいお年をお迎えください. (でもこのコメントが掲載される時点だと既に新年迎えているから「あけましておめでとうございます」の方が良いのか…？)
  -- よい年を迎えてからの，あけましておめでとうございます．
- 乱択クイックソートに関して、ランダムな要素をピボットとして選ぶことがあることは知っていた。しかし、今回の講義のように比較回数の期待値の上界を求めるようなことはしなかったので、興味深かった。今後、乱数を用いるようなアルゴリズムと出会った時には、今回学んだことを活かして解析したい。
  -- 乱択アルゴリズムの設計と解析は非常に重要なトピックです．ぜひ活用して下さい．
- メインに議論したい部分ではないよなぁと思いつつ, 言い淀まれると質問しちゃう人です…w 「最悪時期待比較回数」は「期待比較回数」が場合ごとに求められてその中で最悪なものであって, 「最悪時比較回数」の期待値である「期待最悪時比較回数」とは別物だってことですよね(改めて文章にしてもややこしい…)
  -- では，リアルタイムの授業でこちらは補足します．
12/21 (9) 離散確率論 (2)：確率的離散システムの解析 (発展)
- コメントをありがとうございました．
- 動画内でも述べられていましたが, 標示確率変数を自由に使いこなせるようになることは, 計算を簡単にしてくれるという点で確かに大事そうだと思いました. ただ, 問題ごとにうまい標示確率変数を定義するためには, 問題の要をよく理解する必要がありそうで, これはこれで難しくそうだなぁとも思いました…
  -- その通りですね．リアルタイムの授業では，もう一つ例を挙げてみます．
- 第8回でも感じたが、標示確率変数をうまく考えられるようになりたいと思った。
  -- 標示確率変数を使えるようになることはとても重要なので，ぜひ身につけて下さい．
- 何となく昨年度後学期に先生が担当していた「計算理論」の講義スライドを覗いてみたのですが, 議論のための道具が全く違っていて, 面白そうだと思いました(今年度の前半は武永先生が担当で, チューリングマシンを使って議論が進められました). スライドのPDFを斜め読みしただけだと分からない部分が多いので, 時間が許せばぜひ動画も見たいところです.
  -- 私の授業で扱った計算モデルはWHILEプログラムですが，計算モデルをチューリングマシンとしても計算可能性理論の本質はあまり変わりません．ただ，チューリングマシンでプログラミングを行うのは，かなり骨が折れます．それがチューリングマシンを計算モデルとして使うことの難点ではあります．一方で，形式言語理論 (オートマトン理論) の観点からは，計算を言語における語の受理と見なすという考え方をチューリングマシンでも採用することができるので，その点は利点になります．
12/14 (8) 離散確率論 (1)：確率的離散システムの解析 (基礎)
- コメントをありがとうございました．
- 初回のガイダンスで出席者の誕生日が見事に一致しなかったのが思い出されます. (Classroomのメンバーを見ると生徒が55人いて, 10人くらい欠席していたとしても90%以上の確率で同じ誕生日の人がいるはずなのに…)
  -- 記録を見てみると31人の回答がありました．この場合，同じ誕生日の2人がいる確率はおよそ73%になります．
- どんな文章でも当然気を付ける必要はありますが, 特に確率の絡む文章は, 読むときも書くときもその記述が何を表しているのかに神経を使う印象があります(日本語でのモンティ・ホール問題の記述を考えると特にそう感じます…).
  -- その通りですね．「モンティ・ホール問題」については，昔の授業では扱ったので，今年はリアルタイムの補足で扱うことにします．
- 過去の授業でも何回か出てきたのですが, 先生の「嬉しいですね」の言い方が個人的にツボで, 進めなくてはと思いつつ, ついついそこだけ何度もリピートしてしまいますw (でも何故それが気に入っているのかが説明できないんですよね…)
  -- それは…嬉しいからです！
- 期待値の線形性を用いて、厄介な計算を避けられるのは嬉しい。
  -- そうです．嬉しいんです．ぜひ使いこなせるようになって下さい．
- 研究に関する質問ですが、文献管理や執筆環境はどのようにしていますか？他にも研究を効率よく進めるコツなどがあれば教えて欲しいです
  -- 文献管理自体，私は工夫していないのですが，世の中ではよくMendeleyが使われているような気がします．Zoteroも聞くことがあります．論文などはLaTeXで書いているので，普通のエディタを使ってます．私は古風なので，使っているエディタはEmacsですが，好きなエディタを使えばよいのではないかと思います．共同論文を書くときは，Overleafとか，svnとかgitとかdropboxとか使います．これについては相手に合わせてます．
11/30 (7) 離散代数 (3)：有限群の応用
- コメントをありがとうございました．
- 有限でない群のある性質を, 群準同型写像で有限群に写し取って考えやすくする(証明する)部分が, 無限に存在する整数を, ある整数で割った余りという有限の個数の場合に分けて考える(証明する)ことに何となく似ているなと感じました. (現代数学入門Bで出てきた剰余群と関連がありそう？)
  --剰余群は関係があります．群準同型写像と剰余群は「第一同型定理」という定理でつながっています．
- 第6回の追加問題6.16についてですが, 群が演算について結合法則を満たしているかどうかの確認は列挙以外に方法はないのでしょうか?
  --追加問題6.16に限って言えば，簡単な方法はあります．一方で，一般的な群 (に見えるもの) が本当に結合性を持つかどうか判定する方法で簡単なものは知られていません．しかし，「Lightの結合性検査」というもう少し簡単な方法も知られています．この辺りのことは，リアルタイム授業で補足します．また，乱数を使う方法も知られているので，これについては後半「離散確率論」の中で扱うようにしてみます．
- Conwayといえば, ライフゲームや巨大数のチェーン表記(個人的にどちらも見聞きしたことのある話題)の発明者として聞いたことがあった名前だったのですが, 新型コロナウイルスが原因で昨年亡くなってしまったのが本当に残念です.
  --Conwayはライフゲーム等が有名ですが，その他にも多くの数学分野に影響を与えた数学者です．Conwayの本として例えば『数の本』は日本語でも読めますので，ぜひ勉強してみて下さい．
- 卒研配属に向けて何人かの先生と面談をしましたが, どの先生とも話をしていて面白かったので, 来年の卒研が楽しみになりました. ただ, 初めて1対1で長時間話をする先生ばかりで, 面談前にやたらと緊張してしまったので, 面談が終わった瞬間に面談前の緊張が響いて胃が痛くなることが多く大変でした(◎_◎;).
  --その気持ちは分かります．こういうものは慣れもあると思うので，慣れるようになれるとよいですね．
11/16 (6) 離散代数 (2)：有限群
- コメントをありがとうございました．
- ここ2週間, 他の人のコメントが無くて寂しいです(´・ω・`) (他の人の視点は何かと勉強になるので是非書いてほしい…！)
  --はい，私も寂しいです．ぜひ皆さん，コメントをお寄せ下さい．
- 集合の要素に加えて, 演算も一般化されて議論されているので, 抽象度が高いと思いました. 議論自体は追えるのですが, 特に群の準同型がどう嬉しいのかがまだピンと来ていないです. (群の準同型は現代数学入門Bでも登場して, 群の準同型定理等も登場したのですが, 今一つ咀嚼しきれていない…) 関数の線形性と関係してそうだなとは思うのですが…(f(x+y)=f(x)+f(y)で群の準同型の定義によく似てる)
  --群の準同型について，次回の応用例 (タイリング) で使います．そこで嬉しさの1つが分かっていただけるのではないかと期待しています．他の例についてはリアルタイム授業で補足します．
- 群の定義において、集合GとG上の演算が出てきました。このG上の演算というのは、Gで閉じていて、群の条件を満たせばどのような演算でも良いということでしょうか？上手い例を思いつきませんが、例えば、文字列を結合する演算でも条件を満たすなら集合Gと合わせて群となるということでしょうか？
  --はい，どのような演算でもよいです．文字列の結合の場合，普通は「逆元の存在」という条件を満たさないので，群にはならないと見なされています．「単位元の存在」と「結合性」を満たす場合はモノイドと呼ばれたりします．モノイドは「逆元の存在」を満たさなくてもよいです．一方，群とは，「逆元の存在」を満たすモノイドであると見なせます．
- 個人的には15パズルといえば, 某有名RPGのイースターエッグ(船に乗った状態でAボタンを押したままBボタンを55回押すと遊べる)で馴染み深いので, 次回の授業は面白そうです.
  --はい，これは次回の話題となります．お楽しみに．
11/9 (5) 離散代数 (1)：対称群と置換群
- コメントをありがとうございました．
- 置換(群)については, 現代数学入門Bで触ったことはあったのですが, 予想していないところでまた出会ったので, 次回以降どんな議論が展開されるのかが楽しみです.
  --そうですね．楽しみにしていて下さい．
- 講義動画の「置換を見て何を思うか？」のスライドのところで何を話そうとしたのが気になります.
  --では，この部分をリアルタイム授業で話すことにします．行列の話をします．
11/2 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
- コメントをありがとうございました．
- 何らかの規則に則ったものの数え上げ, という字面はとてもシンプルな話題なのに, その議論の中で今までに学んだ様々な数学の道具が使えるのがとても面白いと思いました.
  -- それが組合せ論の面白い所です．世の中を「連続」と「離散」で分けたがる風潮 (?) がありますが，この2つは密接な関係を持っています．リアルタイム授業で補足します．
- 一般化二項係数も出てきてますます解析学っぽい道具が出てきたなと思ったら「解析的組み合わせ論」という分野があるんですね…
  -- そうなんですね．リアルタイム授業で「解析的組合せ論」のフレーバーを少し紹介します．
  また，数学では「組み合わせ」を「組合せ」と書くことが標準的です．これはそのような伝統なので仕方がないと思って下さい．
10/26 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
- コメントをありがとうございました．
- 母関数によって、数列と関数が繋がるのが興味深いと思った。
  -- そうですね．より詳しいことは次回扱いますので，お楽しみに．
- 母関数を見て、テイラー展開の形に似ているなと思いました。
  -- これはまさにテイラー展開 (あるいは，マクローリン展開) です．これはリアルタイム授業で補足します．
- 無限級数が出てきたのでちょっと身構えております…(分からなくなったら, 都度復習したり質問したりすればいいのでそこまでビビる必要はないのですが)
  -- この授業では難しい級数や，級数に関するややこしい事項は扱いません (扱わないで良いように工夫しています)．その意味では身構える必要はありません．一方で，ここは級数について復習をするよい機会であるかもしれないので，ぜひ復習もして下さい．
- 計算量のオーダーでよくわからない数のn乗などを時々見かけて, どこからそんな数出てくるんだ…？って思ってたのですが, 今回の授業での議論がそれに対する解答の一つになっていて, なるほどと思いました.
  -- なるほどと思って頂けたなら，とてもよかったです．実例の1つについてリアルタイム授業で補足します．
- ここ最近の日本でのコロナの広がりは8月や9月の頃に比べれば比較的おとなしい感じで, 第6波もこの調子でそこまでピークが高くならなければと思いますね.(もちろん来ないのが一番)
  -- いまはとても落ち着いているように思いますね．ただ，人類の歴史を見ると，感染症との闘いは常につきまとっていたようにも感じます．そのため，ある程度「感染症との共存」を念頭において，生活をしていく必要はあるのかな，と個人的には思います．
10/19 (2) 数え上げの基礎 (2)：漸化式の立て方
- コメントをありがとうございました．
- 授業内問題0.1の2、0.2の1と2、授業内問題1.2の2の解き方がわかりません。
  解き方を教えていただけませんか。
  --何を試したのか教えて下さい．すみませんが，それが分からないと導きようがございません．
- 動的計画法をはじめとして, 「サイズ」の小さな問題を使って次々問題を解くというのはよく利用する考え方なので, 漸化式の解法は分かりやすく需要がありそうだなと思いました.
  --その通りで，よく利用する考え方です．ぜひ身につけて下さい．
- 今回の講義で、コラッツ予想が出てきました。
  どうしてそのような予想ができたのか興味を持ちました。具体的な数字で試すうちに正しいと考えるようになったのでしょうか？
  -- 歴史を知らなかったので，調べてみましたが，その結果，出自はよく分からない，ということになりました．
- コラッツ予想って雑に言い換えれば「偶数の時は1/2倍, 奇数の時は3倍して1加えるという操作を繰り返すと, どんな自然数でも必ず2の冪になる」ってことになる(と思う)のですが, 直感的には自然数全体から見たら2の冪の数全体なんてほんの一部(割合的にはn/2^nでn→∞で0に収束)なので, 1個位反例があってもいいのではとも思います. (一方で関数f:「自然数全体の集合」→「2の冪全体の集合」をf(n)=2^nとするとfは全単射なので, 無限集合の濃度としては同じだから, スタートと同じくらいゴールも無限にあるとも解釈できてしまいますが…)
  --その言い方は雑ではなく，予想そのものの言い換えです．ただ，予想の真偽は2の冪がどれほど存在するか，ということとはあまり関係ないような気がします．整数について我々が知っていることは圧倒的に少ないのです．
- コラッツ予想は面白い問題だと思うのですが, この問題の系として何か重要なものがあったりするのでしょうか？(証明の枠組みはすごく応用されるのかもしれないと思ったのですが, 問題の結果を利用するとなるとあまりピンと来なかったので)
  --コラッツ予想が解けることで，他の問題が直ちに解決する，というようのものは聞いたことがありませんし，少し調べたところ見当たりませんでした．ただ，ご指摘のとおり，コラッツ予想の解決のために培われる手法の方が重要になると，私も思います．
- 今回、グラフにおける完全マッチングの数え上げを学びました。
  最大マッチングについても完全マッチングのように数え上げられるのでしょうか？
  例えば、今回のグラフB_{n}における最大マッチングの総数を計算する場合を考えると、
  頂点数が奇数の場合が問題になると思います。完全マッチングの場合と異なり、その頂点に接続するマッチングの辺がない場合もあるので場合分けが増えそうだと予想しました。
  -- できます．完全マッチングが存在するときは，完全マッチングが最大マッチングであるので，講義の内容そのものになります．完全マッチングが存在しないときは，いろいろな方法が考えられますが，その1つをリアルタイム講義で紹介します．
10/12 (1) 数え上げの基礎 (1)：二項係数と二項定理
- コメントありがとうございます．いただいたコメントとその回答は以下のように掲載されます．
- 数え上げにせよ最適化にせよ「組み合わせ」について考えるのは難しいと思うのですが, その分奥が深いですし, もし問題が解けた時にはスッキリした感じがするので, 面白い分野だと思います.
  -- そのような面は確かにあると思います．面白さをこの講義で感じてみて下さい．
- なし
  -- 了解しました．