離散最適化基礎論

岡本 吉央

テーマ：グラフの木分解

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

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

講義資料

• 2/10 (13) 固定パラメータ・アルゴリズムと木幅
  • スライド (2/10修正) | 印刷用スライド (2/10修正) | 演習問題はありません
  • この回の内容は期末試験で問われません．
• 2/3 (12) 木分解構成アルゴリズム
  • スライド (2/10修正) | 印刷用スライド (2/10修正) | 演習問題 (2/10修正)
• 1/27 (11) 木幅と論理：アルゴリズム設計
  • スライド (1/30修正) | 印刷用スライド (1/30修正) | 演習問題はありません
• 1/20 (10) 木幅と論理：オートマトン
  • スライド | 印刷用スライド | 演習問題
• 1/6 (9) 木幅と論理：単項二階論理
  • スライド (1/16修正) | 印刷用スライド (1/16修正) | 演習問題
• 12/16 (8) 木分解を用いたアルゴリズム設計：連結性
  • スライド | 印刷用スライド | 演習問題
• 12/9 (7) 木分解を用いたアルゴリズム設計
  • スライド (12/16修正) | 印刷用スライド (12/16修正) | 演習問題
• 12/2 (6) 木幅の性質
  • スライド (12/7修正) | 印刷用スライド (12/7修正) | 演習問題 (12/7修正)
• 11/18 (5) 木分解と木幅
  • スライド (11/29修正) | 印刷用スライド (11/29修正) | 演習問題
• 11/4 (4) 道分解を用いたアルゴリズム設計
  • スライド (11/29修正) | 印刷用スライド (11/29修正) | 演習問題
• 10/28 (3) 道分解と道幅
  • スライド (10/28修正) | 印刷用スライド (10/28修正) | 演習問題
• 10/21 (2) 木に対するアルゴリズム設計
  • スライド (10/21修正) | 印刷用スライド (10/21修正) | 演習問題
• 10/7 (1) 離散最適化における木分解の役割
  • スライド | 印刷用スライド | 演習問題

• 2/10 (13) 固定パラメータ・アルゴリズムと木幅
  • コメントありがとうございました．今回が最終回でした．
  • 半年間講義ありがとうございました。専門性の高い内容を学んで思ったことは、汎用性のある技術にしていくことの重要性です．この知識を活かした研究をしてみたいと思います．
    --- 何か考える材料になるものがあったようなので，私もうれしいです．ありがとうございました．
  • 半年の間 ありがとうございました
    --- こちらこそありがとうございました
  • 禁止格子定理のありがたさが伝わってくる内容でした。
    --- そうですね．定理は偉大なのです．
  • 期末試験、ダメかと思いますが、受験はしたいと思います。5ヶ月間ありがとうございました。
    --- 諦めるにはまだ早いです ;-) ありがとうございました．
• 2/3 (12) 木分解構成アルゴリズム
  • コメントありがとうございました．
  • 修論発表おつかれさまです．
    --- 私は発表していません．
  • 復習を怠っていたので、焦っています。期末試験に向けて頑張ります。
    --- はい，よろしくお願いします．
  • 学部の離散数学の授業には何とかついて行けましたが、この授業の方が全然難しくて心が折れそうです。
    --- その理由は，学部の離散数学が離散数学ではないからです．心を折らずに勉強していってください．
  • 後期の内容がのっている (なるべくやさしい) 参考書はありませんか．
    --- 「後期の内容」が何を指しているのか分からないのですが，私が参考にしている書籍をこのページの下の方に挙げておきました．
  • 実際にアルゴリズムを設計しようとすると中々難しい．
    --- そうですね．それだからこそ演習問題があるのです．
  • 木分解を利用していろいろな問題が解けるのに，木幅がNP困難だと思うとさびしい気分です．
    --- 「なにもかもうまくいく」ということはなかなかないのです…
  • 動的計画法の部分は、TSPと同じなので理解しやすかったです。
    --- TSPに対する動的計画法を提案したのが，HeldとKarp，そしてBellmanです．
  • 最適値を求めることと，最適解も求めることは計算時間の上で異なってきますか？
    --- 異なる場合はありますが，今回の授業で扱ったものについては，オーダーの意味で同じになります．
  • 部分k木 ⇔ tw(G)≦k の証明を復習します．
    --- はい，ぜひお願いします．
  • もし，P≠NPだったとしたら，NP完全の計算量はどのくらいになると思いますか．
    --- これは分かりません．予想すらすることは難しいです．
