離散最適化基礎論
電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
2025年度後学期
火曜2限 (10:40-12:10)
教室：西8-132
岡本 吉央
テーマ：高速指数時間アルゴリズム
注意：テーマは毎年変わります
ショートカット：
講義資料 |
コメント |
レポート課題 |
公式シラバス |
スケジュール |
参考文献 |
関連リンク |
過去の講義
実施形態
この授業はハイブリッド形式で行います．授業は教室からZoom配信します．スライドはZoomで共有し，板書も教室の黒板では行わず，Zoomで共有したスライドの上から行います．教室では，Zoomの画面をプロジェクタで投影します．そのため，教室で受講することのメリットは (1) ライブ感，時空間共有感覚を持てる，(2) 質問を口頭で即座にできる，(3) ネットワークトラブルに影響されない，などといった点にあります．授業は録画し，あとで公開します．
学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．
内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．
講義資料
- 講義動画の再生リスト
- 1/13 (11) 指数時間仮説：原理
- 1/6 (10) 部分集合たたみ込み：例
- 12/16 (9) 部分集合たたみ込み：原理
- 12/9 (8) 包除原理：例
- 11/25 (7) 包除原理：原理
- 11/18 (6) 動的計画法：例
- 11/11 (5) 動的計画法：基礎
- 11/4 (4) 分枝アルゴリズム：測度統治法
- 10/28 (3) 分枝アルゴリズム：高速化
- 10/21 (2) 分枝アルゴリズム：基礎
- 10/7 (1) 高速指数時間アルゴリズムの考え方
コメント
- 1/13 (11) 指数時間仮説：原理
- 今日の授業の前半の内容は比較的に簡単でしたが、後半の内容は難しかったです。
--次回は疎化補題を使うことはなく，そこから得られる結論だけを使うことになると思うので，後半については雰囲気が分かれば十分だと思ってください．
- 疎化補題のg、l、φiが抽象的でイメージしにくく難しかったので、証明のためだけに考えられたのか、実際に実装されているのかが気になりました。NPの話は他の講義などで以前にも少し聞いたことがありますが、未解決であることもあって仮定の話が多く、難しいと改めて思いました。
--証明のためだけに考えられた，と考えるのがよいと思います．ただ，実装することもできると思います．(証明 (アルゴリズム) は特殊な分枝規則に基づく分枝アルゴリズムです．)
- 疎化補題に関して，1. $g(l)$は増加関数でしょうか．2. 指数時間仮説が正しいと仮定したもとで，$3$-SATを節数に関する準指数時間で解くことはできないことを証明する際に，$l = 2/\varepsilon'$ として，疎化補題を適用していますが，$2/\varepsilon'$ が整数でない場合でも問題ないのでしょうか．
--分けてお答えします．
(1) g(l)は増加関数とすることができます．
(2) 整数でない場合は問題がありますので，本来はその小数部分を切り上げたり切り捨てたりして，整数にする必要があります．その部分は煩雑になるので，授業では端折りました．このように丸めても高々1しか違わないので，今回の授業であつかったオーダー記法では，その係数に違いが吸収され，結論に変わりはありません．
- 疎化補題は「節数が変数の個数の $3$ 乗オーダーになるという意味で長い $3$-SATを解くことを，節数が変数の個数の線形オーダーになるという意味で短い $3$-SATを複数回解くことに変換できる」ところにうれしさがあるのかなってところまでは，分かったつもりになったのですが，$l$の役割がまだ整理できていない状態です．参考にしたいので，$l$の役割に関して，解釈の一例を教えてくれませんか．
--lは，出来上がった論理式が疎である具合と出来上がった論理式の数のトレードオフを表しています．lが大きいと出来上がった論理式の数を小さくできますが，その代わりに各論理式の節の数が増えます．lが小さいと各論理式の節の数を小さくできますが，その代わりに論理式の数が増えます．
- 増加 (減少) 関数に関する言葉で，狭義と strictly は対応している表現としてよく見かけますが，strictly のような表現で広義に対応する英語の単語って確かにパッと思いつかない…
--はい，私も対応する英語を知りません．日本語においても「広義増加関数」という言い方はあまり具体的ではなく，分かりにくいと思っています．なお，「広義積分」は英語でimproper integralと呼ぶようです．
- リトルo記法は知らなかった． そもそも，今までO記法をΘ記法だと思っていた． P=NP問題について，同値が沢山出てきて面白かった． 今頃だが，中間レポートでどれだけ得点できたかが気になる． 採点結果を教えてもらうことはできるのでしょうか？
--すみませんが，採点はまだ完了しておりません．少々お待ちください．
- 小さい方は「おmicron」大きい方は「おmega」
--はい，そのとおりですね．O，Ω，Θ記法をポピュラーにしたのはクヌースだと言われていますが，クヌースの論文のタイトルは「Big Omicron and big Omega and big Theta」だったようです．
- nlognのようなやつの大きさ感が自分の中にないなぁと思いました 。o(n^k)なら分かりやすいんですが。
--「log n」というのは分かりにくい関数だと思います．そのグラフを見ても，n→∞において無限大に発散するようには見えないと思います．実際に，いろいろな現象においてlog nは現れますが，小さなnで実験や観察をするだけではそれが発散するようには思えないと思います．私自身，log nのことを「無限大に発散するが，誰も無限大に発散するところを見たことがない関数」と説明したりします．
- 前に最大クリーク問題自体は習ったのですが今回みたいになぜそうなるのかまでは説明がなかったので知れてよかったです
--それはよかったです．
- 今までP NP問題関連の勉強をあまりしたことが無かったので、よい学びになりました
--PとNPに限らず，計算複雑性に関する理解は情報系専門家にとって学ぶべき重要な知識・技術だと思っています．ぜひ慣れてください．
- 本日もありがとうございました。アルゴリズムを考える際には、解きたい問題の計算時間の限界まで考えることを意識したいと思います。
--重要な意識だと思うので，ぜひ励行してください．
- 卒論がんばります
--はい，がんばってください．
- 授業の終わりに次回予告があり、また授業の始めには前回の内容を振り返ってくださるため、全体の流れを意識しながら理解を深めることができています。
--必要な復習を適宜いれるように心がけています．復習をだらだらと行ってしまうために，本題にかける時間がなくなってしまうような授業を見ることもありますが，それはよくないと思っているので，必要な復習だけに留めています．
- 本日も興味深い内容でした
--次回もそうでありますように．
- 本日もありがとうございました
--こちらこそありがとうございました
- 本日もありがとうございました．
--こちらこそありがとうございました．
- 本日もありがとうございました
--こちらこそありがとうございました
- 本日もありがとうございました。
--こちらこそありがとうございました。
- 今日もありがとうございました
--こちらこそありがとうございました
- ありがとうございました
--こちらこそありがとうございました
- 本日もありがとうございました！
--こちらこそありがとうございました！
- 本日もありがとうございました。
--こちらこそありがとうございました。
- 1/6 (10) 部分集合たたみ込み：例
- あけましておめでとうございます
--おめでとうございます
- あけましておめでとうございます。後半の授業も復習しながら理解を深めていきます。
-- おめでとうございます．
- あけましておめでとうございます、少し間が空いたので復習しておこうと思います
--おめでとうございます
- 明けましておめでとうございます。今年もよろしくお願いします。
--こちらこそよろしくお願いします。
- 明けましておめでとうございます。今年（今年度）もよろしくお願いいたします。
--こちらこそよろしくお願いいたします。
- あけましておめでとうございます。本年度もよろしくお願いします。
--こちらこそよろしくお願いします。
- 明けましておめでとうございます．今年もよろしくお願い致します．
--こちらこそよろしくお願い致します．
- 本日もありがとうございました！
--こちらこそありがとうございました！
- 本日もありがとうございました
--こちらこそありがとうございました
- 授業ありがとうございました
--こちらこそありがとうございました
- ありがとうございました
--こちらこそありがとうございました
- 本日もありがとうございました．
--こちらこそありがとうございました．
- 本日もありがとうございました。
--こちらこそありがとうございました。
- 本日もありがとうございました。\sum_{T \in S} f(T) g(S - T) の形は覚えておきたいと思います。
--この形や min{f(T) + g(S-T)} の形はよくでてきます．ぜひ使えるようになってください．
- 今日の講義で理解できなかった部分を復習したいと思いつつ，卒論も書かないといけないので，うまく時間を使いたいと思います．
--時間がうまく使えるというのは重要な技術だと思います．ぜひうまく使えるようになってください．
- fa,b(G)の再帰式の理解が他のことに比べてできていないため、復習しようと思います。13ページの(f∪g)({a})が-5ではないのかと思いました。
--はい，ご指摘のとおりで，(f∪g)({a})は-5が正しいです．ありがとうございます．修正しました．
- 前回から十分大きな数Bを持ってくるの箇所がよくわからなかった(小さいと何の問題が起こるのか)が，今回でZ変換のように多項式の係数に情報を乗せたいということだと理解？した． 少しでも具体的なイメージが持てるように手計算で追っていたが，６ページの(f*g)({b})は８じゃなくて５，12ページの(fUg)({a})は-2じゃなくて-5な気がする．
--はい，ご指摘のとおりで，(fUg)({a})は-5が正しいです．ありがとうございます．修正しました．
十分大きな数Bを持ってくるところのイメージはそのとおりだと思います．組合せ論の文脈では，Z変換のことを(通常型)母関数と呼ぶことが多く，よく使われます．
- 体くらい (場合によっては，環くらいでいいかもしれませんが) 計算が割ときれいにできるお行儀のいい構造があれば，その構造に入っているモノを二つ用意し，それを入力として「計算」ができるのは，当然だと思うのですが「その構造に入っているモノを一列に並べたもの (無限にたくさんあってもいいけど，並べたものに番号づけはできるくらいの個数とする / 多項式をイメージして書いています)」を二つ用意して，それを入力としたお行儀のいい「計算」も色々知られているのは，大変ありがたいです (多項式環を念頭に置いてこの文は書かれています) ．「並べたもの」二つを入力として「計算」したいときに発生する特有の現象を表現するために，多項式の次数がうまくはたらいているのかなーというイメージがあります．
--多項式を扱うというのは技巧的になりがちなのですが，それだからこそいろいろなことができるようになり，いろいろな場面で使われることになります．授業では1変数多項式 (Bを変数とする多項式) を考えましたが，多変数多項式を考えて離散数学の問題を解くこともあります．
- $f_{a,b}(G[X])$の再帰式をよく見ると，計算に必要なものは$X$より要素数が小さいもの$X'$に関する$f_{a,b}(G[X])$であって，その範囲であれば，$a,b$の値は考慮する必要があるどの場合であってもすでに計算済み (特に$b$に関して計算済みであることが重要) であるから，$|X| \geq 2$の場合は，$b$の再帰の開始が$2$からであっても問題ないのですね (あと，$|X| = 1$の場合は，$f_{a,b}(G[X])$の値が定数で定義されていることも重要) ．
--はい，そのとおりです．一番外側のループが|X|に関するループなので，|X|が大きくなったとき，|X|が大きくなる前のすべてのa, bに対して計算が終わっていることになりますし，再帰では必ず集合の部分の要素数が小さくなっています．
- 今回のアルゴリズムは難しく感じたのでしっかり復習しようと思います。
--はい，ぜひ復習をお願いします．
- 本日もありがとうございました。2週間ぶりなので、前回の内容はほとんど忘れてしまいました。今から復習しようと思っています。
--私もほとんど忘れていました ;-)
- 前回に引き続きアルゴリズムの中身を理解するのに苦労した
--それは私の説明がよくなかったのだと思います．説明がよくないというのは，私もよく理解できていないということなのだと思います．私自身もうまく理解できるように努めます．
- ここまでの講義で，いろいろな問題に対して $c^n$ (ただし，$c < 2$) オーダーで，問題が解けるかどうか未解決である，という旨の主張が紹介されましたが，整数同士の掛け算もカラツバ法が発見されるまでは，入力の桁数の2乗より小さいオーダーでは解けないだろうと考えられていたらしいですね．第1回の講義の説明を思い出すと，多項式オーダーの肩が小さくなるのと，指数オーダーの底が小さくなるのでは，ずいぶん事情は違うのですが，予想である以上，誰かが (自分でもいいですけど) オーダーを小さくする方法見つけてしまうかもしれないと思うとワクワクします (高速化できないという結果が出てきてもワクワクしますが) ．
--アルゴリズムや計算理論という分野は未解決問題ばかりです．多項式時間アルゴリズムのほうに関することとしては，例えば，最小全域木問題が線形時間で解けるかどうかは未解決です．アルゴリズムの授業ではクラスカル法やプリム法というものがよく扱われますが，それらが知られている中で理論上最速のアルゴリズムというわけではありません．そして，理論上最速のものでも線形時間にはなっていないというのが現状です．
- 指数時間仮説は言葉だけ何度も見たことあったのに，今まで自分でちゃんと調べたり勉強したりしたことが無かったので，講義で触れてくれるということで楽しみです！
--はい，これが次回のメインテーマになります．お楽しみに．
- 期末レポートの出題日，提出期限，範囲は，いつ発表されますか？また，今の段階で何かわかりますか？
--1月末ごろが出題日になり，そこから約2週間後が提出期限になる予定です．第7回から第12回の内容の理解を確かめる内容になる予定です．
- Pure logical thinking can give us no knowledge whatsoever of the world of experience; all knowledge about reality begins with experience and terminates in it. (Albert Einstein, On the Method of Theoretical Physics より)
--おそらく，このことばのなかで「pure」という部分をアインシュタインが意図的につけていて，これは重要だと思います．pureでない論理的思考というものもありうるのですが，それは経験に裏打ちされることもあるように私は感じ，それだからこそ論理的思考が現実世界でも重要な役割を果たすのだと思います．
- 12/16 (9) 部分集合たたみ込み：原理
- Creative thinking may well mean simply the realization that there's no particular virtue in doing things the way they have always been done. (1995年度 東京大学 入学試験 英語 第4問より)
--「創造的思考」や「批判的思考」を大学生は学ぶべきだと思いますが，そのためのレシピがあるわけではないとも思います．そうであっても，私は，数学を勉強することはそれらを身につけるための方法としてとても有効なものであると思っています．特に，大学において，他の学生や教員と一緒に考えるということが重要だと思っています．(独学で創造的思考や批判的思考を身につけるのは困難だと思います．)
- 最後の変換の計算に関してはxがSに含まれない時はxを気にせずf0を使うということだと思ったのですが、含まれるときのイメージがいまいち浮かびませんでした。何か簡単な例があったら知りたいです。
--含まれているときに $f_1$ を使います．含まれているときに，$f_1(S)$ の引数 $S$ が $x$ を必ず含むようにしたいのですが，数学としてそのように書くには，まず $f_1\colon 2^{U-\{x\}} \to \mathbb{R}$ として定義し (つまり，引数に $x$ が含まれないようにして)，$S \subseteq U-\{x\}$ に対して，$f_1(S) = f(S\cup \{x\})$ とするようにしています．
スライド6ページ目 (あるいは7ページ目) の $f$ を使って例示します．
このとき，$U=\{a,b,c\}$ ですが，$x = c$ とします．すると，$U-\{x\}=\{a,b\}$です．
$f_0\colon 2^{U-\{x\}}\to \mathbb{R}$ は次のように定まります．
- $f_0(\emptyset) = f(\emptyset) = 0$
- $f_0(\{a\}) = f(\{a\}) = -1$
- $f_0(\{b\}) = f(\{b\}) = 4$
- $f_0(\{a,b\}) = f(\{a,b\}) = 2$
また，$f_1\colon 2^{U-\{x\}}\to \mathbb{R}$ は次のように定まります．
- $f_1(\emptyset) = f(\emptyset \cup \{c\}) = f(\{c\}) = 5$
- $f_1(\{a\}) = f(\{a\} \cup \{c\}) = f(\{a,c\}) = 3$
- $f_1(\{b\}) = f(\{b\} \cup \{c\}) = f(\{b,c\}) = -2$
- $f_1(\{a,b\}) = f(\{a,b\} \cup \{c\}) = f(\{a,b,c\}) = 1$
ここでは，$f$ から $f_0, f_1$ を作ったのですが，逆に，$f_0, f_1$ から $f$ を次のようにも復元できます．
$\displaystyle f(S) =
\begin{cases}
f_0(S) & (x \not\in S)\\
f_1(S-\{x\}) & (x \in S)\\
\end{cases}$
いかがでしょうか．
- ゼータ変換やメビウス変換の計算のところは，正しいことを確認するだけなら，総和記号を使った式表示の方が，個人的には楽だと思います．式表示したときに「この部分はこの辺の計算をしている！」って気分を説明するときに，図は便利な気がします．
--授業でやってみたあとで，そうだったかもしれないと思いました．ここで，式を使って証明したいと思います．ゼータ変換の方だけやります．
まず，定義を思い出します．集合関数 $f\colon 2^U \to \mathbb{R}$ に対して，$\displaystyle \zeta[f](S) = \sum_{T\subseteq S}f(T)$として，任意の要素 $x \in U$ を固定して，集合関数 $f_0, f_1\colon 2^{U-\{x\}} \to \mathbb{R}$ を，$f_0(S) = f(S)$，$f_1(S) = f(S\cup \{x\})$ で定義します．
このとき，$S\subseteq U$ が $x \in S$ と $x \not\in S$ のどちらを満たすかで場合分けして，$\zeta[f](S)$ が $f_0$ と $f_1$ のゼータ変換を使ってどう書けるか考えます．
$x \not\in S$ のとき，$f(S) = f_0(S)$ であり，任意の $T\subseteq S$ に対しても ($x \not\in T$なので) $f(T)=f_0(T)$となります．そのため，$\zeta[f](S) = \zeta[f_0](S)$ が成り立ちます．
$x \in S$ のとき，
$\displaystyle \zeta[f](S) = \sum_{T\subseteq S}f(T) = \sum_{T \subseteq S\colon x \in T}f(T) + \sum_{T \subseteq S\colon x \not\in T}f(T) = \sum_{T-\{x\} \subseteq S-\{x\}} f((T-\{x\})\cup \{x\}) + \sum_{T \subseteq S-\{x\}}f(T) = \sum_{T' \subseteq S-\{x\}} f_1(T') + \sum_{T\subseteq S-\{x\}}f_0(T) = \zeta[f_1](S-\{x\}) + \zeta[f_0](S-\{x\})$ になります．
- ちょうど読んでいた論文で，部分集合畳み込みとかメビウス変換とかゼータ変換とか（あるいはそれに類する概念）が，息をするように出てきていて，独学で勉強はしていたのですが，今日の講義のおかげで理解がより鮮明になりました（特にゼータ変換に対応する部分の感覚）．すごく助かります．
--お役に立てたのならよかったです．ぜひ活かしてください．
- シュタイナー木と動的計画法と方針はなんとなくわかりましたが，最小和の計算やζ変換の使い方からりかいできなくなってしまいました．しっかり復習したいと思います．
--時間が余ってしまったのですから，もっとゆっくりと丁寧に説明するべきだったと思います．復習をお願いします．
- μとかζとか文字をたくさん置きすぎると，何が何だったのか分からなくなって結局，導出をもう一回初めから見返すことが数学で多いです．物理学だと置く文字と意味が紐づいている(m：質量 etc.)ので分かりやすいのですが．
--たしかにそうですね．分かりにくくてすみません．μとζは歴史的な経緯で使われている記号だと思いますが，別の文字でもよかったのかもしれません．
- ゼータ変換とメビウス変換が互いに逆変換になっていることを後で自分で確認してみたいと思います。
--補足動画もあげました．ぜひ確認してください．
- 学部のときに信号処理の授業とフーリエ解析の授業を受けましたが、しばらく畳み込みを見ていなかったので、懐かしいと思いました．
--たたみ込みはいろいろな場面で出てくる，とても重要な考え方なので，ぜひ使えるようになってください．
- たたみ込みに触れるのは久しぶりだったため、思い出していきたい
--そうですね．ぜひ復習してください．
- 本日はシュタイナー木、ゼータ、メビウス変換など知らないものが沢山出てきたので、復習して身につけていきたい
--はい，ぜひ復習してください．
- 集合にも畳み込みが定義できるのが面白かった．シュタイナー木での応用は，畳み込みの定義を変えた後あたりから一気に置いて行かれてしまったので，しっかり復習したいと思う．ゼータ変換，メビウス変換は互いに逆変換になっているのが面白かった．
--離散数学においてもこのように「周波数領域」を考えることが有用であると，いろいろな場面で明らかになってきています．その理由のひとつは，離散構造の対する摂動を考えたいからです．普通の信号処理では，摂動は高周波成分が少し動くことだと考えることがありますが，それと同じようなことを離散構造に対して行おうとすると，離散構造の高周波成分のようなものを考えられるとよいように思えます．
- 授業内の説明で定義から理解できてよかったです。
--それはよかったです．用語には定義があるということを理解することがまず重要ですね．
- 今回初めて対面で講義を受けました。遠隔で受けるよりも集中できた気がします。
--対面と遠隔では良い面に違いがあると思います．違いに着目して，ぜひ活かしてください．
- 研究室でウイルスが流行していたため、本日はオンラインで参加させていただきました。先生も体調にはお気をつけください。
--ありがとうございます．お互いに体調には気をつけていきましょう．
- 体調を崩してしまいました。先生もお体に気を付けてください。
--ありがとうございます．お互いに体調には気をつけていきましょう．
- 知識として知っていても使いこなせない悲しみを感じている
--そうですね．「知っている」ことと「知っていることを使える」ことの間には埋めがたいギャップがあるように思います．皆さんは，専門家という人のことを「いろいろなことを知っている人」のことだと思っているかもしれませんが，本当の専門家は「いろいろなことを知っていて，それを使える人」だと私は思っています．少なくとも，私は専門家としてそれを目指しています．
- 本日もありがとうございました。
--こちらこそありがとうございました．
- 本日もありがとうございました!
--こちらこそありがとうございました．
- 本日もありがとうございました。
--こちらこそありがとうございました．
- ありがとうございました。
--こちらこそありがとうございました．
- ありがとうございました
--こちらこそありがとうございました．
- ありがとうございます！
--こちらこそありがとうございました．
- 12/9 (8) 包除原理：例
- 私が勘違いしていなければ，ウェブページにアップロードされている授業スライドは，最新になっていません．スライドP.20が修正前の物になっています．
--10:40の時点では新しいものになっていたはずです．私が授業で使ったスライドはダウンロードしたものなので．
おそらくキャッシュに古いものが残っていたのが原因で，それを捨てるか，強制リロードをしないと，新しいものが見えなかったのかもしれません．
なお，スライドの更新時刻 (私がコンパイルした時刻) は1ページ目に書いてありますので，スライドの新旧はそれを使って判断できます．
- 本日もありがとうございました！
--こちらこそありがとうございました．
- 今日の授業お疲れ様でした。よかったです、ありがとうございました！
--よかったですか．ありがとうございました．
- ありがとうございました。２週間ぶりのため前回の内容をほとんど覚えていませんでした...。これを機に復習しようと思います。
--間があくと，ペースが狂いますよね．ぜひ復習をしてください．
- 授業ありがとうございました！また来週はインターンシップ参加のため、授業が出席できなくなる。本当に申し訳ございません。後で先生に正式なメールを送ります。本当に申し訳ございません。
--この授業に限ってお伝えすると，黙って欠席しても問題ありません．出席も確認していません．
- 思ったより中間レポートが難しかったです。
--何を思っていただくのかは自由ですから，問題ありません．
- ありがとうございました。
--こちらこそありがとうございました．
- なんとなくわかったような気になっているが
--「なっているが」で切れてしまってますか？ 続きが気になります．
- 久しぶりに文字を書くと感じが思い出せなくなる現象にとても共感します！あと，iPadでノートを取っていると，紙に文字を描くときに違和感を感じることがあります．(投げ縄が使えなかったり消しゴムの利便性など)
--私もたまに，紙に書いてあるものを読むときに，ピンチ操作で拡大しようとして，それができないことに気づくことがあります． ;-)
- 授業ありがとうございます。最近急に寒くなってきたのでご体調にお気をつけてくださいm(_ _)m
--ありがとうございます．お互いに体調には気をつけましょう．
- 包除原理について、より詳しく学ぶことができた
--原理自体は単純なので，ぜひ使えるようになってください．
- 本日の講義もありがとうございました。包除原理を彩色問題に応用する流れがとても理解しやすかったです。
--こちらこそありがとうございました．伝わったようで，うれしいです．
- 最初にASの定義を見聞きしたはずなのにWhitneyの公式のASが全てを満たす必要があることを忘れていた。今回のように他のことを学ぶうちに最初のころのものを忘れてしまうこともあるのできちんと復習をしようと改めて思った。
--Whitneyの公式のところでASの復習をしなかったのがよくなかったと思います．失礼しました．
- 包除原理を用いたアルゴリズムの設計の仕方がなんとなくですが理解できました。
--実際に適用しようとしてみると，なかなか難しいのかもしれないです．適用できそうな場面がありましたら，ぜひチャレンジしてみてください．
- いつか4色問題をコンピュータに頼らないで証明する人が現れないかな。
--五色定理には簡単な証明が知られています．授業で扱おうと思えば (グラフや彩色についてある程度の準備ができていることを仮定すれば) 20分ぐらいで紹介できます．
- k彩色で、下から探索するより上から抑えた方が早そうと思った。辺密度などから推定できないのだろうか
--最小色数に対する上界と下界が簡単に得られれば，それを使って二分探索を行うようなことはできます．上界が|V|で下界が0だというつまらないものであっても，二分探索によってk彩色問題を解く回数をO(log|V|)に抑えることができます．一方で，これらよりもよい上界や下界が分かれば，もっと探索にかかる時間を減らすことができます．
上界としては最大次数+1がもっとも簡単だと思います．下界の方はあまり簡単なものが知られていない気がしますが，例えば，Iを最大独立集合とするとき，|V|/|I| は必ず最小色数に対する下界になります．
- 比較的単純なロジックでもまだ誰も気がついていないものがあるかもしれないと考えると、研究の世界は奥深いなと感じました。
--まさにそうだと思います．「言われれば分かる／作れる」ということと「自分で見つける／作る」ということの間に大きなギャップがあることをいつも感じます．
- まだ見つかっていない、比較的簡単な手法で計算量が改善できるアルゴリズムがあると思うとロマンがありますね
--最近，アルゴリズムの研究では単純さ (simplicity) が注目されるようになっています．研究者は複雑で細かいアルゴリズムを考えすぎてきた気がします．これはアルゴリズムだけではなく，ソフトウェアやハードウェアの設計においてもあるべき姿なのかもしれません．
- 彩色問題が$O^{*}(2^n)$で解けることの議論，見れば見るほどなんでこれが2009年まで広く知られてなかったんだ思えますね (様々な問題を解くアルゴリズムの計算量に関する2009年以前の研究で，今日の講義で見た議論より難しかったり，計算機が未発達な時代の先人の観察眼に驚かされる研究はごまんとあるのに)．
--口頭では述べましたが，これが発表されたのは2006年で，それが完全な論文として出版されたのが2009年になります．その意味では，2006年になるまで広く知られていなかった，という方が正しいのかもしれません．いまでは，ここから発展した手法が当たり前のように使われるようになっています．
- 講義資料では chromatic polynomial を「染色多項式」と言ってましたが，グラフ理論やグラフ・アルゴリズムの分野において，chromatic polynomial は「染色多項式」と「彩色多項式」のどちらで訳されることが多いと思いますか．ネットで検索をかけると「彩色多項式」の方が多いように見えたのですが，伝統的な書籍とかだと「染色多項式」の方が多かったりするのでしょうか．
--伝統的かどうかという判断は難しいのですが，グラフ理論では「染色多項式」とします．アルゴリズムの文脈でchromatic polynomial (の日本語訳) が登場することは見たことがないのですが，もしあるのならば「彩色多項式」と訳すことになると思います．『岩波数学辞典 第4版』には，「染色多項式または彩色多項式」と書いてあります．
それに関連して，グラフの彩色で用いる色の数の最小値をそのグラフのchromatic numberと呼びますが，グラフ理論ではこれを「染色数」と呼び，アルゴリズムの分野ではこれを「彩色数」と呼びます．
以下個人的意見ですが，coloringの訳が彩色なのですから，chromatic numberの訳が彩色数であるのはおかしいように思います．ちなみにcoloring numberという概念もグラフ理論にはあり，これはchromatic numberとは異なるものです．
- 彩色と独立集合被覆列の間に，存在性に関する同値性はあるけど，自然に見える対応が多対多なので，数え上げに帰着して考えようとは普通ならないですよね…
--授業でちゃんとお伝えしていなかった (することを忘れた) ので，ここで補足しておきますが，「独立集合被覆列」という用語(?)は私の造語です．このような概念が今回紹介したアルゴリズムが提案される前から存在していたわけではないと思いますし，提案した論文でもそのような名称を与えているわけではありません．ご注意ください．
- 11/25 (7) 包除原理：原理
- ありがとうございました
--ありがとうございました．
- 本日もありがとうございました。
--ありがとうございました．
- 本日もありがとうございました。
--ありがとうございました．
- 授業ありがとうございました！
--ありがとうございました．
- 本日もありがとうございました。良いレポートを出せるように努めます。
--ありがとうございました．
- 本日もありがとうございました。就職活動の予定が落ち着いたので、そろそろレポート課題に着手しようと思います。
--はい，しっかりと準備をしてください．
- 授業ありがとうございました。最近自分の課題いっぱいあります、またソニーのインターン面接もあります、必死に頑張っています。
--ありがとうございました．
- 調布祭の初日にインフルを発症しました．楽しみにしていた調布祭に行けず悔しいです．まだ完治していないので今日もオンラインで受講しました．早く治して，また対面で受講したいです．
--お大事にしてください．
- 今回はいつもより授業の進みがゆっくりだった気がします．
--前半はそのように意識しました．そのため，後半で間に合わなそうになって，少し速くなったと思います．うまくペースを掴めるようにしていきたいと思っています．
- レポートもあるので、理解が追いつけるように復習しながら学んでいきたい
--はい，しっかりと復習をしてください．
- 復習して理解したいと思います
--はい，しっかりと復習をしてください．
- ありがとうございました。またアーカイブも見返しながら復習します。
--はい，動画もありますので，活用してください．
- 今日もお疲れ様でした！授業の内容はあいかわらずわかりやすくて面白かったんです。
--面白かったんですね．ありがとうございました．
- 来週も彩色問題を取り扱うため、復習しておこうと思いました。
--はい，次回は彩色問題を扱います．授業でも復習からはじめる予定です．
- 包除原理の意味と定義を再確認できた．どこで高速化の工夫をするのか楽しみ．
--彩色問題を包除原理によって解きますが，動的計画法とは似ているところもあり，違うところもあります．次回，ぜひ味わってください．
- 包除原理とDPで高速な数え上げを学んだ
--そうですね．包除原理は簡単な原理なのですが，それを使おうと思うと工夫が必要になるので，そのコツを掴んでください．
- 包除原理を分かりやすく説明していただいてありがとうございます
--こちらこそありがとうございます．ぜひ使えるようになってください．
- ハミルトン図の具体例などが載っている資料でおすすめのものはありますでしょうか
--第5回で扱った巡回セールスマン問題 (を動的計画法によって解くときに考えているもの) はハミルトン路になっています．巡回セールスマン問題の文献を見ると，ハミルトン路や (それを閉じたものである) ハミルトン閉路が載っています．例えば，Traveling Salesman Problemのページには関連する情報や図が豊富に載っています．参考にしてください．
- ハミルトン路における「ちょうど1回現れる」のような，重複を考慮する条件は，数え上げを考えると自然に出てくるのに，いざ考慮すると扱いが難しいことが多いと思います．
--はい，そのとおりだと思います．そのため，包除原理がうまく使えるのだとも言えるように思います．
- 離散数学の内容を思い出しました
--そうですね．昔勉強したことは，覚えようとはせずに，このような機会で必要となったときに思い出せれば十分だと思います．
- 以前強化学習の勉強をしていた時に出てきたbellman方程式がハミルトン路を解く際にも使われることが興味深いと思った
--Bellman方程式は動的計画法における基本的な考え方で，それが強化学習にも使われていると考えるのがよいように思います．
- 二部グラフの定義に $V_1 \cap V_2 = \emptyset$ は要らないのでしょうか．
--必要です．ご指摘ありがとうございます．修正したスライドにはその点を書き加えました．
- 総数の偶奇にするだけで考え方を変えることができるから難易度が変わるのは面白いと思いました。
--偶奇の問題の難しさはよく分かっていないことが多いと思います．計算理論を深めるうえでは重要な問題なのですが，応用の上で解く要請はほぼないこともあって，あまり研究されていないように思います．
- 数え上げ→偶奇→存在の順に包含しているのが新しい視点だった。
--そうですね．このように，問題の間の難しさや易しさを比べることは計算複雑性理論の研究対象の1つです．数え上げやそれにまつわる問題の難しさに関する研究は1980年代に盛り上がって，戸田の定理でその高みを見たように思います．その技法は暗号理論や近似最適化に使われるようになって，最近では量子計算量理論との関わりも研究されているようです．なお，戸田の定理の戸田先生は電通大の卒業生です．(東3号館のロビーに写真が飾ってあります．)
- この講義で様々な最適化方法を学習したが、未だそれを使える段階には至っていない。
--まず，使ってみようと思ってみることが重要だと思います．無理に使う必要はないかもしれませんが，使ってみようと思わないと使えるものも使えないので．
- 文化祭の研究室公開で知らない人に対して、研究の話をするのが苦手です。どうしたらよいのでしょうか？
--話す内容を準備しておくのが大事だと思います．その場でいちから話す内容を考えることになれば，うまく伝えることはできないでしょう．それは研究の話であるかどうかということとは関係なく，どんな話でも成り立つと思います．
それを踏まえた上で，研究の話においては，相手の立場や興味に従った内容に絞ることが重要だと思います．高校1，2年生ぐらいをターゲットにして話をまとめておくとよいように思います．自分がそれぐらいの年代であり，大学の研究室公開に来ようと思ったとき，どのようなことを知りたいのか，ということを想像してください．実際に来場する方が高校1，2年生であるとは限りませんが，その程度に合わせれば多くの人には合うはずです．
- 最後に，読者は本書の各篇において，そこで問題になっている数学者の伝記や逸話めいたことについて，実際には何の情報も得られないであろう．本書で，もっぱらやろうとしたことは，おのおのの理論について，指導的理念はどのようなものであり，それらはどんなふうに展開され，またおたがいにどんな影響をあたえあったかというような事柄を，できるだけ明晰に示すことだったのである． (二コラ・ブルバキ 「ブルバキ数学史 上」序文より)
--一方で，数学の教科書というものは，その歴史的な経緯に沿うのではなく，順序だった体系としてすべてを組み直し，提示するものだと思っています．個人的な意見ですが，数学の教科書というのが50年ぐらい同じような内容を同じ順序で教えているというのはおかしいと思っています．現代的な視点で，あらたに組み直し，時代に合った教え方というものをするべきだと思っています．
- 11/18 (6) 動的計画法：例
- ありがとうございました
--こちらこそありがとうございました．
- 今回は特にありません、いつもありがとうございます。
--こちらこそありがとうございます．質問がありましたら，ぜひお願いします．
- 今日の授業お疲れ！内容も良いと思います。
--褒めていただきありがとうございます．:-)
- とても勉強になりました。ありがとうございます。
--こちらこそありがとうございます．
- 時間ぴったりに授業を行うことはすごいことだと改めて思いました．自分は説明が長くなりがちなので,もっと簡潔に話せるよう心がけたいです.
--私が簡潔に話せているのかどうかはわかりませんが，時間に合わせるにはコツがあると思います．慣れもいるかもしれません．
- 私の主記憶装置の容量が小さいせいで、直前のページに出てきた記号の意味を忘れることが多い。次回までに記憶力を向上させたい。
--これは私のせいです．皆さんの記憶のせいではありません．忘れそうな記号はスライド上に書くか，そうでない場合は，口頭で何だったか説明するように心がけます．ご指摘ありがとうございます．
- 昨日が研究室のゼミで夜遅かったので，寝坊しました．後でオンデマンドで受講します．夜遅くても朝早く起きれるようにならないと社会人としてやっていけない気もします．
--夜遅くせずに，生活のリズムを整えることが秘訣だと思います．
- レポートが難しいそうで、なんか微妙に怖いです…笑笑
--「難しいそう」というのは伝聞だと思いますが，私は難しいといったことは一度もないと思います．
- 動的計画法の応用が面白かった。
--面白いとおもっていただけたなら，よかったです．:-)
- 本日もありがとうございました。彩色問題は個人的に苦手なので頑張ります。
--彩色問題は次々回にまた出てきますが，その際に今回のアルゴリズムの詳細を理解している必要はないので，その点は安心してください．
- 前回の TSP・最小被覆に続き，NP困難問題に対しても，構造を丁寧に分解すれば現実的な指数時間アルゴリズムが得られるという動的計画法の威力を実感しました。
--そうですね．動的計画法を適用できる場面は多いように感じています．ぜひ活かしてください．
- 彩色問題は聞いたことがあったので、内容を知ることができてよかった
--それはよかったです．彩色問題はよく使いますので，ぜひ慣れてください．
- グラフ彩色問題について名前だけは知っていたので詳しくしれて良かったです
--彩色問題はよく使いますので，ぜひ慣れてください．
- 二部グラフの判定問題の時間計算量が多項式で表せることを，$ O^{*} $ を使って説明されたところは「そういう理解もあるのか」と思いました．
--はい，そういう理解もあります．この考え方でk色で塗れることの判定を $O^*((k-1)^n)$ 時間でできることはすぐに分かるのですが，あまり知られていないと思ったので，授業で説明しました．
- 彩色問題を動的計画法で解く方法を、具体例によってイメージしやすく理解することができました。
--はい，皆さんもアルゴリズムや解法を考えるときには，具体例を考えるようにしてみてください．
- 新しい問題が出てきて面白かった．彩色問題はカラフルで楽しい．
--カラフルで楽しいというのは，私もそう思います．:-)
- 「極大値」と「最大値」という言葉を使うときは，同じ順序関係を考えることが多い気がしますが，「極大独立集合」と「最大独立集合」だと，考えている順序関係が異なるので，少しこんがらがりそうです．「最大値」は存在すれば一意に定まりますが，「最大独立集合」は存在しても一意に定まるとは限らないとか．
--はい，ご指摘のとおりだと思います．ただ「最大値」というときの順序はいわゆる擬順序です．つまり，$|S|=|T|$ だからといって，$S=T$ であるとは言えないことに注意しないといけませんね．
- 本日もありがとうございました。彩色問題が現実世界でどのように応用されているかを伺いたいです。
--彩色問題の応用としてよくでてくるもの (あるいは，応用として彩色問題がよく出てくるもの) はコンパイラ最適化です．いわゆる「レジスタ割り付け」ではグラフの彩色が当然のように使われています．
さて，それを述べたところで，応用という考え方について補足します．
皆さんは，ある技法を学んだときに，それを自分の解決したい問題に適用できるかどうか考えてみてください．「いままで何に応用されたのか」ということを勉強しても，そこから新しい研究が生まれたり，新しいビジネスが生まれることはほぼありません．「いままで考えられなかった新しい応用」を考えようとしてください．そのためには，応用先のこと (いわゆるドメイン知識) を深く知っていたり，学んでいる必要があります．大学というのは汎用的な技法も学べますし，深いドメイン知識も学べます．1つの研究室の中で閉じていれば，そのなかの1つしか学べないことになるでしょう．それはもったいないです．自分が専門としない内容の授業を受けて，大学のよさをぜひ活かしてください．
- この講義を通して彩色問題への理解が深まり、そこから四色問題にも似たところがあるように感じた。
--四色問題はグラフの彩色に関係しています．平面的グラフと呼ばれる特殊なグラフが必ず4色で塗れるという定理が四色定理です．
- 彩色問題の包除原理による高速化が21世紀に入ってから提案されたことに驚きました。次回以降の講義も楽しみにしています。
--はい，ぜひ楽しみにしていてください．
- 以前，先生が書いた記事で「計算量の解析は数え上げである」という旨のフレーズを見た記憶があるので，ここに来て包除原理を活用して計算量を減らす展開になるのは，個人的にアツいです（包除原理は，数え上げの原点にして頂点のような道具だと思っているのですが，それは言い過ぎ？）．
--おそらくこれのことだと思います．ここで，「計算量の解析」と「アルゴリズムの設計」は明確に区別しているので，それには注意してください．次回以降，包除原理はアルゴリズムの設計に用います．包除原理を計算量の解析に使うわけではないことが注意点です．詳細は次回説明します．
- $O^{*}(3^{|K|})$ がどのようにして $O^{*}(2^{|K|})$ に改善されるのか次回が楽しみです
--楽しみにしていてください．なお，この議論は次回に行うわけではなくて，年明けになるかもしれません．
- 最短路や全域木を求める方が単純化しやすく、多項式時間で解けるのは当たり前のように感じられる部分があるのですが、最小シュタイナー木が多項式時間でないことを聞き改めて考えると、少し不思議な感じがしました。
--授業の内容から，実際は，頂点のうち半分ぐらいが端末であるとき，最小シュタイナー木問題が難しいことが予想されます．そして，実際，そのようなときにNP困難となります．これがスライドの中で|K|を横軸とした数直線 (あるいは線分) において真ん中あたりが赤くなっていることに対応します．
- スライドの32/37で定義した $ f(X,r) $ について，$r'$ の動く範囲をこれだけ広くしないといけないのかが気になります．dreyfus-wagner アルゴリズムの計算量の観点からすると，これが小さくできたところで指数の底や肩が小さくなる気配が無いので，些末な問題かもしれませんが…
--私の理解が正しければ，$r'$ は $r$ の閉近傍 $N[r]$ から選べば十分であるはずです．そして，ご推察どおり，O*(3|K|) よりも計算量が小さくなるわけではないというのは正しいです．
- 最小シュタイナー木が|K|=2 or |V|のときだけ多項式時間で求められるというちょっと変わった性質をもっており、面白かった
--誤解があるかもしれないので，強調しておきますが，|K|=2 or |V|のとき「だけ」多項式時間で求められるわけではないので，注意してください．例えば，3|K|というのは，|K|=3でも4でも100でも定数なので，そのときは多項式時間で解けます．|K| = O(log n) でも 3|K| = nO(1) で，これはnの多項式なので，このときも多項式時間で解けます．
- 簡単な場合から少しずれた場合でも，なお簡単であるのかそうでないのかは気になりますね．境界が見つけられれば，そこに考えていることの本質が宿っているような気がするので．
--はい，そのとおりだと思います．例えば，2-SATは多項式時間で解けるのですが，3-SATはNP困難でした．この場合は「簡単な場合から少しずれると難しくなる」ということになっています．最小シュタイナー木問題と充足可能性問題はそのような「ずれ」に関する振る舞いが違うのです．
- 最小シュタイナー木は何を抽象化した問題なのか思いつかなかったので、お聞きしたいです。
--授業内で述べたことの繰り返しになるかもしれませんが，説明します．(なお，質問する際は，繰り返しになるかどうかは心配せずに聞いてください．何度でも説明します．)
通信ネットワークの中でいくつかの顧客だけをつなぐネットワークを構成するとき，辺の数を最小にすると最小シュタイナー木になります．
他の例としては，地下資源の採掘 (underground mining) があります．地下にある資源を採掘するとき，地上の1点を根として資源の場所を端末とすると，シュタイナー木をつくれば，それに沿って採掘ができるようになります．
- 任意の二項関係は (有向) グラフで表せるので，それくらいグラフで表せることの制約は緩いと思っています．つまり，色々な問題をグラフを使ってモデル化できることになり，ある意味色々な問題をまとめて扱えるという利便性があるので，グラフの例が多くなってしまうのは仕方が無いような…
--「グラフで表せることの制約は緩い」というのはそのとおりだと思います．一方で，グラフだけが離散数学の対象であると思われると，それは大きな間違いになってしまうと思っています．以前，『数学セミナー』に「離散数学・特に理解したい10の概念」という記事を書きましたが，そこで挙げた10の概念は以下のものでした．
- 対象：グラフ
- 対象：束
- 対象：組合せデザイン
- 対象：論理関数
- 対象：文字列とオートマトン
- 対象：集合族
- 手法：再帰
- 手法：二重の数え上げ
- 手法：鳩の巣原理
- 手法：極大性・極小性論法
グラフは挙げていますが，他にも重要な概念はあります．ぜひバランスよく勉強していただければと思います．
- I know you've been waiting a long time for this. The tracks are made. The songs are ready. Let's take it from the top. (映画「Michael/マイケル」 US版第1弾予告より)
--マイケル・ジャクソンが来日したのは，私が小学生ぐらいの頃だったと思います．もちろん，直接見たことはなく，テレビのニュースで見ただけでした．「マイケル・ジャクソンが原宿のKIDDY LANDを貸し切った」というニュースだけ鮮明に覚えています．
- 11/11 (5) 動的計画法：基礎
- ありがとうございました。勉強になりました。
--ありがとうございました．
- 本日もありがとうございました。前期やった内容もあるのでしっかり復習しておきます。
--はい，ぜひ使えるようになってください．
- ありがとうございました。レポート課題が待ち遠しいです。
--ただいま準備中です．お待ちください．
- ありがとうございました！
--ありがとうございました．
- 最短経路問題は前期でも扱ったが, あまり理解できなかったので本講義で復習してより理解したいと思った.
--はい，ぜひ復習してください．
- 風邪を引いてしまい遠隔で授業を受けたのですが、後からでも復習できるのはありがたいです。先生も体調にはくれぐれもお気をつけください。
--お大事にしてください．
- 動的計画法（DP）の基本概念と、その応用例として巡回セールスマン問題（TSP）と最小被覆問題を学びました
--そうですね．ぜひ復習して，身につけてください．
- 動的計画法は多段決定問題 を体系的に取り扱う研究分野である、ということを今まで聞いたことがなかったので知ることができてよかったです．
--はい，そうなのです．適切な文献にあたれば書いてあることを説明しただけなのですが，そのような理解がちゃんとされていないことは問題だと思っています．Wikipediaでも英語版では「Dynamic programming is both a mathematical optimization method and an algorithmic paradigm.」で始まっていて，正しい認識が書かれているのですが，日本語版では「動的計画法は、計算機科学の分野において、アルゴリズムの分類の1つである。」で始まっていて，認識が正しくありません．どうしてこんなことになってしまっているのか，分かりません．
- 動的計画法は、アルゴリズムの授業で、計算量が多いアルゴリズムを小さな問題に分割して効率化を行う用途で登場するという印象でしたが、実際は多段決定問題に時間軸を追加した分野として発展したことを初めて知りました。
--ある大学のプログラミングのテキストには，動的計画法の説明として「なお、これは単なる 1 つの手法であり、特別に動的でも特別にプログラミングでも何でもありません。この手法を考案した人がそういう名前をつけた、というだけです」と書いてありました．いまでも書いてあるかもしれません．こんな理解の仕方で健全な学問的精神が育まれるわけないと思っています．悲しくなります．
- 動的計画法は学部でも学習しましたが、問題に応用するための考え方がよくわかっていなかったため、今回の講義はとても参考になりました。
--はい，ぜひ使えるようになってください．
- お疲れ様でした。今回も非常に興味深く、内容をしっかり理解しました！
--それはよかったです．
- 巡回セールスマン問題の復習をしていきたいと思います
--ぜひ復習して，分からないところがあったら聞いてください．
- 巡回セールスマン問題という名前だけ知っていた概念の理解が深まった
--巡回セールスマン問題自体も多くの応用をもつものです．「セールスマンが巡回する」という比喩でとらえられる問題は多くあるのです．
- 動的計画法については他の授業でも扱っているのである程度理解していたが、日常の場面で利用しようとしてもうまくモデル化できないことが多い気がする。単純に状態の定義の仕方に慣れていないだけかもしれないが。
--授業では適用するための鍵を3つのステップに分けて説明しました．それが常に適用できるわけではありませんが，まず，適用できるかどうかということを考えることが大事かもしれません．
- n!のオーダーがn log nになる証明を途中までやってみました．納得がいくまで続けようと思います．
--n log nではなく，$2^{O(n \log n)}$ です．第1回の授業でも説明しているので，そちらも参考にしてください．
- 最小被覆問題に関連する未解決問題があることを知らなかったので、いい勉強になった
--高速指数時間アルゴリズムの周辺では，未解決な問題がたくさんあります．そのひとつを紹介しました．他のものはこれからの授業で出てくるかもしれません．
- 離散最適化問題が主に3種類というのは今後意識していきたい。動的計画法はシンプルながら応用幅が広くて強力だなと思った。時間計算量と空間計算量の違いが曖昧。
--この3種類しかないというわけではないので，それについてはご注意ください．
- 前期に武永先生のアルゴリズム基礎論の授業を取って，動的計画法と巡回セールスマン問題の色々を扱いましたため，今回の授業は，比較的に余裕がありました．また、スライド１９の５番目のバージョンで、{v1, v2, v3, v4}の下の緑の数字6 5 4が理解できないですけど，それは，なんの総和ですか？
--たとえば，6はi=2 (6の上の黒い数字), S={v1, v2, v3, v4}の場合のf(i,S)の値を表しています．5はi=3の場合です．
- 被覆の再帰式がいまいちわからなかったので確認してみたところ、Xiが必要かどうかで分けていて、実際に必要な要素を求めているわけではなくただ個数を求めていることがわかりました。そのため、実際に何の要素が必要になるか求めるのはどのくらいかかるのか気になりました。
--再帰式でminを達成するのが2つの項のどちら側なのかという情報も覚えることにします．そうすると，最適値が得られたとき，その情報をさかのぼっていくことで，実際に必要な要素を復元することができます．計算量は $m$ だけ増える程度なので，$O^*(2^n)$ のままになります．
- トップダウンとボトムアップの違いのところについて、空間と時間計算量がトレードオフになっているというのは確かにあるなと感じました。動的計画法を通して、メモ化の強力さを改めて感じています。
--「空間と時間のトレードオフ」はアルゴリズムを考えるうえで重要なアイディアです．他の場面でも使えると思うので，ぜひ適用してみてください．
- データ構造で学んだdijkstraアルゴリズムは動的計画法ですか
--最短経路問題 (最短路問題) に対するダイクストラ法は動的計画法ではない，と考えられています．最適性の原理を使っているとは思いますが，その計算法が「表を用いて…」とは違うのではないかと思います．
- 寝坊をしてしまったので，スライドを見て必死に読み取りました．授業動画が出たらちゃんと見て復習します．動的計画法の定義がまだ曖昧なのですが，例として私の研究でよく使用しているFFTアルゴリズムも動的計画法に入るのでしょうか？
--FFT (高速フーリエ変換) は動的計画法ではない，と考えられています．FFTは分割統治法に基づくアルゴリズムだと説明されることが多いように思います．
- なんとなく，動的計画法と代数をつなげるトピックを探していたら，動的計画法に基づく，一部の（しかし，典型的な）アルゴリズムはトロピカル代数（max-plus代数 / min-plus代数）という代数的構造を通して理解できるみたいな話題がありました．「トロピカル代数」という名前は初めて聞いたのですが， 「max-plus代数」はたまたま聞いたことがあり，思わぬところで概念同士の交差点に出くわすことになって面白かったです．
--トロピカル代数という名称はmin-plus代数の別名であるだけで，トロピカル代数とmin-plus代数は完全に同じものです．その点は誤解のないようにお願いします．動的計画法がトロピカル代数を通して理解できる，という言い方はかなり大げさだと思っています．それによって何かよいことが分かればよいのですが，私自身はあまりそのような気分になっていません．ただ，何かよいことが分かるのかもしれないので，調べ続けていく価値はあると思います．
- 先生は離散最適化の講義をご担当されていると思うのですが，連続最適化にもお詳しいのでしょうか？それとも離散の考え方と連続の考え方は似て非なるものなので，離散ほどは詳しくないみたいな感じなのでしょうか？
--私が連続最適化に詳しいかどうか分かりませんし，離散最適化に詳しいのかどうかもよく分かりません，世間的に，私は離散最適化の専門家だと見なされていないような気がしますし，私自身も離散最適化の専門家だとあまり思っていません，ただ，おそらく，皆さんよりはどちらも詳しいのではないかと思います．
私自身は，研究分野とか専門分野という考え方にあまり共感していません．そのような考え方はたんなるレッテルだと思っています．ただそんな考え方しか持っていないと他の人とコミュニケーションができないので，なにかしらの研究分野を自分の専門だと (不本意ながら) 言うことにしています．
- 今夜，私たちの街の日は沈んだかもしれない．だが，ユージン・デブスの言葉を借りれば，「私には，人類にとってより良き日の夜明けが見える．」 (ゾーラン・マムダニ ニューヨーク市長選 勝利スピーチより)
--まあ，政治家としてはそういうことを言わないといけないのでしょう．
- 大統領として，ニューヨークに多額の資金を投入するのは難しくなるだろう．共産主義者がニューヨークを運営するなら，送った金がすべて無駄になる． (CBS News 60 minutesでのドナルド・トランプの発言より)
--この発言は市長選の途中で行われたもののようなので，その点は誤解のないようにしないといけませんね．
- In New York Concrete jungle where dreams are made of There's nothin' you can't do Now you're in New York These streets will make you feel brand new Big lights will inspire you Let's hear it for New York, New York, New York (You Welcome, OG, I made you hot, ****) (Jay-Z ft.Alicia Keys「Empire state of mind」より)
--大都会に憧れをもった若者が大都会に出てきて失望するというのは昔からよくあるモチーフだと思います．
- 11/4 (4) 分枝アルゴリズム：測度統治法
- 今朝は寒くて起きるのが大変でした．ここ1か月で急に寒くなりすぎだと思います（ちなみに，1か月前は最低気温でも20度くらいあったと記録があります）．
--そうですね．季節の変わり目は体調を崩しやすいので，お気を付けください．
- 風邪をひいてしまったため本日は遠隔で受講しました。こういったときに遠隔で受けられるのは本当にありがたいです。
--はい，そういう非常時に遠隔Zoomもお使いください．
- 本日も授業ありがとうございました。すごく個人的なコメントなのですが昨日激辛を食べてしまいました授業中何度か席を立ってしまいました。先生も激辛にはご注意下さい…
--ご注意いただきありがとうございます．;-)
- ありがとうございました！
--こちらこそありがとうございました．
- ありがとうございました。今後ともよろしくお願い致します。
--こちらこそありがとうございました．
- とても勉強になりました。ありがとうございます。
--こちらこそありがとうございました．
- 今日の授業はわかりやすくて面白いです！ありがとうございました！
--こちらこそありがとうございます．
- 今日もありがとうございました
--こちらこそありがとうございました．
- 勉強になりました、ありがとうございます。
--こちらこそありがとうございました．
- 途中計算でついていけなかった部分もあったので，自分で計算して復習したいと思います．
--細かい計算はややこしいので，あまり気にしなくても大丈夫です．それでも，流れはぜひ理解してください．
- 授業の内容がどんどん難しくなっている、先生の説明は説明が分かりやすかった、自分も頑張って知識を理解できるようになる。
--おそらく，今回の内容が前半で一番ややこしいところだと思います．細かいところまで理解できなくても大丈夫です．
- 今回は少し難しく, 講義中に理解ができなかった. 時間ができたら復習したい.
--私にも難しかったです．ぜひ復習してください．
- 今回は数式多めで少し理解に時間がかかりそうなので復習したいと思います。
--細かい計算は理解できなくてもよいと思うのですが，流れは理解してください．
- 自分にとっては進むスピードが速く、講義内で理解することが難しかったです。。
--そうですよね．私も今回は速かったと思います．反省しています．
- 理解がまだできていない部分があるので、復習しておきます
--はい，復習をぜひお願いします．
- 復習をしっかりしたいと思います
--はい，復習をぜひお願いします．
- 従来の頂点数に基づく単純な解析では得られなかった計算量改善を、より精緻な「測度」定義によって達成できる点が非常に印象的だった。
--そうですね．一つのアルゴリズムを解析する方法がいろいろとありうるのは面白いと思います．
- 適切なものである必要はあるとはいえ、パラメータを入れるだけで計算量が変わることに驚きました。
--はい，私もはじめてこの技法を見たときに驚きました．この手法のはじめのバージョンは2006年の国際会議で発表されたものだったと思います．その当時，私はすでに大学教員だったのですが，その直後に著者のFominさんに会ったとき，感動を直接お伝えすることができました．
- 計算量が小さくなるようにパラメータを決めるところがかなり根気が必要そうだが時間があったら自分で計算してみたいと思いました。
--はい，ぜひやってみてください．私が見つけた値も本当に最適なものだとは思っていないので，もっとよいものはあると思います．
- 実際に自分で実数を当てはめて最適解を探すやり方をすると、自分が選んだ値よりもっと良い解があるのではと不安になる。また、今回はμ₃・μ₄だけだったが、μ₅やμ₆まで動かすとなると解析がかなり大変そうだと感じた。
--パラメータのよい値を私は手作業で調整しましたが，本来はコンピュータで調整するのがよいと思います．元論文にもコンピュータで調整する方法が書いてありますが，その方法は授業で説明しませんでした．興味がありましたら，元論文を見てみてください．
- 講義の最後に「週末にやった」とおっしゃっていましたが、測度統治法の計算量解析やパラメータの調整は、休日も使って取り組まれたのでしょうか。
--実は，先週の平日もずっとやっていました．論文に書いてあるものは4つのパラメータを調整することになっていて，これは授業で説明できない (難しくなりすぎる) と思って，2つのパラメータを調整するバージョンに変えようと思って準備を始めたのですが，それでもパラメータの調整がうまくいかなかったりして，かなり苦労しました．それがまとまりだしたのが先週の金曜日で，そこから週末 (休日) にスライドを作りました．そのため，説明があまり練られておらず，申し訳ないです．
- 本当になんでmeasureって言葉を充てたんでしょうね… 次数分布の重み付き和（weighted sum of degree distribution）とか名付けられてもよかったように思います（ちょっと長すぎる？）
--measureはweighted sum of degree distributionである必要はないので，その名称だと誤解を生んでしまうかもしれません．ただ，グラフの問題においてはweighted sum of degree distributionがmeasureとして使われることが多いように思います．
- 測度統治法は初めて学んだ。
--これは高速指数時間アルゴリズムに特有の技法なのですが，もしかしたら，他の文脈でも活用できるかもしれません．ぜひ考えてみてください．
- 測度を導入することで、頂点数があまり減らなくても「問題の難しさが実際には小さくなっている」ということを評価できるため、無駄な探索を減らして高速化できることが分かりました．
--前回でも少し出てきたのですが，次数3の頂点vに次数3の頂点wが隣接しているとき，vを取り除くとwの次数が2になって，すぐさま前処理を適用可能になります．そのような効果を測度は自動的に取り入れることができます．仕組みがうまいと思います．
- 測度論の存在自体は知っていたが今まで勉強したことが無かったので、これを機に勉強してみようと思った
--授業でも述べたとおり，今回導入した「測度」は測度論でいう測度とは違うので，注意してください．そうであっても，測度論というものは重要な考え方を豊富に含んでいるので，ぜひ勉強してみてください．
- 必要なところに復讐が出てきて前回の内容を確認できたのはとてもありがたい
--各回の授業の内容に必要なことしか復習しないように絞っています．それで足りないかもしれませんので，足りない場合は自習で補ってください．
- もう自分には 夢の無い絵しか描けないと言うなら 塗り潰してよキャンバスを何度でも 白い旗はあきらめた時にだけかざすの 今の私はあなたの知らない色 (宇多田ヒカル 「COLORS」より)
--ぜひ，自分の色をしっかりと持ってください．
- 中間レポートの範囲が，動的計画法までと授業中に言われました．そのことから，中間レポートの課題が出るのが11/18(火)ってことで間違いないですか？また，中間レポートの期限はいつまでになりますか？
--間違いはあるかもしれません．出題は11/18の付近になる予定ですが，詳細は決めていません．期限は出題日から2週間とする予定です． - すみません、コメント遅れてしまいました。今日授業出席することができなかったため後ほど動画拝見いたします。
--まだ締め切っていなかったので大丈夫です :-)．ぜひ動画で学習してください．
- 10/28 (3) 分枝アルゴリズム：高速化
- コメントをありがとうございました．
- 「わかりました．僕でも一瞬なら栄光を掴めるということですね．」 (魚豊「ひゃくえむ。」 小宮のセリフより」)
--そうですね．ぜひ掴んでください．
- 最近寒くなってきました。
--そうですね．体調には気を付けてください．
- 今回は高速化の考え方、折畳操作、計算量解析、分枝規則などについて勉強した。ありがとうございます。
--ありがとうございました．そのように学んだことを振り返ることができるのはよいですね．
- とても勉強になりました。ありがとうございました。
--こちらこそありがとうございました．
- 本日も授業ありがとうございました。内容が難しくなってきたのでついていけるように努めます。
--次回はこみいった話になるかもしれません．復習をよろしくお願いします．
- 今日も勉強になりました
--こちらこそ．私も勉強になりました．
- 解説はわかりやすくてとても勉強になりました。ありがとうございました。
--こちらこそありがとうございます．
- 今回の内容が個人的に難しかったので，後でスライドを見て復習しようと思います．
--そうですね．復習をよろしくお願いします．
- 勉強になりました、ありがとうございます。
--こちらこそありがとうございました．
- 図も多く、説明が分かりやすかった
--図を多くすることは意識しています．ただ，ことばを少なくしすぎている気もしていて，バランスをとるのが難しいです．
- ゼミの資料を作るときに1枚にどのくらい情報を載せるかよく迷います。先生のスライドも参考にしたいと思います。
--参考になるのなら，それはとてもありがたいです．
- 講義の冒頭で復習があるのが助かります。
--各回で必要なことだけを復習するようにしています．すべてを復習するのは，みなさん自身で行ってください．よろしくお願いします．
- 授業は面白かったのですが前回より知らないことが多くちょっと進度が早いと感じでしまいました。
--知らないことはどんどん増えていきますので，復習をよろしくお願いします．
- （適切な文脈があれば）スライド15/45の図がグラフに見えるのはおかしくないと思います！ …多分
--皆さんはおかしくないので，ご心配なく．:-)
- 前回よりは、岡本先生が意識するときに少し話のスピードがゆっくりになりましたが，説明に夢中になるとだんだん加速し始めている感じです．授業一回分で扱う内容が多いからかもしれないですが，大学院の授業だと内容がその分量になるのは当たり前だと思います． また，スライド15のSが図の中で下方のローフ・パンのような形をした黒い枠のここで間違いないですか？
--Sは赤で示している頂点からなる集合で表しています．黒い枠はグラフにおいてuとv以外の部分を表します．
- ときどき、岡本先生が思われたことをストレートに言葉にするのがとても好きです
--ときどきそうなります．そんなのが動画として残ってしまっていいのかどうか不安になりますが，あまり気にしないでください．;-)
- 優越，折畳，鏡像と新しい概念が沢山出てきてまだ理解しきれていない． 講義資料を見てちゃんと復習したい． 手を動かした方が頭に入る人間なので板書を取りながら講義を受けているが， 進むスピードと登場するグラフの複雑さからいよいよ追いつかなくなってきた． とりあえず，前処理を行う目的は頂点数を減らすことで，それは漸化式の特性方程式解を小さくする方向に動くことがわかった． 情報の分野にあまり詳しくないので，早いアルゴリズムを見つける研究というのは既存のものと全く違う驚くべきアルゴリズムを提案するイメージだったが，今回の講義を聞くと，分岐のような根幹のアルゴリズムは変わらず，前処理やメモ化などの付け足しを試行錯誤してより早いものが研究されていく方が多いのだろうか？
--最後の部分の質問に対する私の回答は「分枝アルゴリズムについてはそのとおりです」ということになります．ただ，分枝アルゴリズムの考え方と他のアルゴリズムの考え方を組み合わせて高速化を行うこともあります．そのような組合せについては，この授業は扱わない予定です．
以下，一般論です．「既存のものと全く違う驚くべきアルゴリズム」が提案されることはほとんどありません．たまにあるのですが，それは歴史の中でも一握りです．たいていのアルゴリズムは先人が積み上げたものをうまく組み合わせたり，新たな視点から見てみることで得られているのだと思います．もちろん，そのように得られたアルゴリズムが簡単に生み出されているわけではないことには注意しなくてはなりません．組み合わせることや新たな視点を見つけることも自明ではないのです．
- 補題：近傍から2 頂点 仮定：v ∈ V G のどの最大独立集合もv を含まない 結論：S がG の最大独立集合⇒ |S ∩ N (v)| ≥ 2の背理法にによる証明がやや難しく感じた。また折りたたみの復元操作自体も直感的にはイメージが難しい。アルゴリズムの計算量を理解するだけなら、どちらも理解する必要はないので、そこで詰まってついていけなくなることはなかった。
--分からないのは私の説明が悪いのだと思います．こういうものは，まず，自分で証明しようとしてみるとよいかもしれません．それを行ってから，書かれている証明を見てみると，証明の理解が進む気がします．
- 前処理をうまく扱うと多項式時間とした時と同じになることに驚きました。2-SATでも前処理が強かったので、改めて前処理の威力を知りました。
--前処理はとても有効ですので，ぜひ活かしてください．
- グラフ問題に対しても前処理という概念があることを知り, 驚いた. コンピュータで計算しやすくなるようにする処理はどの分野に行っても大切であると感じた.
--そのような前処理と区別するために，今回紹介したような手続きを前求解 (まえきゅうかい，presolve) と呼ぶこともあります．授業では，参考にしている本に合わせて前処理 (preprocessing) にしました．
- 問題を効率良く解決するには前処理(事前の準備)が大事と学びました。就活をしている立場としては、この考え方は仕事と共通していると思いました。
--そうですね．実生活にも活かしてください．
- 前処理をすることの威力を知ることができました。畳込みのほうが一回では理解できなかったのでオンデマンドで復習しようと思います
--はい，ぜひ復習してください．
- 折畳規則と鏡像の考え方が興味深かったです。特に、前処理でグラフ構造を単純化して高速化する発想が勉強になりました。
--こういうことが可能であって，しかもそれによって計算量が理論的にも小さくなるというのが面白いと思っています．
- 前回学んだアルゴリズムに様々な角度から改良を加えられることを学び、アルゴリズム改善の奥深さを知った。
--いろいろな見方で改良ができていっているのは，奥深いですね．
- 使える条件がたくさんあって嬉しいですが，考えている途中で忘れちゃいそうです．道具を十全に使い切るのは大変です．
--忘れてしまって構わないので，調べて思い出しながら理解するようにしてください．
- 折畳操作自体は，グラフの辺の縮約を知っていれば，非辺に対して縮約と同じことをすると考えればすっと理解できました（無いものを縮約するって言うと変な言葉遣いですが）
--自分なりの理解ができるのはいいですね．
- 鏡像のあたりでよく分からなくなってしまったので、後でゆっくり見直そうと思います。
--はい，復習をよろしくお願いします．
- 折り畳みの性質から、それを利用したアルゴリズムへの飛躍が大きくて発想に感動した
--ここは難しい部分だったと思います．私もうまく説明できていないような気がします．
- 折畳規則や優越規則の考え方がよく理解できました、内容が難しかったですが、理解できてよかったです。
--それはよかったです．次回も登場しますので，復習をしておいてください．
- 講義の後に質問しましたが，喋りたいことがその場ですぐにまとめられなくて，何が疑問であったのかが伝えきれていないと思ったのでこちらでも書いておきます（文の方が分かりやすくなるかというと，そうとは限りませんが）．私が気になっていたのは，「性質：優越」において，$N[v] \setminus N[u]$ に属する頂点 $w$ が存在して，$w$ が $N(u) \cup N(v) \setminus \{u\}$ に属する頂点とだけ隣接しているときでも（対面で聞いたときは$w$が$v$とだけ隣接していることにこだわっていましたが，気になっていたことを考えるとこの設定の方が適切な気がします），結論が成り立つのはなぜかということでした．対面で聞いた時の議論を落ち着いて振り返ると，そのような場合では，$S \cup \{u,w\} \setminus \{v\}$ が $G$ の独立集合で，$S$ より要素数が多くなってしまうため，「$S$ が$G$ の最大独立集合である」という結論の前提が否定されてしまい，結論全体が真になるということだったんですね．学域生だった頃よりは慣れたつもりですが，$A$ を仮定して，$B \Rightarrow C$ が得られるという形式の数学的主張を理解するには未だに手間取ります．$A \Rightarrow B$ は，$\lnot A \lor B$ と同値で，議論の正しさを検証するうえでは $\lnot A \lor B$ を念頭に考えた方が分かりやすそうなので，$A \Rightarrow B$ の形の命題が正しいかわからなくて困ったときの処方箋として，頭の片隅に入れておきたいですね．
--あるいは，「前提条件が成り立たないときは考えなくてよい」と思ってもらう方がよいのかもしれません．その理由はコメントの中で自ら理解しているとおりだと思います．
- アルゴリズムそのものも，もちろん面白いですけど，解析の仕方というのはもっと直接的にものの見方につながると思っているので，次回がとても楽しみです．
--そうですね．21世紀になってから，アルゴリズムの計算量を解析する新しい手法が誕生したというのは，なかなかすごいことだと思います．
- 最初の論文からすでに結構計算量が小さいのは笑ってしまいました。
--本来は，アルゴリズムやその計算量を紹介したとき，それを発見した論文の著者名にも言及するべきだと思うのですが，いままで紹介したものは，最初の論文にもまだ劣っているのです．そのような経緯もあって，著者名がいままででてきていないと思ってください．
- 指数領域の場合は2001年以降指摘されてないのでしょうか
--指摘されています．すみません，これは説明が悪かったと思います．以下補足します．
メモ化 (記憶化) による計算量の改善は最近でもいろいろな論文で見られます．2001年の論文として挙げているRobsonのものは，カッコで囲っていますが，これはいわゆるテクニカルレポートであって，論文誌 (ジャーナル) で出版されていません．私は昔このテクニカルレポートを読もうとしたことがあるのですが，膨大な場合分けがあって，しかも，記述も切り詰められていて，読む気が失せました．いまでも読めないと思います．しかし，一応，いまでも，この2001年のRobsonのテクニカルレポートが最大独立集合問題に対する最速のアルゴリズムだといろいろなところで言われています．
そのため，その後の研究は，いかにシンプルな方法で計算量を改善するのか，ということに焦点が移ってきたように思います．特に，Xiao, Nagamochiの2017年の論文は「指数領域を使わないのに1.2を切っている」というのがうれしいポイントのようです．ただ，この論文のアルゴリズムが簡単かというと，そういうわけではありません (Robsonのテクニカルレポートよりは簡単だと思いますが)．しかし，ジャーナルに掲載されているので，それを読んで正しさを確認した人 (著者以外の人) はいることになります．
- 最大独立集合問題の計算量が何年もかけてアルゴリズムが改良され少しずつ高速になっていることに驚きました。
--そうですね．まだまだ改良する余地はあるように思います．
- 6歳から物を写生する癖があり，50歳から画図を発表してきたが，70歳前のものは取るに足らないものだった．73歳で禽獣虫魚の骨格や草木の出生がわかってきた．80歳になればもっと深まり，100歳で神妙の域に達するだろう．110歳では一点一画，すべてが生きているように見えるだろう． (葛飾北斎 75歳の弁より)
--みなさんは50歳なんて遠い未来のことのように思っているかもしれませんが，案外すぐに50歳は来ますよ．私は身をもって感じています．
- 10/21 (2) 分枝アルゴリズム：基礎
- コメントありがとうございました．
- 放送禁止用語を言いそうになったって言ってましたが，何を口走ろうとしたんですかw
--書けるわけないじゃないですか ;-) いじわるですね．
- 今日の授業お疲れ様でした！非常にわかりやすくて面白かったです。
--こちらこそありがとうございました！
- 勉強になりました
--はい，ぜひ復習してください．
- 基礎的なとこは忘れてる部分もあったのでもう一回勉強できてよかったです
--はい，復習になったようで，よかったです．
- Wolfram Alphという便利なツールがあることを知りませんでした。今後使ってみようと思います。
--こちらです．このようなツールはぜひ活かしてください．
- とても勉強になりました。ありがとうございました。
--私も勉強になっています．こちらこそありがとうございます．
- 出てきた記法を整理して、しっかり復習していきたいと思います。
--いろいろな記法がでてきて，混乱しますね．ぜひ復習してください．
- 今日の解説も大変わかりやすかったです。ちなみに先週の体育祭はご覧になられましたでしょうか？
--体育祭は見ていないです．すみません．
- 今日は特定方程式，単位伝について学びました。先生がけっこ早口でした、留学生の自分に対して少し聞きにくいでした、少しゆっくり話してぼしい。次回の授業内容を期待しています。
--はい，私自身も早口すぎて話しにくいです．おそらく，留学生でなくても少し聞きにくいと思います．ゆっくり話したいと思いますが，なかなかうまくいきません．少しゆっくりと話すように心がけます．
- 授業が面白いけど、進み具合が速くて微妙に追いつけないです。
--ゆっくりと話せば追いつけるようになるのかもしれませんので，ゆっくりと話すように心がけます．今回の内容も付録を話すつもりはなかったのに話してしまっているということは，速かったのだと思います．
- 前回の復習を踏まえたことで全体の流れを理解することができた。また、具体的な例を用いた説明がわかりやすく、内容が頭に入りやすかった。
--できるかぎり，例は具体的にしようと心がけています．ただ，心がけても具体的なものを作るのが難しい場合があるので，そのときはイメージ図になってしまいます．また，イメージ図の方がわかりやすいと判断した場合もイメージ図になります．
- 探索木の概念など、分岐アルゴリズムの基礎的な点について学ぶことができてよかった。
--分枝アルゴリズムですね．分枝アルゴリズムはいろいろな問題の解決に使えますので，ぜひ活用してください．
- 計算量の最大を見積もるために，漸化式に落とし込んで計算する方法が面白かった．単位伝搬法の意味がわかって面白かった．
--再帰的なアルゴリズムの計算量解析には漸化式が自然に出てくると思ってください．その視点でいまいちど今までに扱ってきた再帰的なアルゴリズムを見直してみると，新たな発見があるかもしれません．
- deg(v)が3で抑えられる理由がわからなかった。単位伝播強い。
--アルゴリズムAではvとして次数最大の頂点を選んでいますが，それを選ぶとき，Step 1を通過していますから，最大次数が必ず3以上になっているのです．
- 場合分けの説明が分かりやすくて良かったです。特性方程式で正の実数解が2つ以上出てくることがあるのかどうかが気になりました。
--この授業の文脈では正の実数解が2つ以上出てくることはありません．以下，もう少し詳しく説明します．
解くことになる特性方程式は $x^n = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1}$ という形を必ずしています．ただし，$a_1, \ldots, a_{n-1}$ はどれも非負 ($0$ 以上) の実数で，$a_0$ は正実数です．このとき，デカルトの符号規則から，この方程式の正の実数解の数が1であることが分かります．
デカルトの符号規則を知らない場合は，次のように直接，次数 $n$ に対する帰納法で正の実数解の数が1であることを証明できます．
関数 $f$ を $f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1} - x^n$ で定義します．$n=1$のとき $f(x) = a_0 - x$ なので，$f(x) = 0$ の解は $x = a_0 > 0$ であり，正の実数解が1つだけあることが分かります．では，次数 $n$ が $k-1 \geq 1$ 以下のときに正しいとします．そして，次数が $k$ であるときを考えます．このとき，$f'(x) = a_1 + 2 a_2 x + \cdots + (k-1)a_{k-1} x^{k-2} - k x^{k-1}$になります．
$a_1 > 0$ のとき，帰納法の仮定から $f'(x)/k = 0$ は正の実数解をちょうど1つ持ちます．それを $\alpha$ とします．$f(x)$ に対する増減表を $x$ が $0$ から $+\infty$ の範囲で書くと，$x \to +0$ のとき，$f(x)\to a_0 > 0$ であり，$x \to +\infty$ のとき $f(x)\to -\infty$ なので，$x$が$0$から$\alpha$の範囲ではずっと$f(x) > 0$ であり，$x$が$\alpha$以上のとき，$f(x)$は狭義単調減少になります．そのため，$f(x)=0$ を満たす正の実数 $x$ はちょうど1つしかないことが分かります．
$a_1 = 0$ のとき，$f'(x)/x = 2 a_2 + \cdots + (k-1)a_{k-1} x^{k-3} - k x^{k-2}$ になります ($x > 0$ を仮定しているとしてください)．$a_2 > 0$だったら，$a_1 > 0$ のときと同様に考えると，$f(x)=0$ を満たす正の実数 $x$ がちょうど1つしかないことが分かります．そうでない場合 ($a_2 = 0$ のとき)，$f'(x)/x^2$ を考えて…ということを繰り返すと，同様に $f(x)=0$ を満たす正の実数 $x$ がちょうど1つしかないことが分かります．
- satを解くときに、考える必要のない割当を省く考え方が面白かったです。p34の未割当の変数数がn-3になるところの理解が曖昧です。0,0,0の場合を省くからその分3つの変数を除くから、という理解で問題ないでしょうか？
--残念ながらそうではありません．変数がn個あるとき，3個の変数に値 (0か1) を割り当てると，残っている (つまり値を未割当の) 変数の数はn-3個になる，というわけです．
- スライド38/51って，描いた探索木の高さが違うから，アルゴリズムCについて描いた探索木の葉が多くなってるだけですよね．
--そうだとは限らないのがややこしいところです．葉の数が小さい探索木の特徴は2つあって，その特徴は (1) 高さが小さい (低い)，(2) 分岐が少ない，ということです．例えば，高さが小さい，例えば3であるからといっても，1つの頂点の子が1000個もあったりすると，葉の数は3の1000乗になってしまいます．Bの方は高さが小さいのですが，分岐が大きい (7つに分岐する) ので，上に書いた (1)は満たすが(2)は満たさないことになります．一方でCの方は分岐が小さい (3つに分岐する) のですが，高さが小さいわけではないので，(2)は満たすが(1)は満たさないということになります．そのため，授業でも述べたのですが，特性方程式を解くまでは (漸近的に) どちらの探索木の葉の数が小さいのかよく分からないということになります．実際，nを大きくしていくと，Bの探索木の方がCの探索木よりも葉を多く持つようになります．授業で述べたのは，このスライドの例 (たしか，n=12のときに描いてます) では，Cの方がBよりも葉を多くもってしまったということだけでした．言わなければよかったかもしれません．
- 解く過程が細かくスライドごとに分けられていて理解しやすかった。て
--ぜひ自分のそばにある問題でもアルゴリズムを考えてみて，理解を深めてみてください．
- 3-SATについて、x1,x2,x3について全てを同時に比較するのではなく、1つずつ独立して見るだけで計算時間を減らせるのは面白いと思った。n=30の時で3.5倍程がつくので規模が大きい時に特に有効だと思う。
--漸近評価はnが大きいときにとくに有効であることを教えてくれます．3-SATはあとの授業でも登場する予定ですので，楽しみにしていてください．
- 充足可能性問題について、いくつかのサンプルから論理式を導出する問題は他の講義で見ましたが、論理式が充足可能かを判定する問題は初めてでした
--いくつかのサンプルから論理式を導出する問題はいわゆる「例からの学習」だと思います．これは重要な問題で，典型例は決定木の学習で，それを発展させたものと考えられるのが機械学習の応用でよく使われるランダム・フォレストという手法です．論理式や論理回路の周辺には多くの最適化問題やアルゴリズム的問題があり，よく研究されています．
- 昔（確か6歳か7歳のころ），復刻版の学研の電子ブロックを誕生日プレゼントでもらったことがあります（おそらく半分以上，親が欲しかっただけでしたが，自分も楽しく遊べたので結果オーライです）．当時の自分には複雑な回路が多すぎて，ラジオをはじめとした多くの回路はとりあえず動くのを楽しんでいたのですが，単純な2入力のAND回路（スイッチが2個あって，2個ともONにした時だけ回路中の電球が光るようなもの）をはじめとした論理回路は，昔の自分（もらった当時ではなく9歳か10歳頃になって遊びなおした時のような気もしますが）でも何が起こっているのか，考えてみれば納得できていた記憶があります．いま，この手の論理の話が面白いと思えるのは，当時そのようなものに触ったことも影響しているのかもしれません．
--それはよい経験をしましたね．いまでは，プログラミング教室というかプログラミング塾というか，そういうものをよく見かけます．子供がこのような技術に触れる機会が増えているのかなと思います．
- 資料のp33, p36のアルゴリズムB,Cについてになるのですが，2.の論理式は^ではないのでしょうか？vになる理由が資料からだと読み取れなかったので，お時間があれば教えて頂きたいです．よろしくお願い致します．
--2のところは節を1つ選んでいて，節はリテラルのORなので，スライドのままで正しいです．
- 論理式の話は好きなので面白かった。
--それはよかったです．論理式はいろいろなところで出てくるので，ぜひ慣れてください．
- 前処理が強力であることを改めて認識しました。
--前処理は強力です．ぜひ活用してください．
- CNFの意味がわかったら授業資料がすんなり読めて楽しかった 単位伝播は方法が名前から印象より比較的平易でわかりやすかった
--単位伝播は充足可能性問題に対してよく使われる手法なのですが，同じような考え方は他の問題でも使えますので，身近な問題に使えるか考えてみてください．
- 2-SATのアルゴリズムは実際にどのように動かすのか気になって調べてみると節を有向グラフにする方法などがあった。節のサイズで考え方などが変わることが改めてわかり、面白く感じた。
--2-SATの多項式時間アルゴリズムにはいろいろなものがありますが，よく出てくるものは，有向グラフの強連結成分分解を使うものです．ただ，この授業では有向グラフやその強連結成分分解を説明したくなかった (それを説明しなくても済む方法で通したかった) ので，単位伝播による手法を説明しました．
- 2-satで数珠的に解を導き出すアルゴリズムが面白いと思いました
--はい，これは私も面白いと思います．これと似たものが後で出てくるかもしれません．
- 先人たちの偉業 リスペクト 先人たちの偉業 リスペクト 人の営み積み重ね歴史 文明 文化 文明 文化 （U-zhaan，環ROY，鎮座DOPENESS 「BUNKA」より引用）
--今回までは，あまり研究者の名前を出していませんでしたが，次回は最大独立集合問題に対するアルゴリズムがどのように改善されてきたのかという歴史も少し述べる予定です．
- 10/7 (1) 高速指数時間アルゴリズムの考え方
- コメントをありがとうございました．以下のように掲載されます．
- よろしくお願い致します．
--こちらこそよろしくお願い致します．
- 今後ともよろしくお願いします
--こちらこそよろしくお願いします．
- 半年の間よろしくお願いします。
--こちらこそよろしくお願いします．
- お疲れ様です 🙇
--こちらこそお疲れ様です．
- 良い
--ありがとうございます！
- すごく愉快な先生だなと思いました。スライドもわかりやすく次の授業が楽しみです。
--私が愉快かどうか，私自身では分からないのですが，言い回しにクセがあることは自覚しています．次回もお楽しみに．
- 非常に面白かったです
--面白く感じていただけて，よかったです．:-)
- 面白そうなので受講しようと思います。よろしくお願いします。
--はい，よろしくお願いします．
- 内容が分かりやすくて、興味深かったです。
--内容はわかりやすくなるように努めていますが，分からなくなったら，ぜひ質問してください．
- 数理最適化に関する研究を行なっているので、その知見をこの講義で得たいと考えています。4ヶ月間よろしくお願いします。
--はい，よろしくお願いします．
- この講義を落とすと留年が決まります。頑張ります。
--評価の方法は授業内で述べたとおりです．しっかりと復習するようにしてください．
- 研究内容に必要なそうな内容でもあるし、授業の内容も魅力的で、面白そうだが、難しそうです。でもわかりやすいです。
--あとでレポート課題に取り組むとき，それまでの内容があまり分かっていなかったかな，という気持ちになるかもしれません．でも，それで構わないと思います．一度聞いたことをその場ですべて理解できるとは限りませんし，むしろ，理解できる方がまれです．あとから思い出せるように復習していくことが大事かな，と思います．
- 先生少し長く休憩を取っても大丈夫です。
--お気遣いいただきありがとうございます．
- 金輪際って表現が自然に口から出る人を先生以外に会った記憶がないなと（私の交友が狭いだけ…？）．
--私はいろんな表現が自然に口から出ます ;-)
- 十把一絡げ → ざっくりまとめると とかどうですか．
--提案ありがとうございます．「ざっくり」は「おおまかに」のような意味だと思うので，少し思っている意図とは違うかもしれません．「すべてをひとまとめにして」とかの方が私の意図としては近かったかもしれません．
- 昨日横浜のコクトーバーフェストに行ってきました．二日酔いですが頑張って来ました．
--二日酔いにはご注意ください ;-)
- 情報・ネットワーク工学専攻なので、情報系の授業でついていけるか不安であったが、スライドのアルゴリズムの説明や数学的定義など詳しく解説されていて非常に分かりやすくて面白かった。
--定義すべきものは定義していく予定ですが，わからなかったり，知らないものがあれば，なんでも質問してください．知らないことは恥ずかしいことではありませんので，そのつもりで臨んでください．
- シラバスでも「データ構造やアルゴリズムの授業は，多項式時間でできることに対して多くの時間を割きすぎています」って書いてありましたが，確かに，指数時間アルゴリズムに真面目に向き合ったことって多項式時間アルゴリズムほどないなぁと思ったので，とても楽しみです．
--シラバスに書いたそれですが，「教え方が古い」ことが一番の原因だと思っています．多項式時間でできることについてしっかりと勉強することは重要ですが，それだけに偏ると，アルゴリズムやプログラミングで解決できる問題の幅はとても狭くなります．しかも，基礎的なデータ構造やアルゴリズムは最近の高級プログラミング言語では既に実装されています．そのため，それらを学ぶ意義は「しくみを理解する」という側面が強く，「新しいものをつくる」という側面が弱くなっているように感じます．指数時間でできることについても目を向けていくべきだと思います．
- 今までやってきたようなアルゴリズムやオーダー法をちゃんと理解した。しらみつぶしのところの並べ方は何かの基準があるのか気になった。
--並べ方ですが，10ビットの列を0000000000から1111111111まで順にインクリメントして作り，各列において10個のビットを10個の頂点の1つ1つに対応させています．それを左上から右に進めて，右端まで来たら下の段の左端に移る，ということを繰り返して，グラフを作っています．1であるビットが赤，0であるビットが黒で表されています．
- 今日の授業では高速指数時間アルゴリズムの考え方について学べたが、個人的にとても興味深い内容だった。ただし、忘れている内容が多いので復習したいと感じた。
--はい，ぜひ復習をしておいてください．
- O(c^n)のcを小さくするということは今まであまり触れてこなかったので楽しみです
--そうですね．この授業を通して皆さんには「しらみつぶしでしか解けない」というような主張がどれほど正しくないのかということを味わっていただきたいと思います．
- 指数のオーダーを改善することのインパクトを甘く見ていたので、その凄さを体感できてよかった
--それはよかったです．評価を低くされがちなのですが，とても威力があります．
- 段階的に図で表されたスライドや手書きでの説明が、とてもわかりやすく、内容がスルスル入ってきたため、集合の基礎知識を振り返ることができました。
--それはよかったです．ただ，スルスル入ってきているときは，本当に理解できているか要注意ですので，改めて考えてみて，理解を確認してください．
- 最大独立集合を求める問題のアルゴリズムで、頂点を選ぶ順番が関係ないことが直感的にはわからなかったが、直前のしらみつぶしからの流れで見ると理解できた。目標を明示してくれるのがありがたい。
--目標を先に述べることを私は心がけています．皆さんもぜひ．
- 最大独立集合問題が簡単に解けて驚いた
--ぜひプログラムを書いて，実際に解いてみてください．どんな風に解けているのか，より深く分かるようになると思います．
- グラフ理論における開近傍や閉近傍って，普通の位相空間論とかで使う開集合や閉集合と何か関係があったりしますか．
--関係があってほしいのですが，関係がないというか，むしろ関係がないために混乱します．位相空間論においては開集合がメインの対象であるので，たとえば，単に「近傍」といえばそれは開集合になります．しかし，これはグラフに対する開近傍とは違うものです．もう少し具体的に言います．位相空間論において「xの近傍」のような言い方をするとき，それはxを含むような，ある集合を指します．一方で，グラフ理論において「xの開近傍」と言ったら，それはxを含みません．このあたりのグラフ理論の用語はややこしく，非常に分かりにくいように私自身も感じます．一方で，グラフ理論にはグラフ理論の伝統があるので，その伝統に従った用語をこの授業でも使うことにしていて，そのため分かりにくくなることはあるかもしれません．
- 異なる専攻の学生ですが、受講させていただきます。自分の研究テーマと関連があり、最適化問題にも興味があるからです。まず、最大独立集合問題を考える際に葉の数が大幅に減ったのに驚きました。独立集合が確定した時点で場合分けをやめることで、計算量を減らすことがポイントだと解釈しました。
--異なる専攻の皆さんも歓迎しています．ありがとうございます．最後に書かれたポイントは工夫2の方ですね．工夫1の方も実は重要です．
- 講義で扱ったアルゴリズムから，講義で扱ったグラフに対して最大独立集合を見つけられることはわかったが，本当にこのアルゴリズムで，どのような入力に対しても最大独立集合を出力させられるのか不安が残ります．「しらみつぶし」による安心感から抜け出せない自分がいると感じています．このような，腑に落ちない感覚を払拭するためにも，自らプログラミングをすることが大切なのだと思いました．
--そうですね．実感をするためには，プログラムを書いて動かしてみるのがよいかもしれません．
- 1024通りしらみつぶしの図がすべてグラフだと知った時にぎょっとしました．そのあとの木を使った考え方が際立って見えてとてもよかったです
--図を作るのに，かなり力をいれています ;-)
- 巡回セールスマン問題などは名前だけは聞いたことがあったため、改めてどのようなものか学ぶことができてよかった。今後も授業を通して、引き続き学びを深めていきたい。
--巡回セールスマン問題はあとのほうでまた出てきますので，そのときにまた思い出してください．
- 多項式時間でないアルゴリズムについて考える機会があまりなかったのでこの講義を機に学習したいと思った. 巡回セールスマン問題について, 頂点の中で三平方の定理が成り立つのであれば頂点を結んだ線が交差しないように選べば早くなりそうだと思った.
--ユークリッド平面上では，そのような考え方を進めていくことで，$2^{O(\sqrt{n})}$ 時間アルゴリズムが提案されています．これは $2^n$ よりも圧倒的に速いです．
- 色々な人が考えた結果であるとは思うのですが、最初に計算量を小さく出来ることに気付いた人はどういう考えを基に考えていたのか気になりました。
--最初のことはよく知らないのですが (調べてもよく分からないのですが)，1960年代や70年代には何人かの研究者が既に気にしていたようです．例えば，最大独立集合問題に対するTarjanとTrojanowskiの論文の出版は1977年です．
- 確かにんが非常に大きい時、N^3などの多項式は2^Nといった指数関数と比較して誤差みたいなものなので、O*記法を使用することは理解できる。でも、O(n^3)とO*(1)が同一かというと、元のオーダー記法の方に指数関数がないので、指数関数の存在を意識したこの記法は一見不適切であるように思える。
--ご指摘のとおりだと思います．普通は，O(f(n)p(n))と書くとき，f(n)が指数関数 (あるいはオーダーが多項式より大きな関数) であるときにO*(f(n))と書きます．ただ，授業で紹介した定義では，f(n)がそうでなくてもO*(f(n))と書けることになるので，O(n^3) = O*(1)となってしまいますが，実際にはそのような書き方はあまりしないと思ってください．
- グラフ理論に関する講義は非常に興味があったので楽しみながら講義を聞くことができました。1.3803という数字がどのように出てきたのか気になるので第2回も楽しみです。今後ともよろしくお願いいたします。
--残念ながら，これはグラフ理論に関する講義ではないのです．残念ながら，グラフを扱えばグラフ理論になる，というわけではないのです．また，グラフに関する講義であるわけでもなく，グラフは例としてでてきているだけです．今後はグラフでない例も出てくる予定です．
- 先ほど申し上げました通り，私は約束を守ります．全世代総力結集で，全員参加で頑張らなきゃ立て直せませんよ．だって，人数少ないですし，もう全員に働いていただきます．馬車馬のように働いていただきます．私自身もワークライフバランスという言葉を捨てます．働いて働いて働いて働いて働いて参ります． （高市早苗 新総裁選出後のあいさつより引用）
--馬車馬のように働くような馬車馬を皆さんが見たことあるのか，気になっています．
- 27ページ目のアルゴリズム内の3. A(G-N[v]))の閉じかっこが二重になっているのは誤植でしょうか。
--はい，ご指摘のとおり誤植です．修正しました．ありがとうございました．
- アルゴリズムの改善で具体的にどれくらい嬉しいかの話を聞けるのはありがたいです
--この嬉しさはあまり伝わらないのかもしれないと思っています．本来は，いろいろな例で実際に動作させた場合の状況をお伝えするのがよいのだと思いますが，この授業ではそこまでせずに，「最悪の場合の計算量がよくなった」ということと，「それによって何ができるようになるのか」ということだけをお伝えしていることになります．
- オーダースター記法について初めて知ったので感心しました。それ以外の箇所に関してはいつも通り（離散数理工学の時のような）で安心しました。
--O*記法はあまり標準的に使われるわけではないですが，細かいことを気にしなくてもよいので，この授業では使っていきます．皆さんが使うときには，ひとこと断ってから使う方がよいと思います．
- 先生の授業内にけっこ速口でした。最後の新しいオーダー記法もはじめって聞きました。勉強になりました。
--オーダー記法自体はよく使うので，しっかりと復習をしておいてください．
レポート課題
- 2回のレポート課題により評価を行う予定でいます．
- レポート課題1 (提出法，形式，採点基準などもこちらに記載)
公式シラバス
スケジュール (予定)
以下は仮の予定です．変更もありえます．
- 10/7 (1) 高速指数時間アルゴリズムの考え方
- 10/14 休み (体育祭)
- 10/21 (2) 分枝アルゴリズム：基礎
- 10/28 (3) 分枝アルゴリズム：高速化
- 11/4 (4) 分枝アルゴリズム：測度統治法
- 11/11 (5) 動的計画法：基礎
- 11/18 (6) 動的計画法：例
- 11/25 (7) 包除原理：原理
- 12/2 休み (秋ターム試験)
- 12/9 (8) 包除原理：例
- 12/16 (9) 部分集合たたみ込み：原理
- 12/23 休み (出張)
- 12/30 休み (冬季休業)
- 1/6 (10) 部分集合たたみ込み：例
- 1/13 (11) 指数時間仮説：原理
- 1/20 (12) 指数時間仮説：例
- 1/27 (13) 最近の話題
- 2/3 休み (修士論文発表会)
参考書，参考文献
この講義は以下の書籍・文献を参考にして構成されています．
他にも参考になるものはこちらに追加します．
関連リンク
過去の講義
[Teaching Top]
[Top]
okamotoy@uec.ac.jp