離散数理工学

岡本 吉央

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

講義資料

• 2/2 (14) 離散確率論：マルコフ連鎖 (発展)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/26 (13) 離散確率論：マルコフ連鎖 (基礎)
  • スライド | 印刷用スライド | 演習問題 | 用語集
• 1/19 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • スライド (1/19修正) | 印刷用スライド (1/19修正) | 演習問題 | 用語集
• 1/12 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • スライド (1/14修正) | 印刷用スライド (1/14修正) | 演習問題 | 用語集
• 1/5 (10) 離散確率論：確率的離散システムの解析
  • スライド | 印刷用スライド | 演習問題 (1/19修正) | 用語集
• 12/15 (9) 離散確率論：確率の復習と確率不等式
  • スライド (12/18修正) | 印刷用スライド (12/18修正) | 演習問題 (1/12修正) | 用語集
• 12/8 (8) 離散代数：有限体の応用
  • スライド (12/9修正) | 印刷用スライド (12/9修正) | 演習問題 | 用語集
• 12/1 (7) 離散代数：多項式環による有限体の構成
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • 前回の続きからやります
• 11/24 (6) 離散代数：多項式環
  • スライド (12/2修正) | 印刷用スライド (12/2修正) | 演習問題 (12/2修正) | 用語集
  • 問題6.6, 6.7, 6.8, 6.9, 6.11, 6.12, 6.13, 6.14は次回に持ち越し
  • 前回の続きからやります
• 11/17 (5) 離散代数：整数と有限体
  • スライド (11/17修正) | 印刷用スライド (11/17修正) | 演習問題 (11/17修正) | 用語集
  • 問題5.7は次回に持ち越し
• 11/10 (4) 数え上げの基礎：漸化式の解き方 (発展)
  • スライド (11/11修正) | 印刷用スライド (11/11修正) | 演習問題 (11/11修正) | 用語集
• 10/27 (3) 数え上げの基礎：漸化式の解き方 (基礎)
  • スライド (10/27修正) | 印刷用スライド (10/27修正) | 演習問題 | 用語集
• 10/20 (2) 数え上げの基礎：漸化式の立て方
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • 前回の続きからやります
• 10/6 (1) 数え上げの基礎：二項係数と二項定理
  • スライド (10/21修正) | 印刷用スライド (10/21修正) | 演習問題 (10/6修正) | 用語集
  • 問題1.6, 1.7, 1.8, 1.13, 1.16, 1.17, 1.18は次回に持ち越し

• 2/2 (14) 離散確率論：マルコフ連鎖 (発展)
  • コメントありがとうございました．期末試験にはしっかりと準備をして臨んで下さい．
  • マルコフ連鎖がどのようなものか理解できたと思う．応用としてはシミュレーションが主でしょうか？　また，シミュレーションを回すときに，回数を見積もる時に，期待値を計算するのでしょうか．
    --- シミュレーションで使うことも多いですし，マルコフ連鎖モンテカルロ法と呼ばれるような，モンテカルロ法の計算にマルコフ連鎖を使う手法，つまり計算アルゴリズムとしてマルコフ連鎖を使うこともあります．
  • 前回の演習問題，いろいろあってできなかったのですが，今回の演習問題にくっつけてだしてもよいですか？ すみません。
    --- 受講者が少なすぎて余裕があるので大丈夫です．提出をお待ちしております．
  • とあるラーメン屋で3秒ルールを使ったら，次の日感染性胃腸炎になってしまいました (これが原因かわからないけど)。外で3秒ルール，キケンです。
    --- お大事に．何に3秒ルールを使ったのかは不明ですが，それがスープだったのなら，類稀な勇気だと感じます．
  • 時間はあるのでしっかり復習して試験に臨みたいと思います．
    --- はい，質問がある場合はメールでもよいのでお尋ねください．
  • 試験頑張ります．ありがとうございました．
    --- こちらこそありがとうございました．しっかりと準備してきてください．
  • グラフとネットワークから離散数理工学にかけて，約1年間，ありがとうございました。特に，証明のかきかたについて，先生の講義でたくさん勉強できたと思っています。
    --- こちらこそありがとうございました．証明は重要な技能なので，私の講義の中では力を入れています．楽しんでいただけて何よりです．
  • とても楽しく，分かりやすい講義をありがとうございました．
    --- こちらこそありがとうございました．
