離散数理工学
電気通信大学情報理工学域I類 (情報系)
2019年度後学期
火曜1限 (9:00-10:30)
教室：西9-115
岡本 吉央
ショートカット：
講義資料 |
コメント |
試験・成績 |
公式シラバス |
スケジュール |
参考書 |
過去の講義
講義資料
新たに掲載したとき，つぶやきます
- 1/28 (14) 離散確率論：マルコフ連鎖 (発展)
- 1/21 (13) 離散確率論：マルコフ連鎖 (基礎)
- 1/14 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
- 1/7 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
- 12/17 (10) 離散確率論：確率的離散システムの解析 (発展)
- 12/3 (9) 離散確率論：確率的離散システムの解析 (基礎)
- 11/26 (8) 離散代数：有限群の構造 (続き)
- 11/19 (7) 離散代数：有限群の構造
- 11/12 (6) 離散代数：有限群
-
スライド (11/12修正) |
印刷用スライド (11/12修正) |
演習問題 |
用語集
- 前回の続きからやります
- 演習問題6.4, 6.9, 6.10, 6.11は次回に持ち越し
- 11/5 (5) 離散代数：図形とグラフの対称性
- 10/29 (4) 数え上げの基礎：漸化式の解き方 (発展)
- 10/15 (3) 数え上げの基礎：漸化式の解き方 (基礎)
- 10/8 (2) 数え上げの基礎：漸化式の立て方
- 10/1 (1) 数え上げの基礎 (1)：二項係数と二項定理
コメント
- 1/28 (14) 離散確率論：マルコフ連鎖 (発展)
- コメントありがとうございました．期末試験は2月18日です．しっかりと準備をしてきてください．
-
半年間お世話になりました。非常にわかりやすい講義ありがとうございました。
---
こちらこそありがとうございました．
-
お世話になりました
---
こちらこそありがとうございました．
-
半年間ありがとうございました．とても楽しい講義でした．
---
こちらこそありがとうございました．
-
特になし
---
はい，期末試験はしっかりと準備して臨んで下さい．
-
スライドp. 10で緑のギャンブラーの所持金が0万円になっているのに、終了せず所持金が増えていますがこれは......？
---
すみません，プログラムのバグですね (-_-;
見つけていただいて，ありがとうございます．緑の隣りの濃いグレーも0から増えてますね．
-
ランダムウォーク．(不謹慎ですが) ご年配の方が列車の踏切に立ち入って亡くなる事故を連想してしまいました。
---
私は不謹慎だとは思いませんが，そのようなことを考えるのは重要だと思います．例えば，高齢化が進むと徘徊高齢者が増加する可能性があり，いろいろなところで「日常に潜む危険」が顕在化するかもしれません．そのときに，シミュレーションや数学で問題解決を行なおうとする場合，徘徊高齢者を数理モデル化する必要があり，ランダムウォークは第0近似になると思います．
- 1/21 (13) 離散確率論：マルコフ連鎖 (基礎)
- コメントありがとうございます．次回が最終回となります．
-
いつもありがとうございます。
---
こちらこそありがとうございます．
-
特になし
---
ありがとうございます．質問がありましたら，ぜひお願いします．
-
今日は久々に寝坊をしてしまい、心が痛いです。
---
「心が痛む」というのは「すまないと思う」という意味ですが，私にすまないと思う必要はないです．学生が寝坊をしても，私は損をしないからです．
-
1/4，「いち，よんぶんの」とか言いながら書くこともあります．
---
私が「1/4」を「1」から書き始めるのは，もう1つ理由があります．それは私が3年ぐらいヨーロッパで暮らしていたからです．だいたい英語を使って生活していましたが，「1/4」は「one over four」とか「one quarter」と読みます．(インド英語では「one by four」と読むようで，それもよく聞きました．) その語順に従って書くと，どうしても「1」から書き始めることになります．皆さんは混乱しないようにご注意ください．
-
関数「f(x)」を「エフエックス」と読むのも正しいかどうかあやしい気がします．
---
なかなかややこしい問題です．関数は本来「f」であって，「f(x)」は「関数fのxにおける値」だからです．しかし，「関数f(x)」と呼ぶことはよくあります．これは，関数の引数を一緒に書くことで，関数の引数の数を明確にしたいときや，関数の引数として使う記号を明確にしたいときに使う便法です．ただ，私自身は，この便法を使うのはやめたほうがよいと思っています．紛らわしいからです．
-
配属希望であった研究室への配属が叶わなかったことを理由に休学しようか迷っています。(大学院では学部時代とは少し毛色の異なる学問分野を研究しようと計画していて、どうしても学部時代で配属して研究したいと考えているのです) ただ、周囲からは「就職面で不利になるのではないか」とあまり歓迎されておらず、先生の意見をいただきたいです。
--- ご自身で決めるべきことだと思いますが，私から言えることは2点ほどあります．
(1) 休学して何をするのか，ということが明確でなければ，休学することに意味はあまりないと思います．「配属希望であった研究室への配属が叶わなかったこと」が理由であるとするなら，休学して何をするのか，という疑問に対する回答は「休学して配属希望であった研究室への配属を叶える」ということでしょうか．その研究室が来年度存在するかどうかすら分からないのに，また，存在したとしても，配属を叶えられるかどうかは不確実なのに，「休学して配属希望であった研究室への配属を叶える」というのは本当にやりたいことなのか，問い直す必要はあると思います．再度叶わなかったらどうするのでしょうか．例えば，その研究室が来年度以降存在しないのだったら，何年休学してもその希望は叶いません．自分がコントロールできない未来を，自分でコントロールできるように考えている感じがします．
別の言い方をすれば，休学するのだったら，その意味をしっかりと考える必要があると思います．意味のある休学生活を送って下さい．自分の将来において何を重要だと思うのか，ということをちゃんと考えないといけないと思います．
また，休学は学生支援担任が認めなければ可能ではない，ということもご注意ください．
(2) 研究について，です．学問の自由があるのです．まず，研究室に配属されなくても研究はできます．皆さんは，今この瞬間に研究をすればよいのです．誰もそれを禁じませんし，禁じることはできません．研究室に所属しなくても研究はできますし，ある研究室で指導を仰がなければ研究ができない，と信じているならば，電通大で公式に薦められている研究室訪問／短期滞在という活動を活用すればよいのです．あるいは，GLTPでは，半年早く卒業研究の配属が行われます．また，こういう公式な活動ではなく，非公式に研究をしてもよいと思います．例として適切かどうか分かりませんが，例えば，私は，大学院生 (修士課程) のときに，自分の所属する研究室以外の研究室のゼミによく出たりしてました (発表もしてました)．なぜか，その研究室の忘年会の幹事をすることもありましたが．とにかく，研究とか学問というのは，そういうものだと思います．研究活動というものを狭くとらえすぎない方がよいと思います．
そういう感じで，自立した研究をしたいけど，お金がない，という場合は，お金を獲得する必要があるかもしれません．学生がお金を獲得する術は，探せば案外あります．情報系で有名なものは未踏事業です．お金があれば，自分の考えている研究を自分のやりたいように進めることができるのではないでしょうか．
- 1/14 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
- コメントありがとうございます．
-
ありがとうございました。
---
こちらこそありがとうございます．
-
いつも分かりやすい説明ありがとうございます。
---
こちらこそありがとうございます．
-
講義も残り少ないので集中してのぞみたいです。
---
はい，よろしくお願いします．(^^)
-
留年中にしたほうがいいことって何かありますか？
---
自分のことを自分で決め，自分で責任を持てるようになると，よいと思います．
-
今回の講義ではモンテカルロ法で確率を見積もりましたが この方法を応用すれば ミラー-ラビン素数判定法が偽陽性と判定してしまう (真の) 確率と $p$ とのずれが $\varepsilon$ 以上になる確率の上限が見積もれそうだと直感的に考えてました。
---
ミラー-ラビン素数判定法も間違いを出力する可能性のある乱択アルゴリズムですね．ぜひ考えてみて下さい．
-
$\log_{3/4}\delta$ が $\displaystyle O\left(\log \frac{1}{\delta}\right)$ になるのがよくわからなかったです．$\displaystyle \left(\frac{3}{4}\right)^k = \delta$ なら $\displaystyle \left(\frac{4}{3}\right)^k = \frac{1}{\delta}$ だから 底 を1以上に変換すると $\displaystyle O\left(\log \frac{1}{\delta}\right)$ になるというイメージでしょうか？
---
そのイメージで正しいと思います．授業でちゃんと説明しなかったので，ここで説明します．
$\displaystyle \log_{3/4}\delta = \frac{\log_{4/3}\delta}{\log_{4/3}(3/4)} = \frac{\log_{4/3}\delta}{-1}= -\log_{4/3}\delta = \log_{4/3}\frac{1}{\delta}$ なので，$\displaystyle \log_{3/4}\delta = O\left(\log\frac{1}{\delta}\right)$ になります．
- 1/7 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
- コメントありがとうございます．
-
あけましておめでとうございます
---
あけましておめでとうございます
-
あけましておめでとうございます。今年もどうぞよろしくお願いします。
---
こちらこそよろしくお願いします．
-
今年もよろしくお願いします。
---
こちらこそよろしくお願いします．
-
あけましておめでとうございます。今年もよろしくお願いします。
---
こちらこそよろしくお願いします．
-
授業のはじめで、岡本先生が板書で授業をなされていたのが珍しく感じられました (普段はスライドが主だと思ってます)。
---
そうせざるをえなかったので，そうしました．
折角の機会なので，板書に関する私見を言っておきます．
私は「板書で授業を行ってよいのは，教科書が指定されているときに限る」と思っています．そうでない場合，板書で行われる授業は，ほぼ理解不能になります．よく「板書の授業は，スピードが遅くなって，理解しやすい」という意見を聞くのですが，私はそう思いません．むしろ，私が行う場合は，板書の授業の方がせわしくなります．私が行う場合だけではなく，私が受講した授業でも，板書の授業はせわしなく感じました．
理由はいくつか考えられます．まず，最も重要であると思うのは，板書で授業を行うという行為自体がとても難しいからです．これは相当な技能を必要とします．シロウトには薦められませんが，鍛える価値のある技能でもあります．字の大きさやキレイさ，に始まり，黒板のマネジメント，何を書き何を書かないでおくか，何を消し何を残しておくか，色の使い方，黒板に対して講師の立つ位置の決め方，など，気にしなくてはならないことは山ほどあります．それらを意識的に遂行できる講師と遂行できない講師では，大きな違いがあります．しかも，1回の授業でやるべき分量は決まっているわけです．
他に思い当たる理由は，学生の視点から「黒板に書かれたことを写しとる」という行為が極めて難しいことにあります．特に，講師が自分の立つ位置や書くスピードに無関心である場合，学生の書き写している内容が講師の話している内容からかなり遅れてしまう，ということが起きます．この場合，講義を理解することはほぼ無理です．また，転記ミスは必ず起きます (これは通信，つまり，コミュニケーションの基礎)．
板書派の意見として「板書を写していると，眠くなくなる」というものがあります．私は，これに対して懐疑的です．というのは，私自身が大学生のときに，板書の授業でもよく寝ていたからです．
また，電通大に限定することを言いますが，電通大の教室の黒板は小さすぎます．A棟であっても，です．この黒板では，板書で授業をする気になれません．
私自身は，スライドと板書を併用して授業を行うようにしています．板書を併用するのは，授業にメリハリをつけるためです．授業にはある程度のダイナミズムが必要です．そのため，西9号館のスクリーンの配置はとても困ります．黒板を使いにくいからです．西2号館のスクリーンは黒板の端に配置されていて，これは素晴らしいです．そのような配置に西9号館も変えられるとよいのですが．
さて，それで，板書の授業のこのような欠点を補えるのは，教科書 (あるいはそれに代わる資料) の存在しかありません．しっかりとした教科書があれば，板書の授業が細部を端折っていたり，途中で理解不能な部分が出てきたり，黒板の内容を書き写しきれなかったりしても，教科書を見ることで，補えます．
-
フィールズ賞を受賞した小平邦彦さんは「日本語は数学を研究する上で有利である」と仰っていたそうですが，岡本先生はどう思われますか？
---
私見を問われているので，私見を述べます．
私にとって，日本語で数学を行うのはとても難しいです．というのは，日本語で論理的な文章を作ったり，日本語を論理的に運用することがとても難しいと思っているからです．
例えば，「$X$ は実数の集合であると仮定する」というような，数学でよくありそうな文を考えます．しかし，この文はあいまいです．この文を英語で考えたとき，「We assume that $X$ is a set of real numbers.」と訳すか「We assume that $X$ is the set of real numbers.」と訳すか，迷います．そして，この2つの英文の意味は大きく異なります．
皆さんは長いこと英語を勉強していると思いますが，英語を勉強することの意義として大きなことの1つは，「英語を通して日本語を理解する」ことです．もちろん英語が使えるようになることは重要な目標ですが，それと同時に，日本語も使えるようにならないと困るわけです．よく「英語がうまくならない」と悩む人がいますが，私の考えでは，そのような場合，たいてい，その人は日本語もうまくないのではないかと思います (もちろん，根拠があって言ってるわけではないので，妄想です)．
日本語を論理的に運用できる人にとって，「日本語が数学を研究する上で有利である」という境地に到達することは可能かもしれません．しかし，私はその境地に到達していると言えないです．私はいまだに日本語を勉強して，うまく使えるようになろうと努力しています．そのような境地に到達することを目標としているわけではありませんが，そのような考えを私にも理解できる日が来るかもしれません．
- 12/17 (10) 離散確率論：確率的離散システムの解析 (発展)
- コメントありがとうございます．年明けは1/7が最初の講義になります．
-
来年もよろしくお願いします。
---
こちらこそよろしくお願いします．
-
Pr(事象Eが起こる) は Pr[事象が起こる] と表記してもいいのでしょうか？ (私の受けた確率論の講義では後者でした)
---
普通は「Pr(.)」と書くと思いますが，「Pr[.]」でも通じるとは思います．なお，「Pr{.}」という記法も見た事があります．
補足します．期待値を「E[.]」と書いていますが，なぜかというと，期待値は汎関数 (関数の関数) だからです．それは，ラプラス変換を「$\mathcal{L}[.]$」と書くのと同様です．その一方で，確率は汎関数であると見なさないのが普通なので，Pr(.)と書くのが普通だと思います．
-
$1+x \leq \mathrm{e}^x$ って便利だなと思いました。
---
この不等式は本当に有用です．使いこなせるようになって下さい．
-
朝眠くてなかなか起きれません。朝スムーズに起きることが出来るコスをご存知ですか？よろしければ教えて下さい。
---
「コス」じゃなくて「コツ」だと思うので，そのつもりで回答します．
私自身は早く眠るようにしています．あと，明るいと目が覚めやすいので，すぐに照明をつけるようにしています．
-
研究室配属で岡本研への配属が叶わず，かねてから携わりたいと考えていた最適化の研究ができなくなってしまい，勉強に力が入らなくなってしまっています。よろしければ，配属においてどのような点が配属の決め手にならなかったのかメールでお尋ねできればと考えています。いかがでしょうか？
---
匿名のコメントなので，メールではお返しできないため，ここで簡単にお答えします．
まず，岡本研へ配属されなくても最適化の研究はできるので，その点は誤解しないで下さい．(一方，岡本研で最適化をやっている人は半分ぐらいです．)
次に，どのような点が配属の決め手にならなかったのか，という点は答えづらいです．なぜかというと，これは私の目から見た比較だからです．そういうことなので，「アホな岡本には見る目がなかった」と思っておくとよいと思います．
それで，もし「岡本研でないと困る」というお考えで，大学院に進学することを考えている場合は，大学院で岡本研を志望することを考えればよいのではないでしょうか．自分にやりたいことがあるならば，別の研究室や別の大学院に進むというのは，当然のことだと思います．一般に，大学院の方が学生の「枠」は大きいです．
-
特になし
---
了解です，質問がありましたら，ぜひよろしくお願いします．
- 12/3 (9) 離散確率論：確率的離散システムの解析 (基礎)
- コメントありがとうございます．12/10は中間試験です．しっかりと準備して臨んで下さい．
-
眠いです 眠むい
---
「眠い」が正しいようです．
-
今日、駅乗り過ごしてしまいました．テストの日じゃなくてよかった...
---
そうですね．ご注意ください．
-
中間試験頑張ります。
---
はい，しっかりと準備をしてきてください．
-
説明が分かりやすく，ありがたいです
---
こちらこそありがとうございます．分からない所が出てきたら，質問をよろしくお願いします．
-
確率の話で理解があやふやな所がいくつかあったので、確率についての参考書を見直そうと思います．
---
この講義で必要な部分は復習資料にまとめていますので，そちらもご覧ください．
-
確率の勉強をしているときに調和数のようなものが出てくるのは面白いと思った
---
調和数は離散確率論でよく出てきます．オーダー $\log n$ で増加する数列の代表例です．
-
$X \geq 2\mathsf{E}[X]$ から $2^X \geq 2^{2\mathsf{E}[X]}$ が成り立つのは分かりますが，$\Pr( X \geq 2\mathsf{E}[X]) = \Pr(2^X \geq 2^{2\mathsf{E}[X]})$ が成り立つのが分かりません．
---
質問ありがとうございます．
2つの命題 $A$ と $B$ が同値であれば (つまり，$A \Leftrightarrow B$ であれば)，$\Pr(A) = \Pr(B)$ となります．なぜなら，$A$ が起きるとき，必ず $B$ も起き，$B$ が起きるとき，必ず $A$ が起きるからです．
ここで，$X \geq 2\mathsf{E}[X] \Leftrightarrow 2^X \geq 2^{2\mathsf{E}[X]}$ なので，$\Pr(X \geq 2\mathsf{E}[X]) = \Pr(2^X \geq 2^{2\mathsf{E}[X]})$ となります．
-
ゲームのガチャで，$n$ 種類のキャラのうち1つが当たるとして キャラ $i$ の当たる確率が $p_i$ ($p_1+\cdots + p_n = 1$) として，全種類の景品を集め切るまでに引くガチャの回数の期待値を見積もるの面白そうです．
---
クーポン収集問題の一般形ですね．ぜひ考えてみて下さい．
最終形だけ知りたい場合は，Flajolet, Gardy, Thimonierの論文を見て下さい．
- 11/26 (8) 離散代数：有限群の構造 (続き)
- コメントありがとうございます．これで「離散代数」は終了となります．来週から「離散確率論」の内容に入ります．
-
ありがとうございました．
---
こちらこそありがとうございました．
-
今日は眠気と戦いながら講義を受けていました。
---
しっかりと寝てきてください．;-)
-
今朝，朝が寒い季節になったなあと思いました
---
そうですね．風邪をひかないようにご注意ください．
-
冬の雨は外出たくなくなります．
---
その気持ち，わかります :-)
-
中間試験に向けて、理解の不足している分野を解消したいです
---
はい，しっかりと準備をしてきてください．
-
群についての問題は難しいと感じたので試験のためにも用語や定義を復習しておく．
---
数え上げもあることを忘れないで下さいね．
-
今日は印刷用スライドを印刷してこれなかったのですが、それのせいか授業がとても難しく感じました．
---
うまく上げられていなかったみたいです．すみませんでした．
-
$f(r)=21534, f(s)=21543$ となるのは元の図形を考えると納得できる結果で面白かった。
---
そうですね．元の図形に戻って同型写像を解釈し直す，というところまで授業で触れたかったのですが，時間が足りなさそうだったので断念しました．皆さんは，自分で確認してみて下さい．
- 11/19 (7) 離散代数：有限群の構造
- コメントありがとうございます．次回は，今回残ったところから始めます．
-
二項関係をまったく覚えていなかった。
---
覚えていなくてもよいので，忘れてしまったときに調べ直して，思い出して下さい．
-
理解できていない用語があるととたんに話しについていけなくなるので確実に覚えていきたい。
---
覚える必要はないので，忘れたときに調べて思い出せるようにして下さい．
-
ありがとうございました．
---
こちらこそありがとうございました．
-
「同型写像 $f\colon G\to G'$，部分群 $H\subseteq G$ に対して $f(H)$ は $G'$ の部分群」の証明は，部分群の定義である3つの条件を確かめる方法の方がすっきりしているように感じました．
---
確かに，その方が見通しはよいと思います．ただ，その証明だと1ページに収まらなさそうです．
提案していただいた方法でも，$f(x^{-1}) = f(x)^{-1}$ という等式が必要になると思うので，いずれにせよ，$f(x^{-1}) = f(x)^{-1}$ が正しいことは確認して下さい．
-
$H_1 = g_1 H$，$H_2 = g_2 H$ と表記するときの $g_1 H, g_2 H$ の扱いがよくわかりません．
演習で閉じていることの証明に部分集合の積の性質を用いてましたが
$H_1 H_2 = (g_1 H)(g_2 H) \stackrel{\text{この変形}}{=} g_1 (Hg_2) H$
$g_1 H$について $H$ は $G$ の部分集合ですが $g_1$ は $G$ の部分集合でなく 1つの要素なのではないでしょうか？ ($g_1 \in G$ であって $g_1 \subseteq G$ でないということ)
そう考えると集合でない $g_1$ や $g_2$ に部分集合の積の性質を利用できるのかわからなくなりました．
---
この部分は今回到達しなかったので，次の講義で説明しますが，せっかく質問をいただいたので，ここでも回答します．
質問の内容はごもっともです．この部分は説明していないことがあり，それは，$g_1 H$ と $\{g_1\} H$ は同じ集合を表す，ということです．そのため，$g_1 H$ と書くときに，それは $\{g_1\} H$ であると見なすこともあります．指摘して頂いた変形では，この見なし方を用いていると思って下さい．
-
今日は離散数理工学が始まる時間に起きてしまいました．
---
私も今朝は起きるべき時刻に起きることができず，少し焦りました．;-)
- 11/12 (6) 離散代数：有限群
- コメントありがとうございます．時間の管理がうまくできなくてすみません．次回は，今回残ったところから始めます．
-
[TAコメント] TAは西4号館202室にて，火曜日午後 (19時まで) に在室していますので 聞きづらい質問等ありましたら，この時間をご利用ください．
---
とのことです．よろしくお願いします．
-
分かりやすい授業でした。
---
ありがとうございます．分からないところがでてきたら，ぜひ質問をして下さい．
-
今朝はとても寒いですね
---
サムイ島は暑いそうです．
-
群の話は苦手です。
---
苦手なことができるようにならないと勉強にならないので，ぜひ勉強して，苦手を克服して下さい (^^)
-
6.7を解いてみたが難しかった。
---
この問題は得意な人と苦手な人に分かれるようです．群であるという性質をうまく使ってみて下さい．
-
アーベリアンの話を聞いてラプラシアンやヤコビアンを思い出しました．
---
人名から数学用語や物理学用語ができることは割とありますが，それほど多いわけではありません．形容詞になった数学者として，京大の山下先生がまとめていらっしゃいます．「Sasakian」が光って見えますね ;-)
- 11/5 (5) 離散代数：図形とグラフの対称性
- コメントありがとうございます．次回は，今回残ったところから始めます．
-
今朝は思った以上にとても寒かったので もう1枚着てくれば...と後悔しています
---
寒くなってきましたね．体調管理に気をつけて下さい．
-
ありがとうございました。
---
こちらこそありがとうございました．
-
特になし
---
はい，「特になし」でもよいので，この紙を出し続けて下さい．何かありましたら，ぜひ書いて下さい．
-
2年生前期に現代数学入門Bを受けていたので、今回の内容で群について簡単に復習できてよかったです。
---
実は『現代数学入門B』と内容が重なっていることは分かっているので，毎年，『離散数理工学』の内容も見直して，調整しています．来年度はもう群をやらないかもしれないです．
-
現代数学Bで同じ内容を学んだのですが、群とかわけわからんで終わりました．
---
「わけわからん」で終わってしまうのは悲しいので，何か身につけて下さい ;-)
-
今日の内容は現代数学入門Bで似たようなことをやったので，自分にとっては慣れていた．
---
何度も復習することは重要かもしれないので，演習問題を通して理解を確認して下さい．
-
図形の回転・鏡映によって生まれる配置ですが、ある頂点とその点に隣接する頂点の位置ですべての配置が求められたりしますか？
たとえば、下のような正四面体について、○の頂点の位置4通り
●の頂点の位置3通り
すべての配置は4×3=12通り
---
回転のみを考える場合はそれでよいです．鏡映も考える場合は，もう1つの頂点の位置も指定する必要があります．
-
記号：r, s
規則：r6=1, s2=1, rsrs=1
のところを
規則：r6=1, s2=1, rsr=s
にしても良いのですか？
---
はい，そのように書いてもよいです．しかし，あまり広く受け入れられないかもしれません．
-
鏡映の理解が難かしい
---
頭の中で図形を変換しようとしても，想像が追いつかないことがあります．そういう場合は，実際に模型を使ったり，絵を描いてみたりして，イメージを膨らませて下さい．
-
正六角形の回転と鏡映により群をなすことができるのはとても興味深いです。。
---
そうですね．図形の回転と鏡映は，群の例としてよくでてきます．
-
図形の操作が記号で表されるとわかりやすく感じた。
---
「記号で表されるとわかりやすく感じる」というのは，抽象的な考え方に慣れてきているという証拠だと思います．数学の考え方が身についている感じがしますね :-)
-
同値類とか全単射などなつかしい言葉がでてきたなと思いました。
---
なつかしいと感じられることはいいですね．復習してみて下さい．
- 10/29 (4) 数え上げの基礎：漸化式の解き方 (発展)
- コメントありがとうございます．「数え上げの基礎」は今回で終わり，次回からは「離散代数」になります．
-
フーリエ変換ってなんだっけと思ったので復習しときます。
---
この『離散数理工学』の講義では，意図的に，他の講義で習った (かもしれない) 内容を登場させています．それは，いろいろな講義の内容が有機的に結びつくことで，私たちが暮らしている世界や社会ができていることを感じるためです．ぜひ，復習を励行して下さい．
-
例えば試験で例題1の
\[
a_n = \begin{cases}
1 & (n=0)\\
4a_{n-1} - 3^{n-1} & (n\geq 1)\\
\end{cases}
\]
の一般項を求めよと言われたときに、母関数などの授業で習った知識を用いず $a_n = 3^n$ と予想してから帰納法でそれを証明しても点になりますか？
---
そのように問われた場合は「点になります」が私の回答です．ただし，演習問題にあるように，「母関数を用いる方法によって」と書いてある場合は，点にならないか，減点になります．
-
母関数は便利だと思った。
---
そうですね．ぜひマスターして下さい．
-
母関数を使った解き方がシンプルで感動しました．
---
いろいろな方法を使えると，いろいろな視点から問題を見ることができるようになりますね．
-
母関数を使って漸化式で表された数列の一般項を求めると方法，非常にエレガントで汎用的で感動しました．まるで新しい武器を手に入れたかのようで，「ねんがんの ぼかんすうを てにいれたぞ！」って感じました (某ゲームの台詞)
---
そう かんけいないね ;-)
-
母関数は数列の漸化式の一般項を求めるだけでなく，様々な内容を含んでいそうで興味を持ちました．
---
まさに様々な内容を含んでいます．例えば，前回の講義で紹介したような上界を求める方法は母関数と複素関数論を用いることで，より一般的に，そして組織的に扱えるようになります．また，母関数を用いて最適化を行う手法があります．後者については，参考書のところにある『離散体積計算による組合せ数学入門』という本でも軽く触れられています．
-
$a_0$ を仮定しても元の漸化式に影響が出てこないのかが気になりました。
---
影響が出ないように $a_0$ を定めているのが，講義で紹介した手法です．別の手法としては，添え字をずらす，というものがあります．例えば，
\[
a_n = \begin{cases}
2 & (n=1)\\
3 & (n=2)\\
a_{n-1}+a_{n-2} & (n\geq 3)\\
\end{cases}
\]
という漸化式で定義される数列 $\{a_n\}_{n\geq 1}$ に対して，$b_n = a_{n+1}$ (ただし，$n\geq 1$) とすると，数列 $\{b_n\}_{n\geq 0}$ は
\[
b_n = \begin{cases}
2 & (n=0)\\
3 & (n=1)\\
b_{n-1} + b_{n-2} & (n\geq 2)\\
\end{cases}
\]
という漸化式を満たします．ここから，$\{b_n\}_{n\geq 0}$ の一般項を導き，それを $a_n$ に戻す，という考え方も使えます．
-
寒いです．
---
季節の変り目ですね．体調には気をつけて下さい．
-
空気が一気に冷え込みましたね．私事で大変恐縮ですが、先日傘を電車内に置き忘れてしまい 登校時に雨に打たれてしまいました．もっと体調に気をつけないとダメですね．
---
お大事に．:-)
- 10/15 (3) 数え上げの基礎：漸化式の解き方 (基礎)
- コメントありがとうございます．来週は祝日なので，次回は再来週になり，今回残った部分から始めます．
-
わたしはいつも電車で通学しているのですが、本日は貧血による立ちくらみと吐き気で大学に来るのがやっとでした。昨日はお酒を一滴も飲んでいないのですが、こんなこともあるんだなぁと感じています。
---
ご自愛ください．私も貧血がひどかったときは，苦しかった思い出があります．
-
台風，調布では大きな被害がなさそうで安心しました。インフラが止まるのは怖いので…
---
その一方，日本各地では大きな被害が出たところもありますので，お見舞い申し上げたいと思います．
-
演習問題の分量が多く、なかなか解き切れなくて少し困っています。解く問題の優先順位を決める上でどんな基準があるか 先生の考えをお伺いしたいです。
---
個人個人の好みに依ると思います．まずは，パラパラとすべての問題を見てみて，例えば，復習問題はやらなくてもできそうだと思えば，復習問題はやらなくてもよいですし，復習問題の内容が理解できているか不安であれば，復習問題をやるとよいかもしれません．追加問題も，ぱっと見たときに，解法が思い浮かぶようであれば，やらなくてもよいかもしれないですし，それでも文章を書く練習としてやってみるという選択もあるかもしれません．時間は限られていますから，有効に使えるようにして下さい．
-
提出締切をすぎた場合、提出はしないほうがいいですか？
---
提出していただいてもよいですが，私は全く見ず，お返しすることになります．
-
行列が出てくるとは…
---
線形代数と確率・統計はどこでもでてきます．そのつもりで過ごして下さい
-
行列の復習 やっておきます．
---
線形代数はとても大事です．復習をお薦めします．
-
線形 まじめにやっとけばよかったです．
---
その気持ちは分かります．私も線形代数がよく分かっていないので，苦労しています．
-
漸化式の一般項を求めるということは高校数学でもよくやっていたことなので懐かしく感じた。
---
3項間漸化式は高校数学でやらない (学習指導要領に載っていない) と聞いたことがあるので，この授業では扱っています．
-
漸化式は解き方が多くて大変だった．
---
解き方が多い，ということは，様々な側面を持っているということです．それだけ，奥深く，重要な対象であるということだと思って下さい．
-
$a_n$ の漸化式を $a_n = \lambda^n$ とおく解き方はやりやすいけど $a_n = \lambda^n$ とおく発想が自分1人ではでないと昔から思ってました．
行列の方は考え方は理解しやすいけど、途中の式がとても複雑で計算ミスしそうです．
---
$a_n = \lambda^n$ とおく発想について，ちょっと補足します．
2項間線形漸化式で，定数項がないもの，つまり，$a_n = r a_{n-1}$ のように書ける漸化式は，等比数列の漸化式なので，$a_n = a_1 r^{n-1}$ と一般項が書けると分かります．$\lambda$ はこの公比 $r$ の役割を果たしていると思って下さい．実際，$a_n = r a_{n-1}$ に対して，$a_n = \lambda^n$ とおくと，$\lambda^n = r \lambda^{n-1}$ という式が得られて，つまり，$\lambda = r$ が分かります．講義で紹介した方法は，これを3項間線形漸化式でやってみたことになり，そこでは線形空間の考え方が活きています．
-
岡本先生は森毅先生をご存知ですか？ 私は森先生のエッセイが好きで，時々読みます．
---
お名前は存じ上げておりますが，存命中にお会いしたことはありません．
- 10/8 (2) 数え上げの基礎：漸化式の立て方
- コメントありがとうございます．
-
[TAコメント] 演習問題はぜひ相談しあってください．私でも1人では解けきれないものもありましたが，複数人で相談して新しい発見が出ることはしばしばあります．
---
ということですので，よろしくお願いします．
-
○
---
「快晴」ということでしょうか．
-
眠い
---
しっかりと寝て下さい．
-
起きれて良かったです。
---
それは良かったです ;-)
-
1限は起きるのがつらいですが、頑張って出席したいと思います。
---
はい，よろしくお願いします．
-
天井と天丼は書きまちがえないと思った。
---
案外書きまちがえます ;-)
-
特になし
---
はい，「特になし」で結構ですので，この紙を提出しつづけてください．
-
"台風19号危険"
---
この前の台風15号を超える勢力だとも言われているので，ご注意ください．
-
忙しい授業だなと思いました
---
ご指摘ありがとうございます．もう少し落ち着いてみるように努力します．:-)
-
組合わせ的解釈によってイメージがしやすかった。
---
そうですね．イメージを持つことは大事ですね．なお，「組合わせ」ではなく「組合せ」なので，ご注意ください．
-
多項式 $\displaystyle \sum_{k=0}^{n}\sum_{\ell=0}^{n}\binom{n}{k}\binom{n}{\ell}x^{k+\ell}$ の $x^n$ の係数を求める際，$k$ を $k=k_0$ に固定すると $\ell = n-k_0$ になることと $0 \leqq k_0 \leqq n$ から $\displaystyle \sum_{k_0=0}^{n} \binom{n}{k_0}\binom{n}{n-k_0}$ と求められる というように考えるのはいかがでしょうか？
---
ありがとうございます．よいと思います．
-
二項係数の二乗和がよく分からなかったです
---
説明が詰まってしまって，すみませんでした．どこが分からなかったか，直接お聞きください．
-
二項定理が複素数で成り立つのが面白いと思いました
---
そうですね．例えば，$n=2, x=i\sin\theta, y = \cos\theta$ とすると，$\displaystyle (\cos\theta + i\sin\theta)^2 = \sum_{k=0}^{2} \binom{n}{k} \cos^{2-k} \theta \cdot (i\sin\theta)^{k}$ という等式が得られます．ド・モアブルの定理から，この左辺は $\cos(2\theta) + i\sin(2\theta)$ に等しく，右辺の方は $\cos^{2}\theta + 2i \cos\theta\sin\theta - \sin^2\theta$ になります．この等式の実部から，$\cos(2\theta) = \cos^2\theta - \sin^2\theta$，虚部から，$\sin(2\theta) = 2\cos\theta\sin\theta$ という2倍角の公式が得られます．同じようにすれば，3倍角の公式などが得られます．
-
格子のマッチングの話はドキドキしました。
---
あんまりドキドキする要素はなかったと思うのですが ;-)
-
地道な数え上げが重要だと分かった。
---
そうですね．漸化式を自分で立てられるようになることが重要です．しっかりと身につけて下さい．
-
今日の講義で無向グラフが出てきましたが、多重グラフの場合には、辺集合Eを頂点集合Vの部分集合の集合としては定義できないと思います。多重グラフがどのように定義されているのか知りたいです．(Webで調べてもごまかしたようなものしか出てこなかったので．)
---
普通は「多重集合」をまず定義して，それを用いて多重グラフを定義します．しかし，多重集合を定義することは割と厄介です．よく使う方法では，写像を用いて多重集合を定義します．
-
研究室配属についてですが，去年の卒研配属のページで「重視する科目」の一つにこの科目の記載がありました。これの意味合いについて、「離散数理工学を履修した」という事実が重視されるのか、それとも講義に参加して講義内容を理解することが重視されるのか、お教えいただきたいです。
---
離散数理工学に限定して話をすると，履修登録をしたという事実が重視されます．なぜかというと，3年後学期の科目については「講義に参加して講義内容を理解すること」を測定する方法を私が持っていないからです (卒研配属第一フェーズは12月初旬で，この講義の中間試験は12月中旬)．
- 10/1 (1) 数え上げの基礎 (1)：二項係数と二項定理
- コメントありがとうございます．いただいたコメントとその回答は以下のように掲載されます．
-
10月なのに暑いですね
---
そうですね．もう少し涼しくなってほしいものです．
-
10月なのにまだ暖かいなと思う。
---
なかなか涼しくならないですね．
-
暑くはないけど思ったほど涼しくもない朝でした。
---
季節の変り目は体調を崩しやすいので，ご注意ください．
-
教室がカビ臭い
---
休み明けだったので，湿気がこもっていたのだと思います．これから改善されていくはずです．
-
ねむい
---
眠っていても良いです．音を立てなければ．;-)
-
1限つらい
---
慣れて下さい．:-)
-
夏休み明け初日の1限に来られて幸先が良い。
---
それはよかったです．
-
夏休みが終わってしまって悲しいです．また学校頑張ろうと思います．
---
よろしくお願いします．
-
今年一番の講義でした。岡本先生は1限の時間帯に眠気を感じることはありますでしょうか？
---
朝眠くなることはない気がします．午後に眠くなります．;-)
-
よろしくお願いします
---
こちらこそ，よろしくお願いします
-
起きれるか不安です
---
起きれるようになって下さい
-
ありがとうございました．
---
こちらこそありがとうございました．
-
半年間よろしくお願いします．
---
こちらこそよろしくお願いします．
-
特に無いです
---
はい，特に無くても，この紙を出してください．
-
特になし
---
はい，何かあったら，よろしくお願いします．
-
ありがとうございました．
---
こちらこそありがとうございます．
-
グラフとネットワークから引き続きよろしくお願いします
---
こちらこそよろしくお願いします．
-
お久しぶりな気がします。
---
お久しぶりね
-
授業面白くて好きなのですが，1限なので取って単位まで取れるか不安で悩んでます…
---
朝起きればよいのです ;-)
-
分かりやすいスライドでした
---
それはよかったです．今後も分かりやすくなるように努めます．
-
自分と同じ誕生日の人がいてびっくりしました．
---
自分と同じ誕生日の人がいる確率は割と低いので注意して下さい．「自分と同じ誕生日の人がいる確率」と「同じ誕生日の2人がいる確率」は明確に違うので，区別が必要です．
-
重複組合せについても，高校で習った 5H2 という表記よりもメジャーなものがあったりするのでしょうか？
---
重複組合せについて，aHbという表記は (高校数学以外で) 見たことがありません．重複組合せは，$\displaystyle \left(\!\!\! \binom{a}{b} \!\!\! \right)$ と書くことが多い気がします．例えば，Stanleyの『Enumerative Combinatorics Volume I』やWikipediaではこの記法が使われています．ただ，この記法もあまり広く使われているわけではないと思います．
-
資料がいっぱいあると思いました。
---
皆さんが普段みる必要のある資料は「印刷用スライド」と「演習問題」です．他のものは，皆さんの判断でお使いください．
-
参考書のアップデート．もし余力があればよろしくお願いします。
---
そうですね．下の方に「参考書」の項目を作ったので，そちらに追加していきます．
-
高校で習った内容でも復習すると割とすぐに証明できないものが多いと思った．
---
おそらく，高校ではあまり証明することに対する意識がなかったのかもしれません．今後は，証明しなくてはならないことがたくさんでてきますので，証明に対する意識を高めて，今まで当たり前だと思っていたことも，今一度証明し直してみるという態度も重要になるかもしれません．
-
証明問題多いと 手が痛くなります
---
ご自愛ください ;-)
-
例えばテストに復習問題1.1が出題されたとき，この解答に不等式 $1+x \leq \mathrm{e}^x$ ($\forall\ x \in \mathbb{R}$) を用いたい場合は，この不等式を既知のものとして使用してよいのか，授業内でこの不等式を証明していないので証明してからこの不等式を使用しなければならないのか，教えてください．
---
既知としてよいですが，それを使ったことは明示して下さい．
-
復習問題1.2の答えはスライドのような答え方でも十分ですか？
---
はい．正しければ，どんな方法でもよいです．
-
模範解答が欲しかった．
---
私たちは「模範解答」や「正解」というものが存在する世界に住んでいるわけではない，ということに気付く必要があります．世の中のほとんどの問題にはただ1つの正解というものがあるわけではありません，何か正解があると言っている人がいるなら，その人は騙そうとしているか，あるいは，大きな勘違いをしているか，どちらかだと思います．
私は，大学生時代に加藤尚武『現代倫理学入門』という本を読んで，とても感銘を受けました．この本では，いろいろな難問を取り扱っていますが，それに対して，「正解」や「模範解答」を見せるようなことはしません．そうではなく，その難問を先達がどのように考えてきたか，という道筋を見せてくれるのです．当時の私は，何も解答が示されないことに対する不満を持つと同時に，そこに問題解決の困難さと考えることの重要さを感じた，と記憶しています．
私も講義中にいろいろなことを証明しますが，そのとき1つの証明しか紹介しないことが多いと思います．それは時間が限られているため，そうなっているです．一方で，皆さんがどのように証明しようと，それは自由です．「模範解答」というものを提示することは，そのような自由を隠します．皆さんが私の思いつかないような証明を見つけることは十分にありえますし，そうであってほしいと願っています．(つまり，私は「模範」ではありえないのです．)
私たちが勉強と呼んでいるものは，知っているかどうかというクイズを延々と繰り返すことであってはいけません．とことん考える能力を養うことと，考えるための道具・材料を身につけることであるべきです．私の講義はそれを目指していますし，他の講義もそうであってほしいと思っています．
以上，私見です．反論は大いに受け付けます．反論できることは学問であることの証なのですから．
-
実験第二で岡本先生の実験テーマをとりたかったのですが，テーマが人気だったようで選考から漏れてしまいました。残念です。
---
それは私も残念です．(-_-;
-
確率論の復習してきます．
---
確率論は特に大事なので，積極的に復習して下さい．
-
昨年はこの離散数理工学の時期に体調をくずされたとうかがいました。どうかお体を大事になさってください。
---
ありがとうございます．
-
[TAコメント] 質問内容は，演習問題に限らず講義内容に対しても引き受けます．
---
ということですので，よろしくお願いします．
試験・成績
- 中間試験と期末試験により，成績の評価を行います．
- 成績 = min{100, 中間試験の素点+期末試験の素点} (小数点以下切り捨て)
- 得点分布 (中間試験と期末試験の一方でも受験した人に限る)
- 受講者数 (履修登録者数相当) は25で，
90点以上 (S) が4人 (約16%)，
90点未満80点以上 (A) が1人 (約4%)，
80点未満70点以上 (B) が3人 (約12%)，
70点未満60点以上 (C) が3人 (約12%)，
60点未満 (D) が14人 (約24%) です．
- 中間試験と期末試験の一方でも受験した人の総数は17で，
90点以上 (S) が4人 (約24%)，
90点未満80点以上 (A) が1人 (約6%)，
80点未満70点以上 (B) が3人 (約18%)，
70点未満60点以上 (C) が3人 (約18%)，
60点未満 (D) が6人 (約35%) です．
- 期末試験
- 日程：2月18日(火) 第1時限 (9:00-10:30)
- 教室：西9-115 (いつもの教室)
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 出題範囲：第9回講義の最初から第14回講義の最後まで
- 形式：
- 演習問題と同じ形式の問題を4題出題する
- その中の2題は演習問題として提示されたものと同一である
(ただし，「発展」として提示された演習問題は出題されない)
- 配点：1題15点満点，計60点満点 (0.5点刻み)
- 試験問題
- 得点分布
- 受験した人の数は13，平均点は41.5 (60点満点)．
45点以上 (S相当) が7人 (約54％)，
45点未満40点以上 (A相当) が0人 (約0％)，
40点未満35点以上 (B相当) が2人 (約15％)，
35点未満30点以上 (C相当) が1人 (約8％)，
30点未満 (D相当) が3人 (約23％) です．
- 得点掲示 (辞書順に並べています)
| 10234 | 23 |
| akxoz | 52.5 |
| asddf | 16 |
| BBHFGG | 60 |
| gsrta | 54 |
| mdkir | 37 |
| ndsu | 36.5 |
| qweee | 45 |
| RBASS | 32.5 |
| μ'sic | 47 |
| 研究室リセマラ | 58 |
| プププププ | 58 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：得点分布は平坦ですが，45点以上の人はよくできていたといえます．問題2のできが全体のできを決めている感じがしています．
- 問題1：チェルノフ上界の技法を適用する問題．演習問題にない問題．
平均点は11.5．
これはできた人とできない人の差が大きな問題でした．できた人はすんなりとできています．小問3は小問2の結果を使うとよいと思います．実際に $t$ として $\ln 3$ を選ぶとよいことが分かります．
- 問題2：ランダム・グラフに関する問題．演習問題と同じ問題．
平均点は7.1．
これはあまりできていませんでした．演習問題と同じ問題なので，準備をしてきてほしかったです．この問題はランダム・グラフが何であるか知っていれば，出題された4問中でもっとも簡単な問題のはずでした．その意味で，あまりできていないことは残念に思いました．
- 問題3：マルコフ連鎖の問題．演習問題と同じ問題．
平均点は11.7．
これはよく出来ていました．なぜ極限が存在するのか，という理由が明確に書かれていない場合は減点されてます．定常分布は確率分布なのですから，その成分和は必ず1になります．それが分かっていないのは勉強不足だと思いました．
- 問題4：乱択アルゴリズムに関する問題．演習問題にない問題．
平均点は11.2．
割とできていましたが，最後の小問3をどのように処理するか，というところで最終的な素点が分かれました．証明すべきことが書いてあるのですから，数学的帰納法を用いれば，簡単に証明できます．一方で，数列の一般項を求めようとした答案はどれも失敗しています．何を問われているのか冷静に考えれば，数列の一般項を求める必要がないことは分かるので，無駄な努力をしている印象を持ちました．(その意味で，ヒントは意地悪だったかもしれません．)
- 中間試験
- 日程：12月10日(火) 第1時限 (9:00-10:30)
- 教室：西9-115 (いつもの教室)
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 出題範囲：第1回講義の最初から第8回講義の最後まで
- 形式：
- 演習問題と同じ形式の問題を4題出題する
- その中の2題は演習問題として提示されたものと同一である
(ただし，「発展」として提示された演習問題は出題されない)
- 配点：1題15点満点，計60点満点 (0.5点刻み)
- 試験問題
- 得点分布
- 受験した人の数は17，平均点は35.8 (60点満点)．
45点以上 (S相当) が4人 (約24％)，
45点未満40点以上 (A相当) が3人 (約18％)，
40点未満35点以上 (B相当) が1人 (約6％)，
35点未満30点以上 (C相当) が2人 (約12％)，
30点未満 (D相当) が7人 (約41％) です．
- 得点掲示 (辞書順に並べています)
| 825681 | 22.5 |
| akxok | 18 |
| asdd8 | 47.5 |
| AtskS | 26.5 |
| DPNG | 44 |
| figit | 28 |
| FmtMs | 26 |
| ijadb. | 23 |
| mkdrr | 34 |
| ms116 | 21 |
| ndsu | 42 |
| RBASS | 32.5 |
| warbear | 59.5 |
| μ'sic | 38 |
| タヒ=タイ | 49.5 |
| プププププ | 55.5 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：もう少しできて欲しいと思いました．特に，問題3と問題4はあまりできていませんでした．得点分布も割と平坦なので，できている人とできていない人の差が大きかったと言えるとも思います．
- 問題1：漸化式を導出する問題．演習問題と同じ問題．
平均点は13.6．
これはよくできていました．n=1とn=2の場合もしっかりと記述して下さい．「明らか」と書くだけでは説明にならないので，注意して下さい．
- 問題2：漸化式を解く問題．演習問題にない問題．
平均点は7.2．
これはあまりできていませんでした．母関数を用いない解答が1通ありました (正しい一般項を導けていました)．母関数 $A(x)$ を $x$ の有理関数として表すとき，その式に $n$ が残っていてはいけません (し，正しく導けば残りません)．
- 問題3：群の同型性に関する問題．演習問題と同じ問題．
平均点は11.4．
できている人とできていない人の差が大きな問題でした．多くの人は小問1に正しく答えられていましたが，そうでない人もいました．小問2の答案によると，群の要素の位数というものが何であるか，理解できていない人が割といることが分かり，残念に思いました．
- 問題4：部分群に関する問題．演習問題にない問題．
平均点は3.6．
これはほとんどできていませんでした．何を証明しようとしているのか読み取れない答案が多かったです．こういうものは論理だてて考えることが重要です．論理だてて考えることができないと，日常生活でも苦労します．ちゃんと自らを鍛え直してください．部分群であることを証明するには，部分群の定義を使ってもよいですし，部分群であるための必要十分条件 (第7回講義スライドの8ページ目) を使ってもよいです．
公式シラバス
スケジュール (予定)
- 10/1 (1) 数え上げの基礎：二項係数と二項定理
- 10/8 (2) 数え上げの基礎：漸化式の立て方
- 10/15 (3) 数え上げの基礎：漸化式の解き方 (基礎)
- 10/22 休み (即位礼)
- 10/29 (4) 数え上げの基礎：漸化式の解き方 (発展)
- 11/5 (5) 離散代数：図形とグラフの対称性
- 11/12 (6) 離散代数：有限群
- 11/19 (7) 離散代数：有限群の構造
- 11/26 (8) 離散代数：グラフの対称性と有限群 有限群の構造 (続き)
- 12/3 (9) 離散確率論：確率的離散システムの解析 (基礎)
- 12/10 中間試験
- 12/17 (10) 離散確率論：確率的離散システムの解析 (発展)
- 12/24 冬期休業
- 12/31 冬期休業
- 1/7 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
- 1/14 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
- 1/21 (13) 離散確率論：マルコフ連鎖 (基礎)
- 1/28 (14) 離散確率論：マルコフ連鎖 (発展)
- 2/4 授業等調整日
- 2/11 休み (建国記念の日)
- 2/18 期末試験
参考書
徐々に追加していきます．
全般的な参考書
- J. マトウシェク，J. ネシェトリル (著)，根上生也，中本敦浩 (訳)，「離散数学への招待 (上・下)」，丸善出版，2002．
ただし，「離散代数」のことは書いてないです．
数え上げの基礎
- 浅野孝夫，「情報数学」，コロナ社，2009．
- 小島定吉，「離散構造」，朝倉書店，2013．
- 成嶋弘，「数え上げ組合せ論入門 (改訂版)」，日本評論社，2003．
- M. ベック，S. ロビンス (岡本吉央訳)，「離散体積計算による組合せ数学入門」，丸善出版，2010．
離散代数
- M. A. アームストロング (著)，佐藤信哉 (訳)，「対称性からの群論入門」，丸善出版，2012．
離散確率論
- 玉木久夫，「情報科学のための確率入門」，サイエンス社，2002．
- 伏見正則，「確率と確率過程」，朝倉書店，2004．
- J. マトウシェク，J. ネシェトリル (根上生也，中本敦浩訳)，「離散数学への招待 (下)」，丸善出版，2002．
- M. Mitzenmacher, E. Upfal (小柴健史，河内亮周訳)，
「確率と計算」，共立出版，2009．
過去の講義
注意：内容や説明法は毎年少しずつ変わっています
過去の試験問題
注意：内容や説明法，試験範囲は毎年変化しています．
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
