離散最適化基礎論

岡本 吉央

テーマ：組合せ最適化におけるマトロイドの役割

注意：内容は毎年変わります

ショートカット：講義資料 | コメント | 試験 | 公式シラバス | スケジュール | 過去の講義

講義資料

• 1/29 (12) マトロイドの合併
  • スライド | 印刷用スライド | メモ欄付き印刷用スライド | 演習問題はありません
• 1/22 (11) マトロイド交わり定理：アルゴリズム
  • スライド | 印刷用スライド | メモ欄付き印刷用スライド | 演習問題
• 1/8 (10) マトロイド交わり定理
  • スライド (1/14修正) | 印刷用スライド (1/14修正) | メモ欄付き印刷用スライド (1/14修正) | 演習問題
• 12/25 (9) マトロイドの交わり
  • スライド (12/27修正) | 印刷用スライド (12/27修正) | メモ欄付き印刷用スライド (12/27修正) | 演習問題 (1/14修正)
• 12/18 (8) マトロイドに対する操作
  • スライド (12/18修正) | 印刷用スライド (12/18修正) | メモ欄付き印刷用スライド (12/18修正) | 演習問題 (12/25修正)
  • 前回の続きからやります
• 12/4 (7) マトロイドのサーキット
  • スライド (12/9修正) | 印刷用スライド (12/9修正) | メモ欄付き印刷用スライド (12/9修正) | 演習問題
• 11/27 (6) マトロイドに対する貪欲アルゴリズム
  • スライド | 印刷用スライド | メモ欄付き印刷用スライド | 演習問題 (11/27修正)
• 11/13 (5) マトロイドとグラフの全域木
  • スライド (11/27修正) | 印刷用スライド (11/27修正) | メモ欄付き印刷用スライド (11/27修正) | 演習問題 (11/27修正)
• 11/6 (4) グラフとマトロイド
  • スライド (4/20修正) | 印刷用スライド (4/20修正) | 演習問題 (4/20修正)
  • 前回の続きからやります
• 10/30 (3) マトロイドの基と階数関数
  • スライド (11/7修正) | 印刷用スライド (11/7修正) | 演習問題
  • 演習問題3.6と3.10の提出締切は延長
• 10/23 (2) マトロイドの定義と例
  • スライド (10/26修正) | 印刷用スライド (10/26修正) | 演習問題
• 10/9 (1) 組合せ最適化におけるマトロイドの役割
  • スライド (10/9修正) | 印刷用スライド (10/9修正) | 演習問題

• 1/29 (12) マトロイドの合併
  • コメントありがとうございました．無事，最終回を迎えることができました．
  • 半年間ありがとうございました．マトロイドの日本語の本が少なく，学部生のときから気になっていた分野でしたが，今回学ぶことができてよかったです．
    --- こちらこそありがとうございました．マトロイドに関する情報が日本語でなかなか得られにくいのは事実だと思います．また，今回は組合せ最適化との関連を通して紹介しましたが，それ以外の動機からマトロイドを考えることもあります．情報源によって動機が異なるので，それも近寄りにくさを助長している気がします．一方で，そのように多様な動機を持つことがマトロイドのよいところでもあるので，もしかしたら後々，別の動機からマトロイドに触れることになるかもしれません．そのときには今回勉強した内容も役立つと思います．
  • マトロイドを実装するには大変そうだと思いました．最適化とどう結びつくのかがあまり分かっていないので勉強していきたいと思います．
    --- この授業で触れたマトロイドの側面でも，まだ入り口の段階で，この奥にはまだ深い世界があります．ぜひ勉強して下さい．
  • 内容が変わるのであれば来年も受講したいです．
    --- いわゆる「もぐり」は歓迎しますので，よろしくお願いします．なお，来年はマトロイドから離れる予定です．
  • 全体を通して丁寧な説明で総じて分かりやすく感じました。
    --- ありがとうございます．難しい所もあり，私もところどころ詰まったりしましたが，理論のフレーバーを感じることが第一の目的なので，それは達成できたのではないかと思います．
  • 半年間ありがとうございました．かなり難しい内容と感じましたが，テストを解けるようにがんばりたいと思います．
    --- こちらこそありがとうございます．試験にはしっかりと準備をして臨んでください．
  • 正解の分からない問題を勉強する場合　どうやったら合格点が貰えるのでしょうか。
    --- 自分の書いた証明がしっかりと証明になっていることを自分で理解する，ということが重要です．なんとなく証明を書いていたり，ぼんやりしていると，それは理解できていない証なのかもしれません．
  • e1，e2などの記号は口頭だとやはりこんがらがってしまいますね．うさぎさんやカメさんなど周知のシンボルを使うとイメージしやすいのかなぁなんて考えていました．サザエさんやちびまる子ちゃんとかもシンボルとして優秀だなぁと思ったことがあります．
    --- ラテンのアルファベットはAからZまでしかないので，とても不自由だと感じます．私は日本語の文字を使ってもよいのではないかと思っているのですが，その考えは広く受け入れられなそうです．