• 1/26 (13) 離散確率論：マルコフ連鎖 (基礎)
  • コメントありがとうございました．急遽，板書による講義となりご迷惑をおかけしました．
  • 板書速くても，プリントがあるので大丈夫そうです．
    --- ありがとうございます．板書がはやいのは自覚しているのですが，それぐらいのスピードでやらないとやるべきことが終わらないのです…．
  • スライドでの説明は、発表する人によっては、内容が追えないことがありますが、岡本先生の発表はていねいなので、ノートをとる時間を考えなくても、スライドがいいです。
    --- ありがとうございます．スライドで行うときは，「見返してちゃんと理解できること」を心がけています．その場で理解できれば一番よいですが，そうでないことも多いので，そこは気をつけています．皆さんも，そのような気持ちでメモをとることをお薦めします．
  • 手元にプリントがあるので良かったですが、板書だけではきつそうに感じました。あと、最近はつくづく今まで習ったことが大事だと感じます。(線形代数とか…)
    --- 今まで習ったことが有機的にどんどんと結びついてきます．世界は1つなのですから．
  • 雪がまだとけきらないくらいさむいです…。
    --- そうですね．健康には注意して下さい．
  • 実際に天気予報がこのマルコフ連鎖で得られていると考えるとドキドキです．
    --- 講義では例として天気の変化をマルコフ連鎖で表しましたが，実際の天気予報では大規模な数値計算シミュレーションを行っています．気象庁のページに解説があります．
  • 演習問題を進めているのですが，第11回の配列の最小値を求める問題で，$\mathsf{E}[X_n] \leqq \mathsf{E}[X_{n-1}] + 1 + \frac{1}{n} \mathsf{E}[X_n]$ を導くのに，右辺の $\mathsf{E}[X_n]$ に$\frac{1}{n}$がつく理由がわかりません．
    --- アルゴリズムの6行目で何がおきるのかということを考えて下さい．いつ「p < x」という条件が満たされて，それがどの確率で起きるのか考えて下さい．
• 1/19 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
  • コメントありがとうございました．
  • 雪合戦できたので昨夜は楽しかったです
    --- おめでとうございました．:-)
  • 中央値トリックにおいて，$\displaystyle t \geq \frac{8p(1-p)}{\varepsilon^2}$とする，の8は何ですか？ (聞き逃していたらすみません…)
    --- 聞き逃しではなく，説明していない部分でした．8でなくてもよいです．ここを8でない実定数で2eよりも大きなものにすれば，アルゴリズムはうまく動きます．講義でここを8にした理由は，計算を楽にするためです．
  • 中央値トリック，想像以上のヒストグラムがでてきたのでびっくりしました。ちょっと計算法をかえるだけでこんなにかわるものなのですね。
    --- そうなんですね．それが不思議なところで，乱数の使い方に工夫の余地が十分にあることを教えてくれていますね．
  • 中央値トリックは名前の通り非常にトリッキーな方法だと思いました。
    --- 中央値は「ロバスト」な統計量として知られていて，外れ値の存在に対して頑健です．それによって，少しのグループの中で大きな誤差が出ても全体として誤差が出にくくなるという仕掛けになっているのだと思います．
• 1/12 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
  • コメントありがとうございました．
  • 今朝は電車の遅延で大変でした．
    --- 冬場は天候の影響もあったり，人々の心が不安定になったり，いろいろなことが絡み合って遅延が起きやすいので，気をつけて下さい．
  • 雨が降ってだいぶ寒くなってきましたが、がんばります。
    --- はい，がんばってください．
  • 急に寒くなったのでかぜを引かないようにしたいです。
    --- 急に寒くなりましたね．かぜを引かないように注意して下さい．
  • 明け方雪が降ったみたいなのでそろそろ雪合戦ができるかと，楽しみです。
    --- 英語でも「Yukigassen」と呼ぶようですね．昭和新山国際雪合戦というのもあるようなので，これも楽しみですね．
  • いたるところに調和数がでてきて，不思議な気持ちになります。
    --- 調和数は非常に重要な概念なので，離散数学ではよくでてきます．慣れていって下さい．
