離散数理工学

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

岡本吉央

実施形態

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

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

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

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

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

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

講義資料

1/23 (13) 離散確率論 (6)：マルコフ連鎖 (発展)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
1/16 (12) 離散確率論 (5)：マルコフ連鎖 (基礎)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
1/9 (11) 離散確率論 (4)：乱択データ構造とアルゴリズム (発展)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
12/19 (10) 離散確率論 (3)：乱択データ構造とアルゴリズム (基礎)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
12/12 (9) 離散確率論 (2)：確率的離散システムの解析 (発展)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
12/5 (8) 離散確率論 (1)：確率的離散システムの解析 (基礎)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
11/28 (7) 離散代数 (3)：ブロック・デザイン
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
11/21 (6) 離散代数 (2)：有限射影平面
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
11/14 (5) 離散代数 (1)：整数と有限体
- スライド (11/14改訂) | 印刷用スライド (11/14改訂) | 演習問題 (11/14改訂) | 用語集
- 講義動画
11/7 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
10/31 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
10/24 (2) 数え上げの基礎 (2)：漸化式の立て方
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
10/10 (1) 数え上げの基礎 (1)：二項係数と二項定理
- スライド | 印刷用スライド | 演習問題 | 用語集
- 講義動画
10/3 (0) ガイダンス
- スライド | 印刷用スライド | 演習問題 | 用語集

1/23 (13) 離散確率論 (6)：マルコフ連鎖 (発展)
- ダランベーコラいつもありがとう
  --こちらこそありがとうございました．
- 約半年間の講義ありがとうございました．
  --こちらこそありがとうございました．
1/16 (12) 離散確率論 (5)：マルコフ連鎖 (基礎)
- 推移行列の定義では$n \times n$実行列としていますが，$\mathbb{R}^{\mathcal{S} \times \mathcal{S}}$とした方がより一般的になると思いました．定義で$n \times n$行列とするべき理由があるのでしょうか．
  --ご指摘のとおりで，$\mathbb{R}^{\mathcal{S} \times \mathcal{S}}$ とした方がより一般的です．$n \times n$行列としている大きな理由はありません．
- 縦読みの起源はインターネットや小説ではなく、もっともっと古来、いろは歌からしいのですね。歌を縦読みすると「科無くて死す。」となりますの。ここで言う「科」は「罪科」の「とが」。つまり「科無くて死す」は「無実であるのに死ぬ。」と言った恨み節になりますわね。時代を経ても、人の想いや考え、思念はそう変わらないのかもしれませんね。
  --ありがとうございます．知りませんでした．英語等でもacrosticと呼ばれるものがあるようです．日本語では「折句」というそうです．
1/9 (11) 離散確率論 (4)：乱択データ構造とアルゴリズム (発展)
- コメントは一件もありませんでした．
12/19 (10) 離散確率論 (3)：乱択データ構造とアルゴリズム (基礎)
- 試験、一限、限界、泣きたい、眠い
  --遅れずに来るようにしてください．
- 授業サイトの2022年度中間試験の過去問がNot Foundになっているのですが、載せていただけませんか？
  --失礼しました．掲載しました．ご確認ください．
12/12 (9) 離散確率論 (2)：確率的離散システムの解析 (発展)
- q
  --すみません，何を答えればよいのかわかりませんでした．(-_-;
12/5 (8) 離散確率論 (1)：確率的離散システムの解析 (基礎)
- この時期、昼寝なしで、生きられな、い。
  --短い時間の昼寝は効果的だと聞いたことがあります．ぜひ効果的に昼寝をしてください．
11/28 (7) 離散代数 (3)：ブロック・デザイン
- 多謝
  --こちらこそ．
- 調布祭楽しかったです。
  --それはよかったです．:-)
- 結合行列の定義で$X \times \mathcal{D}$行列とありますが，(集合)×(集合)行列という言い方があるのですか．
  --結論から言えば「ある」ということになります．これは行の添え字が$X$の要素で，列の添え字が$\mathcal{D}$の要素であるような行列ということになります．
11/21 (6) 離散代数 (2)：有限射影平面
- コメントはいただきませんでした．フォームの設置が遅くなったことが原因かもしれません．その点は申し訳ございません．第6回の内容で質問やコメントがある場合，第7回のフォームでも受け付けますので，そちらをご利用ください．
11/14 (5) 離散代数 (1)：整数と有限体
- 朝起きるのが辛くて、つい大学ではなく自宅で問題を解いてしまっています。
  --受講の仕方は人それぞれで構いませんので，自宅で問題を解くのでも私は構いません．ただ，質問できないことになるのはご了承ください．
- Aaa
  --Aaa
