離散数理工学

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

岡本吉央

実施形態

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

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

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

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

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

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

講義資料

12/24 離散確率論 (2)：確率的離散システムの解析 (発展)
- 講義動画
- スライド | 演習問題 | 用語集
12/17 離散確率論 (1)：確率的離散システムの解析 (基礎)
- 講義動画
- スライド | 演習問題 | 用語集
11/26 数え上げの基礎 (6)：スターリング数と集合の分割
- 講義動画
- スライド | 演習問題 | 用語集
11/19 数え上げの基礎 (5)：カタラン数
- 講義動画
- スライド | 演習問題 | 用語集
11/12 数え上げの基礎 (4)：漸化式の解き方 (発展)
- 講義動画
- スライド | 演習問題 | 用語集
11/5 数え上げの基礎 (3)：漸化式の解き方 (基礎)
- 講義動画
- スライド | 演習問題 | 用語集
10/29 数え上げの基礎 (2)：漸化式の立て方
- 講義動画
- スライド | 演習問題 | 用語集
10/22 数え上げの基礎 (1)：階乗と二項係数
- 講義動画
- スライド | 演習問題 (9/30改訂) | 用語集
10/1 ガイダンス
- スライド | 演習問題 | 用語集
演習シート (全回共通)

12/17 離散確率論 (1)：確率的離散システムの解析 (基礎)
- 確率ってなんか曖昧な言葉でわかりにくい気がします
  --「確率」という日本語の単語自体に関するコメントだと思って，回答します．
  日本語の「確率」は英語の「probability」の訳語ですが，この訳語が定着するまでには紆余曲折があったようです．Wikipediaの「確率」の項目に詳しく説明があります．
- 確率論の内容はどれくらい関わってきますか？
  --「確率論」というのが2年前学期の「確率論」という授業を指すものだと思って回答します．
  離散確率論，つまり，離散確率分布に関する内容しか用いません．確率，条件つき確率，期待値，条件つき期待値が分かっていれば十分であるはずです．
- クーポン収集問題の期待値で調和数が出てくるのが面白いなと思いました。アルゴリズムの計算量解析でも第n調和数が O(log n) で抑えられる事実を利用したものをよく見かけるので、調和数は様々な場面で出てくるんだなと感じています。
  --調和数は様々な場面で出てきますし，1/nの和だけでなくて，1/n²の和もよくでてきます (1/n²の無限和は収束します)．
- 採点大変そうですけど頑張ってください。何時間くらいかかるんでしょうか
  --採点自体はおそらく3時間ぐらいでできます．ただ，3時間を確保することがまだできていません．採点はまだ始められていません．
11/26 数え上げの基礎 (6)：スターリング数と集合の分割
- テスト勉強頑張ります。演習の復習を中心的にやろうかなと思っています。
  --はい，しっかりと準備をして臨んでください．
- 中間試験の範囲はここまでですか？
  --はい，第1回から第6回までの内容になります．
- 第2種スターリング数の母関数による表示や一般項についても気になりました。
  --$k$ を固定したとき，第2種スターリング数の指数型母関数は
  $$\sum_{n=k}^{\infty} \left\{ \begin{array}{c}n\\k\\\end{array} \right\} \frac{x^n}{n!} = \frac{(\mathrm{e}^x-1)^k}{k!} $$ と書けることが知られています．一般項はあまり綺麗に書けるわけではないですが，知られてはいます．
11/19 数え上げの基礎 (5)：カタラン数
- コメントをありがとうございました．
- 中間試験まで漸化式に関する内容が主になりそう。
  --はい，しっかりと復習をしておいてください．
- 微積の知識で、忘れている箇所があるなと感じた。院試もあるのでしっかり思い出したい。
  --忘れてもよいです．必要なときに思い出せるようにまとめておくのが大切だと思っています．
- カタラン数の母関数から一般項を求める部分の計算がだいぶテクニカルで面白かったです。
  --これは確かにテクニカルだと思います．一方で，こんな母関数でも級数展開はできて，数え上げに使えるのだということが感じ取れたのではないかと思います．