• 1/5 (10) 離散確率論：確率的離散システムの解析
  • コメントありがとうございました．今年もよろしくお願いします．
  • あけましておめでとうございます。今年もよろしくおねがいします。
    --- よろしくお願いします．
  • 新年あけましておめでとうございます．今年もよろしくお願いたします．
    --- よろしくお願いします．
  • 問題9.12みたいな，独立であることを示す問題，むずかしかったです。
    --- 定義にしたがって証明して下さい．
  • パスワードがmd5でハッシュ化してから照合しているとしたら，$\sqrt{2^{128}}$ 回ぐらいランダムな文字列でチャレンジしたら1/2以上の確率でログインできる，といえたりして，$m \geq \sqrt{(2 \ln 2) k} + 1$ の上界，おもしろいです。
    --- 誕生日攻撃で検索してもらうと，いろいろと情報が得られます．誕生日のパラドックスは応用が多くて重要なトピックなのです．
  • 誕生日のパラドックスが起きる大きな要因として、そもそも確率を自分と同じ誕生日の人がいる確率だとかんちがいする人が多いことだ，と昔この話を聞いたとき思いました。
    --- そうですね．その間違った説明をしている本もあったりするので，困ったものです．
  • 自分の親と友達が同じ誕生日だったり自分と同じ誕生日の知り合いがいるので，30人も集まれば70%の確率で同じ誕生日の組がいるのは高いようでそのぐらいなのだと思いました。計算してみると直感と違うように感じてもよく考えてみると経験的に納得できたりできなかったりして楽しかったです。
    --- 直感や経験と，それを裏付ける数学的・論理的考察が組み合わさって理解できるので，よいですね．
  • お正月に帰省したら、地元の大きな本屋さんが、おそらく、Amazon.comのせいで潰れていました。その本屋では、本、CD、ゲーム、文房具を取りあつかっていたので、地域の文化的損失が著しいはずで、このようなことが日本全国でおきていると思うと、この国の未来が心配で、おもちものどを通らなかったです。海外では、Amazon.comに制限をつけて、本屋を守ろうとする動きがありますが、先生はどう思いますか？
    --- おそらく，どんな業種も今まで通りのやり方で商売をしていては立ち行かないと思います．時代の流れは早くなっています．社会における役割がアピールできないのならば，潰れていくのは仕方ないのか，と思います．
• 12/15 (9) 離散確率論：確率の復習と確率不等式
  • コメントありがとうございました．来週は中間試験です．
  • 来週試験頑張ります
    --- はい，よろしくお願いします．
  • 中間試験がんばります。
    --- はい，しっかりと準備して臨んで下さい．
  • いままでに解けなかった問題，再チャレンジしてみましたがやっぱりどれもむずかしかったです。再提出が多くなってしまい (しかもほとんど完答できなかった) すみません。添削よろしくお願いします。
    --- コメントをつけたものを居室前のレポート返却箱にいれましたので，お持ち帰りください．
  • 期待値の引数に何をいれてもよい (たとえば，E[X²]とかE[7]など) はなんだか不思議なかんじで慣れるのに時間がかかりそうです。
    --- Xが確率変数であるとき，X²も確率変数なので，そのような書き方ができるわけです．とても便利なので，使いこなせると考えることができる範囲が広がっていきます．ぜひ身につけて下さい．
  • モンティ・ホール問題で扉をかえた方が確率が上がると数学的にわかっていても自分は扉を変えない気がします。
    --- Wikipediaでモンティ・ホール問題の項目を見てみると，いろいろなバージョンの違いも説明しています．ぜひ見てみて下さい．
  • マルコフの不等式の威力を実感しました。
    --- マルコフの不等式はよく出てくるので，ぜひ使いこなせるようになって下さい．
  • 年越しの瞬間はなにをする予定ですか？二年参りですか？それともお布団の中ですか？
    --- 瞬間にお布団の中にいることはないと思いますが，お参りにもいっていないと思います．未定です．;-)
