離散数理工学

岡本 吉央

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

講義資料

• 1/30 (13) 離散確率論：マルコフ連鎖 (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/23 (12) 離散確率論：マルコフ連鎖 (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/16 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/9 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 12/19 (9) 離散確率論：確率的離散システムの解析
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 12/5 (8) 離散確率論：確率の復習と確率不等式
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 11/28 (7) 離散代数：有限群の応用
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 11/21 (6) 離散代数：有限群
  • スライド | 印刷用スライド | 演習問題 (11/27修正) | 用語集
  • 6.7, 6.11, 6.15, 6.16, 6.17の提出〆切は延長
• 11/14 (5) 離散代数：対称群と置換群
  • スライド | 印刷用スライド | 演習問題| 用語集
• 11/7 (4) 数え上げの基礎：漸化式の解き方 (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 10/24 (3) 数え上げの基礎：漸化式の解き方 (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 10/10 (2) 数え上げの基礎：漸化式の立て方
  • スライド (10/17修正) | 印刷用スライド (10/17修正) | 演習問題 | 用語集
  • 前回の続きからやります．
• 10/3 (1) 数え上げの基礎：二項係数と二項定理
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • 問題1.8，1.17，1.18の提出〆切は延長

• 1/30 (13) 離散確率論：マルコフ連鎖 (発展)
  • コメントありがとうございました．
  • 寒い。朝動けなかった。
    --- 慣れて下さい ;-)
  • ありがとうございました
    --- こちらこそありがとうございました．
  • ありがとうございました。期末試験がんばります。
    --- しっかりと準備してきてください．
  • 期末試験がんばります．
    --- しっかりと準備してきてください．
  • 少しでも上を目指せるように頑張ります
    --- しっかりと準備してきてください．
  • 数学は直感を正当化したり，逆に裏切ったりするが，真実はいつも1つ (コナン風) なので，直感を信用せず数学を信用しましょう。
    --- 直感を信用することは困難ですね．
  • ランダムウォーク，予想と違う結果におどろきました．
    --- 予想をよそうと思いますよね．:-)
  • 欲張って金を元手の3倍にしようとするから破産しやすいのではないかと思った
    --- そうですね．「3倍」ではなくて「k倍」にしようとすると，kが大きくなればなるほど，破産確率は大きくなりますね．実際に計算してみて下さい．
  • マルコフ連鎖やったけど，MCMCはやらなかった感じですかね
    --- やらなかった感じです
• 1/23 (12) 離散確率論：マルコフ連鎖 (基礎)
  • コメントありがとうございました．
  • 複雑さが増したことを感じた。復習していきたい。
    --- たしかに，だんだん複雑になってきている気がしますんで．しっかりと復習をして下さい．
  • チャップマン・コルモゴロフ方程式がすごく嬉しい内容だなと思った。実際に計算すると大変そうだが。
    --- 意外なところで，行列がでてくる気がしますが，確率的な振る舞いをするシステムの解析においても，行列や線形代数は重要な役割を果たすことがわかりますね．
  • いつも思うが、行列積の計算が面倒。
    --- 実際の応用では手で行列積を計算しないので，それほど面倒ではありません ;-)
  • 推移する確率が0であるような遷移と自己ループになるような遷移は書かないと約束した上で状態遷移図を作成するとします。そして定常分布が存在すると仮定します。このとき定常分布が存在すると仮定します。このとき、定常分布において、出次数が1以上で有向閉路に含まれない頂点 (状態) に対応する値は必ず0になりますか...？ (´・＿・`)
    
    --- 必ず0になります．そのような状態を $i$ とすると，推移行列 $P$ の第 $i$ 列は零ベクトルになります．そして，$\pi$ が定常分布であるとすると，$\pi P = \pi$ を満たさないといけないので，$i$ に対応する値 $\pi_i$ は $\pi$ と $P$ の第 $i$ 列の内積と等しくなり，つまり，それは0になります．
• 1/16 (11) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • コメントありがとうございました．
  • あけましておめでとうございます．今年もよろしくお願いします (新年早々風邪を引いて寝込んでしまいました…)
    --- お大事に．
  • 中央値トリックのタネが意外なところにあっておもしろかったです．
    --- そうですね．トリックにはタネがつきものですね ;-)
  • 「中央値トリック」という名前の付け方は初めて見ました．
    --- 英語ではmedian trickと呼びますが，日本語の文献では見かけないですね．
  • 中央値トリックだと収束ははやいがそれが正しい値になるとは限らないのをみて"よいアルゴリズム"とはなんなのかを考えさせられる。
    --- 確かにそうですね．アルゴリズムの良さを測る尺度がたくさんあるのだと思います．たくさんある尺度の中から，どれを基準にしてアルゴリズムの選定をするか，そして，アルゴリズムを設計するのか，という視点も重要なのだと思います．
  • 中央値トリックの仮定 $\displaystyle t \geq \frac{mp(1-p)}{\varepsilon^2}$．授業では $m=8$ としたが、$m$ を大きくすれば $\Pr(|Y-p|\geq \varepsilon)$ も小さくなるのだろうか。また、$m=8$ には特別な意味があるのだろうか。
    --- $m=8$ に特別な意味はなく，大きな定数ならば何でもよいです．講義でおこなった導出では，$\Pr(|Y-p|\geq \varepsilon)$ を $\delta$ 以下にするためにどうすればよいか，ということを考えていたので，$\Pr(|Y-p|\geq \varepsilon)$ が小さくなるのかというよりは，$\Pr(|Y-p|\geq \varepsilon) \leq \delta$ とするための $n$ が小さくなるかどうかを考えるとよいです．その観点から見ると，$m$ を変えることで，$t$ と $k$ が変わることになりますが，$m$ が大きな定数であるならば，最終的な $n$ のオーダーは講義で導出したものと変わりません．
  • 今回の講義で出た方法以外にもこの場合の確率 $p$ を求める方法はあるのですか。
    --- 考える設定はちょっと違いますが，次回扱うマルコフ連鎖を応用した「マルコフ連鎖モンテカルロ法」(通称MCMC法) というものもあります．確率の推定は重要なトピックなので，多くの研究があります．
• 1/9 (10) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • コメントありがとうございました．本年もよろしくお願いします．
  • 前に習った漸化式が入ってきたので複雑さを感じた。
    --- そうですね．しっかりと復習をして下さい．
  • $\displaystyle t_n = n-1 + \sum_{i=0}^{n-1} \frac{2}{n}t_i$ から直感を得るために $\displaystyle t_n = n + \sum_{i=0}^{n-1} \frac{2}{n}t_i$ でやってみたがこれだと $t_n = O(n^2)$ になる？
    quick sortの比較回数が直観に乗りそうで乗らないのがこそばゆい。
    --- そのように書き換えた $t_n$ でも，$t_n = O(n \log n)$ になると思います．いわゆる分割統治法の計算量に対する直感を持つことは難しいかもしれませんし，乱択だとその傾向がより顕著になります．しっかりと計算を行うことが重要な局面なのだと思います．
  • 乱択クイックソートは他のピボット選択法を使用するクイックソートに比べて、平均的に比較回数は少なくなるのでしょうか？
    --- 「平均的に」という部分が何を意味するのか，に依存しますが，期待値を最大にする入力に対して，という意味だとすると，講義で紹介した他のピボット選択法では，比較回数が $n^2$ に比例する回数の比較が必要となる例もあります．その意味で，講義で紹介した乱択クイックソートの比較回数はそれらより少なくなります．
  • 今朝、電通大マックにいたのを見かけましたが、オススメのメニューがあったら教えてください。
    --- たいてい朝いて，たいていマックグリドルソーセージエッグを食べてます．オススメであるわけではないですが．
• 12/19 (9) 離散確率論：確率的離散システムの解析
  • コメントありがとうございました．年内最後の授業でした．
  • 朝が苦手です。
    --- 慣れて下さい．
  • 今日の講義開始時刻の9時の時点では教室内の学生数が3人でした。そこで質問です。もし、9時の時点で教室にいる学生の数が0人だったとしても、9時に講義を始めるのですか？ また、30分経過して学生の数が0人だったとしても、講義を行うのですか？
    --- 考えたことがないですが，場合によると思います．講義でビデオを撮影しているなら，講義を行うと思います．そうでない場合は，講義を行いませんが，休講にはしないと思います．
  • 色々なことに確率は使えるんだなと思った。
    --- そうですね．数学がいろいろなことに使えることを味わうのがこの講義の目標なので，それが感じていただけているようで，私もうれしいです．
  • 誕生日のパラドックスは「自分と同じ誕生日の人はいるか」にすると直感に近くなりますね．
    --- そうですね．直感的に不思議なことが起こっているように思える，という類のパラドックスは，そもそも，問われている内容を正しく理解することが難しいために，直感と違うことが起きているように思えてしまう，というものが多くあるように思います．前回扱ったモンティ・ホールの問題もそのようなものの1つで，「変えた方がよい」ということを理解するためには，正しく問いを理解する必要があったり，自分が認識していないかもしれない隠された仮定をしっかりと認識する必要があったり，様々な障壁があるように思います．
  • クーポン収集問題で調和関数を用いるとは思わなかった。これの応用でガチャコンプ問題が解けそう．
    --- ガチャコンプは典型的(？)な応用です．調和関数ではなく，調和数ですので，違いに注意して下さい．
  • 
    エルデシュとレニィの結果はこういう気持ちですか？
    --- ちょっと気持ちがわかりませんが，$n$ の大小は関係ないと思います．$e^{-e^{-c}}$ は $c$ を動かすと0と1の間の値をうまくとりますね．$c$ を大きくしたときの確率の減少の仕方を厳密に表したのがエルデシュとレニィの結果です．
  • また来年！
    --- よいお年を．
• 12/5 (8) 離散確率論：確率の復習と確率不等式
  • コメントありがとうございました．来週は中間試験となります．
  • 来週のテスト頑張ります。
    --- はい，しっかりと準備をしてきてください．
  • 布団と離れ難い気温になることが多くなりましたね．
    --- そうですね．体調を崩さないようにご注意ください．
  • スライドが眩しくて見づらい。困った。
    --- スライドが見にくい場合は手元にも資料をご用意ください．
  • 確率変数というものは、例えばトランプにおいて、X(キング)=13やX(クイーン)=12とするようなものですか
    --- そのようなものも確率変数です．他にも使い方はありますが，いろいろな例は今後の講義で見て行きます．
  • チェルノフ上界だけ知らなかった．マルコフの不等式は工学であまりでてこないので未だに覚えてない．後，独立⇒E[ΠXi] = ΠE[Xi] もはじめて聞いたかも。
    --- 離散確率論だけもいろいろと興味深いことができますので，お楽しみに．
  • マルコフの不等式のマルコフとマルコフ連鎖のマルコフは同一人物ですか？
    --- はい，同一人物です．マルコフ連鎖については，後の方の講義で扱います．
• 11/28 (7) 離散代数：有限群の応用
  • コメントありがとうございました．中間試験の範囲は今回の最後までです．しっかりと準備をしてきてください．
  • タイリングにおいて、タイルや盤面に穴が開いていると境界語によるタイリング不可能性の証明はできなくなるのでしょうか？
    --- 一見できなくなりそうですが，穴の部分をうまく切り開く，という操作を考えると帰着できます．ただ，この手法ではあまりエレガントさはないのですが．
  • 盤面が穴空きの場合、タイリングのやり方も変わってくるのですか。
    --- 一見できなくなりそうですが，穴の部分をうまく切り開く，という操作を考えると帰着できます．ただ，この手法ではあまりエレガントさはないのですが．
  • 高級な数学の道具として群がよく使われていることがわかったが日常生活で使う (？) ことはあるのだろうか。
    --- 対称性を考えるときには，たいてい群を使います．別の言い方をすると，対称性というものは群を使ってモデル化されることが多いです．そうすると，自然の中に存在する万物の対称性は群と関係しているわけです．これについてはこの授業では扱いませんでしたが，群に関して「ふつう」の授業を受けると，この側面が強調されます．
  • 群表を作る問題で，記号が少なく位数が大きい問題 (6.14では記号は $a$, $b$ の2つで，位数はヒントによると8) を上手く解くコツはありますか？
    --- 6.14の例でいいますと，$a^4 = e$ になっています．つまり，$e, a, a^2, a^3$ は全部異なる要素で，$a^4$ を考えたとき，はじめてそれが $e$ と等しくなるわけです．これは，「$G$ の部分群として位数4の巡回群が存在する」という言い方ができるのですが，$G$ の位数は必ずその部分群の位数の倍数になります (ラグランジュの定理)．以上のことから，$G$ の位数は4の倍数であることが分かり，$e, a, a^2, a^3$ と $b$ は違うものなので，4 よりも大きい 4 の倍数が $G$ の位数の候補となります．小さい順に候補を考えると，それは 8 になり，実際，8 になるかどうか，考えていく，という手順になっていきます．
  • 寒くなって布団から出るのも一苦労
    --- 字余りですね ;-)
• 11/21 (6) 離散代数：有限群
  • コメントありがとうございました．次回は今回の続きからになるので，資料等を忘れずにお持ち下さい．
  • 群の生成図を見て，オートマトンを思い出した．
    --- そうですね．いろいろなことが連想できますね．
  • 難しかったので線形代数から復習します．
    --- 復習は大事ですので，ぜひ励行して下さい．
  • 1年の頃に現代数学入門でやった群論がすごい難しかったのを思い出しました。
    --- 代数学は割と抽象的なので，難しく感じることも多いかと思います．
  • 群を勉強する上でおすすめの本はありますか？ (´・＿・`)
    --- 志賀浩二先生の「30講シリーズ」は定評があり，群についても『群論への30講』があります．他のものとしては，『対称性からの群論入門』が図形的な直感を重視しているので，とっつきやすいかと思います．
  • 3, 4コースの研究室は1, 2コースに比べて受け入れ人数が少なく感じる。1回につき1つしか希望が出せないので厳しい。
    --- 何が厳しいのか，ちょっと分かりません．
• 11/14 (5) 離散代数：対称群と置換群
  • コメントありがとうございました．次回は今回の続きからになるので，資料等を忘れずにお持ち下さい．
  • 「表現行列」について理解していれば $(AB)^{-1} = B^{-1} A^{-1}$ と $(f\circ g)^{-1} = g^{-1} \circ f^{-1}$ が「本質的に同じ」なのは (行列の場合は「線形」写像だが) 自明では？
    --- 「理解していれば」という仮定があれば，ご指摘どおりです．
  • 1年生のとくに学んだ線形代数の応用はやっと見えてきました。
    --- 線形代数は約に立ちますからね．他の講義でも線形代数の応用がでてきているのですが，選択科目なので，この講義で初めて遭遇するという可能性もあるかと思います．
  • 問題5.9は「絵」を描いて解くものなのでしょうか。
    --- 絵を描かなくてはならないわけではありませんが，互換の積として表す簡便な方法だと思います．「絵」を描けば，そこから互換の積としての表し方が1つ得られるので，そこから偶置換か奇置換か，分かります．
  • 互換の偶奇性の証明の難易度が分かっただけでも収穫です。(汗)
    --- もっと簡単な証明を紹介できるとよいのですが，思いつきません (-_-;
  • 
    2文字ずつ入れかえると、オトカモ → オカトモ → オカモト
    $\begin{pmatrix}\text{オ}&\text{ト}&\text{カ}&\text{モ}\\\text{オ}&\text{カ}&\text{モ}&\text{ト}\\\end{pmatrix} = (\text{モ}\ \text{ト})(\text{ト}\ \text{カ})$ は偶置換。
    --- 正解です！ オトカモっていうのが何なのか知りませんが！
  • $\begin{pmatrix}1&2&3&4\\3&2&4&1\\\end{pmatrix} = (1\ 3)(3\ 4) = (1\ 4\ 3)$ と表せるみたいですが，全通りを列挙する方法はありますか？
    --- 「全通り」が何を意味するのかに依存しますが，互換を2回書けると恒等置換になるので，例えば，$(1\ 3)(3\ 4) = (1\ 2)^2 (1\ 3)(3\ 4) = (1\ 2)^4 (1\ 3) (3\ 4)$ のように，無限に表現の仕方は得られてしまいます．
  • $\begin{pmatrix}1&2&3\\2&1&3\\\end{pmatrix}$ と $\begin{pmatrix}1&2\\2&1\\\end{pmatrix}$ を巡回記法で書くと両方 $(1\ 2)$ になるのですが2つの置換は区別されますか？
    --- 全単射としては異なるものですが，置換を考える際は本質的に同じであると見なすことが多いように思います．つまり，移った先が変わらないものは気にしないことが多い，ということです．
  • 研究室配属が不安
    --- 不安になっていても仕方がないので，しっかりと情報を入手して決めて下さい．
• 11/7 (4) 数え上げの基礎：漸化式の解き方 (発展)
  • コメントありがとうございました．数え上げの基礎に関しては今回で終了です．次回から「離散代数」になります．
  • 早起きのコツを是非教えて下さい．
    --- 早く寝ることだと思います．
  • 懇親会，頭がうまく働かず，話の内容も頭に入らなかったので酒を飲んだのは失敗だったかもしれない。
    --- アルコールがあることは，私も当日知りました．驚きました．
  • 計算は大変です。
    --- そうですね．この講義の中で出てくる計算はぎりぎり手でできるものに留めているので，頑張って下さい．それよりも大きな規模のものは計算機を使うことになりますね．
  • 様々な漸化式の解法があるのかと思った。
    --- 解法によっては，使える場合と使えない場合があるので，その点には注意をして下さい．
  • 数学の美しさを感じた．
    --- 次回から代数のはなしになりますが，また違った風味の美しさを感じて下さい．
  • カタラン数の話が興味深かったです。
    --- そうですね．私にとっても好きな題材です．:-)
  • なぜカタラン数は様々な場合の組み合わせの数に現れるのでしょうか．
    --- 「分割して組み合わせる」という形の数え上げによく出てきますが，そのような形をしている場合が現実世界にもたくさんあるからだと思います．
• 10/24 (3) 数え上げの基礎：漸化式の解き方 (基礎)
  • コメントありがとうございました．来週は休講です．
  • $\displaystyle \sum_{n=0}^{\infty} a_n x^n$ が収束するのは $|x|<1$のときでよいでしょうか．
    --- $a_n=1$ のときはそのとおりです．そうでないときは，その限りではないです．『解析学』の講義で扱っていると思うので，復習して下さい．
  • 母関数を使った数列の変換は2年でやったラプラス変換に似てる気がする．
    --- そうですね．ラプラス変換を通してz変換を導入するという方法もあります．関係は深いですね．
  • 等式の証明は，少ない場合分けを含む等式変形で示せるときも $\leq$，$\geq$ の両方を示した方がよいのでしょうか？
    --- 等式の変形で示すことができるならば，それで十分です．
  • 二回目の演習問題の漸化式はこういう解き方もあるんだと思った。
    --- そうですね．次回は母関数を用いた解き方をやりますので，お楽しみに．
  • 頑張らなきゃいけない計算が出てくるとなんとかして楽にできないかを考えるけどそれでも楽にならない計算も多くて大変
    --- 「なんとか楽にできないか」と考えることは大事だと思います．励行して下さい．
  • 難しい .... (´・＿・`)
    --- 細かい計算は大変ですが，手順は難しくないと思うので，慣れて下さい．
  • 直感というより直観では。
    --- 私の持っている辞書では，直感は「瞬間に感じ取る」，直観は「直接に本質を見抜く」とあります．ということなので，授業で用いた「直感」は「直感」のままでよいと思います．
  • 今日はすこしさむかったです．さいきん冷えてきましたね．
    --- もうそろそろ講義室にも暖房が入ると思います．入口付近にスイッチがあるので，操作してみて下さい．
• 10/10 (2) 数え上げの基礎：漸化式の立て方
  • コメントありがとうございました．掲載が遅くなり，すみません．
  • 朝の早起きがつらいです．秘訣はありますか？
    --- 夜早く寝ることだと思います．
  • 朝一なので少し眠気がおそってくるときがありますね。良く寝るようにします。良い睡眠導入の方法か目覚めの方法ありますか？
    --- どちらにしても軽く運動をするとよいとよく言われる気がします．私は実践していませんが．
  • せっかくの3連休がなにもなく終わってしまった…
    --- それは残念ですね．11月のはじめにも3連休があるので，なにかをするという計画を予め立てておくとよいかもしれません．
  • コラッツ予想がここで出てくるとは！
    --- 再帰の話題ではよく出てくる予想ですよ．
  • 面白いプログラムだなと思いました。
    --- 作るのはそんなに難しくないので，ご自身でもお試しください．
  • アルゴリズムをプログラムする時におすすめの言語はありますか？
    --- 目的に大きく依存しますが，不真面目なプログラムにはRubyを使っています．
  • 次回漸化式が解けるか心配だ。
    --- それをできるようになるようにするのが，この講義の目標なので，やりとげましょう．
  • ユークリッドのアルゴリズムの厳密な評価が意外と難しくてびっくり
    --- 「不等式」になっているので，それほど厳密ではありませんね．もっと直感的に説明する方法もあるのですが，ここでは例題として使っているだけなので，他の場合にも適用可能な一般性のある方法で説明をしているつもりです．
  • もし、ある時、今までの数学理論が間違っていることが発表されたらどうなりますか？
    --- 残念ながらどうもならないです．;-) 例えば，相対性理論が発見されたからといって，ニュートン物理学が役に立たなくなるわけではないことは歴史を見ても分かります．数学自体は時代とともに大きく変容しています．今後もそのような変化は続いていくでしょう．
• 10/3 (1) 数え上げの基礎：二項係数と二項定理
  • コメントありがとうございました．以下のように掲載されます．
  • 分かりやすい説明ありがとうございます．
    --- 分からないことが出てきたら，どしどし質問をお願いします．
  • よろしくお願いします．
    --- こちらこそよろしくお願いします．
  • これから頑張っていきます。
    --- こちらこそよろしくお願いします．
  • 朝 ひえこみますね。
    --- 季節の変り目なので，体調管理には気をつけて下さい．
  • 人が少ないですね
    --- ですね．少ない方が細かい指導が受けられると思って下さい．
  • 補足問題で証明することがらを復習問題の証明で使って大丈夫ですか？
    --- 大丈夫です．
  • 演習問題を解いたレポートを締切前に提出しようとした場合、どこに提出すべきでしょうか．(講義終了時に提出するしかないのですか？)
    --- 西4号館4階の事務室前に「岡本」と書かれたレポート提出箱があるので，そこに提出していただいても構いません．ただ，その場合，提出をしたら，私までメール等でご連絡下さい．連絡があって，はじめて，その提出箱を開けることになります．よろしくお願いします．
  • 復習が分かりやすかった。
    --- 復習ではない内容もだんだん増えていきますので，お楽しみに．
  • 知っていた知識が洗練された形で整理されていて楽しい．
    --- 楽しいことはいいことですね ;-)
  • なぜ二項係数の書き方は縦ベクトルと同じようになってしまったのでしょうか
    --- Wikipediaの項目によると，Ettingshausenがこの書き方を1826年に導入したそうです．なぜこれを使いだしたのかは分からないのですが，注意しなくてはならないのは，組合せ論では，違うカッコを使うと，違う数を表すことになるということです．例えば，丸カッコではなく，角カッコを使うと，それは第1種スターリング数となり，波カッコを使うと，それは第2種スターリング数になります．これらは二項係数とは違うものです．
  • 数学とは何ですか？
    --- 世の中には「現象」と呼べるものがあって，その中には数学的現象と呼べるものもあります．それを研究する学問が数学だと思います．例えば，素数の分布であったり，空間の分類であったり，そういうものが数学の対象だと思います．「数学」の説明をするために「数学的現象」ということばを使って堂々巡りになっている気がしますが，これは「物理学」を説明しようとしても「生物学」を説明しようとしても同じなので，気にしないでください．つまり，物理学というのは物理現象を研究する学問で，生物学というのは生命現象を研究する学問です．
    数学そのものを勉強することと，数学の使い方を勉強することは全く違います．その一方で，数学を正しく使うためには数学を深く理解する必要があります．そうでないと，いくらでも数学を間違った形で使うことができてしまい，困った問題が起きてしまいます．そして，実際にそのような問題が現在起きています．由々しき事態です．皆さんには正しく数学が使えるようになってもらいたいと思っています．
  • 最近おしゃれノートを買うのが趣味です。先週はCampusの日記用ノートを買いました。
    --- これでしょうか．私のスケジュール管理はGoogle Calendarに一任されているので，手書きのものを使うことはなくなりましたね．

• 中間試験と期末試験により，成績の評価を行います．
• 成績 = min{100, 中間試験の素点+期末試験の素点} (小数点以下切り上げ)
  つまり，中間試験の素点+期末試験の素点が59.5点の人の成績は60点で，合格になります．
• 得点分布 (中間試験と期末試験の一方でも受験した人に限る)
  
  • 中間試験と期末試験の一方でも受験した人の総数は11で， 90点以上 (S) が3人 (約27%)， 90点未満80点以上 (A) が3人 (約27%)， 80点未満70点以上 (B) が4人 (約36%)， 70点未満60点以上 (C) が0人 (約0%)， 60点未満 (D) が1人 (約9%) です．
• 期末試験
  • 試験問題 (2月13日実施)
  • 採点：1問15点満点，合計60点満点 (0.5点刻み)
  • 得点分布
    
  • 受験した人の数は10，平均点は43.50 (60点満点)． 45点以上 (S相当) が4人 (40％)， 45点未満40点以上 (A相当) が2人 (20％)， 40点未満35点以上 (B相当) が4人 (40％)， 35点未満30点以上 (C相当) 0人 (0％)， 30点未満 (D相当) が0人 (0％) です．
  • 得点掲示 (辞書順に並べています)

    t624s	39
    89420	46
    !i!i!	36.5
    10点	43
    2018tmt	47.5
    GQ0729	38
    tk960	43
    はるやすみ	51
    もうだめだ	53
    ラリルレロ	38

  • 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
  • 講評
    • 総評：よくできていたと思いますが，一方で，55点以上の人もいないので，答案を見ていても，すごくできているという印象は持ちませんでした．以下，問題ごとの平均点も記載します．
    • 問題1：マルコフの不等式を用いる問題．演習問題と同じ問題．平均点は14.1．よくできていました．3¹⁰⁰/2¹⁹⁰まで導けていれば，よしとしています．
    • 問題2：乱択アルゴリズムの解析．演習問題にない問題．平均点は12.4．これもよくできていました．小問3にて一般項を求めることはなかなか難しいので，証明すべきことを数学的帰納法で直接導くと簡単だったと思います．
    • 問題3：確率的解析の問題．演習問題と同じ問題．平均点は6.45．これはできが悪かったです．事象が互いに独立ではないので，チェルノフ上界の技法を使うのは難しいと思います．合併上界をうまく使えばすぐに導けます．
    • 問題4：マルコフ連鎖の定常分布に関する問題．平均点は10.55．まあまあの出来でした．ほぼ，計算できるかどうかだけを聞いている問題です．
• 中間試験
  • 試験問題 (12月12日実施)
  • 採点：1問15点満点，合計60点満点 (0.5点刻み)
  • 得点分布
    
  • 受験した人の数は11，平均点は40.68 (60点満点)． 45点以上 (S相当) が3人 (約27％)， 45点未満40点以上 (A相当) が2人 (約18％)， 40点未満35点以上 (B相当) が5人 (約45％)， 35点未満30点以上 (C相当) 17人 (約9％)， 30点未満 (D相当) が0人 (約0％) です．
  • 得点掲示 (辞書順に並べています)

    12345	40
    89420	39
    !i!i!	44
    ￥0＼3a	45
    arrgi	35
    jinGq	34
    tk960	35
    ts123	35
    Xmas17	53
    えーん	50
    配属落ちた	37.5

  • 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
  • 講評
    • 総評：よくできていたと思います．全体的に，細かい計算をしなくてはいけない箇所が多く，大変だったと思いますが，それは採点基準に考慮しています．
    • 問題1：漸化式を作る問題．演習問題と同じ問題．平均点は10.82．よくできていました．n=1の場合とn=2の場合もきちんと示す必要があります．
    • 問題2：母関数を用いて漸化式を解く問題．演習問題にない問題．平均点は9.77．完答できた人は少なかったです．まず，母関数が正しく書けることが重要で，その部分まで到達できている答案には割と点数を与えています．
    • 問題3：置換群に関する問題．演習問題にない問題．平均点は8.73．これは出来ている人と出来ていない人の差が大きな問題でした．問3.2の答えは「0」です．これについて気が付いた人はすぐ気が付いたようですが，生成系の置換がどちらも偶置換なので，偶置換の積として現れる置換はどれも偶置換になるからです．その意味では，細かく計算しなくてもわかります．
    • 問題4：群の同型性に関する問題．演習問題と同じ問題．平均点は11.36．GとHの群表を書く部分はよくできていて，私も安心しました．

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

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

過去の試験問題

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