- アンドレの鏡映法とチャン・フェラー性が難しかったです
  --難しいと思います．自分で思いつけ，と言われても思いつかないと感じるので，授業で扱いました．一方で，どちらも，カタラン数やそれと似た数列を扱うときにはよく出てくる考え方なので，一度触れておけば，今後登場したときのハードルが低くなると思います．
- 追加問題5.8の、組合せ論的解釈を与える問題が難しい！　各ノードの色塗りに対応しているのではないかと思ったが上手くいかない！
  --発展問題なので難しいかもしれません．私は全二分木による解釈を使って考えました (そうでなくてはならないという意味ではありません)．全二分木がn+1個の葉を持つとき，頂点の数が2n+1個であることに注目するとよいかもしれません．
11/12 数え上げの基礎 (4)：漸化式の解き方 (発展)
- 追加問題3.9はt_17位まで列挙して法則性を予想して証明しました。⌈n/2⌉⋅⌊n/2⌋と(n/2)^2の大小比較を用いる方法も考えてみます。
  --はい，ぜひ考えてみてください．解き方や考え方が1つしかないということはないので，いろいろな方法を検討することはよいことです．
- 演習問題が面白く、毎週の課題よりも一週先の課題を終わらせてしまっています。第(n+1)回の課題を第n回のレポート提出で提出した場合コメントは貰えますか？
  --はい，問題ありません．
- 最近、形式的べき級数の勉強を少ししていたため、今回の内容は関連深くて面白かったです。
  --はい，形式的べき級数は今回の内容と深く関わっています．形式的べき級数ではべき級数が収束するかということは考えずにべき級数のようなものを考えます．母関数を形式的べき級数と見なすと都合がよいことも多いので，そのようにすることがありますが，この授業では形式的べき級数とはせずに，普通のべき級数として扱うように話を展開しました．
- 漸化式をxの関数に変換するのが今回の目的になりそう。
  --それが第1ステップになります．ぜひ身につけてください．
- 解析学とか複素関数を勉強し直さないとなと思いました
  --そうですね．世の中では「連続」と「離散」を対比させて，まったく違うものだと思わせるような風潮がある気がしますが，本来はそうではなく，その2つは大きく関連しています．いままでに学んだものをうまく組み合わせて，新しいことができるようになっていくことが重要だと私は思っています．
11/5 数え上げの基礎 (3)：漸化式の解き方 (基礎)
- コメントをありがとうございました．
- コメント投稿はマイ講義行った方が良いですか？
  --はい，行ってください．
- ハロウィン何かしますか？
  --特別なことは何もしませんでした．
- 第2回と第3回の内容を見てみると同じ問題を扱っている部分があった。第2回で取り扱った問題を別の角度から解いている印象を受けた。
  --はい，そのとおりで，そのように授業を設計しています．
- 線形代数をきちんと勉強してなかったので対角化も知らなかったけど便利だと思いました。
  --線形代数はどの分野でも使う，重要な道具です．ぜひ復習してください．
- 久々に固有値や固有ベクトルなどの話が出てきて懐かしいなと感じた
  --固有値問題はよく出てくるので，ぜひ慣れてください．
- 追加問題3.9がなかなか難しい。床関数だけならばスライドと同じように出来るが、天井関数の扱いに悩んでいる。
  -- ヒントですが，$\lceil n/2 \rceil \cdot \lfloor n/2 \rfloor$ と $(n/2)^2$ を比較してみてください．
- 隣接四項間漸化式も同様に特性方程式を用いて解けそうですが、六項間漸化式は特性方程式を用いて解くことはできないですよね？五次方程式の解の公式は存在しないので
  --五次方程式の解の公式が存在しないという意味では，特性方程式が解けないというのは正しいです．そのとおりです．
10/29 数え上げの基礎 (2)：漸化式の立て方
- コメントをありがとうございます．
- 授業内課題は、だいぶ前に解いていたので紙に書くだけだったのですが、いざ口頭で説明しようとすると難しいなと思いました。
  --書いたとおりに説明すれば，大丈夫だと思います．落ち着いて説明してください．