• 1/27 (11) 木幅と論理：アルゴリズム設計
  • コメントありがとうございました．
  • 今までの話の中で1番難しかったです。
    --- 私自身もそう感じました．
  • Büchiの専門は何だったのでしょうか．
    --- Wikipediaのページには論理学と数学，と書いてありますね．
  • ∀と∃が何重にも入れ子になっていて、プログラムで書くとすごい計算量になりそう
    --- たしかにそうだと思います．実際，すごい計算量になります ;-)
  • 英語の論文を読むのが遅くて困っています。先生はどのように英語を勉強されましたか。
    --- 難しい質問ですね．中学生のときにNHKのラジオ講座を聴いていて，それが役立っている気がします．
• 1/20 (10) 木幅と論理：オートマトン
  • コメントありがとうございました．
  • 間違っていたら申し訳ないのですが，任意の非決定性オートマトンはかならず決定性オートマトンに変換できなかったはずではないですか？
    --- 間違っているかは気にしないでください ;-) オートマトンの場合は必ず変換できます．プッシュダウンオートマトンの場合は変換できない場合があったり，とか，ややこしいですが，オートマトンの場合は変換できます．
  • 道を文字列とみなす考えはキレイでした．
    --- このような導入のしかたはあまり行わないのですが，試してみました．
  • 午前中は雪が散らついていました。教室移動が辛いです。
    --- そうですね．健康管理には注意して下さい．
  • オートマトンの授業以来久々にオートマトンという言葉を聞きました。
    --- 重要な道具なので，何度もでてきます (^^)
  • 修士が取り組む研究テーマを決める上で重要なことは何であるとお考えですか。
    --- 何でもよいですが，極めようとして下さい．それに加えて，そのテーマに興味を持つ人が世界に少なくとも100人いるとよいと思います．
• 1/6 (9) 木幅と論理：単項二階論理
  • コメントありがとうございました．
  • 明けましておめでとうございます．今年もよろしくお願いします．
    --- 今年もよろしくお願いしまsう．
  • 授業で紹介されたURLに実際に行ってみようと思います．
    --- 下の方にもリンクがあります．そちらからどうぞ．
  • 今日のお話はとてもすっきりしました。
    --- それはよかったです．演習問題にも取り組んでみてください．
  • 用語集が欲しくなりました。今から挽回できるか不安です。
    --- しっかりと復習をして下さい．:-)
  • 線形時間アルゴリズムの存在の有無が分かると、何が良いのですか？
    --- 「線形時間アルゴリズム」はある意味で究極のアルゴリズムです．なぜかというと，入力を読み込むだけで線形時間がかかってしまうからです．その意味で，線形時間アルゴリズムよりも速いアルゴリズムを作ることはできません．つまり，何も考えずに，最も速いアルゴリズムが作れるという意味でCourcelleの定理は強力なのです．
  • Adjacentの発音を間違って覚えていました。
    --- たとえば「judge」をカタカナにしても「ジャドジ」にはならず「ジャッジ」です．慣れないうちは，英語の辞書を引き，発音もちゃんと調べるということが重要だと思います．そのためには，発音記号 (音声記号) を読める必要があります．
  • たとえば，$|X|=2$ は，
    $(\exists x_1\in X. \exists x_2\in X. x_1 \neq x_2) \land (\forall x_1 \in X. \forall x_2 \in X. \forall x_3 \in X. x_1=x_2 \lor x_2 = x_3 \lor x_3=x_1)$
    とかではダメでしょうか？
    --- よいと思います．同じような考え方で，$|X|=3$ や $|X|=4$ は書けます．
  • $|A| \geq |B|$ もがんばれば単項二階論理式で書けると思うのですが $|\phi|$ がグラフのサイズに依存しそうです。そのような意味でp21で扱えないとしたのでしょうか？
    --- おそらく，頑張っても書けません．もし書けるようでしたら教えて下さい．
  • グラフの性質を入力として、単項二階論理式を出力するアルゴリズムというのは設計できるのでしょうか？
    --- グラフの性質をどのように入力するのか，ということがはじめに考えなくてはいけない問題になります．普通は性質を論理によって表現するので，そのとき，すでに単項二階論理式を考えることになってしまうかもしれません．
  • Courcelleの定理の使い方で，単項二階論理式で書けないなら，良い動的計画法のアルゴリズムはないのですか？
    --- そうとはいえません．「単項二階論理式で書ければ解ける」とはいえますが，逆は成り立ちません．別の言い方をすると，Courcelleの定理が成り立つ論理の範囲を広げていく，という研究はあります．
  • 単項二階論理で記述できない性質に対するメタアルゴリズムの研究とかあるのでしょうか？
    --- ちょうど上で言及したことですね ;-) また，考える対象がグラフではない場合にも，性質を論理で書くことによってアルゴリズムを設計することを考えることもあります．
