離散数理工学

岡本 吉央

ショートカット： 講義資料 | コメント | 試験・成績 | 公式シラバス | 履修上の注意 | スケジュール | 過去の講義

講義資料

• 2/7 (14) トピックス
  • スライド | 印刷用スライド (前半) 印刷用スライド (後半)
• 1/31 (13) 離散確率論：マルコフ連鎖 (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/24 (12) 離散確率論：マルコフ連鎖 (基礎)
  • スライド (1/30修正) | 印刷用スライド (1/30修正) | 演習問題 | 用語集
• 1/17 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/10 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 12/20 (9) 離散確率論：確率的離散システムの解析
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 12/6 (8) 離散確率論：確率の復習と確率不等式
  • スライド (12/6修正) | 印刷用スライド (12/6修正) | 演習問題 | 用語集
• 11/29 (7) 離散代数：有限群の応用
  • スライド (12/5修正) | 印刷用スライド (12/5修正) | 演習問題 (12/5修正) | 用語集
  • 前回の続きから行います
• 11/22 (6) 離散代数：有限群
  • スライド | 印刷用スライド | 演習問題 (12/6修正) | 用語集
  • 問題6.15にて，「群準同型写像」ではなく，正しくは「群同型写像」です．すみません．
  • 前回の補足と訂正から行います
• 11/15 (5) 離散代数：対称群と置換群
  • スライド (11/21修正) | 印刷用スライド (11/21修正) | 演習問題 | 用語集
• 11/1 (4) 数え上げの基礎：漸化式の解き方 (発展)
  • スライド (11/2修正) | 印刷用スライド (11/2修正) | 演習問題 (11/2修正) | 用語集
• 10/25 (3) 数え上げの基礎：漸化式の解き方 (基礎)
  • スライド (10/25修正) | 印刷用スライド (10/25修正) | 演習問題 | 用語集
• 10/18 (2) 数え上げの基礎：漸化式の立て方
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 10/4 (1) 数え上げの基礎：二項係数と二項定理
  • スライド | 印刷用スライド | 演習問題 | 用語集

• 2/7 (14) トピックス
  • コメントありがとうございました．最後までお付き合いいただきありがとうございました．来週は期末試験です．しっかりと準備をお願いします．
  • 半年間ありがとうございました．
    --- こちらこそありがとうございました．
  • 半年間授業，添削ありがとうございました．
    --- こちらこそありがとうございました．
  • 毎週とっても素敵な時間でした．もっと勉強したいです．ありがとうございました．
    --- こちらこそありがとうございました．
  • 後学期間ありがとうございました．
    --- こちらこそありがとうございました．
  • 半年間ありがとうございました．
    --- こちらこそありがとうございました．
  • 戦略SのSはSenryakuのS! 尾は白くないですけど面白かったです。
    --- SはStrategyのSです．
  • 定義だけではなく，実際の応用例が知れてよかったです．テスト頑張ります．
    --- 定義だけではイメージがつかみづらかったり，なぜそれを勉強しなくてはいけないのか分かりにくいと思うので，いろいろな例を通して理解できるようにしてみたつもりでいます．
  • テストがたくさん重なっていて非常につらいです．
    --- 私も辛いです．
  • Feel free to〜の対義語 ("これに挑戦するのはやめた方がいい"？) に相当するような言い回しはありますか？
    --- おだやかな言い方なら "I don't recommend it." とかでしょうか．
  • 囚人問題で、それぞれの囚人が箱をあけるたびに箱内の紙はシャッフルしないのですか．
    --- シャッフルしませんし，シャッフルすると，確率を高くすることはできなくなります．囚人の間の独立性を無くすことが重要なのですが，シャッフルしてしまうと，独立にならざるをえなくなります．
  • 100囚人の問題や帽子ゲームなど数学者は問題を作りそれを解決するのですね。今更ながら敬意を表します。
    --- そうですね．講義の中ではパズルやゲームとして紹介していますが，それを考えるきっかけとなったデータ構造や情報理論の話が背後にあったりします．そこまでは講義の中で踏み込めなかったのですが，いろいろな問題を考えて，それを単純化した先に，今回扱ったようなパズルがあるのだと思って下さい．
  • 
    --- そうではありません．:-)
  • 「後半はPowerPointで…」ということは普段は何でスライドを作っているのですか？
    --- 講義スライドはLaTeXのbeamerを使っています．研究用のプレゼンテーションは同じくLaTeXのbeamerかPowerPointを用途に分けて使っています．アニメーションをたくさんいれたい場合はPowerPointにしています．講義のスライドは資料としての意味もあり，数式をちゃんと書きたいのでLaTeXにしています．