- 試験直前に練習問題に取り組もうと考えているのですが、その際にわからない問題があった場合メールで問い合わせたら対応いただけますか？
  --演習問題に取り組んだ場合は，レポートとして提出することになっています．メールで問合せをしてもよいですが，その場合，私から回答があることを保証できないので，ご了承ください．(試験直前などに，まとめて多くの人が問合せをした場合に，私が処理しきれませんので，そのようにしています．)
- 演習問題を提供してくれるのはテスト対策にもなるし、授業で得た知識などを確認するいい機会になると思う。
  --はい，演習問題で理解を深めてください．
- 計算量解析の基礎は数え上げについて、他の授業でもそれっぽいことしてたなと思いました
  --同じことを様々な観点から見ると，新たな発見があるかもしれません．ぜひ見つけてみてください．
- グラフに苦手意識があり、実際に使うために記述することに抵抗感があります。今回の授業を期に、少し慣れられるように頑張ります。
  --この授業でグラフは今後あまり出てこないかもしれませんが，慣れることに越したことはないので，ぜひ慣れてください．
- 格子の完全マッチングの総数を求める問題で、ある頂点と接続する頂点を固定して考えるのは大事な考え方だと思った。
  --これは場合分けをする場合の重要な考え方です．似たような考え方は他の場面でも使えるので，ぜひ活かしてください．
- グラフの完全マッチング数計算において、一見複雑そうでも局所的に分割していくとアルゴリズムが設計できるのが面白かった。自力では3段の解法が思いつかなかったが、今後このような問題が解けるような力をつけたい。
  --授業内演習問題は同じような考え方をする問題なので，ぜひ取り組んでください．
- 41ページの証明の「a>=bよりq>=1」が何でそうなるのかよくわからなかった
  --a=qb+rと書いていて，0<=r<bなので，q=0だと，a=r<bとなり，a>=bに矛盾します．いかがでしょうか．
- ホモロジー群が完全マッチングの数え上げに使えるのではと思いました。しかし、例えば2n個の点による円環グラフと、その一点から2k個の点による直線グラフが生えたグラフを考えると、完全マッチングの個数は2,3と違うのに対して、2つのグラフはホモトピー同値であることから、完全マッチングの個数がホモトピー不変量でないことが分かったため撃沈しました。
  --他のところで勉強したことを活かそうとする姿勢は素晴らしいので，ぜひそのような考察はしてみてください (今回はうまくいかなかったようですが)．なお，グラフにおいて，1次ホモロジー群のランク (第1ベッチ数) は，ある意味で独立なグラフの閉路の総数に対応します．
- コラッツ予想はどうして解くのが難しいんですか？
  --難しいことの理由もよく分かっていないというのが数学の現状です．有名な数学者エルデシュはコラッツ予想を指して「Mathematics is not yet ripe enough for such questions」と言ったそうです．ただ，コラッツ予想が難しいことの理由の傍証として，似た問題が決定不可能であるということは知られています．(決定不可能であることについては『計算理論』の授業を参照してください．)
10/22 数え上げの基礎 (1)：階乗と二項係数
- コメントをありがとうございます．
- まず，10月1日に投稿されたコメントを掲載します．これらはガイダンスに対するコメントだと理解したので，第1回の授業に対するコメントと分けます．
- ガイダンスが分かりやすかったです。積極的に演習問題に取り組みたいです。
  --はい，よろしくお願いします．
- 今日の100を作る問題は「できない」ですか？グループで演習を行うというのを大事にして受けようと思いました。
  --演習問題に対する解答をこの欄では述べないことにしているので，直接聞いてください．
- プログラミングは得意でないが、講義が面白そうだと感じたためチャレンジしようと考えています。ソフトウェアの必須事項は信頼性だと思う。7月のクラウドストライクの件では高い費用をかけてセキュリティ対策をしていた企業が影響を受ける結果となったため。
  --ソフトウェアの信頼性は信頼性工学という学問分野で研究されています．ソフトウェアに限定する場合は，ソフトウェア工学でも議論されます．そこでは確率の考え方を使うことが多いので，この講義の後半の内容が関わってきます．ただ，この授業でソフトウェア信頼性を直接扱う予定はありませんので，ご了承ください．
- 誤った内容を解答してしまいました。興味のある分野なので予習に力を入れたいと思う。
  --はい，よｒそいくお願いします．