• 12/16 (8) 木分解を用いたアルゴリズム設計：連結性
  • コメントありがとうございました．
  • 「よいf」は英語では何と言うんでしょうか (niceのときのように、訳すのが大変だったのでしょうか)
    --- 「よいf」は私の造語なので，訳したわけではありません ;-)
  • 計算量から木幅が小さい＝木っぽい方が高速に解けるという認識であっていますか？
    --- はい，合っています．講義でその点を強調しておくべきでした．
  • $t^{O(t)} = \text{定数}^{t\log t}$ があまりよくわかりませんでした．
    --- 具体的に書くと，例えば，$t^t = 2^{t \log_2 t}$ となります．両辺に対して，$\log_2$ を考えてみれば，等しいことがわかります．
  • 各再帰式で「$\lor \{s(j;f_j) \mid f_i \text{ と } f_j \text{ が整合}\}$」とORをつなげている理由がよくわからなかったのですが，$X_j$ に対して $f_j$ を複数考えられるからなのでしょうか。
    --- はい，その通りです．$f_i$ と整合する $f_j$ が1つに定まるとは限らないからです．
  • 「アルゴリズムを設計せよ」という問いに対して、どのような流れで解答すれば良いかがわかりません。
    --- 講義でやっているような手順に沿って，記述して下さい．
  • ややこしい
    --- 確かにややこしいですね．しっかりと復習をして下さい．
  • 節点によって、整合しているしていないという部分的な話はわかったが、なんだか面食らったような半ば信じられないようなアルゴリズムでした。
    --- 素敵な木分解を考えているおかげで，導入節点，忘却節点，結合節点において何をすればよいかだけを記述すればよいということで，アルゴリズムの設計がだいぶ単純化されているのですね．これでも．
  • 時間がしばらく空くのでゆっくり考えてみようと思います．
    --- はい，よろしくお願いします．
  • ハミルトン閉路の存在性は、固定パラメータで解けることを理解しましたが、ハミルトン閉路自体を求めようとすると、状態数がすごいことになって求められないのですか？
    --- 求められます．ハミルトン閉路の場合は，$s(i;f_i)$ を true にする道の集まりを1つ覚えておけばよいです．各 $s(i;f_i)$ に対して，$O(|V|)$ 個の辺を覚えておけばよいだけなので，それほど難しくありません．この覚えておく道の集まりも再帰に従って更新していく必要があります．
  • 内容がガラリと変わるっぽい後半もたのしみです．
    --- ぜひお楽しみに．
• 12/9 (7) 木分解を用いたアルゴリズム設計
  • コメントありがとうございました．
  • ついに，木分解を使ったアルゴリズムがでてきた！
    --- なんと 木分解を使ったアルゴリズムが おきあがり なかまに なりたそうに こちらをみている！ なかまに してあげますか？
  • 複雑で復習が必要です。がんばります。
    --- はい，がんばってください．
  • 親と子のA, Bが違う場合は合わせても独立集合にはならないから大丈夫，という部分が良くわからなかったので，直されたスライドが上がったら復習します．
    --- 直しました．よろしくお願いします．
  • 実装してみたいけど，難しそうです。
    --- 動的計画法のアルゴリズムは再帰式を解くだけなので，実装は単純になる傾向があります．試してみてください．
  • 特に最小支配集合問題の結合節点部分の話が難しかったです。
    --- 再帰式をしっかりと作るところは難しいです．だからこそ，訓練が必要だと思います．
  • おもしろいけど難しいと思った．
    --- 難しいので，復習して下さい．
  • 資料を作っているかいないかでどれだけ説明に差がでるかわかった。自分も気をつけたい
    --- 気をつけて下さい．私も気をつけます．(-_-;
  • 今回は何か教室の室温が高いように感じました。
    --- 暖房が効きすぎていたのかもしれませんね．
  • 人力で木分解をするときのコツ等があれば教えて下さい．
    --- これは2月頃の講義で扱います．お楽しみに．
  • 木分解をはじめに発見した人はだれですか？ どんな気分で発見したのかが気になります。
    --- RobertsonとSeymourがグラフ・マイナー定理を証明するために導入したと言われています．1980年代の前半のことです．
  • 演習5.2の命題の対偶はどうなりますか？
    --- 「$V(T_1)\cap V(T_2)\cap V(T_3)=\emptyset$ ならば，$V(T_1)\cap V(T_2)=\emptyset$ または $V(T_1)\cap V(T_3) =\emptyset$ または $V(T_2)\cap V(T_3)=\emptyset$」です．
• 12/2 (6) 木幅の性質
  • コメントありがとうございました．
  • p.25の"これが本当に $\mathcal{T}$ の〜" は $\mathcal{T}$ でなくて $H$ ？
    --- ありがとうございます．その通りです．修正しました．
  • 辺の縮約は直感的に分かりやすかった。
    --- 電気回路で短絡と呼ばれる操作に対応しています．そのため，電気回路にこの手の考え方を応用するときにもよく出てきます．
  • 3x3の格子を縮約してK₄をつくれてうれしくなりましたが，nxnの格子の木幅を下からnでおさえるのは考えてもどうするのかわかりませんでした．
    --- 格子をどう頑張って縮約してもK₅が作れないことは次のようにして簡単にわかります．格子は平面上に辺交差なく描けますが，それに対して辺の縮約を繰り返していっても，平面上に辺交差なく描けるグラフしか得られません．その一方で，K₅は平面上に辺交差なく描けないグラフ (として知られている有名な例) なので，格子から辺の縮約によってK₅は得られないのです．別の方法をつかって格子の木幅は証明します．
  • 格子の木幅の下界，むずかしく良く理解できていないので，時間をかけて復習します．
    --- はい，よろしくお願いします．
  • 証明に追いつくのが精一杯です。(追いつけていない)
    --- 私も精一杯です．:-)
  • スゴク、ムズカシイ
    --- そうですね．私も難しく感じます．
  • 毎回授業の最初の方は木幅や木分解についての復習を取り上げていますが、その部分を省いて新しい用語や定義、定理の説明 (特に証明部分) に時間を割いた方がいいと思います．
    --- 提案ありがとうございます．では，次回はそうしてみます．
  • パスグラフの定義は何ですか？
    --- 木の上でパスの交わる様子を表したグラフです．向きがついているものと向きがついていないものの2種類があります．
  • 演習問題が証明問題ばかりですが、期末テストも全て証明問題でしょうか。
    --- 期末テストはなく，期末試験を行うのですが，期末試験で問われる問題は演習問題と同じような問題です．初回にアナウンスをした通りです．
  • 古い演習問題は見てもらえないのですか？
    --- 再提出ではない限り見てもらえないです．
  • 研究にゼミの準備に課題など、12月はいつもより多く重なっていて頑張らないとまずいです。先生は色々な期限が重なって忙しいとき、どのように処理していきますか。何かコツなどがあれば教えて下さい。
    --- 処理しきれていない，というのが現状です．命を削ってます．
  • スナック＆ドリンク、ごちそうさまでした。楽しかったです！
    --- こちらこそありがとうございました．またよろしくお願いします． :-)
  • 急に寒くなったので体調に気をつけようと思います．
    --- QSNですね．お大事に．