• 1/31 (13) 離散確率論：マルコフ連鎖 (発展)
  • コメントありがとうございました．掲載が遅くなりすみません．
  • 来週の内容が楽しみです
    --- お楽しみに ;-)
  • 来週の内容面白そうです．
    --- ぜひお越しください．
  • 多分来週もでます
    --- よろしくお願いします．
  • "1/2¹⁰⁰ 〜 0.0………08" のインパクトがすごい
    --- このように0を並べてみると，どれほど小さいのかわかりますね．
  • (世の中様々な) 講義で例示されるようなモデルは名前や条件がかなり生々しいことが多い気がします．
    --- そうですね．ただ，そういう設定で考えていても，それは何かの比喩であって，それを道具としていろいろな現象をモデル化できる，というところも重要ですね．
  • 酔って居酒屋か家のどちらかにはたどり着けそうなので，これからは安心して酔えそうです．
    --- 今回の内容が役立ちそうでよかったです．ただし，この話は居酒屋と家の間に分かれ道がないこと (その間が一本道であること) が仮定されています．交差点などがあるとこの限りではないので，注意して下さい．:-)
  • 債務超過しているわけでもないのに、破産というのは変ではないか．
    --- すでに借り入れをしていて，そこからギャンブルを始めていると思って下さい (^^)
  • 僕の破産確率は0です (ガチャガチャ)
    --- 破産するのは簡単なので気をつけて下さい ;-)
  • ギャンブルは所持金が負になってからが本番だと思います。
    --- 破滅しないようにご注意ください．
  • 適用の範囲の広さに驚きました。この授業が大好きです。
    --- でもゾウさんの方がもっと好きです．
  • gamblers ruinは1/2確率のように思ってしまいますが、マルコフ連鎖を使えば{0, 1, ..., kn} の k の与え方によって異なる倒産確率を与えることが判明するのですね．
    --- その通りです．そのように一般化することを考えやすいのも数理モデルのよいところですね．
  • 拝んだり頼みこむことによって試験の素点を下げることはできますか？
    --- いままでそのような視点を持ったことがなかったので，新鮮で，感激しています．下げることはできません (^^)
• 1/24 (12) 離散確率論：マルコフ連鎖 (基礎)
  • コメントありがとうございました．
  • 次回で最終回とは悲しいです
    --- 補講もあります ;-)
  • テーマ：ゲーデルの (不) 完全性定理を証明するアルゴリズムは存在するのでしょうか (離散数理工学との関係があれば)
    --- 『離散数理工学』とは関係がありますが，この講義で扱う内容からは離れていて1回では扱えなさそうです．すみません．
  • 極限の存在判定は興味深かったです．
    --- いままで勉強してきたことがどんどん役立つ様子が浮き彫りになってきている気がします :-)
  • 行列が応用されている所を見ると，ほっこりします．
    --- 行列はどこでもでてくるので，重要で，それだからこそ1年生のときから勉強するのです．
  • 行列の累乗を、時刻の経過に対応づけることができるのが面白いです．
    --- そうですね．行列自体を「状態」だと見るのか「操作」だと見るのか，ということに関連しますね．そのような見方が置換に対してもあったことを思い出して下さい．
  • 推移行列と状態遷移図の一致がなるほどと思った．
    --- 1つの概念にもいろいろな見方があるのだ，ということを理解させてくれますね．
  • 状態遷移図は多用途で便利だと感じました。
    --- 「図示をする」ということで理解が深まりますね．
  • 確率行列 P を m乗したときの各成分は全て正になることが多いと思うので，証明が難しい命題が成立することは多い感じですか？
    --- 確率行列をm乗したときの各成分が全て正になりやすいかどうか，ということは慎重に判断する必要があるように思います．例えば，単位行列は確率行列として典型的な例ですが，この性質を満たしません．その意味では，命題の仮定が成立するかどうかを見極める (確認する) ことは見逃してはならないステップなのです．
  • 最近急に寒くなった気がします．
    --- 健康管理には十分気をつけて下さい．
  • やっと開始時刻に間に合うように来れました
    --- 「やっと」ですか ;-)
• 1/17 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • コメントありがとうございました．中間試験の採点はまだできていません．すみません．
  • 先生は何か楽器やられるのですか．BGMが幅広いなあと思いました．
    --- 楽器に負けたことはないのですが，BGMは適当に検索して見つけてます．
  • 恣意的な実験結果 強い…
    --- すみません，まだ直ってないです…
  • インターネット接続を確立する確率
    --- 確率を確立と書き間違える (打ち間違える) ことが多いので，注意して下さい．
  • 先生色々センスありすぎておもしろすぎます。
    --- ほえ？
  • 中央値トリック感動しました．
    --- 私も，はじめて知ったとき感動しました．その気持ちが共有できて，うれしいです．
  • 不公平な硬貨を投げることのみで中央値トリックにまで着想を展開できるとは、人間の思考はスゴイですね。
    --- 確率を推定することはとても基本的な問題なので，いろいろなことを考える人がいるわけですね．
  • 2つのアルゴリズムの違いが納得いかなくて，確率って神秘的だなあと思います。
    --- データの処理の仕方が違うのです．それでこれほどの違いが出てくるのは驚きますね．
  • なんで 1/8 で考えるのですか．
    --- 1/8にしなくてもよいです．計算がしやすいように1/8にしています．
  • この範囲に入ってから，以前より理解できているように (自分では) 思います。
    --- それはよかったです．演習問題を通してしっかり復習をして下さい．
  • 10回，11回の講義内容のどの辺がデータ構造と関係するのかよく分からなかった。
    --- たしかにそうですね．講義の細かい内容を考える前はデータ構造の話もするつもりでいたのですが，中身を練っているうちに，データ構造に関わる内容が落ちてしまいました…
  • 最近アルゴリズムや法則を考案・発見した人の名前や顔が出て来ませんけど、今回の中央値トリックは誰が考案したのですか？ 予備日は今までやったアルゴリズム等の考案者について話すのはいかがでしょう？
    --- 中央値トリックを考案したのは，Alon, Matias, Szegedyだと言われていて，その論文が出版されたのは1999年のことです．
  • 予備日ですが，もし講義で扱わなかった漸化式関連の内容があれば，それが良いです．
    --- なるほど．例えば，『複素関数論』との関連について講義することはできるかもしれません．考えます．
  • 多項式環，多様体などに興味があるので，予備日のテーマが決まらなければお願いします．
    --- 「多項式環」と「多様体」はだいぶ毛色が違いますね．どちらも準備が割と必要なので，1回では無理かもしれません．
