離散最適化基礎論
電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
2025年度後学期
火曜2限 (10:40-12:10)
教室：西8-132
岡本 吉央
テーマ：高速指数時間アルゴリズム
注意：テーマは毎年変わります
ショートカット：
講義資料 |
コメント |
レポート課題 |
公式シラバス |
スケジュール |
参考文献 |
関連リンク |
過去の講義
実施形態
この授業はハイブリッド形式で行います．授業は教室からZoom配信します．スライドはZoomで共有し，板書も教室の黒板では行わず，Zoomで共有したスライドの上から行います．教室では，Zoomの画面をプロジェクタで投影します．そのため，教室で受講することのメリットは (1) ライブ感，時空間共有感覚を持てる，(2) 質問を口頭で即座にできる，(3) ネットワークトラブルに影響されない，などといった点にあります．授業は録画し，あとで公開します．
学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．
内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．
講義資料
- 11/25 (7) 包除原理：原理
- 11/18 (6) 動的計画法：例
- 11/11 (5) 動的計画法：基礎
- 11/4 (4) 分枝アルゴリズム：測度統治法
- 10/28 (3) 分枝アルゴリズム：高速化
- 10/21 (2) 分枝アルゴリズム：基礎
- 10/7 (1) 高速指数時間アルゴリズムの考え方
コメント
- 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