• 11/18 (5) 木分解と木幅
  • コメントありがとうございました．掲載が遅くなりすみません．
  • 乾燥していて風邪の人が多く自分自身も風邪気味で気を付けなくてはならないと思う今日この頃です。
    --- そうですね．予防が大事ですから，しっかりと対策をして下さい．
  • 朝がさむいです
    --- 昼でもさむいです (-_-;
  • 当日連絡でやることが増える、というのが最近多いのですがどう対処すべきでしょうか
    --- あってはならないことだと思いますが，仕方がないので，やれるうちはやって下さい．
  • 調布祭では何かしますか？
    --- 研究室公開をします．
  • すてきな道分解は左から右へ見ていって導入，忘却だったが，すてきな木分解は下から上へ見ていくようだったのでややこしくなりそうだった。一度こう書いておけばもうまちがいませんね。
    --- 道分解のときは，一番右を根とする木だと思って下さい．そうすればちゃんと対応がつきます．
  • 道分解の回を休んでしまったので難しかった。しっかり復習したい。
    --- はい，しっかりと復習をして下さい．
  • 復習をサボっていたこともあり、すでにチンプンカンプンですが、まずはまともに質問できるレベルまで追いつけるように頑張りたいと思います。
    --- はい，よろしくお願いします．
  • 素敵な気分さ。(必ず誰かが「素敵な気分かい？」と聞いてくると思うのでそのコメントの下に載せて下さい。違ったら独り言だと思って下さい。)
    --- 残念ながら，そのようなコメントはありませんでした．
  • なんて素敵なジャパネスクというマンガがおもしろいですよ．
    --- なんて素敵「に」ジャパネスク，だそうです．
  • 今回は演習の時間が10〜15分くらいとれたので復習にちょうどよかった．
    --- 毎回，あまり演習の時間がとれず，すみません．時間に対する感覚がだいぶ鈍っています．
  • 復習問題2.5のTotal dominating setが分からないです．根付き木を考えて，葉，葉を子に持つ頂点の集合 $S$，$S$ を子に持つ集合で場合分けしたのですが上手くいきません．
    --- 3つの場合ではなくて，4つの場合を考える，というのはどうでしょうか？
  • スライドp.13の図で，頂点5に対応する橙の線の長さが足りないように見えます。
    --- ご指摘通りです．修正しました．
  • 前回(4)で分からないところがあります．
    1. P32の「$\because G_i = G_{i-1}$」は「$G_i \subseteq G_{i-1}$」ではないですか？
    2. P67の $S(i;A_i;B_i;C_i)$ の右辺の「$A_i-\{w\}$」や「$B_i-\{w\}$」は「$A_i \cup \{w\}$」と「$B_i \cup \{w\}$」ではないですか？
    3. P66の「$w \in C_{i-1}$ だと問題がある」という部分が分かりませんでした．
    
    --- 順に回答します．P32ですが，$G_i = G_{i-1}$ は正しいです ($G_i \subseteq G_{i-1}$ も正しく，それを観察すれば十分ですが)．なぜ正しいのかというと，$X_i$ は忘却頂点であり，$G_i$ にはその忘却された頂点も含まれているからです．P67については，ご指摘どおりです．修正しました．P66については，$w \in C_{i-1}$ であるとすると，$w$ はまだ支配されていないのに忘却されることになってしまい，最終的に支配集合が得られなくなってしまうことが問題です．
• 11/4 (4) 道分解を用いたアルゴリズム設計
  • コメントありがとうございました．掲載が遅くなり，すみません．
  • niceな道分解が思ったよりもniceでした．
    --- ナイスですね．:-)
  • 考えるべき場合の数が，1つの頂点の導入と忘却だけになるなんて、素敵です！
    --- そうですね．それが素敵なところですね．
  • 素敵な道分解はやはり素敵だったと，規則的なものはやはり良いなと思いました。でも難しいです…。
    --- 確かに難しいですね．私もそう感じます．
  • 難しくなってきます。
    --- しっかりと復習をして下さい．
  • 難しいのでしっかり復習します
    --- はい，よろしくお願いします．
  • 休講はさむ時はじっくり考えられる時間があるので活かしたいと思います．
    --- はい，演習問題に取り組んで下さい．
  • レポートに質問を書いて提出してもよいでしょうか。(授業中に質問するのが難しいので)
    --- よいです．活かして下さい．
  • 前の回の演習問題で解けなかったものを、来週が休講なのでこの間に解こうと思うのですが、それを次回提出するレポートに含めても大丈夫でしょうか。
    --- 含めてもよいですが，提出締切は過ぎているので，私が見る保証はありません．ご了承ください．
  • 最大独立集合のアルゴリズムの方は，動作例もあって気分がわかりやすかったです。
    --- 最小支配集合の方は，動作例を作る気力がありませんでした．皆さん，自分で確かめてみてください．
  • 最小支配集合問題について参考になる書籍は何がありますか (多少難しい内容の本でも構いません)
    --- 「Fundamentals of Domination in Graphs」という本があり，私が学生のときはそれを参考にしてました．図書館で借りていたので，持ってはいません．
  • 固定パラメータ・アルゴリズムは強そうです．
    --- 実際に強いですが，この講義は固定パラメータ・アルゴリズムを扱う講義ではないので，そこには注意して下さい．ただ，道分解や木分解が固定パラメータ・アルゴリズムを考えるうえで重要な概念になっていることは確かです．
  • 素敵な木分解Pを効率よく求めるのに O(pw(G)・n) より高速に出来るのでしょうか？ また木分解を経由しない場合により高速に求まるのでしょうか．
    --- はじめの「素敵な木分解」はおそらく「素敵な道分解」の意だと思うので，そう解釈して答えます． O(pw(G)・n)時間で素敵な道分解を求める方法は知られていませんし，おそらくないと思われています．
  • 本での学習だと自分でグラフをうまく書けないので板書を参考にします。
    --- はい，自分の勉強しやすいように進めて下さい．
  • 最近寒くなってきたので朝がつらいです。
    --- もう20年ぐらい生きているのですから，慣れて下さい ;-)
  • 暖房の管理がどうなっているのかわからないので変えられないことかもしれませんが、少し教室が寒かったです。
    --- 私もどのように暖房が管理されているかしらないのですが，調整できるようならば，調整するので，寒い時は直接言って下さい．
  • 再来週は出張の話題を期待してます
    --- 残念ながらありません ;-)
  • 演習問題だけでも早くあげてもらえると印刷がしやすいのでお願いしたいです．
    --- 講義スライドができてから演習問題を作っているので，これは無理です．(-_-; すみません．
  • 「演習」と「印刷用スライド」を混ぜたPDFがあると便利そうだと思いました．
    --- では，次回から用意するようにします．ありがとうございます．
• 10/28 (3) 道分解と道幅
  • コメントありがとうございました．
  • 寒い日でした。
    --- そうですね．体調にお気を付けください．
  • 内容が難しくてなかなか追いつけません。深く理解するための良いやり方はありますか？
    --- 演習問題に取り組むことをお薦めします．
  • Σと証明問題が苦手です。どうすれば克服できるでしょうか。
    --- 演習を多くやることがよいと思います．
  • 期末テストが不安になってきた…
    --- 分からない所は質問をして下さい．質問なしで理解できることを私は想定していません．
  • 先生の説明が分かりやすいなと思っています．説明するときに心がけていることはありますか．
    --- 例を多く出すことです．例を考えることは重要です．
  • これの道分解 (道幅2となるように) を考える．
    すると、2体のベイマックスが現れる。
    --- 権利関係が問題化しないよう，あえて似てないようにしてます (嘘です)
  • 閉路があると道幅が3以上になってしまいそうな気がしました．
    --- 閉路の道幅は2です．考えてみてください．
  • 木の重心 (centroid) をvとしてえらべば木の道分解の係数を小さくできませんか？
    --- できるかもしれませんが，証明がややこしくなると思います．
  • 木の道幅の証明を自分でもう一度復習してこようと思いました．
    --- 何ステップもある証明なので，一段ずつしっかりと確認して下さい．
  • tw(G) ≦ pw(G) で道⊆木なので木を含むようなクラスで分解をしたくなるのですが他にうまいものが存在するのでしょうか。
    --- 存在するかもしれませんが，役に立てにくいと思います．木以外を考えると，閉路を含んでしまうので，アルゴリズム設計という立場からはあまりよいことがありません．
  • 素敵な道分解が予想以上に素敵だった。ところでなぜ「素敵」という言葉には「敵」という文字が入ってるんでしょうね
    --- まず，「素敵」は当て字なのだそうです．「敵」には「敵う」(かなう) という用法があります．「匹敵」にも現れますね．それで「素晴らしすぎて敵わない」という意味から「素敵」が当てられた，とそのページには書いてあります．
  • 「道分解 P が素敵であるとは」という文で何故か笑ってしまいました．
    --- 「素敵」という形容を人以外に使うことはあまりないのかもしれませんね ;-)
  • 素敵な道分解の作り方から，節点数がO(|V|)となる道分解の存在が言えるというところが，あまりよくわかりませんでした。
    --- 区間の端が重ならないようにしていますが，「区間の端」として表れる箇所の数は 2|V| になります．そのため，2|V|+1個の節点だけで素敵な道分解は作れるのです．
  • 素敵な木分解もありますか？
    --- はい，素敵な気分です．あります．
  • 素敵な道分解．
    Such a wonderful path decomposition!
    --- 「素敵な」は「nice」の訳語として使いました．「素敵な道分解」に定訳がないので，もっとよいものがあったら教えてください．候補としては「よい道分解」というものもありますが，そうすると，もし誰かが「good path decomposition」という用語を使いだしたら，それに対応させる訳語が作れなくなってしまいます．そのため，訳語の選定は割と慎重さを要するのです．
  • 素敵な道分解がわかりやすく理解できた。
    --- 区間を使って考えると分かりやすいと思います．
  • 素敵な道分解の素敵さはなんとなく伝わってきました。
    --- 次回，アルゴリズムを設計するときに，素敵さがもっと分かると思います．
  • 次回のアルゴリズムに期待しておきます！
    --- 期待して下さい！
  • IPEでつくった図をBeamerでアニメーションするとき，どのようにやっていますか？ widthを指定すると，図のサイズがかわってしまったりして，しかたなくいつも白いみえないわくで図をかこったりしています。
    --- 私もいつも白いみえないわくで図をかこったりしています．
  • 英語の論文の探し方を教えてください．たまにgoogle scholarにない論文があって悩みます．
    --- どのような状況を想定しているのか，分かりませんが，私自身は，単にgoogleを使うこともあります．