• 12/8 (8) 離散代数：有限体の応用
  • コメントありがとうございました．次回から離散確率論の内容になります．
  • 中間試験がちかづいてきたので，解けなかった問題，再レポート頑張ります。
    --- はい，よろしくお願いします．
  • 中間試験頑張ります
    --- しっかりと準備をしてきてください．
  • 位数q=12の場合でさえ，有限射影平面の存在がありえないことを計算するの，たいへんなのでしょうか。
    --- 正直なことをいうと，私自身が試したことはないので，わかりません．ただ，まだ解決していない，という現状を見ると，難しいのだとは思います．
  • 射影と聞くと，これまでの学習ではKernelとか直射影とかを思い浮かべます．
    --- 「射影」というのは，だいたい「次元を下げること」だと思っていただければよいです．授業で扱ったのは，$\mathbb{F}_q^3$ における平面と直線を考えましたが，有限射影平面における用語では，それぞれ直線，点と呼ばれることになります．実際，ある意味で次元を下げているのですが，細かい説明ははぶきます．
  • 色々な関係性が出てきて話に追いつくのがやっとでした．
    --- そうですね．ややこしい部分が多かったので，復習して下さい．
  • 紅茶派ですか？ コーヒー派ですか？
    --- コーヒーの方を頻繁に飲みますが，紅茶も緑茶も飲みます．気分で変えます．
• 12/1 (7) 離散代数：多項式環による有限体の構成
  • コメントありがとうございました．
  • $g(x) \in \mathbb{Z}_p[x]$ を $m$ 次の多項式としたとき，$\mathbb{Z}_p[x]/(g(x))$ の要素が次数 $m-1$ 以下の $\mathbb{Z}_p[x]$ の中のすべての多項式になるというのが，あまりよくわかりませんでした。
    --- 講義では口だけで説明したので，ここでもう一度繰り返します．
    まず，「$\mathbb{Z}_p[x]/(g(x))$の要素である多項式は次数$m-1$以下である」ことを証明します． $\mathbb{Z}_p[x]/(g(x))$の要素である任意の多項式 $r(x)$ を考えます．多項式 $r(x)$ は $\mathbb{Z}_p[x]$の多項式を $g(x)$ で割った剰余なので，その次数は $m-1$ 以下でなければなりません．
    次に，「次数 $m-1$ 以下の $\mathbb{Z}_p[x]$ の多項式は必ず $\mathbb{Z}_p[x]/(g(x))$ の要素になる」ことを証明します． $\mathbb{Z}_p[x]$ の要素である多項式で次数 $m-1$ 以下のものを任意に選んで $f(x)$ とします．このとき，$f(x)$ の次数が $g(x)$ の次数よりも小さいので，$f(x)$ を $g(x)$ で割った剰余は $f(x)$ 自身になります．つまり，$f(x)$ は $\mathbb{Z}_p[x]/(g(x))$ の要素となります．
  • $\mathbb{Z}_p[x]/(g(x))$ の元を係数とした，$y$ の多項式 $(\mathbb{Z}_p[x]/(g(x)))[y]$ ？ とかあれば (もうよくわからない)，またこれも多項式環になったりするのかなと思いました。
    --- 正しいです．前回の内容では，多項式の係数としてどんな体を使ってもよかったので，その体として $\mathbb{Z}_p[x]/(g(x))$ を持って来れば，前回の内容はそのまま通用しますし，その多項式環における既約多項式を持ってきて，剰余環 $(\mathbb{Z}_p[x]/(g(x)))[y]/(h(y))$ を考えれば，有限体を構成できます．ただし，$g(x)$ の次数が $m$ で，$h(y)$ の次数が $\ell$ のとき，出来上がる有限体の位数は $(p^m)^\ell$ になります．しかし，$(p^m)^\ell = p^{m\ell}$ なので，これは，$\mathbb{Z}_p[x]$ を次数 $m\ell$ の既約多項式で割ってできる剰余環と同型になります (同型になることの証明は必要ですが)．その意味では，そこまで考える利益はあまりないことになります．
  • 位数9の有限体をつくる時の計算が大変でした。
    --- 確かにそうですね．でも，一度手でやってみると，その原理が分かってよいと思うので，完成させてください．
  • 筆記用具を忘れないようにしたい。
    --- はい，よろしくお願いします．
  • 風邪気味で今週きついです
    --- 病院に行きましょう．
  • 研究室配属が今からドキドキです。
    --- いよいよですね．しっかりと決断をして下さい．
  • 今年も早いもので、もう12月になってしまいましたが、今年やり残したことなどはありますか？
    --- たくさんありすぎて書ききれません…。