• 1/10 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • コメントありがとうございました．
  • 明けましておめでとうございます。中間でこの先が不安になりましたが、期末までよろしくお願いします。
    --- 明けましておめでとうございます。
  • あけましておめでとうございます．体みが案外少なかったので，思うようにやりたいことができなかった冬休みでした．
    --- 体みではなく，休みですね．
  • 寝正月を過ごしたかった...
    --- 活動的なのはよいと思います．
  • 教室の暖房が安定しないですね．
    --- そうですね．寒かったら言って下さい．
  • 冬休みあけだからか、かなりだるかった．
    --- ひきしめてください ;-)
  • この大学は冬休みが短い気がします．
    --- 普通だと思います．
  • オフトゥンに入らないとそれはそれで眠いです…。
    --- では，オフトゥンを入れる，というのはどうでしょうか？
  • BGMの1曲目の曲名は何ですか．
    --- すいません，どれだったか忘れました．アシッドジャズです．
  • 先生はなぜ研究者の道に進んだのですか．
    --- 4年生のときに，卒業研究をしてみて楽しいと思ったからです．そのときの指導教員の先生に進路について相談して，この道に進みました．
  • マカオ・アルゴリズムとか有るんですか？
    --- マカオ・アルゴリズムは聞いたことがありません．聞いたことがあるのは，ラスベガス・アルゴリズム，モンテカルロ・アルゴリズム，アトランティックシティー・アルゴリズムです．
  • 第7回のタイリングについての質問
    置換 $H$ の選択 (ex $H=\langle (123), (345)\rangle$) はケーリー表に基づくとして、その中から如何にchoiceするのでしょうか？ (合理的に選択するためのアルゴリズムを作るのでしょうか？)
    --- 合理的に選択するためのアルゴリズムは知られておらず，がんばって見つけている，という現状です．頑張り方にもいろいろとあり，頑張る中で，群論に関するさらに深い概念を用いることもあります．
  • 単純なアルゴリズム1と2の違いが，辺の選択が「任意」か「一様分布に従う」かという点でした。なぜ任意だとよくないアルゴリズムなのですか．
    --- 任意だと「最悪の場合」に悪いアルゴリズムとなるからです．最悪な場合を避けるために，乱数を使いました．
  • 長さ n の配列 A (全要素異なる) に対する X_A の最大値は一意なので X_n は確率変数ではないようにみえます．
    --- 講義の説明に正確さが少し欠けているのですみません．「X_Aの最大値」と言っているときには，Aに関する最大値の意味になります．乱数の使い方すべてに対する最大値，を意味するならば，「X_Aの最大値」は一意になります．
• 12/20 (9) 離散確率論：確率的離散システムの解析
  • コメントありがとうございました．
  • BGMがクリスマス感満載でしたね
    --- 折角なので ;-)
  • 良いお年を
    --- 良いお年を
  • 良いお年を
    --- 良いお年を
  • あけましておめでとうございます
    --- あけましておめでとうございます
  • 寝正月を迎えたい
    --- あけましておめでとうございます
  • 朝のオフトゥンから逃げ切るのが辛くなってきまして…
    --- オフトゥンに入らなければよいのです
  • サーバを荒らされたのが先月でなくて良かった。(卒研配属に影響するので)
    --- 荒らされなければもっとよいのですけど．
  • 今更ですが、小休憩があるのは何故ですか．
    --- ずっと講義をしていると疲れるからです．
  • 直観的にはクーポン購入問題の期待値は超多項式で爆発しそうな気がするけど $O(n \log n)$ とマイルドで意外
    --- 確率の関わる現象が直感に合わないことを示すよい例なのかもしれませんね．
  • 中間テストについて、しっかり準備したつもりでしたが、だめでした。期末はもっと頑張ります。数学を勉強する際に特に注意するべきことは何かありますか．
    --- 「細かいことに気配りをする」ということだと思います．優しい心と厳しい心をもって日々生活すると，よいと思います．
  • $1+x \leq e^x$ や合併上界等不等式の有用性が何度も確かめられました
    --- 不等式を操ることはなかなか難しいことなので，これにも慣れが必要だと思います．等号でつなげていくことができないときや難しいときに，不等式はとても重要な道具となるので，ぜひ身につけて下さい．
  • モーメント母関数は統計数学に出てきた
    --- そうですね．一つの概念を様々な方向から眺めて理解を深めていければよいと思います．
  • $X_1,\ldots,X_n$ が互いに独立であることを示すには、直感でわかっていても、$\forall x_1,x_2,\ldots,x_n \in X$：$\mathrm{P}(X_1 =x_1 \text{ かつ } X_2 = x_2 \text{ かつ } \cdots \text{ かつ } X_n = x_n) = \mathrm{P}(X_1 = x_1)\cdot \mathrm{P}(X_2 = x_2) \cdot \cdots \cdot \mathrm{P}(X_n = x_n)$ を全通り書いて、確認したことを示さないといけないのですか？
    --- 本来は定義に従って確認しなくてはいけませんが，考えている状況が特殊な場合は，その特殊性を使って確認してもよいです．例えば，サイコロを独立に $n$ 回振っている場合は，その状況から $n$ 回の出目が互いに独立である，と言ってしまってよいです．
  • 授業中にWolframAlphaでexp(-exp(-x)) を書いてもらおうと思ったら 503…
    --- ブラッド・ピットですね．