• 10/21 (2) 木に対するアルゴリズム設計
  • コメントありがとうございました．スライドの間違いは修正しました．
  • 前回出ていなかったので、今回が初めてです．よろしくお願いします．
    --- よろしくお願いします．
  • 講義内容をまじめに聞いているつもりですが、内容について行けず、演習問題に手が出ません。前提となる知識が不足しているのでしょうか？ 単に頭が悪いだけなのでしょうか？
    --- 質問して下さい．簡単に分からなかったり，誤解してしまっている部分があるのかもしれません．分からないところを分からないまま放っておかずに，質問をして解決することをお勧めします．
  • 大学院の講義のせいか学部の講義より難易度の上がり方が急な気がしました．
    --- もしかしたら，そうかもしれません．分からない所は積極的に質問して下さい．
  • 説明はわかりやすいのですが，自分で考えてみると難しかったです…。
    --- そういうものですので，演習問題に取り組んで下さい．
  • 今回は難しかったので、しっかり復習したい
    --- はい，よろしくお願いします．
  • 難しかったので復習が必要でした。
    --- 授業資料を見返しながら，演習問題に挑戦して下さい．
  • グラフおもしろいです。
    --- すみませんが，尻尾は生えていません．
  • 「小さな紙」の正式名称はありますか？
    --- 小さな紙，です．こういうものは名前をつけると廃れます．名前を付けない方がよいです．
  • 無理に日本語にしなくてもいいと思います
    --- 確かにそう思います．ありがとうございます．
  • 英語の論文を日本語に訳して説明しようとしたときにしっくりくる日本語が見つからない事は自分もよく経験します。
    --- 一応授業なので，できるだけ訳そうとおもってはいるのですが，無理な場合はそうしないことにします．
  • 右妹辺 (うまいへん) と読むことにしてます
    --- うまいですね ;-)
  • 祖先と先祖がわからなくなる話で子孫はわかるんだけどねということで逆にしたら孫子になって、確かにわかりやすかった。
    --- 祖先と先祖の違いが分かりましたら，教えてください．
  • 「$\leq_v$ において $e$ よりも1つ大きい辺」とあるので「$e$ の右妹辺」よりも「$e$ の右姉辺」なのかと思いました．
    --- むずかしいですね．家系図などでは，長兄を左に書きます．そのため，左から右に並んでいる場合，右の方が妹になるわけです．一方，数学的には左のほうが小さく，右の方が大きいので，つまり妹の方が大きい，ということになるわけです．そういう意味では，直感的にわかりにくい語法であると思います．
  • 根は頂点vの祖先として含まれるのですか？
    --- どの頂点vに対しても，根はvの祖先です．正しいです．
  • 妹じゃなくて弟と言うこともありますか
    --- あります．
  • 木における集合問題の計算量は根の位置には関係ないでしょうか．
    --- 関係ありません．どれを根にしても計算量は O(|V|) になります．
  • 漸化式ができたつもりでも全ての場合を網羅できていないことが多く難しい
    --- 後の方の講義でオートマトンをやりますが，そこにいくと，今日の内容が改めて，別の見方から理解できるかもしれません．
  • 2.4の問題，具体的にどういうことをかけばよいのか，よくわからないです。
    --- 構成法 (つまり，アルゴリズム) を記述して，それによって得られる線形順序が満たすべき性質を満たしていることを証明して下さい．
  • 講義と関係ないのですが，Beamerで8分割のスライドをどう作っていますか
    --- 講義と関係なくてもいいです ;-)
    documentclassのオプションとしてhandoutをつけて，いろいろといじればよいです．Beamerのユーザガイドの第21章に書いてあります．