- さいころの確率の問題が自力で解けなくて悔しかった. 次回は解けるように問題文にとらわれずに考えたい.
  --自由な発想でとりくんでください．分からない場合はどんどんヒントを出しますので，聞いてください．
- 以下，10月2日以降に投稿されたコメントを掲載します．
- 講義内容には非常に興味があり受講することを考えているのですが、留年せずに卒業するのに単位取得状況が厳しく履修に余裕がないです。昨年(例年)の不可の割合などをご教授いただければ幸いです。
  --昨年度のことだけを書きます．履修登録者数は40で，成績はSが4名 (10.0%)，Aが5名 (12.5%)，Bが9名 (22.5%)，Cが2名 (5%)，Dが20名 (50%) です．なお，Dの中の11名は未受験です．
- 半年間よろしくお願いします！
  --はい，よろしくお願いします．
- よろしくお願いします
  --はい，よろしくお願いします．
- 第0回のコメントを送信しわすれていました。よろしくお願いします。
  --はい，よろしくお願いします．
- 練習問題がたくさんあって助かります
  --ありすぎるかもしれないので，適宜取捨選択して取り組んでください．
- 運動会で授業がなかったため、質問もありません。
  --第1回の授業 (10月22日) に対するコメント欄なので，第1回の授業に対してコメントをお願いします．
- たくさん式がでてきたので演習を重ねることで使いこなせるようにしたい。
  --たくさん出てきた式を覚える必要はありません，必要になったときに，調べて思い出せるようにしておいてください．
- 極限で発散を表すとき、lim = ∞と書き表すことが高校数学ではありました。しかし、この表記によって、無限とは一種の実数であり、∞-∞=0のような演算が成立すると勘違いする同級生が散見されました。いっそのこと高校数学では有限値確定でもしない限りlim = αと書くのを禁止するのは良い案だと思いませんか？
  --考え方としてはありえると思います (そもそも，振動する場合に「lim = 振動」とは書かないですし) ．ただ，lim = ∞ と書くのは高校数学に限らないので，その書き方を (ある程度) 正確に理解すべきであるという立場の方を私は重視します．教育としては勘違いをしっかりと正すようにしていくのが大事だと思っています．また，実数に+∞と-∞を付け加えて考える便利な場合があるので，そうすることもあります．拡大実数と呼んだりするようです．
- 復習問題1-2が解けなかったので、授業でヒントか何かを得られたらと思う。
  --はい，授業で聞いてください，また，復習問題は授業のスライドや動画で説明しているものなので，それを参考にしてみてください．
- 定理を数式的と直感的(組み合わせ的解釈)の両方から理解できて面白かった。
  --面白さが伝わったようで，私もうれしいです．組合せ的解釈を使いこなせるようになってください．
- 組合せ的解釈を用いると様々な式が直感的に理解できる感じがして面白かったです。
  --面白さが伝わったようで，私もうれしいです．演習問題にも組合せ的解釈を考えるものがあるので，ぜひ取り組んでください．
- 組み合わせ解釈による証明は、図を描けば成り立っているような気がしてくるのですが、文章で書くのが難しいです。
  --文章にするのは確かに難しいと思います．全単射による証明のときは，どのような全単射を考えるのか書いて，それが全単射であることを議論してください．例えば，逆写像があることをいえば十分です．また，二重の数え上げによる証明のときは，何を2とおりに数えるのか書いて，その数え方を2つ書いてください．
- パスカルの規則を繰り返し使用して展開していったら、$\binom{a}{b} = \sum_{k=0}^{b} \binom{a - b + k -1}{k}$ と展開できて面白いですね
  --そうですね．組合せ的解釈による説明もぜひ考えてみてください．
- 各問題の証明の捉え方が分かりやすかったです。簡単な上界、下界を使えるように特に頑張ります。
  --簡単な上界・下界は今後使います．
- 組み合わせ的解釈が難しかったです
  --慣れると便利なので，慣れるために，演習問題にも取り組んでください．
10/1 ガイダンス
- コメントをありがとうございます．皆さんのコメントとそれに対する返答は次のように掲載されます．
- 半年間よろしくお願いします
  --はい，こちらこそよろしくお願いします．