• 11/24 (6) 離散代数：多項式環
  • コメントありがとうございました．機器トラブルで遅れてすみません．次回はあまり気にせずやっていきます．見えにくい場合は前の方の席に座って下さい．
  • 調布祭のおかげで、体調が40%ぐらいです。
    --- お疲れ様です．しっかりと回復しましょう．
  • 調布祭楽しかったです．
    --- 大学祭は大切なイベントなので，しっかりと盛り上がれてよかったです ;-)
  • 調布祭で何かご覧になりましたか？ 屋台とかステージとか。
    --- 成見研の謎解きゲームにいってきました．楽しかったです．
  • 既約多項式，なんだか素数みたいだなと思いました。もし，似た性質なら，素数pを法として体がつくれたように，既約多項式を法とした加算，減算，乗算，わり算でまた体がつくれるのでしょうか。
    --- まさにそれが次回のテーマです．お楽しみに．
  • 問題4.6は簡単な一般項になりましたが，簡単な一般項からどうやって複雑な漸化式をつくるのかなと不思議です。
    --- これは確かに難しいですし，不思議ですね．別の見方をすると，1つの数列は幾通りもの異なる漸化式から得られることがあるわけですね．
• 11/17 (5) 離散代数：整数と有限体
  • コメントありがとうございました．
  • 「互いに素」というのは非常に強力な性質だということが分かりました。
    --- その通りですね．そのため，素数がとても役に立つわけです．
  • まえに実験でRSA暗号の実装をしたときに法nについてのaの逆元を求めるコードを書いたのを思い出しました (そのときはきちんと理解していない)。拡張ユークリッド互除法とか言われてました。
    --- 拡張ユークリッドの互除法ですね．授業の中でやった「ユークリッドの互除法を逆にたどっていく」というプロセスを前から反復的に (あるいは再帰的に) やっていくと，拡張ユークリッドの互除法が得られます．
  • 年末も近くなり，世間では今年の流行語が話題になっていますが，先生の今年の流行語はなんですか？
    --- なぜか今年一番ワクワクしたのは，5/17の「大阪市特別区設置住民投票」です．流行語でもなんでもないかもしれませんが，ユーキャン新語・流行語大賞のノミネート語に「大阪都構想」があるので．
  • いつも眠い眠いばかり言っているので…コーヒーはブラック派ですか？私はミルクを入れないと飲めません。
    --- どちらでも飲みますが，たいていブラックです．
• 11/10 (4) 数え上げの基礎：漸化式の解き方 (発展)
  • コメントありがとうございました．次回から「離散代数」になり，趣が変わります．お楽しみに．
  • とても寒くなってきたのでカゼに気をつけましょう
    --- ありがとうございます．お互いに気をつけましょう．
  • 寒いからかとても眠かったです。
    --- 11/16から教室にも暖房が入ります．
  • 最近、少し高い買物をしようとしているのですけど、先生は学生時代に高い買物をしたことはありますか？又、何を買いましたか？
    --- ノートPCでしょうか．IBMのThinkPadで，Windows 98がのってました．
  • 一瞬，カタラン数をカタラン教に空目しました。
    --- 「カタラン教」というものは存在しないようです ;-)
  • 問題3.6，うまくいくような不等式を考えるのはむずかしかったです。
    --- 不等式は難しいですね．しかし，現実の問題では漸化式を厳密に解くことがほとんど不可能な場合も多いので，不等式で上界を与えるという手法をぜひ身につけて下さい．
  • MICS実験第3ラウンドは先生の題目なのですが，事前に予習しておくとよさそうなことなどありますか？
    --- 特にないですが，実験のページが既にありますので，そこにかかれている言葉を見て，関連しそうなものを調べてみて下さい．