• 12/6 (8) 離散確率論：確率の復習と確率不等式
  • コメントありがとうございました．今日は演習の時間がとれなくてすみません．
  • 何も思い付かなかったです
    --- それでも提出していただき，ありがとうございます．何か思い付いたときによろしくお願いします．
  • 眠気には勝てなかったよ...
    --- しっかりと寝てきてください ;-)
  • 今週，中間だとかん違いしていたので来週忘れていないか心配です
    --- 忘れずに，気持ちを保って下さい :-)
  • 研究室配属は戦争ですね．
    --- 本物の戦争に怒られるので，そういうことは言わない方がよいです ;-)
  • ヤギははずれ
    --- 代打の神様なのではずれではないです．
  • 確率は好きですが，扱うのは苦手なので，しっかりと学習したいです．
    --- 得意になれるところまではいけないかもしれませんが，慣れていって下さい．
  • 復習ができてありがたかったです。一度理解したつもりの事も時が経つとすっぽり忘れてしまって悲しいです。
    --- そうですね．定義があいまいだといろいろな考え方に影響を及ぼすので，しっかりと復習をして下さい．
  • "A given B" は和訳すると「A は B を与えられます」だそうです。今後はこれで言ってみてはいかがでしょう？
    --- "A given B"は「B が与えられたときの A」という意味です．
  • 期待値の方が確率より取り扱いやすいということの意味がチェルノフ上界技法例でよくわかりました．
    --- 次回，もう一度やりますので，お楽しみに．
  • 知識が増えた今の方が確率を扱いやすくなっているように感じた。
    --- いろいろなことを勉強したり経験したりすると，今までよく分からなかったことも分かるようになる，ということもあると思います．
  • 説明がわかりやすいです！！
    --- すぐにわからなくなるので，気をつけて下さい．
  • 不等式の応用が楽しみです
    --- 次回以降増えていきます．お楽しみに．
• 11/29 (7) 離散代数：有限群の応用
  • コメントありがとうございました．離散代数については今回で終了となります．次回から離散確率論を取り上げます．
  • 前回までは抽象的でしたが，今回群の具体的な応用例を知れて，面白かったです．
    --- 例までたどり着くのに時間がかかってしまった気もしますが，生き続ける数学は実際役に立っているわけなので，その様子をできるかぎり短い準備でお届けできるように努力しました．そのため，「ふつう」の代数系の教科書で説明している順序や方法とは違う説明の仕方もしています．これで群に興味がでてきたら，しっかりとした代数系の教科書を通して勉強することをお薦めします．
  • 証明、すげーーーって感じでした。自分じゃ絶対思いつかないし結びつかないけどきけば納得、でした。
    --- 思いつくのは難しいですね。だからこそ、「研究」という営みは行われるわけで、たゆまぬ努力が必要なのだと感じます。
  • 境界語を発想したり，置換群を見つけるなど，数学者 (人間) は偉大です！
    --- そうですね．群は数学の中でも応用が多い概念であることが知られていますが，講義ではその一端しか紹介できていません．関連する応用が登場したとき，この講義のことを思い出していただければありがたいです．
  • タイルの境界語から置換群を作ることは多項時間アルゴリズム無いのですか？
    --- 具体的に置換群を作るための多項式時間アルゴリズムを私は知りませんが，盤面に「穴」がなく，タイルが長方形の場合には，敷き詰められるかどうかを多項式時間で判定できることが知られています．
  • 15-puzzle感動した．
    --- 偶置換と奇置換の応用例としてよく出てくるものではありますが，講義で紹介できるぐらいのシンプルさで，巧妙に「できない」ということを教えてくれるのは感動的ですね．
  • 群同型写像の確認で「A=e」の形の関係式が成立するかどうか確認するだけで群同型写像と断定してよいのか．
    --- 断定してよいです．実際，それが確認できたら群同型写像である，ということが証明できます (講義では証明していませんが)．
  • 群は、集合と二項演算で定義される。ちかん群は集合 (写像の集合) は定義されているけど、二項演算が定義されていない (？)。なのでなんで群という語がついているのかギモン。
    --- 置換群では，置換の合成を二項演算であると考えて，それによって群になっています．置換の合成しか考えないので，それを省略して置換群と呼んでしまうことが多いです．
  • 数学ソフトはチート級
    --- いまでは，ほぼすべての数学者が数学ソフトウェアを使っています．それがなければ研究ができない，という世の中になっているのです．
  • 今日は興味深い内容でした．
    --- 前回もそうであってもらえればよかったと，私は残念がっています ;-)
  • 調布祭後すぐの授業はキツイです…
    --- 私もキツイです．:-)
  • そろそろ研究室決定の時期になってきました。
    --- そうですね．しっかりと決めて下さい．
