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