• 1/22 (11) マトロイド交わり定理：アルゴリズム
  • コメントありがとうございました．次回は今回の続きからやります．
  • 今回は最大共通独立集合問題に対するアルゴリズムの正当性の証明の前半で終わってしまってちょっと残念でした。図をかきながら証明を追っていかないと理解できそうにないので，復習が大変になりそうだと思いました。
    --- 図を自分で描いて，式の内容を理解するのは重要ですので，是非進めて下さい．
  • アルゴリズムの動作は理解できたので色々な問題に対して実行して確認しておきます．
    --- 例を自分で作ることができると，完全な理解にかなり近づくので，試してみて下さい．
  • 今日の授業は半分以上理解できないです。どうしたらいいですか？
    --- 講義回数も10を超えて難しくなっているので，理解できなくてもしかたないかもしれません．あまり悲観しないで下さい．
  • e₁, e₂, ...などで図と口頭で言っていることがこんがらがってしまいました．
    --- そうですね．冷静にならないといけないですね．
  • 二部グラフのマッチングのときは増加道が最短でなくてもよかったと思うのですが、最短じゃないとうまく動作しない例があるのでしょうか？
    --- あります．ご指摘は正しく，最短というか，ショートカットのない増加道を見つける必要があります．そうではなく，ショートカットのある増加道を使うとうまくいかない場合があり，そのような例も存在します．見つけるのはちょっと難しいかもしれませんが．
  • 二部グラフの最大マッチング問題や最小有向木問題以外にどんな問題がマトロイドによって定式化できるのか気になりました．
    --- 次回，マトロイドの合併をやります．マトロイドの合併はマトロイドの交わりを使って解かれるので，それも範疇に入ることになります．
  • 出題対象は発展以外とのことですが、復習、補足、追加問題が対象という認識で良いのでしょうか．
    --- はい，その認識でよいです．
  • 卒業発表がせまっていますね．失敗なくやりとげられるか心配です．
    --- 先人もやりとげてきたことなので，しっかりとやりとげて下さい．
  • 修論が気がかりであまり内容が入ってきませんでした。
    --- 気がかりになりますね．いろいろなことを平行して進めていく必要があるので，時間の管理に気をつけて下さい．
• 1/8 (10) マトロイド交わり定理
  • コメントありがとうございました．掲載が遅くなりすみません．
  • あけましておめでとうございます。今年もよろしくお願いします。
    --- あけましておめでとうございます．
  • 明けましておめでとうございます．
    --- あけましておめでとうございます．
  • あけましておめでとうございます．
    --- あけましておめでとうございます．
  • 平成27年という表記に慣れないまま平成28年になってしまいました．
    --- 慣れなくてよかったのかもしれませんね ;-)
  • ここまで複雑な数学的帰納法は初めて見ました．
    --- 帰納法の仮定に使い方はそれほど複雑ではありません．その他の部分でいろいろなことを確認しないといけないので，そこが骨の折れる部分ではあります．
  • 除去と縮約が出てきたあたりから (とくに縮約) 少し証明についていけなかったのでよく復習しておきます．
    --- 前に登場したものが再び出てきているので，復習をお願いします．
  • 今回はマトロイドの交わり定理の証明が長くて大変でした．ちゃんと復習しようと思いました．
    --- これでも，ある本では18行の証明です．別の本では，26行だったり，18行だったりします．どの本でもおよそ，1ページの半分ぐらいしか使っていません． それを細かくかみ砕いていくと，このようになるわけです．
  • 今日は最適化という感じでした．
    --- 双対性は最適化における重要な道具なので，しっかりと身につけて下さい．
  • 先生は問題が解けなかったとき，証明が思い付かないときはどうしますか．
    --- いろいろな場合がありますが，主なものを挙げます．(1) あきらめて，他の問題に移る．そのために，日ごろから多くの問題を蓄えておく．(2) たくさん例を作って，問題に対するヒントを得る．プログラムを書くことを含む．これで解決することが割とある．(3) 寝る．次の日になると思いつくことがある，と期待しているが，それが起こったことはない．(4) 他の人に聞く．私として，これは最終手段に近い．
  • Emacsのorg-modeの表で縦棒が出せません．助けてください．
    --- 細かい状況が分からないので，助けようがありません ;-)