• 10/27 (3) 数え上げの基礎：漸化式の解き方 (基礎)
  • コメントありがとうございました．
  • 3項間漸化式の計算が難しかったです。
    --- そうですね．まずは原理を理解して下さい．
  • 無理矢理計算頑張って漸化式を解くのも大変だけど，上界を導く方はちょっとヒラメキが必要そうで…そういうのは苦手なので練習が必要です。
    --- はい，演習問題もありますので，そこで練習して下さい．
  • 帰納法，調べてみると，数学的帰納法，累積帰納法 (今日つかった)，構造帰納法などいろいろあって，おもしろそうでした。整礎関係というのが一番一般的なのでしょうか？
    --- 「一番」かと言われると，私は数学基礎論について詳しくないのでちゃんとわからないです．しかし，整礎関係がいろいろなところで重要な役割を果たしているのは確かです．
  • 入力に対し，logでへっていくのを視覚で感じるのは楽しいですね。(前回のプログラムの出力とか)
    --- そうですね．「計算は現象」という (私の) 格言があります．物理や化学と同じように，計算は科学の対象となり，そこでは，計算という現象を深く理解したいという営みが生まれるわけです．
  • 急に冷えこみ始めて鼻水が止まりません
    --- 季節の変わり目ですので，体調管理には十分注意して下さい．
  • 遅刻して申し訳ありませんでした！
    --- 謝る必要は全然ありません ;-)
• 10/20 (2) 数え上げの基礎：漸化式の立て方
  • コメントありがとうございました．
  • 内容が難しくなってきたので復習が必要
    --- はい，演習問題を通して復習をして下さい．レポート提出は歓迎します．
  • 演習問題を解いてみて，数学の力が衰えているのをとても実感しました。
    --- 実際に手を動かすのは重要なので，励行して下さい．
  • 組合せ的解釈を考えるのは，思っていた以上に難しかったです。
    --- うまく解釈ができると，だんだん楽しくなってきますよ．
  • 目が悪い等の種々の理由でPCからスライドを見ています．が，今日は充電を忘れました．残念．
    --- 充電は社会的な問題だと思ってます．なんとか解決する必要がありますね．
  • Collatz予想は、偶数が続く割合と奇数が続く割合を考えていくのかな？もしくは、2つのでる割合で…難しそう！！
    --- 難しいですね．アルゴリズムが停止することを証明するためには，何かが単調に減少する，あるいは，増加する，ということを観察することが多いのですが，そのような手法がコラッツ予想に使えるのかよく分からないのです．
  • こんど，とある大学院大学の説明会にあそびにいってみようと思っているのですが，注目しておくべきこととか，聞いてみるとよいこととかありますか？
    --- 大学院なので，まず，研究の質の高さです．これは重要です．研究の質というのは「楽しそう」とか「面白そう」という感覚では分かりません．研究成果がどこで発表されているのか，どのように発表されているのか，どのように受け止められているのか，どのような世界と関係を持っているのか，といういろいろな側面を捉えることが重要です．そして，次は学生支援です．例えば，奨学金とか報奨制度とか学生宿舎の充実とか，です．地方の大学の場合は，就職活動のための資金的援助があるか，とか，そういうことも重要かと思います．私は学生・教員として (現在も含めて) 6つの大学に所属していましたが，文化が大学ごとに大きく違うことは身をもって知っています．説明会だけでは分からないかもしれないですが，違いがあるのだということに注意しながら見ていると何かが浮かび上がってくるかと思います．
    あと，教員や職員だけではなく，学生にも聞くことができればよいです．それによってバランスのとれた情報が得られると思います．
  • 近ごろ、AKBやら地下アイドルやら、二次元アイドルが、流行していますが、先生はアイドルに夢中になったことはありますか？
    --- アイドルに夢中になったことはないですね．私の世代だと，大学生のときにようやく「モーニング娘。」がでてきたぐらいです．中学生や高校生のときに，今でいうような国民的アイドルはいなかったような気がします．