• 10/7 (1) 離散最適化における木分解の役割
  • コメントありがとうございました．以下のとおり掲載されます．
  • 受講しようと思います。
    --- よろしくお願いします．
  • 今学期もよろしくおねがいします
    --- よろしくお願いします．
  • 先行り修のハンコがほしい場合、もらいに行くのに良い日時はありますか？
    --- 可能でしたら，10月12日(水)の13:00から16:00の間に，CEDのエリア2へ来てください．
  • 木分解をする気分かい？
    --- はい，そうです．
  • 今年は，木分解の気分かい？
    --- はい，そうです．
  • 「木っぽい」構造について分かったっぽい
    --- このテーマで一学期間通しますので，理解を深めて下さい．
  • Tree Automataを勉強しているので，第10回が気になります．
    --- 木オートマトンは出てこないかもしれませんが，普通のオートマトンを使って説明をしてみたいと思います．(本来は木オートマトンを出すべきなのですが，時間が足りないので，出せなそうです．)
  • まずは定義 (用語) をしっかり覚えたいと思います。「節点」がどのようなものかわからなくなってしまいました。
    --- 「節点」は「頂点」のことです．
  • 頂点数1の木においてその頂点は葉なのでしょうか．
    --- その頂点の次数は0なので，葉ではありません．
  • 講義の中の``木幅が現れる場面''という点に興味を持ちました。いい例だと思います。
    --- 自分の興味がある例で，木幅がどうなるのか考えてみるのもよい練習になると思います．
  • 木幅が大きい高分子がハニカム構造に似ていて、あのような形は、物理的だけでなくて難しさにも強い！と思いました。
    --- 実をいうと，木幅が大きなグラフには必ずそのような部分構造がある，ということが知られています．正確に述べようとすると，もう少し用語を定義する必要が出てきますが，その事実がアルゴリズム設計の中で役立つ場面も多く，グラフ・アルゴリズムの理論研究ではよく使われます．
  • 木幅を求める効率的なアルゴリズムは知られていますか？
    --- 木幅を厳密に求めることはNP困難であることが知られています．
  • 非常に日常的なNP困難な問題の例を1つお願いします．
    --- 人によって「非常に日常的」であることに対する感覚が異なるので，答えることは難しいですが，非常に日常的なものは大抵NP困難です．
  • プログラムの制御フローグラフで木幅が小さいとどのような問題を解くときにうれしいのですか？
    --- 例えば，コンパイラ構成におけるレジスタ割当問題がある意味で解きやすくなります．
  • 離散構造上で木分解に対応するものってありますか？
    --- 「離散構造」が何を意味するのかに依存しますが，有限集合族に対して木分解を定義することができ，その応用として，関係データベースにおけるクエリ最適化などがあります．
  • 「幅が1の木分解」とは「幅が1の木」(のようなもの) に分解するという意味で良いのですか？
    --- 違います．「木分解」というのは操作に対する用語ではなく，操作によってつくられた構成物に対する用語です．何かを行ってできあがるものが「木分解」です．そのような (ある意味で，日本語として) 分かりにくい用語法はいろいろな分野でよくありますが，それは英語を直訳しているからだとも言えます．英語においては，動詞から派生する名詞が，その動作によって出来上がる構成物を表すことがあります．
  • 木分解してみると、条件 (各頂点 $v \in V$ に対して $\mathcal{T}$ の節点で $v$ を含む者は $\mathcal{T}$ の部分木を誘導する) を満たせてなかったりしてやきもきしました。パッと見で分かるようになりたい。
    --- 慣れが必要かもしれません．1学期間かければ，慣れていけると思います．
  • いいタイミングでの休憩だと思います．
    --- 水分補給ができなかったので，私はあまり休憩できませんでした (-_-;

• 期末試験により成績評価を行います．
• 期末試験問題 (2/17実施)
• 受講者数 (履修登録者数相当) は17で，受験した人の数は9． 平均点は78.7 (120点満点)． 80点以上 (A) が4名， 80点未満70点以上 (B) が1名， 70点未満60点以上 (C) が2名， 60点未満 (D) が2名です．
• 得点掲示 (辞書順に並べています)

  aksw	69
  cpwPV	72
  eeee3	84
  qazwsx	112
  SUSHI	62
  tmmsm	82
  去年の平均	54

• 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
• 講評
  • 総評：想定していたよりもよくできていたと思います．問3，問5は授業でやったものをそのまま出したので，よく準備をしてきてもらえたのだと思います．一方で，問1の誤答が多くて，それには驚きました．以下，各問題に対する平均点も記載します．
  • 問題1：平均点は11.1． 木分解を実際に作る問題．細かい採点基準があったのですが，結局，配点は0点か20点になっています．受験者は9名なので，つまり，5名は完答して，4名は不正解だった，ということです．これは出来ていてほしかったです．
  • 問題2：平均点は15.6． 道幅と道の関係．これは問題1よりもできていました．それに驚きました (むしろ，問題1のできが悪いことにまだ驚いています)．いろいろな例がありますが，どれであっても正しければ構いません．
  • 問題3：平均点は14.7． 動的計画法の問題．授業でやったものなので，そのまま書いてもらえればよいです．
  • 問題4：平均点は5.56． 完全二部グラフの木幅を定める問題． これは出来が悪かったです． 「○○であることは自明」という書き方は証明にならないので，ご注意ください． 下界の方はマイナーを使うとよいです．上界の方は実際に木分解を構成して下さい．
  • 問題5：平均点は17.2． 単項二階論理式を書く問題．授業でやったものなので，よくできていました．
  • 問題6：平均点は10.0． オートマトンを構成する問題．いまいちでした．完答できている人はいません．「a」はLの要素ではなく，受理してはならないので，注意して下さい．

• 10/7 (1) 離散最適化における木分解の役割
• 10/14 国内出張のため休み
• 10/21 (2) 木に対するアルゴリズム設計
• 10/28 (3) 道分解と道幅
• 11/4 (4) 道分解を用いたアルゴリズム設計
• 11/11 海外出張のため休み
• 11/18 (5) 木分解と木幅
• 11/25 調布祭 のため 休み
• 12/2 (6) 木幅の性質
• 12/9 (7) 木分解を用いたアルゴリズム設計
• 12/16 (8) 木分解を用いたアルゴリズム設計：連結性
• 12/23 天皇誕生日 のため 休み
• 1/6 (9) 木幅と論理：単項二階論理
• 1/13 センター試験準備 のため 休み
• 1/20 (10) 木幅と論理：オートマトン
• 1/27 (11) 木幅と論理：アルゴリズム設計
• 2/3 (12) 木分解構成アルゴリズム
• 2/10 (13) 固定パラメータ・アルゴリズムと木幅
• 2/17 期末試験

• 動的計画法 東京理科大学 小林先生
• The 1st Parameterized Algorithms and Computational Experiments Challenge --- Track A: Tree Width
• Sequoia A fast EMSO-solver for graphs of small treewidth
• ToTo An open database for computation, storage and retrieval of tree decompositions

• Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.
• Jörg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006.
• Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Parameterized Algorithms, Springer, 2015.

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