• 12/25 (9) マトロイドの交わり
  • コメントありがとうございました．今年最後の授業でした．来年もよろしくお願いします．
  • 今日、サンタさんからチョコレートをいただきました。ありがとう。
    --- 私はサンタさんではありません．
  • チョコレートありがとうございました．
    --- いえいえ．どうも．
  • チョコレートおいしかったです。ありがとうございました。
    --- いえいえ．どうも．
  • チョコレートはノドに悪いらしく歌手や役者にとってはご法度らしいです。
    --- そうなんですね．ありがとうございます．今後気をつけます．
  • 今回はクリスマス回でとても楽しかったです。でもOxford University PressのMatroid Theoryがプレゼントされなかったのでちょっと残念でした．
    --- プレゼントは高価過ぎると，もらう方が気まずくなるという事例を何度か経験したので，このような形になりました．
  • 図や説明で概念はわかるけど文字(式)にするとややこしい内容だった印象
    --- その通りですね．証明を自分で考えてみると，同じような証明になることが結構あり，そうすると，書かれている証明が分かるようになる，ということもあるので，挑戦してみて下さい．
  • だんだんマトロイドの考え方の感覚がわかってきて授業内で理解できるようになってきました．
    --- それは慣れてきた証拠ですね．単純なものの積み重ねで授業を構成しているつもりなので，今後も気を抜かずについてきてください．
  • マトロイドの交わりの話は実用性が実感できて楽しいです。
    --- マトロイドの交わりを使うことで，いろんな問題が解けるようになるというのは面白いですね．
  • 交わりの話を聞いて2と3の違いの話を思い出しました．
    --- これですね (PDFが開きます)．まさにこの話題に合っていますね．
  • 段々と内容が複雑になっているので追加問題等に解き方の筋道などのヒントをもって付けて頂けるとありがたいです。
    --- ヒントをつけすぎると，皆さんの思考の邪魔になるので，あまりつけていません．ヒントが必要な場合は直接お尋ねください．
  • マトロイドの合併の問題を解くのに、マトロイドの交わりを利用すると効率よく解けるというのが気になりました．楽しみにしてます．
    --- 次回の内容になりますね．お楽しみに．
• 12/18 (8) マトロイドに対する操作
  • コメントありがとうございました．来週もありますのでご注意ください．
  • サンタさんへ．今年のクリスマスプレゼントは世界平和でお願いします．
    --- 私はサンタさんではありません．
  • ぼくはキリスト教徒ではありませんが、クリスマスプレゼントはOxford University PressのMatroid Theoryがほしいです。よろしくおねがいします。
    --- 附属図書館の開架にあるようです．借りて下さい．
  • 滑らない話はお持ちですか？
    --- ありません．はい．
  • 今日は本当に寒いですね…。初氷も今日だったようで…。
    --- 今朝は，寒くて目が覚めました．健康には気をつけて下さい．
  • いよいよ卒論を書く時期になってきました．つらいです．
    --- みな，そうやって大人になっていくのです…
  • 最大独立集合問題に対する局所探索アルゴリズムをグラフの閉路マトロイドで考えたとき，e'を木に含まれていない辺で重み最大のもの、eをe'を加えたときに出来る閉路の中の重み最小の辺にすると効率的だと思ったのですがこれは正しいでしょうか？
    --- はい，だいたいそれでよいです．
  • 貪欲法よりも局所探索法を使った方がうれしいことはあるのでしょうか．
    --- 例えば，既に最大独立集合を手に入れているとき，一部の要素の重みだけが変化した場合，局所探索法を使えば，数回の反復で最適解が見つかるかもしれませんが，貪欲法の場合は，一から全部構築する必要があります．そのような場合には局所探索法がとても有益です．
  • マトロイドの操作は、集合の数が多くて計算が大変であったり、ある集合を除いた集合で考えたいというような問題を解くときに使う、という認識でよろしいですか？
    --- マトロイドに対して再帰的なアルゴリズムを考えるときによく出てきますが，これについてはこの講義では行う予定がないです．この講義では，マトロイド交わり定理の証明の中で使います．お楽しみに．
  • なぜ除去，制限，縮約と似たような記号なのでしょうか？
    --- 除去の「$\setminus$」と縮約の「$/$」はある意味で「双対」の関係を持っているため，向きが異なる斜線として表されていると，直感的で都合がよいです．制限の「$|$」は他の文脈でも制限の意味としてよく使われます．
  • 図があるとマトロイドの操作や証明の全体像が分かるのでとても助かっています。
    --- スライドにもっと図を載せられればよいのですが，ちょっと横着しています．すみません．その分，黒板に図を描くようにしています．
  • 証明で「つまり」とか「ゆえに」の使い分けがよく分かりません．
    --- 私も分かりません．私は気分で使っています．使い分けがあるならば，私も知りたいです．
  • 先生は新しい概念を勉強したときや論文を読んだときにまとめますか．まとめるとしたらどのようにまとめますか．
    --- 「まとめますか」という質問に対して，答えはNoです．まとめないので，後々困ったことになることはあります．