- スライド26ページ: 加法の逆元の存在性に関する証明にある$y = (-x) \mod n$について，$-x$を「$x$に対する$\mathbb{Z} / n \mathbb{Z}$上の加法の逆元」と解釈してしまうと意味のない証明になってしまうと思います．授業動画では$-x$の解釈を口頭で言及されていましたが，自分で証明を書くときには文章で明示するべきでしょうか．それとも読み手の常識的な判断を期待して，そこまで気にする必要はないのでしょうか．
  --この部分は自分でも何をやっているかよく分からなくなって混乱しました．ここの $(-x) \bmod n$ は $x$ を普通の整数だと思って $(-x) \bmod n$ を考えることになります．自分で文章を書くときに明示する必要はないですが，意識する必要はあります．
- 今回のスライドの46枚目、-122+123=1となるため、x=43ではなく41ではないでしょうか？
  --はい，そのとおりです．スライドを修正しました．
11/7 (4) 数え上げの基礎 (4)：漸化式の解き方 (発展)
- 今回のコメントは次の1件のみとなります．
- 本来は岡本先生や講義へのコメントとその返信を掲載する場なので，TAからのコメントをここに載せるのはよろしくないかもしれませんが… 10月24日および10月31日の対面授業にいらっしゃった方は，同じ旨の話を聞いたかと思いますが，もっと岡本先生（とTA）を活用してくれると嬉しいです． ―コメントについてこのコメントが掲載されている（であろう）ページの下の方に，岡本先生が過去に行った講義資料一覧へのリンク(Teaching Top)があります．コメントしてみたいけど，どんなコメントをしようかと思っている人は，リンク先から他の講義資料のページに飛んで，コメント欄を読んでみると雰囲気の参考になるかもしれません．（別にそんなこと思っていない人でも，一回は他の講義のコメントを覗いてみてほしいです．万人にとって面白いとは言いませんが，刺さる人にとってはハマるコンテンツだと思うので．）講義に関する質問をする人が多いなぁと思われるかもしれません（し，それに対する疑問を解消するのも先生の仕事なので，そのようなコメントは大歓迎だと思うのです）が，雑談に対しても先生は極めて真摯に返信してくれます．私見ですが，コメント欄においては，質問と同じくらい雑談も大事な気がするので，雑談の投稿を遠慮することはないと思います．長々と書きましたが，要するに，何でもいいので，もっと気軽にコメントしてくれて，コメントが増えると嬉しいと（少なくともTAは）思います．以上，お気持ち表明失礼しました．TAより．
  --ということですので，皆様よろしくお願いします．
10/31 (3) 数え上げの基礎 (3)：漸化式の解き方 (基礎)
- 感謝！
  --こちらこそありがとうございます．
- 難しい
  --分からないところはぜひ質問してください．
10/24 (2) 数え上げの基礎 (2)：漸化式の立て方
- 特になし
  --わからないことがでてきたら，ぜひ質問してください．
- 宿題の提出を忘れてしまっている。
  --忘れずにご提出ください．
- 私は大学生なのでパチスロが好きです。パチスロのゲーム性（初当たり確率や演出の期待値、平均出球の算出など）の制作に関わる仕事はやはりこの講義のような概念を完璧に理解している人でないと務まらないのでしょうね。
  -- 完璧に理解しようとする努力は必要だと思いますが，最終的に完璧に理解する必要はないと思います．そもそも，あることを完璧に理解することは誰にもできないと思います．少しでも完璧な理解に近づくために研究をしているのですから．
- 0と0の最大公約数についてここまで真剣に議論したのは初めてでした。
  --私もあまり気にしていなかったのですが，ちゃんと扱ってみました．定義に基づいて考察することの大切さを感じ取ってください．
10/10 (1) 数え上げの基礎 (1)：二項係数と二項定理
- 半年間よろしくお願いします！
  --こちらこそよろしくお願いします．
- よろしくお願いします
  --こちらこそよろしくお願いします．
- よろしくお願いします。テスト頑張ります。
  --こちらこそよろしくお願いします．
- 特になし
  --なにかあったらお尋ねください，よろしくお願いします．
- 分かりやすかった。
  --わからなくなったら，ぜひ質問してください．
- おもしろかったです
  --次回も楽しみにしてください．:-)
- 一気に涼しく、というより肌寒くなってきて半ば驚いています。服選びに困ってしまいます。
  --そうですね．いきなり秋になりましたね．体調には気を付けてください．
- 二項係数は少し苦手意識があったので規則の内容を図で解説してくれたことでとても理解が深まりました．
  --それはよかったです．何事も図で考えられると理解が深まるので，他のものでも試してください．
- ずっとcombinationだと思っていたのですが、chooseでもいいことを今知りました。
  --私は $\displaystyle \binom{n}{k}$ を「$n$ combination $k$」と読まれるのを聞いたことがありません．私は「$n$ choose $k$」としか読まれないものだと思っています．
- 総和とコンビネーションがあったらすぐ二項定理の利用を考えますよね。
  --そうですね．二項定理がうまく使えるようになってください．
- 「○○は□□である」が「□□は○○である」に言い換えられないという話は僕も昔からずっと思ってました。 / 単調な格子道を使った問題は受験数学でもさんざん見ましたし、パターン数を求めよと言われて組合せを用いた計算に落とし込むことは当時の僕も出来たと思いますが、組合せの方から格子道を思い浮かべるという経験は一度もしたことがありませんでした。
  --組合せ的解釈を考えるというのはとても有用なので，演習問題を通して身に着けてください．
- 履修しなくても問題を解きに行くことは大丈夫ですか？
  --「履修」ということばを定義どおりに解釈して答えます．なお，学修要覧によると，「科目の履修」とは，「その科目に対応する授業を受講し，試験に合格することによって，その科目の単位を得ること」です．この授業では講義を動画で提供しているので，それを視聴することを「授業を受講する」ことと見なします．この上で，履修しなくても問題を解きに来ることは大丈夫です．ただし，授業を受講せずに問題を解くことはできないと思います．受講してから問題を解きに来ることをお薦めします．
10/3 (0) ガイダンス
- コメントありがとうございます．いただいたコメントとその回答は以下のように掲載されます．
- よろしくお願いします
  --こちらこそ，よろしくお願いします．
- 半年間よろしくお願いします！
  --こちらこそ，よろしくお願いします．
- よろしくお願いします
  --こちらこそ，よろしくお願いします．
- よろしくお願いします
  --こちらこそ，よろしくお願いします．
- 今学期はよろしくお願いします。
  --こちらこそ，よろしくお願いします．
- よろしくお願いします。
  --こちらこそ，よろしくお願いします．
- よろしくおねがいします
  --こちらこそ，よろしくお願いします．
- ありがとうございました。
  -- こちらこそ，ありがとうございました．
- ありがとうございました。朝から頭を働かせることが出来ました。
  --こちらこそ，ありがとうございました．
- 今日は暑いですね。寒暖差で風邪を引かぬよう気を付けたいと思います。
  --季節の変わり目は体調を崩しやすいのでお気をつけください．
- 1限は起きるのが大変です。
  --私も大変です．早く眠りについて，朝早くから準備できるように心がけてください．
- 考える力を養えそう
  --はい，それを目指しています．ぜひ養ってください．
- Group discussionがあって、コミュニケーション力に役に立つことは良いと思います。。
  --はい，ぜひ活かしていってください．
- 今日の授業内演習問題はグループの中でも証明方法がいくつか考えられて面白かったです．
  --そのような楽しさを感じてもらえて，私はうれしいです．よく数学は「答えが一つ」と言われ，それで批判されることがありますが，仮に答えが一つであっても (私はそれ自体に異論を持っていますが)，考え方は一つではないことをいろんな人に知ってもらいたいと思っています．
- 演習問題を自力で解くのは大変そうだが、頑張りたい。
  --自力で解ければ，それは何よりですが，ぜひ他の人と相談しながら進めるようにしてください．分からない部分は私やTAに質問したり，ヒントを要求してください．
- 難しいです．グループワークでは一方的に教えていただく形になりました．勉強します．
  --今回の演習問題は解けなかったとしてもあまり悲観的にならないでください．次回 (第1回) からが本番だと思ってください．
- 演習問題を解く練習で、一人では到底思いつけないような発想をメンバーが思いついて感動したので、グループワークは大変いいと思いました。
  --感動できるのは素晴らしいですね．今後も感動を味わったり，感動を提供してください．
- 上手く記述するの難しかったです。半年間、頑張ります！
  --そうですね．「記述する」ということは考えていることをはっきりさせるときには重要になると思います．その訓練ができれば，この授業の目標の1つは達成できることになると思います．
- 難しい。最後に答えを発表してほしい。
  --答えを知ることが重要ではない，ということに注意してください．考えることが重要です．考えてもわからないときに，答えを欲しがるのではなくて，まずヒントを要求してください．答え (というものがあるとして，それ) を知るだけで勉強になることはほぼありません．解けなくても，解こうとして考える時間と機会にまずは価値を見出してください．
- 一人では整理することができなかった問題もグループで相談することで問題の本質が分かり、より簡潔な証明を作ることができたのが良かった。他者との会話の大切さを改めて認識させられた。
  --グループで問題解決をすることの楽しさを味わうことができたようで，私もうれしいです．今後もその楽しみを味わっていってください．
- 演習問題にかなり苦戦しました。質問なのですが、授業後のコメントは毎回必ず提出する必要がありますか？
  --必ず提出する「必要」はありません．そうであっても，毎回提出してほしいと思っています．私からの要望です．授業は毎回90分もあり，長いように感じるかもしれませんが，私はこの内容について語ろうと思えばもっと長い時間語れます．そのようにある意味で「進んだ内容」や，この90分の中に隠されているものは，皆さんが質問をしない限り，私から引き出せないと思ってください．それを引き出すも隠されたままにしておくのも，皆さん次第です．授業自体はオンデマンドなので，この大学の学生でなくても視聴できます．皆さんが授業に対して持っている利点は，私が目の前にいて，自由に質問等ができることです．それを活かさないと，授業料を払っている意味がないのではないかと心配します．ぜひ活かしてください．
- 試験の持ち込みについて，A4用紙両面とは1枚の紙の表裏のみということでしょうか．
  --明確でなくてすみません．A4サイズの紙1枚のオモテとウラという意味です．
- どのような理論を学べるか，とても楽しみにしております．
  --今後の授業をぜひ楽しみにしてください．
- 数学やってない友達に写像の話をすると、高確率で「写像ってなんすか？」とひろゆきのモノマネを返されるのが腹たちます。
  --そういうときは「それってあなたの感想ですよね？」って返せばよいのではないでしょうか．まったくコミュニケーションが成立してませんが．;-)

試験・成績評価

2回の試験により，成績の評価を行う予定です．
期末試験 (2024/2/6実施)
- 問題
- 試験当日が大雪であったため，試験は実施しませんでした．その代替として，評価方法をレポートに変更しました．レポート問題は試験問題と同一です．

中間試験 (2023/12/26実施)

問題
得点分布
受験した人の数は29，平均点は22.2 (60点満点)． 45点以上 (S相当) が3人 (約10％)， 45点未満40点以上 (A相当) が0人 (約0％)， 40点未満35点以上 (B相当) が1人 (約3％)， 35点未満30点以上 (C相当) が3人 (約10％)， 30点未満 (D相当) が22人 (約76％) です．

得点掲示 (辞書順に並べています)

54387	19
7584	26
alscb	31.5
astrum	14.5
ccbba	26
gaiya	3
GHJKZ	52
H2504	15
Kaseki	15
KERNE	32
kjnhd	20.5
kosuz	16.5
loser	30
mwtfq	17
ocdzm	20.5
OZETEN	48.5
score	28.5
stknb	47
STWOK	12.5
tohuw	27.5
ドドスコ	17

念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
講評
- 総評：できという意味ではかなり悪いです．この調子だと受験した人の中だけも76％近くの学生が不合格になります．それでも私は構いませんが，私は勉強していない学生を合格にしたいと思うような人ではありません．「ワンチャンなんとかなる」と思っている方に言いますが，ワンチャンなんともなりません．いままで「ワンチャンなんとかなってきた」のならば，皆さんは相当なめられてきたのだと思ってください．一方で，45点以上取れている人は，答案を見てもよくできていたと感じます．
- 総評 (続き)：答案を見て思ったことがあります．多くの人の数学に関する技術と知識が大学入学時で止まっているように見えます．大学で何を勉強したのか全く見えませんでした．とても残念だと感じました．以下，問題ごとの講評になりますが，1問15点満点であることに注意してください．
- 問題1：二項係数に関する問題．平均点は7.12．授業で扱った問題の類題なのですが，小問1はほとんどの人ができていませんでした．一方，小問2は多くの人ができていました．そのため，平均点が満点15点の半分ほどになっていると思ってください．
- 問題2：アフィン平面に関する問題．平均点は4.66．あまりできていません．そもそも有限体が何なのか分かっていない人が多い気がします．勉強してないように感じます．「直線の数」という部分だけ見て「$q^2 + q + 1$」(で$q=67$としたもの) を答えている人がいるように思います (この解答は正しくありません)．「インターネットで調べれば何でも分かる」とか「AIに聞けば何でも分かる」と思い込んでる人が陥りそうな答え方だと感じました．
- 問題3：母関数を用いて数列の一般項を導出する問題．平均点は8.00．できている人とできていない人の差が大きい問題でした．この問題ではいろいろな手段を用いて部分点を与えているのですが，それでも平均点はこんなものなのです．
- 問題4：ブロック・デザインに関する問題．平均点は2.40．あまりできておらず，実際，白紙解答が多かったです．定義を理解できていれば，数えるだけだと思うのですが．