- よろしくお願いします。
  --はい，こちらこそよろしくお願いします．
- 朝が早くて不安ですが、履修してみようと思います。よろしくお願いします。
  --はい，こちらこそよろしくお願いします．
- がんばります
  --分からないところがあれば，どんどん質問をしてください．
- 去年は途中から諦めてしまったため今年度は頑張っていきます。
  --はい，ぜひよろしくお願いします．
- 興味深い内容だったです。
  --今後も皆さんにとって興味深い内容になっていることを願っています．
- とても面白そうな内容だと思いました。
  --今後も皆さんにとって面白い内容になっていることを願っています．
- 朝から頭を使って目が覚めるので良い
  --それはよい効果ですね :-)
- 難しいと思った
  --難しいぐらいがちょうどいいと思っています．そうでないと勉強にならないので．
- 問題がパズルみたいで面白かったです。
  --どんな問題もパズルみたいだと思ってもらえるとよいのかもしれません．パズルみたいに楽しんでください．
- 今回の演習問題がパズルをやっているような感覚になって面白かったです。
  --演習を楽しむ，あるいは，楽しめる，という態度が大事だと思います．今後も楽しんでください．
- 今日解いた問題はなんかちょっとした頭の体操みたいで面白かった。
  --今後の問題も頭の体操みたいに取り組んでください．
- 問題を解くのに知識が必要でなく、謎解きのような感覚で考えることができて楽しかったです。
  --第0回目なので，知識は余り必要としないものを題材にしています．今後は各回の授業の内容に基づいた演習になります．
- 問題が解けて良かった
  --それはよかったです．ただ解けなくてもあまり悲観的にならないでください．解けることも重要ですが，それと同時にしっかりと考えることが重要です．
- 授業内課題0.2が難しかったです。課題0.1はきれいに解くことができました。
  --問題0.2は難しいと思うので，解けなくても悲しむ必要はないと思ってください．
- 0.2は無理そう
  --問題0.2は難しいと思うので，解けなくても悲しむ必要はないと思ってください．
- これから友達と頑張って演習に取り込んで行きたいです。
  --はい，ぜひそのように取り組んでください．
- 演習問題が解いてて面白かったです。誕生日のパラドクスについて計算してみると23人以上では確率が0.5を超えるとわかり、直感に反して面白いなと思いました。
  --はい，誕生日のパラドックスについては，後の方の授業でもう少し一般的な状況で確率の計算をする予定です．
- 1限なのは正直億劫と感じてしまいましたが、内容はすごく面白そうだなと感じました。
  --億劫だと感じず，積極的に参加してください．:-)
- 数学がかなり苦手なんですが、高校〜大学一年生の範囲で復習しておいた方がいい内容はありますか？
  --シラバスに書いてあるとおり，「離散数学，プログラミング通論，線形代数学第一，アルゴリズム理論第一，確率論」を前もって履修しておくべき科目としています．あと，ここに書き忘れていますが「微分積分学第一」の内容も使ったりします．これらの科目は (I類では) 必修の授業なので，履修していることは前提としています．ただ，それらの内容をすべて覚えている必要はありません．その内容を使いますが，使うときには必要な部分を復習しながら使うことになるので，そのときに思い出せれば十分です．そのような個別の知識よりも，むしろ論理的に考えることが重要になる気がします．

試験・成績評価

各回の授業内演習と2回の試験により，成績の評価を行う予定です．
成績の計算方法
- 授業内演習の配点：1点×12回 = 12点満点
  - 授業内演習は9:30までに教室へ入らないと1点が与えられません．9:30を越える場合は理由 (公共交通機関の遅延証明書など) を添えてください．
- 試験の配点：50点×2回 = 100点満点
- 成績 = min{授業内演習の素点+試験の素点, 100}
中間試験
- 日時：12/10(火) 第1時限，いつもの教室
- 出題範囲：講義第1回の最初から第6回の最後まで (第0回は含まない)
- 出題形式：全4問にすべて解答する．そのうち2問以上は演習問題のものと同一である．
- 備考1：A4用紙1枚の両面に自筆で書き込んだメモを持ち込んでよい．
- 備考2：学生証を持参し，机上に提示すること．