• 12/4 (7) マトロイドのサーキット
  • コメントありがとうございました．今回は途中何度か止まってしまってすみません．その周辺については，スライドにも補足を加えて修正しました．
  • 記号が多く出てくると頭が混乱して，何をやっているのか分からなくなってきますね．
    --- もう少し多く図を描くとよかったかもしれません．実際に集合の包含関係などを図にすると，記号として書かれているものが何を意味するのか分かりやすくなると思います．
  • 命題の主張を全て講義時間に説明するのか，演習問題としてやらせるのかはっきりさせてほしかったです．ちょっと残念でした．
    --- たしかにそうでしたね．ご意見ありがとうございます．
  • 説明が多いとやはり疲れますね．具体例が充実していると理解が深まるかななんて思います．
    --- そうですね．同時交換公理をもっと簡潔に証明したかったのですが，思いつかず，今回のような形になってしまいました．私も難しいと思います．
  • 自主学習用の例題解説が多い参考書を教えて下さい．
    --- 残念ながら，マトロイドに関してそのような書籍を知りません．私の講義は，これでも，例が多い方です．
  • グラフ上で見れば，同時交換公理はとても理解しやすい。その上で考えるとマトロイドでももっともだなと分かる。グラフは偉大だなと。
    --- グラフにおいて正しいことを，いかにマトロイドでも証明するか，ということが大きなテーマの1つですね．それをすることで，グラフの性質がグラフに特有であるのか，マトロイドまで一般化できるのか，ということが分かり，本質が見えてくることになります．
  • ↯ の記号は初めて見ました．そのような記号があるとは知りませんでした．
    --- 「矛盾」を表す記号はいろいろあるようです．私はこれをよく使います (そのように育ったので)．
  • 夜間作業におすすめの飲み物はありますか？ (炭酸飲料以外で)
    --- 月並みで悪いのですが，コーヒーです．カモミールティーというのもあります．
  • 最近寒いですね．…
    --- そうですね．体調管理に気をつけて下さい．
  • 「サ」は「リ」を書いて「一」ではなくて，「一」を書いて「リ」だと思ってました．
    --- すみません．調べたら私が間違ってました．どうして間違っている方を覚えていたのか，自分でもわかりません…．
• 11/27 (6) マトロイドに対する貪欲アルゴリズム
  • コメントありがとうございました．めっきり冷え込んできましたので，体調にはご注意ください．
  • クリスマスプレゼントは貰えますか？
    --- では，なんか考えておきます．
  • 卒研つらいです。
    --- しっかりとやれば大丈夫なはずです．
  • 二部グラフを書いているとグチャグチャになるので工夫が必要ですね
    --- 図は大きく描くとよいです．
  • 黒い辺によって結ばれる道が見つかって、でも目的関数の暫定の値が増えない場合はどうなるのか少し気になりました。
    --- その場合は追加しても追加しなくてもどちらでもよいです．最終的に重み和が最大の独立集合が得られることに変わりはありません．(つまり，そのような場合，重み和が最大の独立集合が複数存在することになります．)
  • スライドページ49/57で、J3が[2]でなく[3]に行った理由は何ですか？ 貪欲なら[2]に行くはずではないのでしょうか。実際、自分で[2]からアルゴリズムを適用したら結果は変わらなかったので、たいしたギモンではなくなりましたが...。
    --- マトロイドの台集合がジョブの集合であることに注意すると，貪欲に選ぶべきものはジョブだけだと分かります．つまり，時間帯の方は選んだジョブを飽和するマッチングがあれば，何を選んでもよいのです．その点で，時間帯については貪欲に選んでいるわけではない，ということになります．
  • 最近、最小シュタイナー木問題というものを知ったのですが、これがNP問題なのがいまいち納得できません。なにかよい資料等ありましたら教えてください。
    --- 人によって納得するための方法が違うので何を推薦するのがよいか判断が難しいですが，私自身，シュタイナー木問題については『The Steiner Tree Problem』という本で勉強しました．この本は意欲的で，なかなか面白いです．ソフトウェアとしてはGeoSteinerというのがあって，実際に解くと，どれくらい難しいか分かります．
  • 学部3年のとき、R.J.ウィルソン著『グラフ理論入門原著第4版』のマトロイドの章を断片的に読んだときに横断マトロイドが出てきたのを思い出しました．当時は抽象的に書かれていて嫌だなぁと思いました．
    --- 「横断」はもともと集合族に対する概念なのですが，授業では二部グラフを使って導入するようにしました．本質は変わりません．
  • 前回までのスライドは目次がはっきり表示されず、一部分だけで見づらかったので、今回ははっきり表示されて良かったです。
    --- ありがとうございます．これからはそのように目次を書くようにします．
  • PDF viewerは何を使っているのですか？ 私はあまり詳しくないので知りたいです．
    --- SumatraPDFを使ってます．