• 10/6 (1) 数え上げの基礎：二項係数と二項定理
  • コメントありがとうございました．以下のように掲載されます．
  • 前期に引き続き，後期もよろしくおねがいします。
    --- はい，こちらこそよろしくお願いします．
  • 予想以上に人が少なくて驚きました．
    --- 私も驚きました．配布物は35部用意したのですが．
  • グラフとネットワークのときよりも受講者の数がぐんと減っていて驚きました．
    --- 1限だからでしょうか．それを理由にされるのも困るのですが．
  • 1限つらい．
    --- しっかりと起きてきてください．
  • 1限で眠くて頭がぼーっとしているのにわかりやすかったです。
    --- しっかりと目を覚ましてから来ると，もっと理解できると思います．
  • 夏のよどんだ空気から、冬の澄んだ空気に変わってきましたね。秋といえば「食欲の秋」や「芸術の秋」など様々な秋がありますが、先生が一つ選ぶとしたら、どの秋ですか？
    --- 食欲の秋ですね．きのこが好きです．
  • グラフとネットワークの講義を受けていた頃はまさかヤクルトが優勝するとは思いませんでした．
    --- その通りですね．一時期はDeNAが首位独走だったんですよね．
  • 初回授業の追加問題でいきなりつかえてしまった…。
    --- つかえてしまってもよいので，時間をかけてできるようにしていきましょう．質問もお待ちしています．
  • 1.10の下界の問題，上界と同じようにやると，$1+x \leq e^x$の不等式の向きがよくなくてむずかしいです。
    --- $x>-1$のとき，$\displaystyle \frac{1}{1+x} \geq \frac{1}{e^x}$となることに着目してみてください。
  • 証明のあたりの式の展開がわかりやすくてよかったです．
    --- 細かい部分もあるので，丁寧に追っていって下さい．
  • 二項係数が配列と見間違えそうになります．
    --- 二項係数の記法は慣れるまでちょっと大変かもしれませんが，世界中で標準的に使われている記法なので，身につけて下さい．
  • ヤギと新車の問題がなぜ手を変えた方が良いのかとても不シギです．
    --- 不思議ですね．これについては後の方の講義でしっかりとやる予定です．

• 中間試験と期末試験により，成績の評価を行います．
• 全体の成績
  • 成績 = min{100, 中間試験の素点+期末試験の素点の小数点以下切り上げ}
  • 入学年・学科によって，「離散数理工学」の成績が「シミュレーション理工学第二」，「有限要素法」の成績として報告されている場合があります．注意して下さい．
  • 得点分布 (中間試験と期末試験の少なくとも一方を受験した受講者のみ対象)
    
  • 受講者数 (履修登録者数相当) は12で， 90点以上 (S) が3人 (約25%)， 90点未満80点以上 (A) が1人 (約8%)， 80点未満70点以上 (B) が1人 (約8%)， 70点未満60点以上 (C) が1人 (約8%)， 60点未満 (D) が6人 (約50%) です．
  • 中間試験と期末試験の少なくとも一方を受験した受講者数は9で， 90点以上 (S) が3人 (約33%)， 90点未満80点以上 (A) が1人 (約11%)， 80点未満70点以上 (B) が1人 (約11%)， 70点未満60点以上 (C) が1人 (約11%)， 60点未満 (D) が3人 (約33%) です．
• 期末試験 (2/16)
  • 期末試験問題
  • 採点：1問15点満点，合計60点満点 (0.5点刻み)
  • 得点分布
    
  • 受験した人の数は7，平均点は41.29 (60点満点)． 45点以上 (S相当) が2人 (約29％)， 45点未満40点以上 (A相当) が1人 (約14％)， 40点未満35点以上 (B相当) が1人 (約14％)， 35点未満30点以上 (C相当) が2人 (約29％)， 30点未満 (D相当) が1人 (約14％) です．
  • 得点掲示 (辞書順に並べています)

    0714	60
    Ansible	21
    NIKUUU	44
    RADIO	36.5
    strega	60

  • 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
  • 講評
    • 総評：できている問題とできていない問題の差が大きいと感じました．
    • 問題1：チェルノフ上界を導く問題．演習10.8と同じ問題．よくできていました．昨年も同じ問題を出したので，対策ができていたのかもしれません．小問1で必要になるのは期待値の線形性ではなく，確率変数が互いに独立であることです．間違えている人がいましたので，注意して下さい．
    • 問題2：乱択アルゴリズムの解析．小問1, 2はよくできていましたが，小問3があまりできていませんでした．小問3はそのまま数学的帰納法を使って証明するのが最も簡単だと思います．一般項を導出するのはなかなか難しいかもしれません (前半の講義内容を思い出せば可能ではありますが)．
    • 問題3：マルコフ連鎖の問題．演習13.6の数字を変えたもの．よくできていました．
    • 問題4：ランダムウォークの問題．演習14.7と同じ問題．細かいミスが目立ちました．頂点1に隣接している頂点の数はn-1ですし，そこから頂点nに行かなかった場合，頂点1に戻るためにもう1回移動することを数えていない答案が多く見られました．
