離散数理工学
電気通信大学情報理工学部情報・通信工学科
2014年度後学期
火曜1限 (9:00-10:30)
教室：西9-115
岡本 吉央
ショートカット：講義資料 | コメント | 試験・成績 | 公式シラバス | 履修上の注意 | スケジュール
講義資料
新たに掲載したとき，つぶやきます
- 2/3 (13) 離散確率論：マルコフ連鎖 (発展)
- 1/20 (12) 離散確率論：マルコフ連鎖 (基礎)
- 1/13 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
- 1/6 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
- 12/9 (9) 離散確率論：確率的離散システムの解析
- 12/2 (8) 離散確率論：確率の復習と確率不等式
- 11/25 (7) 離散代数：対称性を考慮した数え上げ
- 11/18 (6) 離散代数：部分群と軌道
- 11/11 (5) 離散代数：群と対称性
- 11/4 (4) 数え上げの基礎：漸化式の解き方 (発展)
- 10/28 (3) 数え上げの基礎：漸化式の解き方 (基礎)
-
スライド (11/4修正) |
印刷用スライド (11/4修正) |
演習問題 (11/11修正) |
用語集
- 演習問題3.3と3.7の締切は延長
- 11/11の演習問題修正はヒントのみ．
- 10/21 (2) 数え上げの基礎：漸化式の立て方
- 10/7 (1) 数え上げの基礎：二項係数と二項定理
コメント
- 2/3 (13) 離散確率論：マルコフ連鎖 (発展)
- コメントありがとうございます．来週はなく，試験は再来週です．しっかりと準備をしてきてください．
-
楽しかった
---
ありがとうございます．またご縁がありましたらよろしくお願いします．
-
講義楽しかったです．気分良く春休みをむかえられるようにも試験勉強頑張りたいと思います．
---
ありがとうございます．試験にはしっかりと準備をして臨んでください．
-
今日の笑顔はとても爽やかでした．
---
笑顔というか，苦笑ですね ;-) 変なまとめになってしまってすみませんでした．
-
ギャンブルに勝つのは難しいことが分かりました．
---
そうですね．ギャンブルによって儲けようとか，他の人を出し抜こうとか，そういうことを考える人が多いので，そのためにも，数学的にしっかりと考えることが重要ですね．
-
前半の (ギャンブラーの破産の) お話で，終了条件を3n万円か0万円としたときに破産確率が2/3となることが示されていましたが，最初の所持金と最終金額の差が3万円のとき，2n万円，0万円のとき，n万円となることから，比較的直観に合致した結果であるように，感じました．特に2n万円を終了条件にすると，破産確率が1/2になるのが腑に落ちる感じですね．面白かったです！
---
その通りですね．その直感を支えるためにしっかりと計算をしたわけですね．確率においては，直感通りに成り立たないことがあったり，直感が人によって違ったりするので，いつでもしっかりと計算をすることは重要ですね．
-
ここまで計算できるならかなり応用の幅が広そうと思ったが，例を挙げようとすると案外思いつかない．過去を見ない，というのは結構特殊な状況なのだろうか．
---
マルコフ連鎖は本当にいろんなところで出てきます．「過去を見ない」というのが結構特殊だというのは正しいのですが，「過去を見ない」ということにして現実をモデル化する，ということがよく行われています．例えば，「3つ前までは覚えている」という状況もマルコフ連鎖でモデル化できます．実際にマルコフ連鎖を使ってモデル化を行うときは，そのようなことを行います．
-
一学期間ありがとうございました．グラフとネットワークを含めると一年間お世話になりましたが，おかげで数学的な証明の考え方が鍛えられました．この授業も，今後の人生で知って得をする内容が多くてとても楽しかったです．
---
こちらこそありがとうございました．「数学の証明」は技能だと思っています．特に，大学で身につけられる技能として，重要であるけれども，あまり強調されなかったり，ときには見過ごされることもある気がしています．そのため，「証明からできるだけ逃げないで，しっかりと行っていく」ということが，この講義でもできて良かったです．
-
約半年間丁寧な授業をしてくださりありがとうございました．確率はもともと好きだったのですが，さらなるきっかけをあたえてくれました．
---
こちらこそありがとうございました．カリキュラム上，確率に関する講義は基礎的なものが「確率統計」で，その発展として「情報理論と符号化」や「統計数学」があると思うのですが，その辺りと少し違う風味の確率論を扱ってみました．深く勉強できる題材がいろいろあると思うので，是非挑戦してみて下さい．
- 1/20 (12) 離散確率論：マルコフ連鎖 (基礎)
- コメントありがとうございます．来週は休講ですので，お間違いのないように注意して下さい．
-
肌が乾燥してカサカサです．
---
今日は晴れてるので，特にそう感じますね．ハンドクリームを塗りましょう．
-
今日は他講義でテストがあり，その勉強のために夜更かしをしたせいで寝不足でした．マルコフ連鎖をもう一度復習しないとダメそうです．
---
試験にしっかり臨んで，それから復習をして下さい．
-
おやすみなさい
---
おつかれさまです．試験準備ですか？
-
海外はどちらへ行かれるのですか？
---
ドイツです．ドイツにはほぼ毎年行ってます．
-
最近感動したことはありますか
---
感動したこととは違うのかもしれませんが，最近『テキサスの五人の仲間』という古い映画をDVDで見たのですが，とても面白かったです．予備知識なしで鑑賞することをお薦めします．
-
同じ確率の話でも，これまでのものとは毛色がかなり異なる印象を受けた．多少知ってる話題だったこともあり面白かった．
---
そうですね．マルコフ連鎖は独特な雰囲気を持っていますね．ただ，その中でも条件つき確率のような基本的な概念がちゃんと登場しているので，今までの内容やその中で培った慣れも使ってるということをお忘れなく．
-
今日の内容は面白かったです！線形代数の復習をしたいのですが，なかなか時間がとれないので，春休みにはなんとか取り組みたいと思います．
---
線形代数自体は1年生のときに扱う内容なのですけど，その後，いろんな講義や実験で頻繁に使うようになってきたので，もう一度振り返って復習してみると，1年生のときにはあまり理解できなかった内容も理解できるようになると思います．復習することはとてもよいので，お薦めします．
- 1/13 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
- コメントありがとうございます．中間試験の採点は終わりました．講評などご覧ください．
-
いろいろといそがしいです
---
お疲れ様です．いそがしいと自分に思わせていると，本当にいそがしくなるので，あまりいそがしいと思わないようにしていた方が，楽になるかもしれません．
-
3連休はずっと外でバイトしてました．体調悪いです．
---
お疲れ様です．内で3日間バイトするよりは健康的だと思いますよ．
-
春休みが待ち遠しいです．
---
そうですね．あと1か月ぐらいですね．
-
課題につかれるとオブジェのことを考えてしまいます。(輪郭の断片など)。先生は学内にある様々なオブジェについてどうお考えでしょうか。
---
私は案外，ああいうの好きです．冷遇されていたりすると悲しくなります．韓国にPOSTECHという大学があって，ときどき訪問してたのですが，そこには，アインシュタインやニュートンの胸像 (他にもあったかも) の近くに胸像のない台座が置かれていました．その台座をよく見ると「ここには君の胸像が置かれることになる」というような意味のことばが書いてあって，なんか面白いな，と思いました．
-
今日の授業は人生で得をしそうな内容で楽しかったです．
---
ぜひ，人生の中で活かしていって下さい．確率にまつわる話は直感的でないことも多いので，いろいろと勉強しておくと役立つことが多いと思います．
-
だんだん難しくなってきました．何を確率変数にしたり，同値変形したりなど慣れない…．
---
そうですね．慣れが必要ですね．標示確率変数はとても重要な道具なので，しっかりと身につけて下さい．
-
上限や下限を考える際の不等式の変形のセンスを磨きたいです．
---
個人的な見解を述べます．おそらく高校まで，そして大学1年の前半までの数学は「等号による変形」が多かったと思うのです．これはいわゆる計算です．しかし，その後，数値解析も含めて，学年が進んでくると「不等号による変形」が多くなってきていると思います．この2つは大きく違うと思っています．誤解を恐れずいえば，「等号による変形」は闇雲にやってできてしまうかもしれませんが，「不等号による変形」は目標を定めてそこに向かっていくという気持ちでやらないとうまくいかなかったりします．「何かが起きる確率が小さいことを証明する」というのはまさに不等号による変形が必要なので，その点が難しく感じる理由なのかもしれません．
-
不等式は自由度が高いので説明なしだと理解できそうにないし，正しいかも分からなくなりそう．意図を読み取る力を付けたいと思った．
---
そうですね．不等号による変形は，なぜそれが成り立つのかという論理をしっかりと考える必要があるので，考えながら1つ1つの不等号が成り立つことを確かめていって下さい．講義の中ではさらっと済ませているかもしれないので，しっかりとメモをとって，後で確認して下さい．
- 1/6 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
- コメントありがとうございます．中間試験の採点はまだ終わっていません．すみません．終了次第ご報告します．
-
明けましておめでとうございます．授業も残り3回ですが，今後もよろしくお願いします．
---
はい，こちらこそよろしくお願いします．
-
明けましておめでとうございます．中間試験の結果が恐いです．
---
採点が終了次第ご報告します．少々お待ちください．
-
明けましておめでとうございます．割とたるんでしまっていますが頑張っていきたいと思います．話は変わりますがTwitter上で「プリクラ問題」というもので盛り上がっていて結構面白い内容だったので，周りにも考えて欲しい問題です．
---
これがプリクラ問題ですね．いわゆるcombinatorial design theory (組合せデザイン理論) の問題で，一般的な最適構成は未解決なはずです．この辺りに文献情報とSageによる実装があります．ぜひ考えて下さい．
-
確率的問題と聞いてイメージしてたほどややこしくなかった印象．計算は十分ややこしいが，数え上げ等とやり方は似ているように感じた．
---
そうですね，数え上げのときと考え方は非常に似ていますね．
-
乱数でクイックソートを使う必要はあるのですか？
---
この質問には2つの内容があると思います．(1) 「クイックソートに乱数を使う必要はあるのか？」という問い．回答：必要はありませんが，使うと実装が簡単にできます．ソーティングを$O(n \log n)$回の比較で行おうとしたとき，クイックソートによってそれを行うためには，ピボット選択法を工夫する必要があります．乱数を使わないピボット選択法で$O(n \log n)$回の比較しか行わないものもありますが，少々ややこしいです．それに比べて，乱数を使う方法は非常に設計が簡単なのです．(2) 「そもそもソーティングに乱数を使ったクイックソートを使う必要があるのか？」という問い．回答：必要はありませんが，使ってもよいです．ソーティングのためのアルゴリズムはたくさんありますが，それぞれ長所と短所があります．クイックソートの長所が生きる場面ではクイックソートを使えばよいと思います．
-
どこから$3 \frac{\ln n}{\ln \ln n}$が降って湧いてきたのか私，気になります．
---
$\frac{\ln n}{\ln \ln n}$に比例するオーダーが重要な役割を果たしそうだ，ということはシミュレーションをすれば分かるかもしれません．そのような当たりをつけた後，実際に数学的な解析を行うときには，それがうまくいくように「3」という定数を見つけてあげればよいです．
-
大学院進学について悩んでいます．
---
進路については十分に悩んでください．具体的な悩みがありましたら，私でも相談にのれますので，私の部屋までお越し下さい．
-
正月は何をしていましたか？ 自分は食べてばかりでした．
---
1月から始まった実験第4ラウンドの準備をずっとしていました．それをしながら，年を越しました．
- 12/9 (9) 離散確率論：確率的離散システムの解析
- コメントありがとうございます．やり残した分は年明けになりますので，資料などは忘れずに持ってきてください．来週は中間試験です．
-
今朝はお客様トラブルで電車が遅延し，9時に間に合うことができませんでした．師走ということもあり，来週が心配です．
---
そうだったんですね．心配ですね．
-
20分早く出て，10分遅刻したので，確かに年末の魔物はいそうです．(JRと京王線のW遅延)
---
年末は人の心が動きやすいですからね．どうにか切り抜けたいものです．
-
インフルエンザが流行ってますね．
---
季節ものなので，これも注意しないといけませんね．寒い時期に入試とかあるのは，あまりよくないと思うのですけど，こればかりは文化の一部なので仕方ないですね．
-
授業に出ている人の人数が少なくてさびしいです．
---
少ないことを活用した講義づくりにした方がいいかもしれないので，アイディアがあったら，よろしくお願いします．
-
中間試験がんばります。
---
はい，しっかりと準備をしてきてください．
-
中間テストが恐いです．(とりあえず準備を頑張ります．) よかったら何か励ましの言葉を頂けませんか．
---
終わったら，楽しい冬期休業があると思って下さい．
- 12/2 (8) 離散確率論：確率の復習と確率不等式
- コメントありがとうございます．いよいよ後半に入りました．後半も楽しい内容ですので，ご期待ください．
-
$A$と$B$がかさなっていても$A$と$B$が排反であることがありえるというのがよくわからなかったです．
---
具体的な例を出します．$\Omega=\{1,2,3\}$で$\Pr(1)=\Pr(2)=1/2, \Pr(3)=0$だとします．そして，$A=\{1,3\}, B=\{2,3\}$のとき，$\Pr(A\cap B)=\Pr(\{3\})=0$なので，$A$と$B$は排反になります．
-
確率はやってるうちに訳が分からなくなるので苦手です．
---
おそらく，高校までの確率は厳密に計算することが多くて，数え上げを正確にやる必要があり，大変だったと思います．しかし，この講義の確率は割とざっくりとやる場合が多いので，それほど難しくないはずです．(ただし，期待値は正確に計算することが多いです．)
-
今回は確率統計などの復習分が多く，配属でいっぱいの頭でも理解できた．確率変数の存在をイマイチわかっていなかったので，そのあたりを確認できてよかった．
---
確率変数は重要な概念なので，しっかりと身につけていきましょう．
-
遅刻してしまいましたが，序盤は復習だったので安心しました．あと，サイコロ振りお疲れ様です．
---
プログラムでサイコロ振ってるので，そんなに疲れてないです ;-)
-
目がくぼんでいるタイプのサイコロは『5の目』が出やすいってトリビアでやってました。
---
そのようですね．その一方で，とても正確なサイコロもあって，とても高価なのだそうです．
-
つかれた
---
お疲れ様でした．
-
もう12月ですね．
---
私は走りません．
-
先生の人気投票が始まりましたね。
---
別に人気投票ではないと思いますが，しっかりと自分自身の決断は行って下さい．
- 11/25 (7) 離散代数：対称性を考慮した数え上げ
- コメントありがとうございます．次回からまた新しい内容になりますので，ご期待ください．
-
ネックレスの問題は数珠順列で検算できて楽ですね
---
ネックレスの問題は数珠順列というよりは円順列と呼ばれているようです．そして，円順列というときは，同じ色の石を複数使わないことになっているようです．その点に関して，授業で扱った問題そのものは円順列とは違う，ということになります．
-
やはり前提の部分があまり身についておらず，今回の話がイマイチ飲み込めなかった．四面体の話で0°回転を4回数えたあたりで既にわかっていない．
---
4回数えていたのは，おそらく頂点の軌道のことだと思います．1つの頂点が回転によってどこにうつることができるのか，というものを追ったとき，自分自身以外に3か所にしかいけない，ということなので，自分自身を含めて4か所，つまり4回，となるわけです．よく分からなかったら，直接質問を下さい．1つずつ解決していきましょう．
-
コタツでヌクヌク
---
学生のとき，コタツでカップラーメンを食べていて，こぼしてしまい，掛布団，敷布団とも大変なことになり，それ以来コタツは使わないことにしています．
-
最近，コーヒーを飲み過ぎて，カフェインの効果が半減してきたような気がします．
---
そういうの，あると思います．ただ，ヨーロッパの人と話すと，コーヒーは眠気を覚ます効果より，消化を助ける効果の方を大きく主張されます．本当かどうか分からないのですが，私自身は食後にコーヒーを飲むと，なぜだか消化がよくなる気がします．
-
調布祭お疲れ様でした．研究室の説明会とその後の懇親会にも行かせていただきました．雰囲気を間近に感じられて良かった一方であの珍味を口にするとは思いませんでしたのでびっくりでした．
---
こちらこそありがとうございました．珍味は今年だけ特別です ;-) ちなみに去年は別の特別なものを出して，それを今年は仕入れられなかったのであれになったのです．
-
調布祭にはしゃぎすぎて，気付いたら課題が大変なことになっていました．なんとか頑張ります．
---
はしゃぎすぎる，というところまでいく機会はあまりないので，いいのではないでしょうか．課題は頑張って下さい．
-
今年は12月24日から冬期休業が始まるとのことで大学に来るという予定がなくなり空虚なような複雑な気分です．自由な時間を有効に使うコツなどあれば教えて下さい．
---
休みのときにしっかりと充電するというのも重要かと思います．私にとって，ここ数年の冬休みを思い出すと，雑誌の記事を書いたり，本を書いたり，ということを主にしている気がします．今年は，とりあえず3つぐらい旅行にいきます．旅行先で何をするかはあまり決めてません．
- 11/18 (6) 離散代数：部分群と軌道
- コメントありがとうございます．今回は最後かけ足になってしまったので，次回はその部分の補足から入ります．(しかし，今回のスライドは使いません．次回のスライドの中で補足します．)
-
立体の1点を固定して$|\text{Stab}_G(x)|$を求めるという操作がよく分からなかった
---
次回，もう一度補足をします．
-
中学校時代から立体は苦手です．何が何だか分からなくなります…
---
こういうものは，実際に物理的な実体に手を触れていると，だんだん分かるようになってくるものなのだそうです．
-
これの$e^{-1}$はなんででてきた？
---
スライドにあるとおり，$aH$から$bH$への写像$f$を$f(x)=ba^{-1}x$と定義するので，図に描いてある状況では，$b=a$, $a=e$なので，$ae^{-1}x$と書いてあるわけです．実際$e^{-1}=e$なので，書く必要はないのですが，対応を明確にするために書きました．
-
今回の内容も面白かったです
---
ありがとうございます．次回で群の話は最後になります．
-
群の話は比較的面白く感じられる，が，次回分がややこしくなりそうで少し怖い
---
私の個人的な感覚で言いますが，離散数学をやりだして，だいたいのことはわかっても，同値関係と同値類がつまづきやすいポイントの1つになっていると思います．今回の内容はそれらが出てきたので，少し難しく感じられたと思います．しかし，同値関係や同値類というのはとても重要で便利な道具なので，今後もよく出てくると思います．
-
今回の内容はとても興味深かったです！同値関係復習しておきます…
---
同値関係はやはり難しいですね．集合に対して「割る」という操作を行うところに直感が働くようになると，かなり慣れてきたという感覚が出てくると思います．
-
クリスマスが忙しいということが果たして充実しているということにイコールでつながるのかどうか，疑問ですがどう思われますか．
---
「忙しい」ということばがポジティブな意味合いとネガティブな意味合いの両方を兼ね備えているのだと思います．ポジティブな意味で使えば，それが「充実している」ということにつながるのは自然だと思いますが，ネガティブな意味ならば，あまり「充実している」ということにつながらないと思います．
-
そろそろ1限にも慣れてきました．月曜の1限も終わるのでもう少し楽な生活ができそうです．
---
大学や会社によっては，8:30に始まるというところもあるので，9:00で苦しいといってるのはあまりよくないかもしれません．朝に慣れていく必要がありそうですね．
-
最近，財布の札の減るスピードがめちゃくちゃ早いような気がします．
---
クレジットカードを使えば，物理的に減ってはいかないのですが，それでも何かが減ることには変わりないですね．
-
講義中，板書を書くのに追いつけなくて説明が聞けないというお話がありましたが，私も全く同じことで悩んでいました．(そのせいで講義中に内容を十分に理解しきれないことが多いのです．) 長らく，単なる自分の理解か集中力不足のせいだと思っていましたが，先生も同じことを感じた経験があると聞いてちょっとほっとしました．
---
ほっとしてもらえてよかったです．こういうものには，いわゆる「正解」がないので，どちらが正しいともいえなくて，それよりは相性の問題だと思っています．
- 11/11 (5) 離散代数：群と対称性
- コメントありがとうございます．次回は今日の続きからやります．
-
いつから暖房が解禁されるのでしょう…寒い．
---
暖房運転期間は11/17から始まるようです．
-
小田急永山のトイレにこもっていたせいで，群の基礎を聞き逃してとても辛いです
---
お大事に．基礎部分については復習して下さい．
-
追加問題5.12，イマイチ理解できませんでした．
---
授業でいっていたヒントを繰り返します．まず単位元がなんであるか特定しましょう．そして，各要素の逆元が何であるか特定して下さい．それでかなり埋まるので，あとはしらみつぶしに調べていけばできると思います．
-
クリスマスにご予定はありますか？
---
24日は学科の会議があります．25日はおそらく温泉にいきます．
-
第3回の残っていた演習問題をすっかり忘れていました…来週提出しても見ていただけますか？
---
見る保証はありませんが，提出者が著しく少ないので，おそらく見れます．
-
回転・鏡映は状態遷移図を思い出しました．
---
そうですね．実際，群論とオートマトンの話は密接に関連していて，オートマティック群という概念も提唱されています．
-
パズルはニガテです．
---
離散数学は割とパズルのような側面が強いですね．ぜひ慣れていって，パズルも得意になって下さい．
- 11/4 (4) 数え上げの基礎：漸化式の解き方 (発展)
- コメントありがとうございます．次回から「離散代数」の内容になります．
-
$\displaystyle \sum_{i=0}^{\infty}\sum_{n=i}^{\infty} = \sum_{n=0}^{\infty}\sum_{i=0}^{n}$の変形がイマイチ理解出来ませんでした．最初から$\infty$にいくかどうかの違い？
---
「最初から$\infty$にいくかどうかの違い」ではないと思います．講義で描いた図をここでも描いてもう一度説明します．
和の計算において，足すことを考えている$i$と$n$の組を$(n,i)$座標平面の点として表しています．ここで，$\displaystyle \sum_{i=0}^{\infty}\sum_{n=i}^{\infty}$は左側のように，まず，$i$を固定して，その後で，$n$を$i$から$\infty$まで動かしています．「$n$を$i$から$\infty$まで動かす」というのを赤い線で表しています．一方，$\displaystyle \sum_{n=0}^{\infty}\sum_{i=0}^{n}$は右側ののように，まず，$n$を固定して，その後で，$i$を$0$から$n$まで動かしています．「$i$を$0$から$n$まで動かす」というのを青い線で表しています．
-
母関数の使い方も強力っぽいこともなんとなくわかったが，使いこなせる気がしない．計算怖い．
---
そうですね．そのため，コンピュータを使って母関数を扱うことが多いです．例えば，gfunのようなソフトウェアがあります．
-
HP上の10/28の資料が消えている気がします．
---
すみません，編集したときに変なことをして消してしまったみたいです．復活させました．
-
組合せ的解釈は2つだけでてんやわんやだったのに，リチャードさんは207個も考えて，すごいですね
---
リチャードさん自身が207個考えたわけではなく，「207個集めた」というのが正しいのだと思います．それにしても207個はすごいですね．
-
岡本先生，つかれてない程度にがんばってください
---
ありがとうございます．おそらく，まだそんなにつかれてないです．
-
空はあんなに青いのに…．
---
「スイミン不足」ですか？
-
朝から頭を回しました．今日はよく寝ることができそうです．
---
私もよく寝ることができそうです ;-)
-
ずいぶん寒くなってきましたね．空気が冷たいと景色がいつもより鮮やかな気がします．いまの時期は特に落ち葉の色が美しくて好きです．
---
風邪をひきやすい季節になってきましたので，体調には注意して下さい．
- 10/28 (3) 数え上げの基礎：漸化式の解き方 (基礎)
- コメントありがとうございます．今日はなんかすみませんでした．
- 演習問題2.8が間違っていたので訂正しましたが，演習問題3.6はそのままにしておきます． (訂正された演習問題2.8に対応する演習問題は次回出します．)
-
授業プリントをできればJEDで印刷したいのですが，前日の3,4限は3年生の実験があるのでやりにくいです．お昼までにwebにアップロードしていただくことはできないでしょうか．
---
可能な限り努力します．ただ，すみませんが，そうできると確約はできません．3年生は実験をやっていますが，空いているPCもあるので，そこを利用して印刷して下さい．
-
最近寒くなってきました．冬も近いです．
---
そうですね．朝方が辛くなってきますが，毎年のことなので慣れていきましょう．
-
昨日の夜はもの凄く寒かった…もう冬だ．
---
そうですね．季節の変わり目なので，体調管理には十分気を付けて下さい．
-
寝不足はお互い様のようです…．
---
失礼しました．
-
もう少し寝た方がいいと思います．
---
ありがとうございます．
-
おつかれさまでした
---
ありがとうございます．
-
先生の調子は今日良かったみたいですが，僕は眠かったです．どうも先生の体調と僕の体調は反比例してるみたいです．
---
私の調子は後半にいくにつれてだんだん下がっていったので，皆さんの調子が上がったことになりますね．それはそれでよかったです．
-
スライド15/39．$\begin{vmatrix}\lambda-1&-1\\-1&\lambda\\\end{vmatrix}$では？特に影響はないが．色々とお疲れ様です．
---
ありがとうございます．その通りです．修正しました．
-
復習問題2.1では「$a_n=$頂点数$n$の道$P_n$における独立集合の数」と定義されていますが，この説明だけで授業中の例の問題の条件を表せるのでしょうか．
---
「頂点数$n$の道」というのはグラフ理論においてよく出てくる一般的な用語なので，それを認めれば，授業中の例の問題を過不足なく表していることになります．
-
$\lambda^n$でおきかえたりベクトルをつかったり色々あって難しいです．
---
演習問題を通じて，身につけていって下さい．
-
数学のいろんな定理や問題に対する解法を学ぶのは楽しいのですが，しばらく触れない期間があると忘れてしまうのがとても悲しいです…論理的に答案を組み立てたり，問題について切り口を探したりするベースの力は昔より上がってきたと思うのですが，忘れてしまうことが多すぎて，あまり「身についた」感覚がないのです．今後数学を学んでいくにあたって何かアドバイスを頂けないでしょうか．
---
数学を道具として使う，という立場だと思うのですが，その場合，まずは「忘れてしまってもよい」と割り切った方がよいと思います．ただ，細かいことは忘れてしまっても，そのような道具があったということは覚えておく必要があります．それは自分の中で整理をしなくてはならない部分です．知識の体系化ですね．それができていれば，忘れてしまったものを思い出しやすくなると思います．数学に限りませんが，大学の講義というのは，道具箱に入れる道具を提供するものだと思います．その道具の手入れをして，磨き上げるのは皆さん自身ですし，道具箱に仕切りやポケットをつけて，道具を取り出しやすくするのも皆さん自身なのだと思います．
-
きざみ幅を小さくすると直角三角形の斜辺ABとその他の2辺の和AC+BCが等しくなる
という疑問が正しいかどうか分からずよく眠れませんでした．斜辺ABが滑らかな線かどうかが重要だと思うのですが…
---
私の解釈によれば，「曲線の長さ」の定義に基づいて近似を行っていないため，そういうことが起きるのではないかと思います．例えば，$\{a/n \mid a \in \{0,1,\dots,n\}\}$という集合 (数直線上で，$0$と$1$の間に$n+1$個の点を等間隔で並べたもの) は$n$を無限大に持っていくと閉区間$[0,1]$になりますが (実数のディオファントス近似)，任意の固定した$n$に対して，この集合の「長さ」は$0$であるのに対して，閉区間$[0,1]$の「長さ」は$1$です．集合として近づいていくことと長さが近づいていくことは全く異なるわけです．「長さ」や「面積」というのは，より一般に「測度」と呼ばれる数学的概念なのですが，このように人間の直感に合わない部分があるため，注意が必要です．
-
おつかれさまです．数列の母関数の本を前によみました．行列の計算は難しいです．
---
次回のテーマが，その「母関数」になります．お楽しみに．
- 10/21 (2) 数え上げの基礎：漸化式の立て方
- コメントありがとうございます．履修登録者がやたらと少ないですが，その分，濃い指導ができると思いますので，できる限り活かしていって下さい．
-
朝の授業は寝起きだと頭が全く働かないことがわかりました
---
ラジオ体操をしましょう．
-
1限から数学は辛いです…
---
休憩のときにストレッチとかするといいかもしれません．
-
数学つらいので履修取り消ししたくなってきました．三限あたりにあればよかった (>o<)
---
私にとっては2限が一番やりやすいのですけど，時間割編成上，そうできなかったので，1限になってます．ご了承下さい．
-
朝早いのに元気ですね．
---
テンションを高めるために，朝から準備をしてます ;-)
-
人が少なくてさびしいです
---
そうですね．でも，それだけ濃い指導が受けられると思って，活かしてください．
-
人少なくて楽しいです．
---
少ないことが楽しめるのはとてもいいですね．質問できる機会も多いので，そちらも楽しんでください．
-
今更ですが演習問題は再提出時にまだ未着手の問題を新たに解いたときは添削されるのでしょうか？
---
その場合は添削されません．ただし，はじめに提出するとき，未完成でもどこまで考えて，どの点で詰まったか教えてもらえれば，ヒントが出せるので，そのヒントをもとにして再提出して下さい．その場合は添削されます．
-
組合せ論的解釈がなかなか考えられないです．
---
慣れるまで難しいかもしれませんが，そのように解釈できるということが組合せ論の面白さの1つだと思います．次々回には，組合せ論的解釈の極限とも言えるものが登場する予定です．
-
中学受験でフィボナッチ数列が出てくることがあるので，バイトでこの前教えたのですが，あまりうまく説明できなくて申し訳なく思ったことを思い出しました．(旗上げ (赤・白) の総数を，旗の数に応じて数える問題でした．赤の下に白は来てはいけないというルールで，今回の「道」の独立集合と似た雰囲気の問題です．)
---
「赤の下に赤は来てはいけない」が正しいでしょうか？ フィボナッチ数列はとても重要な対象なので，いろんなところにでてきますね．
-
昨日格安のタイ料理屋に行って来ました．めちゃくちゃおいしかったです．
---
大昔ですが，タイ料理屋ではじめてカエルを食べました．それ以来食べてないのですが，また食べてみたいです．
- 10/7 (1) 数え上げの基礎：二項係数と二項定理
-
過去問や過去の講義ページなどはありますか．
---
今年から始まった講義なので，ありません．
-
1限ツライです…．頑張ります．
---
私もツラいです．お互い頑張りましょう．
-
講義が1限で大変ですが頑張ります．
---
はい，お互い頑張りましょう．
-
すごく眠いです．学校に仮眠室が欲しい．
---
大学院生はだいたい研究室で仮眠してます．
-
来週の体育祭，出ますか？
---
他の大学で講義をするので，出ません．
-
いい復習になりました．
---
数回は復習のような内容が続きますが，突然難しくなるかもしれないので気を付けて下さい．
-
いきなりガッツリ数学だった．個人的に代数系が楽しみ．
---
代数系が3回しかなくて，本当はもっとしっかりやりたいのですけども，時間は限られているので仕方ないです．
-
問題が多くて大変そうですが，その分離散数学についてしっかり学べそうだと感じました．
---
実を言うと，普通の数学の教科書にはもっとたくさん問題が載っているので，それに比べれば厳選してあると思って下さい．(実際，厳選しています．)
-
がんばって演習問題をやって，提出しようと思います．
---
はい，ぜひ提出して下さい．
-
グラフとネットワークが面白かったので，この講義もとることにしました．半年間よろしくお願いします．
---
はい，こちらこそよろしくお願いします．
-
グラフとネットワークから引き続き履修を考えて講義に参加しました．宜しくお願いします．実験でも岡本先生の実験に参加しますが，台風で手鼻くじかれた感じがあり大変そうです．
---
はい，よろしくお願いします．台風はまた来そうなので，ちょっと困りますね．
-
グラフとネットワークの講義で離散数学に興味が出たのですが，今回は一限で頭も回らない上に履修者も少なそうなので迷ってしまいます．今日の講義でお話しして下さったこと以外にこの講義を履修しなくなってしまうような魅力やお言葉がありましたら，ぜひ教えてください．
---
「履修しなくなってしまうような」であってますか？ 勝手に「履修してしまうような」に変えて答えます．魅力は「離散数学の幅広さと奥深さを感じられるところ」です．『グラフとネットワーク』のときと同じように，できるだけモデル化や応用例を紹介する予定で，そこから幅広さを感じられたらいいな，と思っています．また，確率論や代数系はちょっと込み入った数学になってくるわけですが，道具として使えるようになると，とても役立つので，「離散数学を使う」という立場で，そのような数学を扱っていきます．また，履修者が少なければ少ないほど，指導は密にできるようになるので，それは得をしていると感じて下さい．
-
組合せと組み合わせ，気を付けます．
---
あまり知られていないことだと思うので，気を付けて下さい．
-
数学はキライです
---
私のことはキライになっても，数学のことはキライにならないで下さい．
-
最初に説明された定理が衝撃的でした．一見確率が同じように見えて確率が違うという事象はゲームとかにとても応用できると思いました．
---
そうですね．そのように直感とずれたことをうまく利用したパズルがいくつかあったりします．この講義の他の箇所でも，パズルやゲームが何回か出てくることになると思います．
-
モンティ・ホールは番組名です
---
調べてみたところ，司会者の名前のようです．失礼しました．
-
変更した場合，最初に引いたものがヤギなら車が，車ならヤギが当たるとなるので，2/3の確率でヤギを引いてきているのだから，変更すれば2/3の確率で当たることになる．面白いと思います．
---
そうですね．これは授業の中で「条件付き確率」の応用例として後の方でもう一度ちゃんと扱います．
試験・成績
- 全体の成績
- 成績 = min{100, 中間試験の素点+期末試験の素点}の小数点以下切り上げ
- 入学年・学科によって，「離散数理工学」の成績が「シミュレーション理工学第二」の成績として報告されている場合があります．注意して下さい．
- 受講者数 (履修登録者数) は20で，90点以上 (S) が3人 (約15%)，90点未満80点以上 (A) が5人 (約25%)，80点未満70点以上 (B) が2人 (約10%)，70点未満60点以上 (C) が4人 (約20%)，60点未満 (D) が6人 (約30%) です．
- 中間試験と期末試験の少なくとも一方を受験した受講者数は14で，90点以上 (S) が3人 (約21%)，90点未満80点以上 (A) が5人 (約36%)，80点未満70点以上 (B) が2人 (約14%)，70点未満60点以上 (C) が4人 (約29%)，60点未満 (D) が0人 (約0%) です．
- 中間試験と期末試験の両方を受験した受講者数は14で，90点以上 (S) が3人 (約21%)，90点未満80点以上 (A) が5人 (約36%)，80点未満70点以上 (B) が2人 (約14%)，70点未満60点以上 (C) が4人 (約29%)，60点未満 (D) が0人 (約0%) です．
- 試験を受けた人は，全員単位が取得できています．しっかり勉強して臨んでいただけたのだと思います．1学期間，ありがとうございました．
- 期末試験 (2月17日実施)
- 期末試験問題
- 採点：1問15点満点，合計60点満点
- 得点分布
- 受験者数は14で，平均点は44.61 (60点満点)．45点以上 (S相当) が8人，45点未満40点以上 (A相当) が1人，40点未満35点以上 (B相当) が2人，35点未満30点以上 (C相当) が2人，30点未満 (D相当) が1人です．
- 得点掲示 (辞書順に並べています)
| (・8・) | 36 |
| 04503 | 37.5 |
| 12121 | 24 |
| 25252 | 40 |
| abcba | 51.5 |
| abdcbc | 47 |
| Daijiro | 57 |
| helpme. | 31 |
| htbm | 57.5 |
| log365 | 58 |
| mofny | 46 |
| rooty | 32 |
| ZBa35 | 52.5 |
| るかぽん☆ | 54.5 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：平均点がやたら高いのですが，採点していた体感上，あまりできている感じはしませんでした．部分点を出しやすくしたため，平均点が高くなったものと思われます．
- 問題1：条件つき期待値に関する証明問題．定義通りにやろうとすれば，シグマが2つでてきて，その順番を入れ替える，という方針で証明できます．$X$ と $Y$ は確率変数であり，事象ではないので注意して下さい．そのため，$\Pr(X \mid Y=i)$ といった表現は意味を成しません．$X$ と $Y$ が独立であると仮定して証明を進めている答案もありましたが，独立性は必要ありません．
- 問題2：チェルノフ上界の技法を使う問題．演習問題9.8と同じ問題．案外，小問1ができていなくて衝撃を受けました．$X=i$ となる確率を求めて，期待値の定義に基づいて計算をすることは非常に難しいです．講義でやったように標示確率変数を使うとすぐにできます．小問3で式変形や計算間違いをしている答案がありますが，軽く減点しています．
- 問題3：ランダムウォークの到達時刻の期待値の計算．演習問題13.3と同じ問題で，講義でも扱ったものです．よくできていました．できていない人の答案は，どう解いたら良いのかという方針すらよく見えていないようなので，復習をして下さい．
- 問題4：乱択アルゴリズムの計算量解析．これは講義でやった例 (クイックソート) や演習問題にあったものよりも簡単なアルゴリズムなのですが，あまりできていませんでした．小問3で漸化式を解くところがあまりできていなかったのも残念です．式変形をして2項間漸化式が得られれば，そこからすぐに解答が得られます．
- 中間試験 (12月16日実施)
- 中間試験問題
- 採点：1問15点満点，合計60点満点
- 得点分布
- 受験者数は14で，平均点は38.75 (60点満点)．45点以上 (S相当) が4人，45点未満40点以上 (A相当) が1人，40点未満35点以上 (B相当) が4人，35点未満30点以上 (C相当) が2人，30点未満 (D相当) が3人です．
- 得点掲示 (辞書順に並べています)
| 04503 |
31.5 |
| 10y75 |
17 |
| 25252 |
47 |
| acdcbc |
39 |
| Daijiro |
54 |
| helpme. |
37 |
| kelkom |
29 |
| log365 |
60 |
| np125 |
44 |
| rooty |
36.5 |
| るかぽん☆ |
50.5 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：全体的に，できている問題とできていない問題のムラがあったように思います．準備の仕方にムラがあったのではないかと感じました．
- 問題1：再帰アルゴリズムの計算量に対する漸化式を導出する問題．演習問題2.9と同じ問題．できている人は完璧にできていて，できていない人は全然できていませんでした．時間が足りなかったのではないか，と見られる解答もいくつかありました．演習問題として出てきていた問題なので，この問題はしっかり解答してもらいたかったです．
- 問題2：母関数を用いて，数列の一般項を導出する問題．部分分数分解が案外できていなかったので，復習をしておいて下さい．母関数自体は$A(x)=-\frac{7x+1}{2x^2+x-1}$なのですが，この分母$2x^2+x-1$の根が$-1, 1/2$だからといって，$A(x)=\frac{a}{x+1}+\frac{b}{x-1/2}$と部分分数分解をしようとすると，混乱する可能性があります．実際，この式の右辺を通分すると，$A(x)=\frac{(a+b)x-a/2+b}{x^2+x/2-1/2}$となるので，元の式$A(x) = -\frac{7x+1}{2x^2+x-1}$と分母が異なります．分母を同じにするため，通分したあとの分母と分子に2をかけて，$A(x)=\frac{2(a+b)x-a+2b}{2x^2+x-1}$とすれば，間違いなかったと思います．注意して下さい．
- 問題3：コーシー・フロベニウスの定理を用いて対称性を考慮した数え上げを行う問題．これは難しかったようで，一般の$n$に対して正しく解答できている答案は2つしかありませんでした．最終的な解答があっていても，そこに至る道筋が (コーシー・フロベニウスの定理を使っても使っていなくても) 間違っている場合，点はありません．$n=3,4,5$の場合が正しく解答できている答案は10点にしています．($n=2$の場合を答えている答案もありましたが，それには点がつきません．)
- 問題4：どちらも有限群に関する証明問題．
- 問題4A：演習問題5.9と同じ問題．二面体群が非可換であること．$n$に関する帰納法で証明しようとしている答案がありました．残念ながら間違いです．要点を説明します．$D_n$が非可換であると仮定して，$D_{n+1}$が非可換であることを証明しようとします．そのために「$D_n$の要素がどれも$D_{n+1}$の要素である」ということを理由にします．しかし，これでは理由として不十分なのです．なぜならば，$D_n$における演算結果と$D_{n+1}$における演算結果は一致しないからです．もし$D_n$が$D_{n+1}$の部分群であるならば，この論法は正しいのですが，実際そうではないので，正しくないわけです．
- 問題4B：演習問題6.6と同じ問題．固定部分群が実際に部分群であることを証明する問題．授業でやったように，$a,b$が固定部分群の要素であるとき，$a^{-1}b$が固定部分群の要素であることを証明してもよいですし，部分群の定義に基づいて証明してもよいです．授業でやった問題だったからかもしれませんが，4Bを選んだ答案の方が4Aを選んだ答案よりも多かったです．
公式シラバス
こちらをご覧ください
履修上の注意
『離散数理工学』は，『シミュレーション理工学第二』(情報・通信工学科：新)，『有限要素法』(情報工学科：旧昼) の読替科目です．
これらを履修した人 (つまり，単位取得した人) は『離散数理工学』を履修できません．
スケジュール
- 10/7 (1) 数え上げの基礎：二項係数と二項定理
- 10/14 休講 (体育祭)
- 10/21 (2) 数え上げの基礎：漸化式の立て方
- 10/28 (3) 数え上げの基礎：漸化式の解き方 (基礎)
- 11/4 (4) 数え上げの基礎：漸化式の解き方 (発展)
- 11/11 (5) 離散代数：群と対称性
- 11/18 (6) 離散代数：部分群と軌道
- 11/25 (7) 離散代数：対称性を考慮した数え上げ
- 12/2 (8) 離散確率論：確率の復習と確率不等式
- 12/9 (9) 離散確率論：確率的離散システムの解析
- 12/16 中間試験
- 1/6 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
- 1/13 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
- 1/20 (12) 離散確率論：マルコフ連鎖 (基礎)
- 1/27 休講 (海外出張)
- 2/3 (13) 離散確率論：マルコフ連鎖 (発展)
- 2/17？ 期末試験
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