• 11/13 (5) マトロイドとグラフの全域木
  • コメントありがとうございました．調布祭のため，1週間空きます．ご注意ください．
  • 変な時間に寝て変な時間に起きてしまうと大変ですよね
    --- 案の定，体調を崩しました．
  • 最近急に寒くなったので不規則な生活リズムで風邪を引かないように気をつけて下さい。
    --- 案の定，風邪を引きました．お気遣いありがとうございます．
  • 今日は導出が中心で証明が論理的に正しいことはわかるのですが，その命題の心やイメージがなかなかつかめなかったりします．演習問題を楽しんでイメージをつかみたいと思いました．
    --- だんだんと話が抽象的になってきてしまっていますね．次回はできる限り具体的にしようと思います．
  • はじめは階数の使いどころが分からなかったのですが，今回の証明で階数は重要だなと思いました．階数を定義した人すごいです．
    --- 貪欲アルゴリズムの正当性の証明にはいろいろなものがあり，階数を使わないものもあります．この講義では階数などの道具を既に用意したので，階数を使った証明を紹介しました．
  • 話を聞いて理解はできても，実際に演習で証明をするのはとても大変ですね。何も見ずに証明できるように練習しておきます。
    --- そうですね．演習問題に実際取り組むと，理解があやふやである箇所が分かってくるので，是非やってみて下さい．
  • 最小基問題を最大独立集合に帰着する際のゲタをはかせる$\displaystyle C=\sum_{e \in F}c(e)$ が理解しきれなかったので，復習がんばります．
    --- はい，復習は励行して下さい．講義が始まる前に，前回の資料をちょっと見ておく，というだけでも違うと思います．
  • 先日SOCPの目的関数の変形について証明をしましたが，SOCPの時は許容解集合が同じだったのに対して今回の証明は異なる許容解集合からなる目的関数についての証明だったので手強く感じました．
    --- そうですね．より一般的な手法になるので，それだけ応用範囲も広く，いろいろなところで使えます．
• 11/6 (4) グラフとマトロイド
  • コメントありがとうございました．
  • レポートでなやんだあげく (漢字が書けない) 解けなかった問題が1,2問あるのですが，この問題の証明ができたときに提出締切が過ぎても提出できますか．
    --- 提出できますが，私がコメントを付ける保証はありません．その点をご了承ください．
  • 基の数え方が知りたいです．
    --- これは重要なトピックで，いろいろと研究もあります．もしかしたら，最後の「最近のトピック」として扱うかもしれません．
  • 効率的に閉路マトロイドの基族Bを書き下す方法があったら嬉しいなって思います．
    --- 閉路マトロイドの場合 (つまり，グラフの全域木の場合) は行列式を用いる方法が知られています．閉路マトロイドであるとは限らない場合には，いわゆる縮約除去公式があります．調べてみて下さい．
  • 昔からもれなく場合分けを数えるという行為が苦手なのですが，どうすればよいでしょうか？
    --- 系統立てて考えることが重要で，場合分けをするとき，いきなり3つ以上の場合にわけるのではなく，2つの場合に分けることを繰り返すとよいと思います．
  • 場合分け多すぎです…。
    --- そうでしたね．簡単な例を作ろうと思っていたのですが，なんだか多くなってしまいました．すみません．
  • 印刷用スライドにもう少し書き込みができるスペースが欲しいです．
    --- ありがとうございます．では，そのようなバージョンも次から作ってみます．
  • 階数函数の劣モジュラ性の証明でB'∩(X∩Y)=Bが証明なしで出てきましたが，前の補題で言及するか，補足問題3.10で言及するか，演習問題で出題しておいた方がよかったですね．ちょっと残念でした．
    --- これはすみませんでした．講義では包含関係のみを確認して証明するように変えました．スライドもそのように修正しました．
  • 前回までより直感的にわかりやすい内容でした (初回で難しい証明がなかったから？)
    --- マトロイドは抽象的なものですが，今回グラフとマトロイドの関係を紹介したので，次からは，グラフを例として抽象的な概念の説明ができるようになります．次回はそこから始めます．
  • 全ての頂点で接続する辺が偶数本 (＝行って帰ってこられる) なら閉路というイメージですね．
    --- そうですね．ただ，0も偶数なので，その点を気をつけて取り扱う必要があります．
  • 院試勉強でそこそこ線形代数をやった身としてはむしろグラフとかの方が暗いです．
    --- グラフ自体をあまり深く扱うことはしませんが，2つの方向で登場します．1つは今回のようにマトロイドの例としてグラフを扱うということです．もう1つはマトロイドに関する概念を説明したりアルゴリズムを設計するためにグラフを使うということです．後者については，まだ登場していませんが，じきに出てきます．お楽しみに．
  • 学部2年のときに『離散数学への招待 上・下』を読んだことがあります．今回の講義でやったようなことが載っていた気がしますが，あまり思い出せません．当時はあまり理解を深められなかったんだなぁと思いました．
    --- 抽象的な思考には慣れが必要だと思います．慣れてきた証だと思います．
  • 差集合の記法 $A-B$ や $A\setminus B$ がありますが，使い分けたりするのでしょうか？ 本や論文によっては，$A \supseteq B$ の場合に限って $A-B$ の記法を使うとしていました．
    --- 私自身は使い分けず，講義では $A-B$ を使うようにしています．(論文を書く時は $A \setminus B$ を使いますが．)
  • 論理演算の含意の記号として⇒と→がありますが使い分けたりするのでしょうか？ 意味が違ったりするのでしょうか？
    --- 私は使い分けています．→は論理式を書くときに使う，その論理式の真偽は問いません．一方，⇒も論理式を書くときに使いますが，その論理式が真であるときに限定して使用しています．この方法以外の使い分け方をする人もいますし，全く使い分けず同じ意味であるとして使う人もいます．その点は気をつけていろいろな本や論文を見る必要があります．