• 中間試験 (12/22)
  • 中間試験問題
  • 採点：1問15点満点，合計60点満点 (0.5点刻み)
  • 得点分布
    
  • 受験した人の数は9，平均点は38.56 (60点満点)． 45点以上 (S相当) が4人 (約44％)， 45点未満40点以上 (A相当) が0人 (約0％)， 40点未満35点以上 (B相当) が0人 (約0％)， 35点未満30点以上 (C相当) が2人 (約22％)， 30点未満 (D相当) が3人 (約33％) です．
  • 得点掲示 (辞書順に並べています)

    0714	55
    11235	23
    a4508	25
    abctoz	54
    CTSTR	48
    NIKU	50.5
    oasis	33
    vagrant	25.5

  • 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
  • 講評
    • 総評：できている人とできていない人の差が大きいと感じました．
    • 問題1：アルゴリズムの計算量を評価する問題．一番できていない問題でした．(1) についてはn=1のときだけ等号が成り立たないので，そこに注意して下さい．数学的帰納法で進めようとすると，そこだけ別の取り扱いが必要になります．(2) については，証明すべき式がどの範囲のnに対して成り立つのか明示していない場合は減点しています．
    • 問題2：母関数を用いて数列の一般項を導出する問題．演習問題4.7と同じ問題．できている人とできていない人の差が大きな問題でした．演習問題と同じ問題なので，しっかりとできてほしかったです．
    • 問題3：モジュラ算術と二項定理に関する問題．演習問題5.11と同じ問題．できている人とできていない人の差が大きな問題でした．(1) について，pが素数であることをどこで使っているのか明示できていない場合は減点しています．
    • 問題4：多項式が既約であることを証明する問題．よくできていました．既約でないからといって，根を持つとはいえないので，注意して下さい．この問題で考える多項式に対しては正しいのですが，それは確認する必要があります．
• 過去の試験問題 (注意：内容や説明法，試験範囲は変化しています．)
  • 2014年度：中間試験 | 期末試験

• 10/6 (1) 数え上げの基礎：二項係数と二項定理
• 10/13 休講 (体育祭)
• 10/20 (2) 数え上げの基礎：漸化式の立て方
• 10/27 (3) 数え上げの基礎：漸化式の解き方 (基礎)
• 11/3 祝日 (文化の日)
• 11/10 (4) 数え上げの基礎：漸化式の解き方 (発展)
• 11/17 (5) 離散代数：整数と有限体
• 11/24 (6) 離散代数：多項式環
• 12/1 (7) 離散代数：多項式環による有限体の構成
• 12/8 (8) 離散代数：有限体の応用 ※創立記念日であるけれども，授業が行われる
• 12/15 (9) 離散確率論：確率の復習と確率不等式
• 12/22 中間試験
• 12/29 冬期休業
• 1/5 (10) 離散確率論：確率的離散システムの解析
• 1/12 (11) 離散確率論：乱択データ構造とアルゴリズム (基礎)
• 1/19 (12) 離散確率論：乱択データ構造とアルゴリズム (発展)
• 1/26 (13) 離散確率論：マルコフ連鎖 (基礎)
• 2/2 (14) 離散確率論：マルコフ連鎖 (発展)
• 2/9 授業等調整日 (予備日)
• 2/16 期末試験

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