• 11/22 (6) 離散代数：有限群
  • コメントありがとうございました．掲載が遅くなりすみません．
  • さむいです (´・＿・`）
    --- 暖房が途中で切れたいるようです．つけ直しました．
  • 今週はちゃんと寝ているにも関わらずどうにも眠い…
    --- では，もっと寝てきてください ;-)
  • 置換群は群
    ぐんぐんグルトも群
    --- ぐんぐんグルトは群ではありません．乳酸菌飲料です．
  • 群がぐんぐん育つ
    --- ケーリー・グラフを作るときは，そのようなイメージを持って下さい．
  • 用語が多くなりイメージがなかなかピンときません
    --- たしかに，代数は抽象的なものので，もう少し直感的な説明を心がけた方がよかったかもしれません．
  • ケーリー・グラフは頂点間の孤は全て書かなくてよいのですか
    --- 生成系を使って得られる場合だけ書きます．そうでない場合は書きません．
  • ケーリー・グラフは要素ごとの関係を把握するのに良さそうですが，2つ並べたときに，同型かどうかはわからなそうですね
    --- そのとおりですね．2つの有限群が同型かどうか判定することは難しい (正確にいうと，どれくらい難しいのかよく分かっていない) ので，同型かどうかを判定することに使おうと思わない方がよいのかもしれません．
  • 非可換群は非アーベル群と呼称しないのですか？
    --- そのように呼ぶこともあります．
  • 位数が一瞬拉致に見えた
    --- 何かを企んではいけません ;-)
  • 次回の有限群の応用が楽しみです
    --- お楽しみに．
  • 研究室見学を通じて大学の先生の仕事量に驚きました
    --- 私も驚きました ;-)
  • :-) っていう顔文字が良い
    --- :-)
• 11/15 (5) 離散代数：対称群と置換群
  • コメントありがとうございました．最後の方，かけ足になってしまいすみません．偶奇性の証明について，スライドを少し修正しました (大意に変わりはありません)．
  • ケーリー・グラフのあたりから理解が追いつかなかった．
    --- すみません．次回の最初に復習します．
  • 
    --- その3駅を選んだこころは？ :-)
  • ケーリー・グラフのケーリーさんはハミルトンさんの相方の人ですか？
    --- そうです．この人です．ハミルトン・ケーリーの定理でおなじみのケーリーですが，他にもいろいろな研究成果で有名です．
  • 現代数学入門で置換、置換群、対称群、交代群 etc は見たけどケーリーグラフは見た記憶がない。
    --- 見たことがあることばかりやってもつまらないからです ;-) 「図に描いて考える」ということは重要なので，そのような道具は惜しげもなく使っていきます．
  • 対称群の $\mathfrak{S}(X)$，交代群の $\mathfrak{A}(X)$の ？$(X)$ の ？の部分をどう変換しているのか気になりました。(書式上で)
    --- LaTeXでは，\mathfrak{S} や \mathfrak{A} として出しています．スタイルファイルとフォントが必要ですが．
  • 巡回置換は巡回群のお仲間と思って大丈夫ですか？
    --- はい，そうです．どのようにお仲間なのか，ということは次回扱います．
  • "ちかんの集合を見る"て言葉の破壊力．
    --- 破壊力がありますか．ちかんの魅力を味わって下さい．
  • 置換とか互換とか似たワードが多い ＞＜
    --- そうですね．混同しないように気をつけて下さい．
  • 代数学は定義をおさえる事が非常に大切だと思うので、おいていかれないように頑張りたいと思います．
    --- はい，よろしくお願いします．今回と次回，用語がたくさん出てくるので，混乱しないようにして下さい．
  • 全射、単射の射をずっと写だと思っていました。
    --- 全写，単写と書くこともありますが，普通は全射，単射と書きます．「射」という概念が数学にあって，それに由来すると思って下さい．
  • End(V) とか線積分とか 高校のときの積分定理とか 構造解析とか 似てるなあと思うものがたくさん思い浮かびました。色んなもののつながりをわかるようになりたいです。
    --- そうですね．いろいろなものがつながっているので，そのような味わいが感じられるとよいですね．妄想力が必要なのかもしれません．
  • 線形代数の記憶がよみかえってきました
    --- 置換群の話の中には，線形代数の言葉で言い換えられるものが多いです．その意味でも，線形代数と似てるといえますね．
  • 社会的事象についても「集合を考えれば構造が理解できる」という格言が適用できそうです
    --- 「木を見て森を見ず」とはよくいったものだと思います．森を見る思考が数学なのだとも感じます．
  • 研究室決め焦ってます．
    --- もうそろそろですので，しっかりと情報を集めて下さい．
  • 研究室見学楽しみにしてます！
    --- はい，こちらこそよろしくお願いします．
• 11/1 (4) 数え上げの基礎：漸化式の解き方 (発展)
  • コメントありがとうございました．来週は休講です．
  • 雨の日学校来るの大変です．
    --- もうそろそろ慣れて下さい (^^;
  • 行きたい研究室が定まりません．
    --- さだまさし
  • 1日24時間1週間168時間をうまく使えず課題をやってこれない自分の足りなさがつらいです。
    --- 時間をうまく使うのは重要な技能ですね．こだわりを持つべきところとそうでないところの区別をはっきりとつけられるとよいのだと思います．私自身もそうできているわけではないですが，時間をうまく使っている人を見ると，それができているように感じます．
  • 皆思いうかんでいるだろう 『語らん』という単語
    --- それを誰も語らないのです ;-)
  • 語られるカタラン数
    --- 誰も語らないと思ったら語っていました (^^)
  • 吾人は今すゑよりカタラン数をば語らん．
    --- 昔の人も語っていたみたいです．
  • 母関数が便利だということが判明！！
    --- 判明しましたね．実をいうと，母関数からうまく一般項を導き出すことができるのは稀で，母関数を作り，その性質を探究することで，数列の性質を導き出す，ということをよく行います．母関数は数列の性質を探るための一般的な道具になっているのです．
  • 漸化式にも様々な切り口がありおもしろいと思った。切り口が多いというのは応用先が広いことだとも思うので、調べてみたい。
    --- 様々な切り口がありますね．この授業で扱っているのは，1変数の数列 (つまり，a_nという形をしている) ですが，それが2変数 (例えば，a_m,nという形をしている) であったり，もっと多くの変数を持つ数列になると，より複雑になりますが，応用も広がっていきますね．
  • 情報理論はカタラン数やDyck道など深い学問の上に成り立っていることが実感されました．
    --- いろいろな分野が1つにつながっていることを感じさせてくれますね．
  • 母関数すごいですね．変換表は手元に置いておきたいです。群論は好きなので楽しみです。
    --- 群論をあまり深くやるわけではなく，私たちの道具として使えるような「さわり」の部分だけをやります．「群論」の「論」の部分はほぼありません ;-)
  • 再来週は4.4を解いてきます。
    --- 止してほしいと言ったのに ;-)
  • 講義で回した本の値段が気になる．
    --- わりと高いです．専門書は高いのです．(-_-;
  • さむくなってきたので南国風の曲がききたいです
    --- 提案ありがとうございます．検討します．
• 10/25 (3) 数え上げの基礎：漸化式の解き方 (基礎)
  • コメントありがとうございました．間違っていた部分は直しました．
  • 固有ベクトル出すの めんどくさい...
    --- 2x2行列なので，これぐらいはやってください ;-)
  • 固有値から対角化ができなくなってました。精進します…。
    --- なにごとも忘れるものですから，「忘れたら，そのときに調べて思い出す」という程度の気持ちでよいと思います．簡単に思い出せるようにしておくことは重要だと思います．
  • 次の回迄に行列を復習します．
    --- はい，よろしくお願いします．
  • 漸化式たのしい！！
    --- じゃあ，1日3つではなくて，1日5つ解きましょう (^^)
  • 特性方程式で解いた結果と，固有値，固有ベクトルで解いた結果はどんな場合でも一致しますか？
    --- 同じ数列が得られるという意味では一致しますが，その表現が一致するかどうかはわかりません．特性方程式で解いても，同じ表現が得られるのかは分かりません．
  • 行列のべき乗の計算はスペクトル分解する方法が一番好きです。行列の表記は (・) ではなく [・] を用いても良いですか．
    --- スペクトル分解は少し高度ですね．表記は [・] でもよいです．
  • なぜ先生は固有値が好きなのですか．
    --- いろんな道具として使えるからです．「ハイパフォーマンスコンピューティング第一」と「ハイパフォーマンスコンピューティング第二」で有用性が分かると思います．
  • $a_n = \lambda^n$ とおくシーンで、$a_n = \log n$ や、$a_n = n!$ や $a_n = n$ とおくのはダメなのですよね．$a_n = \lambda^n$ でなければダメなのですよね．??
    --- 線形漸化式の場合は $\lambda^n$ でなければダメです．他のものではうまくいきません．
  • 演習が数多くできるからうれしい。今日は簡単だった。
    --- 演習をたくさんやることは重要なので，強調してます．次回はまた少し違ったフレーバーの問題に取り組むことになりますので，お楽しみに．
  • 「斉次化」，「z変換」，「母関数」等々 多彩な概念がピンと来るようになれば、数学の"楽しさ"や解けることの"うれしさ"につながるのだろうと思います。
    --- そうですね．用語とその定義だけでは，あまりにも抽象的すぎて，何をしようとしているのかよく分からないこともあります．そのような概念に対して直感が湧くようになったり，それを使って問題解決ができるようになって，理解が進むようになると思います．
  • 漸化式の様々な解き方があるのは、使いこなすのは難しそうだとも、おもしろそうだとも思いました．
    --- 基本的なことなので様々な方法があるのだと思います．様々な方法があることで，様々な見方をすることができて，おもしろさが広がっていく気がします．

  • 	♀	♂
    親	母関数	父関数
    子ども	娘関数	子関数

    
    --- 「母関数」を英語でいうと「generating function」です．どこに「母」のニュアンスがあるのか，読み取るのは難しいかもしれませんが，generateする，つまり，生み出す，というところが「母」っぽいと思います．「母」という感じには「もとになるもの」とか「物の出てくる所」という意味があって，それは例えば，「母国」とか「酵母」といったことばを思い出すと理解しやすいと思います．
  • 母関数を傍観する
    --- ポカーン
  • 母艦数
    ---それは母艦の数です．
  • 母関数楽しみです．フィボナッチ数列の一般項の母関数を使った導出が好きです．
    --- それに近いことを次回やります．私も楽しみです．
  • 証明系の問題が最も理解度が深まるので復習問題で多く出題していただけるとうれしいです。
    --- 今回と次回は漸化式を解くということしかしないので，その意味では証明はしないことになります．それが終わって「離散代数」の話になると，証明が増える予定です．
  • 天才を3人あげるなら誰ですか？
    --- 私は「天才」という考え方にあまり同意していないので，誰もいません．「天才」ということばを使うとしても，肯定的な意味ではなく使うことが多いので，ここで3人挙げることは止します．
  • ジャージークラブが聞きたい気分です．
    --- 検討します ;-)
  • 音楽は洋楽限定ですか？
    --- ボーカルはできるだけ避けようとしてます．ボーカルが入ってしまう場合は日本語以外になるようにしてます．そうでないと気が散るので．
  • ごはんが食べたいです。
    --- 食べてきてください ;-)
• 10/18 (2) 数え上げの基礎：漸化式の立て方
  • コメントありがとうございました．
  • これから宜しくお願いします
    --- よろしくお願いします．
  • なんか人が急に減ったような…
    --- 私としては20人ぐらいがやりやすいです．もちろん，それより多くても少なくてもよいのですが．
  • 中かっこがある言語が好きです
    --- 「｛」と「｝」は波括弧と呼ぶことになっています．
  • KAKEHASHI Project 落ちた… (´；ω；`)
    --- それは残念です．折角のよい機会なのですけどね．
  • 音楽がよかった。
    --- ありがとうございます．次回以降も続けます．
  • 次回はトロピカルハウスを流して下さい
    --- 提案ありがとうございます．検討します．
  • 朝からプリンをたくさん食べたらおなかがいたくなってしまったなぁ
    --- プクリンに進化しないよう，注意して下さい．
  • コラッタ予想
    --- ラッタに進化しないよう，注意して下さい．
  • ハードコア人間関係模型 → 人は独立集合
    
    --- ひとりだけ笑ってますね :-)
  • 連続モデルの統計力学も離散構造を基礎に置いているとはじめて知りました．
    --- そうですね．あまり知られていないことなのかもしれませんし，これによって統計力学の考え方がいろいろな場面に適用可能になっている，という側面があります．
  • 学問の面白さは何だと思いますか．
    --- 何も分かっていないということに気付くことと，何か分かった気になる瞬間があること，そして，それが繰り返されることです．
  • たくさん ＜＜＜ もっとたくさん
    --- その上は「もっともっとたくさん」になります ;-)
  • グラフの独立集合の総数を求めるのが、面白かった．
    --- うまく漸化式を作れるようになると，いろいろなものがモデル化できるようになって，さらに楽しくなっていきます．
  • 重複のないようにうまく場合分けして数え上げるのが難しいです．
    --- いくつかの場合に分けるとしても，まず2つに分けて，そこからまた2つ，…というように分けるのがよいです．いきなり3つや4つに分けようとすると，重複や漏れが出てきやすくなりますね．
  • 前回の演習問題のような証明が相変わらず苦手です．数をこなしてなんとかついていきたいです．
    --- そのための演習問題ですので，積極的に取り組んで下さい．:-)
  • 不等式のゼンカシキ、どう扱うか期待
    --- 不等式をちゃんと扱えるようになることはとても重要ですので，次回しっかりやりましょう．
  • たのしかったです．
    --- 次回もお楽しみに．