• 10/30 (3) マトロイドの基と階数関数
  • コメントありがとうございました．今回残った部分は来週やります．今回の復習を進めておいて下さい．
  • 前回の講義で，マトロイドの性質の基の同濃度性までやってほしかったです．今回は時間内に劣モジュラ性まで終わらなくて残念でした．
    --- 途中で油断してしまったのがいけませんでした．すみません．
  • 増加公理は極大な独立集合のサイズを等しくする (サイズの小さな極大な独立集合のサイズを増加させる) ことから増加という名前が付いているのでしょうか．
    --- 極大な独立集合のサイズは増加させられないので，カッコの中身に書いてあることは無視しますが，増加公理という名前はもっと単純に，|X|>|Y|のときにYのサイズを増加できるということを指しているのだと思います．
  • 基交換公理ではハッセ図上で任意の基B, B'がちょうど2つの枝 (線？) でつながっていることを言っている感じがしました．これも増加公理で基のサイズが等しいから成り立つと考えると面白かったです．
    --- あとの方の講義で局所探索法を扱う予定ので，そのときにこの視点についてはもう少し詳しく説明します．
  • 劣モジュラ性でr(X)やr(Y)とr(X∪Y)は何か関係があるのでしょうか．r(X∩Y)≦r(X), r(X∩Y)≦r(Y)であることは分かったのですが，r(X∪Y)との関係がよく分かりませんでした．
    --- 同じように単調性から，r(X)≦r(X∪Y)とr(Y)≦r(X∪Y)が得られます．面白いところは，単調性を組み合わせるだけでは劣モジュラ性が得られないことです．
  • r(X)+r(Y)≧r(X∪Y)+r(X∩Y)を満たす関数であれば、劣モジュラ性があると言えるのですか。
    --- 言えます．マトロイドの階数関数以外にも劣モジュラ性を満たす関数は多く知られていて，応用上よく現れるものとしてよく研究されています．
  • submodularを"劣"モジュラと訳すのは何故ですか？ subsetは部分集合なのに…
    --- 確かにそうですね．似た用語にsubadditiveというのがあって，それは「劣加法」と訳します．こちらも関数に対して用いる用語で，測度論や経済学のような割と伝統的な分野でも使われているので，おそらくそれをまねたのではないかと思います．
  • よくいるアニメキャラ等のアゴヒゲがマトロイドに見えるようになりました．
    --- よい傾向です ;-)
  • ゴジラ＋モスラ＝モジュラ
    Firefoxなど作ってそう
    --- それはモジラです (-_-;
  • この講義のおかげでクリスマスに予定ができました。
    --- おめでとうございます．クリスマスにお会いしましょう．:-)
  • 日本シリーズが終わりましたね．松田は巨人にFAするでしょうか？ (僕は巨人ファンではないです)
    --- 終わりましたね．ヤクルトが盛り返すかとおもったらわりとあっさり終了して，その点についてはちょっと残念でした．
• 10/23 (2) マトロイドの定義と例
  • コメントありがとうございました．
  • 世界を救ってきました 軽傷で済みました
    --- お勤め，ご苦労様です．
  • 黒板は電気つけてもらわないと見づらい。
    --- では，次回は電気をつけます．
  • マトロイドの勉強と線形代数の復習、はかったです。
    --- 「はかったです」の部分がうまく読み取れなかったのですが，「はかったです」と書いてあるとしか認識できなかったのでそのままにしてあります．線形代数は重要ですので，いろいろなところで復習して下さい．
  • 今回は具体例と線型代数の復習だけでつまらなかったので、演習問題で楽しもうと思いました まる
    --- はい，演習問題を楽しんで下さい．
  • どこまで詳しく説明するかを考えるのは難しいと思うが、前提知識の所はもう少し流してもいいかなと感じた。
    --- ありがとうございます．一応，復習も兼ねている，ということと，記法を統一する，という目的もあるので，ひととおりやっています．
  • なんとなくの概念はわかったような気がするが、似たような定義や言葉があってややこしいのでしっかり押さえておきたい
    --- はい，演習問題を通して理解を深めて下さい．
  • 最適化輪読の延長なので，すんなりついていけてます．
    --- だんだんと難しくなっていくので，気を抜かないようにしてください．
  • ベクトルマトロイドの後半の証明以外は理解できました．ベクトルマトロイドの証明は次回までに理解しておきます．
    --- はい，しっかりと復習をお願いします．
  • 講義中に「眠くて書き忘れた」と言っていた部分はわざと書いてないかのかと思うくらい鮮やかでしたね
    --- 今回はなんとかなりました．このようにならないように注意します．
  • 分割マトロイドが選択公理と似ているなと思いました．
    --- そうなんですね．私には似ているところが見た当らないので，ぜひ教えてください．
  • ベクトル・マトロイドの例は分かったのだけど，具体例 (どのような問題) を解くときに使うかなどを知りたい。
    --- 今後でてきます．お楽しみに．
  • これからこのマトロイドを使ってどのように最適化をしていくのか楽しみです。
    --- はい，楽しみにしていてください．
  • ○○マトロイドっていくつぐらいありますか？ 全てをまとめているサイトってありますか？
    --- たくさんあります．まとめているサイトは知りませんが，あると便利かもしれませんね．
  • 前回の追加問題1.7はどういう操作を意味してるのでしょうか．
    --- ある意味で「射影」なのですが，そうすると，幾何学的な解釈が必要となるので，深入りはしないことにします．
• 10/9 (1) 組合せ最適化におけるマトロイドの役割
  • コメントありがとうございました．来週は休講です．
  • 最近夜は急に冷え込むようになりましたね。
    --- それも貪欲アルゴリズムの一種です (嘘です)。
  • 今日は気温が高い日だった。
    --- そうですね．寒暖の差が激しいので，体調管理には気を付けて下さい．
  • 風邪を引きまして珍しく弱ってます．殺すなら今です．
    --- 安心して下さい，殺しません ;-)
  • 黒板に字を書かないときは前の照明を消してもらえるとありがたいです．
    --- 照明のスイッチが私から近いところにないので，消したりつけたりするのは難しいです．そのため「ずっとつける」か「ずっと消す」のどちらかになります．次回は「ずっと消す」にしてみましょう．
  • 学部4年での受講なので、講義内容が理解できるか不安ですが、がんばっていこうと思います．
    --- 4年生でも大学院生でもあまり変わらないので，その点は気にしないでください．どちらにしても，理解するためにはしっかりと復習をして下さい．
  • 今日は丁寧に進められていたと思われますが，いつもこの様な感じで進めていただくと理解でき助かります。
    --- はい，そのように進められるように努力します．難しかったり分からない所が出てきた場合は質問して下さい．
  • 院の各授業に学部での授業名＋"基礎論"されているのが気に入らないのでなんとかしてください。(例：離散最適化基礎論，シミュレーション理工学基礎論) あとCITIが難しかったです
    --- 学部に「離散最適化」という講義はないので，残念ながらご指摘は正しくありません．
  • 私はプリム法も好きです．後期の間もよろしくおねがいします．
    --- ひとつの問題にいろいろな解き方があるのはよいですね．こちらこそよろしくお願いします．
  • マトロイドについて学びたいと思った．
    --- はい，半年間よろしくお願いします．
  • マトロイド理論楽しみにしています
    --- 残念ながら，この講義では「マトロイド理論」をやるわけではありませんので，その点は注意して下さい．テーマは，「組合せ最適化におけるマトロイドの役割」です．
  • マトロイドは常に目先の利益だけ考えて動けば最終的に利益が最大になる…現実世界でもそうそう無い好都合なsystemですね
    --- はい，その通りだと私も思います．そのように好都合であるからこそ，いろいろなところで使えるのです．
  • マトロイドの語源はどこからだろう。
    --- 行列を表す「matrix」の語尾に○○もどきを表す「-oid」をつけて「matroid」になったと言われています．ということなので，無理やり和訳をすると，「行列もどき」になります．なぜ行列なのか，ということは次回説明します．
  • マトロイドなら任意の重み関数に対して貪欲アルゴリズムが最適解を出力すると書いてたのですが，重み関数の線形和のみ成り立つのでしょうか？
    --- 答え方が難しいですが，例えば，「重みの2乗の和」としても成り立ちます．なぜなら，重みの2乗を新たに重みであると見なせばよいからです．
  • ホロムコビッチ著『Algorithmics for Hard Problems』を読んでいて第4章PCP定理のところで止まってしまいました．PCP定理の証明や使い方の日本語の情報源が少なすぎてつらいです。たすけてください。
    --- 日本語の情報源が少ないのは確かなのですが，PCP定理に関わる研究は最近大きく様変わりしたので，昔の説明の仕方にあまりこだわらない方がよいかもしれません．
  • 最大重みマッチング問題「ハイ2人組作ってー」
    --- そういうことですね ;-)