• 10/4 (1) 数え上げの基礎：二項係数と二項定理
  • コメントありがとうございました．以下のように掲載されます．
  • コンピュータサイエンスコースの人間でもこの科目を履修登録できるのでしょうか？
    --- できます．同じ学科の専門科目は選択科目として履修できる，と学修要覧に書いてあります．但し書きもありますが．
  • 他学科履修は可能ですか？
    --- できます．所定の手続きを踏んで下さい．
  • すごくおもしろそうです．ポロシャツが素敵でした．
    --- 実をいうとアロハシャツです．;-)
  • 後期もよろしくお願いします．
    --- こちらこそよろしくお願いします．
  • グラフとネットワークに引き続き，よろしくお願いします．参考書の中で特にいちおしのものはありますか？
    --- どれもおしてますが，『離散数学への招待』はよい本です．
  • グラフとネットワークのリベンジです ('・_・`)
    --- よろしくお願いします ;-)
  • 朝がつらい
    --- 慣れて下さい．
  • 1限目は眠いですがよろしくお願いします．
    --- こちらこそよろしくお願いします．
  • 本講義とは関係ないのですが、グラフとネットワークにおいてレポートの提出と成績に相関があったかどうか知りたいです。
    --- 特に調べていませんし，誰がレポートを提出していたのかという記録もとっていません．そのため，分かりません．
  • 演習問題の紙におすすめ度 (?) とか、難易度を何らかの形で明示して欲しいです。
    --- 実をいえば，どれもおすすめなんです．数多の演習問題の中からピックアップして出題しているので，その時点でもうおすすめになっています．その意味で，講義中に「おすすめ」と言っているのは，「授業中に取り組むことをおすすめしている」のだと思って下さい．難易度に関しては「発展」とつけて，少し難しそうなものを寄り分けています．
  • パスカルの三角形が楽しかった．
    --- 楽しさを共有できて，私もうれしいです (^^)
  • パスカルの三角形や主に色を塗る問題、格子道などの具体的な話が非常に面白かったです．公式や式変形も上の例を用いていただいたのでとてもわかりやすかったです。確率や離散、グラフを用いた話は好きなのですが、複素や応用数学は苦手なのでこれらを用いた話が出たときは出来るだけ努力してみます。
    --- 『複素関数論』や『応用数学』の内容を直接使う場面はありません (というか，省いています) が，それらを知っていると理解が深まる部分もあります．そういう意味で，必須ではありません．出てきたときに少し思い出してもらえれば十分です．
  • 様々な解釈の仕方が示されていたので理解が深まりました。
    --- いろいろな解釈があるというところが面白いですよね．
  • 二年前学期の確率・統計学では二項係数が絡んだ等式の証明はやらされたが、組み合わせ的解釈は行わなかった。等式の理解を深めることができて良かった。
    --- 式変形だけではなくて，その式の意味を考えることが重要なので，その点を強調してみたかったのです．理解が深まったのならよかったです．
  • 格子道が好きです。
    --- でもゾウさんの方がもっと好きです．
  • 格子道や2項定理の展開になじむのが大変です
    --- そうですね．演習問題を通して慣れていって下さい．
  • メェ〜
    --- それぞれのヤギに名前を付けておいて下さい．;-)
  • 冷房をキンキンに効かせて欲しい
    --- 風邪ひきます．(-_-;
  • 今回は休憩中に曲流さないんですか
    --- じゃあ，次回から流します．;-)

• 中間試験と期末試験により，成績の評価を行います．
• 全体の成績
  • 成績 = min{100, 中間試験の素点+期末試験の素点} (小数点以下切り上げ)
    つまり，中間試験の素点+期末試験の素点が59.5点の人の成績は60点で，合格になります．
  • 得点分布 (中間試験と期末試験の一方でも受験した人に限る)：小数点以下を切り上げたものが示されています．
    
  • 受講者数 (履修登録者数相当) は26で， 90点以上 (S) が8人 (約31%)， 90点未満80点以上 (A) が0人 (約0%)， 80点未満70点以上 (B) が2人 (約8%)， 70点未満60点以上 (C) が1人 (約4%)， 60点未満 (D) が15人 (約58%) です．
  • 中間試験と期末試験の一方でも受験した人の総数は19で， 90点以上 (S) が8人 (約42%)， 90点未満80点以上 (A) が0人 (約0%)， 80点未満70点以上 (B) が2人 (約11%)， 70点未満60点以上 (C) が1人 (約5%)， 60点未満 (D) が8人 (約42%) です．
• 期末試験
  • 期末試験問題 (2月14日実施)
  • 採点：1問15点満点，合計60点満点 (0.5点刻み)
  • 得点分布
    
  • 受験した人の数は16，平均点は39.13 (60点満点)． 45点以上 (S相当) が7人 (約44％)， 45点未満40点以上 (A相当) が1人 (約6.4％)， 40点未満35点以上 (B相当) が1人 (約6.4％)， 35点未満30点以上 (C相当) が3人 (約19％)， 30点未満 (D相当) が4人 (約25％) です．
  • 得点掲示 (辞書順に並べています)

    46点	46.5
    bb913	47.5
    ckABz	27.5
    conf	42.5
    ecdsa521	58
    hoge	37.5
    monot	28.5
    OSAMU	33.5
    uts.	51.5
    zousan	50
    好評稼働中	46
    つらい	53

  • 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
  • 講評
    • 総評：まず，出題ミスについて，すみませんでした．全体的には，予想していた程度のでき具合でした．以下，問題ごとの平均点も掲載します．
    • 問題1：平均13.4点． チェルノフ技法に関する問題を出すつもりが，ミスをしてしまい，わけのわからない問題となり，すみませんでした．2月14日を意識しすぎたのかもしれません．よくできていました．
    • 問題2：平均7.44点． 乱択アルゴリズムの計算量解析ですが，これはでき具合に割と差がありました．演習問題と同じ問題なので，準備してきてもらいたかったです．問3の帰納法ですが，$n=k$ と置くとき，$k$ の範囲を明示して下さい．
    • 問題3：平均6.25点． クーポン収集問題について．これも演習問題と同じものなのですが，でき具合に差がありました．できている人はすんなりとできています．
    • 問題4：平均12.1点． マルコフ連鎖の定常分布に関する問題．よくできていました． 問2ではしっかりと方程式を解く必要があります．定常分布は確率分布なのですから，成分和が1でなくてはならないことに注意して下さい．
• 中間試験
  • 中間試験問題 (12月13日実施)
  • 採点：1問15点満点，合計60点満点 (0.5点刻み)
  • 得点分布
    
  • 受験した人の数は19，平均点は30.84 (60点満点)． 45点以上 (S相当) が6人 (約32％)， 45点未満40点以上 (A相当) が1人 (約5.3％)， 40点未満35点以上 (B相当) が1人 (約5.3％)， 35点未満30点以上 (C相当) が3人 (約16％)， 30点未満 (D相当) が8人 (約42％) です．
  • 得点掲示 (辞書順に並べています)

    ckABz	47
    conf	59
    hash	18
    hoge	52
    ktrnn	34
    LGH00	2
    mknwh	11
    MONOT	33
    NN	37
    OSAMU	2
    sta35	50
    TmokuJ	24
    turai	11.5
    yavai	40.5
    静的な置換	49
    単位ガチャ	46

  • 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
  • 講評
    • 総評：でき具合にばらつきがありました．ヒストグラムを見ても，ほぼ横ばいで，傾向というものもないです．以下，問題ごとの平均点も掲載します．
    • 問題1：平均6.74点． 漸化式を導出する問題．演習問題にない問題． これはちょっと難しいかもしれないと思って出してます．そう考えれば，割とできていたように思います．式変形をするときに，nの範囲がはみ出てしまっているものは減点しています．
    • 問題2：平均5.37点． 母関数を用いて漸化式を解く問題．演習問題4.8と同じ問題． これは思ったよりできていませんでした．演習問題を事前に解いていれば，思いのほか簡単な見た目の一般項が出てくることは記憶に残っているかもしれません．最終的に出てきた漸化式が n=1 の場合に成立するかどうか，確認するとよいと思います．b0をうまく設定できていない答案もあり，まぁ計算間違いかなぁ，と感じるのですが，点はありません．
    • 問題3：平均10.1点． 群の準同型写像に関する問題．演習問題にない問題． よくできていました．数学的帰納法を使えばすぐできます．n=0の場合を忘れずに．
    • 問題4：平均8.63点． 置換群の応用として，15パズルの問題．演習問題7.6と同じ問題． できにばらつきがありましたが，できている人はすんなりできています．どのように置換に対応させるのか，ということはちゃんと記述して下さい．

• 10/4 (1) 数え上げの基礎：二項係数と二項定理
• 10/11 休講 (体育祭)
• 10/18 (2) 数え上げの基礎：漸化式の立て方
• 10/25 (3) 数え上げの基礎：漸化式の解き方 (基礎)
• 11/1 (4) 数え上げの基礎：漸化式の解き方 (発展)
• 11/8 休講 (海外出張)
• 11/15 (5) 離散代数：対称群と置換群
• 11/22 (6) 離散代数：有限群
• 11/29 (7) 離散代数：有限群の応用
• 12/6 (8) 離散確率論：確率の復習と確率不等式
• 12/13 中間試験
• 12/20 (9) 離散確率論：確率的離散システムの解析
• 12/27 冬期休業
• 1/3 冬期休業
• 1/10 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
• 1/17 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
• 1/24 (12) 離散確率論：マルコフ連鎖 (基礎)
• 1/31 (13) 離散確率論：マルコフ連鎖 (発展)
• 2/7 授業等調整日 (予備日)
• 2/14 期末試験

• 離散数理工学 (2015年度後学期，情報・通信工学科)
• 離散数理工学 (2014年度後学期，情報・通信工学科)

過去の試験問題

• 2015年度： 中間試験 | 期末試験
• 2014年度： 中間試験 | 期末試験