• 期末試験により成績評価を行います．
• 期末試験問題
• 採点：1問20点満点，合計120点満点
• 受験した人の数は8． 80点以上 (優) が4人 (約50.0％)， 80点未満70点以上 (良) が1人 (約12.5％)， 70点未満60点以上 (可) が1人 (約12.5％)， 60点未満 (不可) が2人 (約25.0％) です． (大学院の講義に秀はありません．)
• 得点掲示 (辞書順に並べています)

  abba	62
  b16212	98
  k87xzy	98
  pandora	45
  rk1990	90
  ZXy92	88
  重力波	77

• 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
• 講評
  • 総評：できている人とできていない人の差が大きいと感じました．特に，問4, 5, 6は授業でやった証明そのままなので，できていてほしいものでした．
  • 問題1：マトロイドの定義を確認する問題．演習問題2.1, 2.6の類題．よくできていました．
  • 問題2：マトロイドの性質を証明する問題．ほとんどできていませんでした．劣モジュラ不等式をどのように使っているのか不明である答案には点を与えていません．
  • 問題3：最小全域木を答える問題．演習問題5.1の類題．全員できていました．
  • 問題4：マトロイドの性質を証明する問題．演習問題7.4と同じ問題．授業の中でもやった証明です．ただ1つ存在することを証明するように聞いているわけですから，まず存在することを証明しないといけません．「2つ存在すると仮定すると矛盾する」ということを証明しても，存在することの証明にはなっていません．
  • 問題5：マトロイドの操作に関する問題．演習問題8.3と同じ問題．授業の中でもやった証明です．できている人とできていない人の差が大きい問題でした．支離滅裂な論証を行っている答案がいくつかあり，衝撃を受けました．自分の書く日本語の意味は理解していてほしいものです．
  • 問題6：マトロイドの交わりに関する問題．演習問題10.1と同じ問題．授業の中でもやった証明です．できている人とできていない人の差が大きい問題でした．できている人は3行で終わってます．

• 10/2 卒研準備発表会のため 休み
• 10/9 (1) 組合せ最適化におけるマトロイドの役割
• 10/16 海外出張 のため 休み
• 10/23 (2) マトロイドの定義と例
• 10/30 (3) マトロイドの基と階数関数
• 11/6 (4) グラフとマトロイド
• 11/13 (5) マトロイドとグラフの全域木
• 11/20 調布祭 のため 休み
• 11/27 (6) マトロイドに対する貪欲アルゴリズム
• 12/4 (7) マトロイドのサーキット
• 12/11 国内出張 のため 休み
• 12/18 (8) マトロイドに対する操作
• 12/25 (9) マトロイドの交わり
• 1/1 元旦 のため 休み
• 1/8 (10) マトロイド交わり定理
• 1/15 センター試験準備 のため 休み
• 1/22 (11) マトロイド交わり定理：アルゴリズム
• 1/29 (12) 最近のトピック
• 2/5 授業等調整日 (予備日) ← 補講はしません
• 2/12 期末試験

• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム