離散最適化基礎論
電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
2017年度後学期
金曜4限 (14:40-16:10)
教室：西5-214
岡本 吉央
テーマ：幾何的被覆問題
注意：内容は毎年変わります
ショートカット：
講義資料 |
コメント |
試験 |
公式シラバス |
スケジュール |
関連リンク |
参考書 |
過去の講義
講義資料
- 2/2 (13) 幾何アレンジメント (2)：浅胞複雑性とεネット
- 1/26 (12) 幾何アレンジメント (1)：浅胞複雑性
- 1/19 (11) 幾何ハイパーグラフ (3)：εネット定理の証明
- 1/5 (10) 幾何的被覆問題 (4)：局所探索法
- 12/22 (9) 幾何的被覆問題 (3)：局所探索法 (準備)
- 12/15 (8) 幾何的被覆問題 (2)：シフト法
- 12/8 (7) 幾何的被覆問題 (1)：線形計画法の利用
- 12/1 (6) 幾何ハイパーグラフ (2)：εネット
- 11/17 (5) 幾何ハイパーグラフ (1)：VC次元
- 11/10 (4) クラスタリング (1)：k-センター
- 10/27 (3) 最小包囲円問題 (2)：乱択アルゴリズム
- 10/20 (2) 最小包囲円問題 (1)：基本的な性質
- 10/6 (1) 幾何的被覆問題とは？
コメント
- 2/2 (13) 幾何アレンジメント (2)：浅胞複雑性とεネット
- コメントありがとうございました．
-
一学期ありがとうございました。
---
こちらこそありがとうございました．
-
今学期、ありがとうございました．
---
こちらこそありがとうございました．
-
今回のスライドが印刷できなかったのは自分だけでしょうか。表示はできたのですが印刷するとundefined resourceというエラーが出ました。
---
そのような報告は他に聞いておりません．
-
講義が難しいけど、いろんな問題解決の考え方を勉強になりました。
---
何かしらの役に立ったのでしたら，それはよかったです．
-
内容が難しく、理解するのが中々大変でした。期末に向けて頑張ります。
---
はい，がんばって下さい．
-
最近寒くて外出したくないです．
---
慣れて下さい．;-)
-
スーパーブルーブラッドムーンはご覧になりましたか？
---
見てません．;-)
-
既にアンケートにも書かれているかもしれませんが、先生は岡崎体育に似ているなぁと思ってました。
---
言われたことはなかったです．レパートリーに入れておきます．:-)
- 1/26 (12) 幾何アレンジメント (1)：浅胞複雑性
- コメントありがとうございました．次回が最終回となります．
-
戦法
漢方
先輩
担保
のように「ん」の後のハ行の音は濁るので、浅胞 (せんぽう) になると思います．
---
なるほど，そうですね．では「せんぽう」にします．
-
"せんぽう"だと，同じ読みの語と分かりにくそうだと思いました．
---
これは文脈で判断するしかないですね．同音異義語はたくさんありますから．
-
理解しきれてませんが、伏線が回収されてることはわかりました。
---
そうですね．いままで扱ってきたことが密接に関連しあっていることがわかりますね．
-
観察1を見て，軽い感動をしたのですが，名前はついていないのですか？
---
名前はついていないです．
-
期末試験やさしめだと嬉しいです。頑張りますが。
---
しっかりと準備してきてください．
- 1/19 (11) 幾何ハイパーグラフ (3)：εネット定理の証明
- コメントありがとうございました．
-
最近は乾燥が辛くて卒業まで完走できるか心配です。
---
…という感想ですね．
-
もしかして分数を書くときに英語を思い浮かべているんでしょうか？
---
分数を書くときに，勝手に手が分子へ動いてしまうのです．:-)
-
目的を見失わずに聞けました。
---
参考書では2ページ程度の証明で，割と簡潔に書かれています．授業では，行間も出来る限り補って，流れを分かりやすくしたつもりです．
-
今日の証明はマジックみたいでした．
---
マジックみたいな例を演習問題のために作ろうと思ったのですが，なかなか思いつかず，やめました ;-) -
確率を見ると苦手な印象がとれません．
---
確率は重要な道具なので，慣れて下さい．
-
演習問題が難しい問題ばかりで単位を取れるか心配になってきました
---
解けるものから解いて下さい．全部が解けることを想定していないので，まずは簡単に見えるものからやってみて下さい．
-
NP困難な問題も、今回のやつみたく、高い確率〜で解が得られるようにできないのかなぁと思いました．
---
回答は2つあります．(1) 最適解を高い確率で見つけることは難しいと考えられています．判定問題に限定すると，高い確率で正答が得られる多項式乱択アルゴリズムを持つ問題のクラスはBPPと呼ばれていますが，BPPとNPが違うか，分かっていません (包含関係も分かっていません)．実際，BPPはPに近いと多くの研究者が思っていて，P=BPPであり，P≠NPならば，BPP≠NPとなります．(2) 最適解ではなく近似解ならば，いろいろな研究があります．この講義で扱っているものはその例になっています．
- 1/5 (10) 幾何的被覆問題 (4)：局所探索法
- コメントありがとうございました．次週はセンター試験準備のため，授業がありません．
-
今日出てきたDelaunayグラフはボロノイ図を作って、領域が隣り合う頂点間に辺を引いてできるグラフと同じものですか？
---
はい，それと同じものです．
-
パックマンにも必勝法とかあるのでしょうか？ ("全てのエサを取ったら勝ち"というルールで勝ち目は無さそうなので変形する必要はありそう)
---
パックマンでプレイヤーが勝てるか判定する問題はNP完全だということが知られています．その意味では，必勝法がないことになります．
- 12/22 (9) 幾何的被覆問題 (3)：局所探索法 (準備)
- コメントありがとうございました．
-
超天才な頂点
辺が変
---
有頂天ですね．:-)
-
Menger「面がッッ！！」
---
綿々と受け継いでください．
-
パックマンすきです。
---
それはよかったです ;-)
-
今，受講している人のほとんどは，パックマンをプレーしていないけど，映画等で見た事はあるので，知ってはいると思います。
---
パックマンの映画があるということは知りませんでした．ありがとうございます．
-
平面的分離集合定理の証明ですがグラフとネットワークっぽくておもしろかったです．
---
今回はグラフの話でしたからね．
-
証明中のグラフが落花生に見えてきました．
---
筋張った部分までちゃんと再現されてますよね ;-)
-
背理法の仮定に背理法を使っていたので、今どこをやっているのか分からなくなりそうでした。
---
背理法による証明は直感的に分かりにくくなることが多いので，あまりお勧めできないのですが，強力であるため，よく使われますね．込み入った論理を追うときには意識的に注意して下さい．
-
もっと簡単でわかりやすい証明ができそうだと思ってしまいました．
---
ぜひ挑戦して下さい．
-
全ての平面的グラフは辺として線分のみを用いて平面描画できるのでしょうか．(曲線を用いなければならない例はあるのでしょうか．)
---
全ての平面的グラフは辺として線分のみを用いて平面描画できることが知られています．これはFáryの定理としてよく引用される事実です．
-
寒い…
---
暖房がついていないときは，暖房をつけて下さい．お願いします．
- 12/15 (8) 幾何的被覆問題 (2)：シフト法
- コメントありがとうございました．
-
先日は体調を崩されていたようだったので心配しましたが、回復したようで何よりです．
---
ありがとうございます．まだ全快ではありませんが．
-
コメント返しで海外の顔文字の方を使っているのは何故ですか (-ω-？)
---
海外の顔文字って何でしょうか？ ;-)
-
パズルのようで面白いです。
---
それはよかったです．:-)
-
近似アルゴリズムを設計する際のメジャー法は何がありますか．
---
この講義で扱っているものはメジャーな方法だと思って下さい．他にもいろいろありますが．
-
8.4は単位円グラフ上の最大独立集合問題ですか？ であるとしたら、単位円グラフの特徴がもっと知りたくなります．(一般のグラフとどれだけ違うから最大独立集合問題が解ける〜みたいなことです)
---
その通りで，単位円グラフ上の最大独立集合問題です．つまり，単位円グラフ上の最大独立集合問題に対してはシフト法により多項式時間1+ε近似アルゴリズムが作れます．シフト法が適用できるのは幾何学的な性質をグラフが持つからで，そのようなことがどんなグラフにもできるわけではない，という特殊な性質を単位円グラフは持っているわけです．
-
一瞬，3点で楕円を決めれば連続の楕円被覆も可能かと思ったのですが，向きがバラバラで分割が難しい？
---
向きがバラバラであることはあまり大きな問題にならず，もっと大きな問題は，いくらでも平べったい楕円を考える必要があることです．一方で，単位円の場合は縦横比が一定なので，考えやすくなっています．別の言い方をすれば，長軸と短軸の長さの比がある定数以下であり，面積もある定数に等しい楕円で被覆する，という問題に対しては，同じようなシフト法で多項式時間1+ε近似アルゴリズムが作れます．
-
シフト法での分割を正方形でなくてもっと角数の大きい多角形 (正六角形) とかでやるような研究はなされているのでしょうか？
---
なされています．そのとき，うまく空間を敷き詰めるような図形を考えることが重要です．
- 12/8 (7) 幾何的被覆問題 (1)：線形計画法の利用
- コメントありがとうございました．掲載が遅くなりすみません．
-
P17/34でlinearであるべき所がintegerになってました。
---
ありがとうございます．修正しました．
-
17枚目のスライドで，"integer"は"linear"の誤りではないかと．
---
その通りです．修正しました．
-
西暦2995年、地球はどうなっていると予想しますか？
---
私の死後の世界には興味がありません ;-)
-
糖質制限ダイエットのため，思考力が低下になって、どうしましょう…
---
医師ではないので何とも言えません．
-
前回紹介していただいたNP完全の本にhitting set problemを集合打問題と訳していたので，hitting setは集合打と書くのかなと思います。ただ読み方は分からないです。
---
集合打とは誰も呼ばないと思います．「集合打」という日本語が集合を指すとは，健全な精神を持つ日本人は思わないはずです．
-
ε-ネットの定義は美しいなと今日の応用例で思いました．
---
それは良かったです．:-)
-
εネットが綺麗に活用されて面白かったです．
---
それは良かったです．:-)
-
週末はどうしても気だるいです．先生はどうやって乗りきっていますか
---
「乗りきる」というほど，気合を入れなければいけないわけでもないですが，たいてい外出します．
-
なんかナップサック問題みたいです
---
ほう，そうですか．どの辺りがナップサック問題みたいでしたか？
-
３３対４
---
ほう，そうですか．どの辺りが３３対４みたいでしたか？
- 12/1 (6) 幾何ハイパーグラフ (2)：εネット
- コメントありがとうございました．次回はようやく幾何的被覆問題を解きます！
-
演習問題とかのアップロードが遅い．
---
当日の12:00までにあげる，と初回に言ってまして，それは守っているはずです．
-
最適化の授業は離散，連続共に比較的レベルが高い気がします．
---
では，一生懸命レベリングをして下さい． ;-)
-
直線も円もそうですが，εネットのサイズの上界と下界のギャップが広くておどろきました．
---
世の中には分かっていないことの方が多いのです．;-)
-
もう今年も1ヶ月になってしまいました。
---
そうですね．1年がはやく感じますね．
-
すいみんをしっかりします
---
はい，しっかりと家でしてきてください．
-
かぜひきそう
---
ひかないように気をつけて下さい．
-
カゼを引いて大変だったので，先生も御体に気をつけてください
---
ありがとうございます．ご自愛ください．
-
講義中の水分補給は大体麦茶のようですが，これは習慣なのでしょうか？
---
お茶なら何でもかまいませんが，烏龍茶はのどを乾燥させると聞いたことがあるので，最近は避けています．
- 11/17 (5) 幾何ハイパーグラフ (1)：VC次元
- コメントありがとうございました．残った部分は次回にやりますので，お忘れなく．
-
調布祭が忙しいです
---
別に，調布祭が忙しがっているわけではないと思いますが…
-
大学院に進学したら，新しくプログラム言語を学習しようかなと思います。オススメはありますか？ (岡本研の某学生からはRubyとHaskellを勧められています)
---
特におすすめするものはありません．一方で，プログラム言語を学習する，という目的でプログラム言語を学習する，ということ自体はあまりお勧めしません．
-
おすすめのカフェをドトールとミスド以外で教えて下さい．
---
別に，ドトールとミスタードーナツをおすすめしているわけではないです ;-)
-
英語の単語を日本語に訳するときと，カタカナにする場合の違いはどこにあるのでしょうか。
---
伝統的には，日本語に訳すべきだと思います．それが明治時代の人々，例えば，夏目漱石，福沢諭吉，二葉亭四迷らの大きな関心事の一つであり，その恩恵を我々は受けて，西洋の様々な概念を日本語で享受できるようになっているわけです．ただ，翻訳というのは相当慎重に行わなければならず，慎重さのない翻訳は未来に悪い影響を及ぼしかねません．その意味においては，専門的な見解を持たない人が下手に翻訳を行うことは害悪である可能性があり，注意が必要です．
-
道中迷子になりかけましたが、なんとかわかりそうです。
---
しっかり復習をして下さい．
-
今回のはなかなか...難しい...。
---
ハイパーグラフの話は抽象的ですよね．しっかり復習をして下さい．
-
ハイパーグラフを図で示すと，どうしても見にくくなってしまうのですが，コツか何か良い方法は無いのでしょうか．
---
これはなかなか根深い問題で，情報可視化の分野でいまでも多く議論されている話題です．
-
VC次元と機械学習との関わりについてのお話を楽しみにしております。
---
残念ながら，その側面はこの講義で扱うことはありません．
-
粉砕の粉砕っぽさが感じ取れなかった。
---
集合 $X$ の上に射影するときに，$X$ の部分集合がすべて現れる，というのが粉砕している雰囲気です．$X$ という集合が完全にバラバラにされている，という気持ちなんだと思います．
-
$V=\mathbb{R}$，$E=\{ [a,b] \colon a,b \in \mathbb{R}, a \leq b\}$ とか無限個の頂点や無限個の頂点からなる辺とかちょっと気味が悪いような気がします
---
一方で，無限個の頂点や無限個の頂点からなる辺を考えることで，一般性の高い議論もできるので，その点は便利なわけです．
-
閉半平面のVC次元が上から3で押さえられるのは，平面が3点で定まることと関係している？
---
はい，若干関係しています．この講義では扱いませんが，粉砕次元 (shattering dimension) というVC次元に関連する概念があり，そこでは図形が何点で定まるのか，ということが重要になります．
- 11/10 (4) クラスタリング (1)：k-センター
- コメントありがとうございました．
-
食後で眠くなっていた為，小休憩中に寝れて助かりました。
---
それはよかったです ;-)
-
冬
---
寒くなってきましたね．
-
研究が行き詰って焦ります。
---
焦っても仕方がないので，コツコツ進めていきましょう．
-
研究室の同期が優秀なのでプレッシャーがかかっている気がして心理的に厳しいです
---
他の人が何をしているのか気にしても仕方ありません．自分のできることを確実にしていってください．
-
クラスタリングにおいて，3モデル以外にも利用されるようなモデルはあるのでしょうか．
---
いろいろありまして，そのためにクラスタリング研究がいまでも盛んに行われていることになっています．
-
円以外を使ってクラスタリングするような研究などはされているのでしょうか？
---
端的にいえば，あります．円は分かりやすさのために例として用いましたが，考えている状況によっては楕円を使ったり，その他の図形を使ったり，また，そもそも埋め込まれている空間がユークリッド空間ではない場合もあります．
-
k-ミーンズがk-メディアンと違う結果になることが直感的に分からない…。距離 d≧0 なのだから2乗しても最小値は変わらないような気がするのに。
---
別の具体的な例を出してみます．1次元の数直線上で，座標0の位置 (つまり原点) に2個，座標1の位置に1個点があるとします．考えるクラスタの中心は0と1の間に位置すると当たりが付けられるので，それをxとしましょう．k-メディアンの場合に最小化するべきものは，2x + (1-x) = x+1 になります．つまり，x=0のときに最小化されて，求めるべき中心は座標0に来ます．一方で，k-ミーンズの場合に最小化するべきものは，2x^2 + (1-x)^2 = 3x^2 - 2x + 1となり，これが最小となるのは，x=1/3のときです．なんとなく持つ印象としては，k-ミーンズの方が遠くにあるものとのバランスを取りたがっているように思います．(距離を2乗するため，遠くにあるもののコストが大きく寄与しがちである，ということです．)
-
近似比について「○○近似アルゴリズムが存在しない」というときに○○が小数であることがよくあるように感じます．今回出てきた「1.822近似は存在しない」の1.822はどこから来たのでしょう
---
$(1+\sqrt{7})/2$ です．
-
下界を示すのを学べるおすすめの本とかありますか？
---
古くなりましたが，岩田茂樹先生の『NP完全問題入門』は昔よく薦められた本です．しかし，現在絶版です．
- 10/27 (3) 最小包囲円問題 (2)：乱択アルゴリズム
- コメントありがとうございました．来週は祝日で，休講になります．
-
今日はプレミアムフライデーですが、何かプレミアムな事をしましたか？
---
授業が終わってから吉祥寺にいきました．
-
Trieには2017/10/27時点で何回行きましたか？
---
2回ぐらいは入場しています．
-
昼夜の寒暖差が大きいので体調が崩れました．
---
夜はおとなしく寝て下さい．;-)
-
確率・統計に苦手意識があるので警戒しましたが、今回の内容ではなんとかなりました。
---
今後も連続確率変数は登場しない予定なので，計算などは難しくないはずです．
-
乱択にするだけで、ここまで計算量が落ちるのは中々面白いですね
---
そうですね．乱数を使うことで計算量が小さくなったり，アルゴリズムの設計が簡単になることがよくあります．乱数を使うということが本質的である場合があるのです．
-
確率の話がこれからも関わってくると思うので勉強しておきます．
---
その通りです．この講義では離散確率変数の話しか使いませんが，少し復習をしておいてもらうとよいと思います．
-
最悪期待計算量が小さくなるという結論は当然のような気がしましたが、解析が面白かったです。個人的に計算量の計算も参考になります。
---
小さくなる度合いをしっかりと計算して，どれだけ小さくなるのかということを評価することが重要ですね．
-
最悪計算量ではなく期待値の最悪を考えることによってオーダーがすごい小さくなったということですが、アルゴリズムのやっていることは変わってないので、あまりすごみを感じませんでした。
---
アルゴリズムのやっていることは変わっています．乱数を使うか，使わないか，ということは大きな違いなのです．
-
今日の乱択アルゴリズムは脱乱択化できるのでしょうか
---
脱乱択化と呼ぶべきなのかは分かりませんが，同じ計算量O(n)で乱数を使わずに最小包囲円を計算するアルゴリズムはあります．
-
LP-type problemは前に読んだとき難しくてあきらめたのでもう1度チャレンジします．
---
はい，是非チャレンジしてみてください．
-
楕円は何故5点で一意に決まるんでしょうか？
---
直感的な説明をしますが，楕円は「中心のx座標，中心のy座標，長軸の長さ，短軸の長さ，長軸の傾き」という5つの量を決めると，1つに決まるからです．
-
とても眠くて途中の説明を聞きのがしてしまったので復習したいと思います
---
はい，よろしくお願いします．
-
「たぶんこんな感じ」から正確な証明の書き方に落としこめません．厳しい…
---
慣れが必要だと思いますので，演習問題を通して身につけて下さい．
-
「AならばBとなるとき、A⊆B」のような定理 (?) が割と好き
---
私にその気持ちがちょっと伝わってきません ;-)
-
周りが知らない人ばかりで演習のときに相談する勇気がありません。
---
勇気を持って下さい :-)
- 10/20 (2) 最小包囲円問題 (1)：基本的な性質
- コメントありがとうございました．
-
1.5のヒントを下さい
---
数直線の左から右へ順に見て行って下さい．
-
複雑な展開になると最後までついていけなくてつらいです．(復習しますが。)
---
難しいところは質問して下さい．お待ちしております．
-
少し難しかったです．がんばって復習します．
---
難しいところは質問して下さい．お待ちしております．
-
スライドp14の $D_0 \cap D_1 \subseteq D_2$ を証明するには数式立てて解析的にやればできそうですが、他に使うと簡単に証明できるようになる定理などはあるのでしょうか？
---
私も解析的にやることを想定していました．それよりも簡単な論法があるならば，私も知りたいです．
-
直感的には当たり前でも証明は大変だと思った．
---
そうですね，しっかりと証明しようとすることと，それができることが大切ですね．
-
点を書いてから円を描くのではなく、円を描いてから点をかくと上手く円が描けます．
---
ありがとうございます．ただ，それだと，3点を通るように円を描く，という「操作」を黒板上で示すことができないのです．見せたいことは3点を通る円という「物体」なのではなく，「操作」なのです．
-
途中まで O(n4) のアルゴリズムで残念だなと思っていましたが最後でやられました。次回に期待します。
---
はい，ご期待ください :-)
-
実際に (3-3) が毎回選ばれることがなさそうなので，このアルゴリズムで解析を頑張れば高速になりそうな気がするのですがどうでしょうか？
---
実際に (3-3) が毎回選ばれることはあります．その意味では，最悪の場合は起こりえます．
-
sed(P, R)の例の図などはどのソフトで描いていますか
---
これはIpeで描いています．
-
円を描くために使っていたソフトは何というものですか？
---
動かしていたものはCinderellaです．
-
$D_0$ と $D_1$ を $\lambda : (1-\lambda)$ に内分する点を中心にもち、$D_0$，$D_1$ の交点を通る円 $D_\lambda$ の説明に使われたツールが見ていて分かりやすかったです。
---
直感を得るために，しっかりとした図を描くことは重要です．幾何の場合には，コンピュータを使えるととても効率がよいですし，正確な図も描きやすくなります． -
あるRがあるのである
---
Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffaloや子子子子子子子子子子子子みたいですね．;-)
-
寒いですね．好きなみそ汁の具を教えて下さい．
---
なめこですね．:-)
-
Trieには行きましたか？
---
入館はしました．何も買っていませんが．
-
平成の次は何になるのでしょうか？
---
こういう情報はすっぱぬくと変更されてしまうので，変に予想しない方がよいと思います．
- 10/6 (1) 幾何的被覆問題とは？
- ありがとうございました．コメントは以下のように掲載されます．
-
履修登録をしない場合でも講義のコメントやレポートを提出してもよいのでしょうか？
---
提出してもよいです．特にチェックもしていません．
-
できるだけ毎回演習問題全部に答えられるようがんばります。
---
はい，よろしくお願いします．
-
先生はおもしろいです。
---
ありがとうございます．おもしろくいようとはあまり思っていないのですが ;-)
-
今学期よろしくお願いします
---
はい，よろしくお願いします．
-
(留年したので) 3年次後期の離散数理工学以来2年ぶりの岡本先生担当の講義を受講することになりました
---
よろしくお願いします．
-
コメント返すの大変そう．
---
たしかに大変ですが，これが「生きがい」なので問題ありません ;-)
-
西5が遠いので西4でやってください。
---
西4に教室はないので，西4ではできません．あしからず．
-
教室の中がすごく暑かったです
---
窓を開けて下さい．;-)
-
調布トリエが気になっているのですが，探索できてないです。先生は見に行きましたか？
---
見に行っていないですが，trieをトリエと読むことも気になっています．
-
被覆問題の例の21ページの図が色合い的に大学いもに見えておなかが減りました
---
昼食をとってきてください ;-)
-
Beamerのスライドを久々に見たと思いました．
---
いまはBeamerを使っていますけど，今後もずっとそうであり続けるかはわかりません．よいと思っている道具を使っています．
-
スライド中の美術館問題，3点で足りそうです．
---
確かにそうですね．ありがとうございます．
-
1.3が「連続型直線被覆問題」になっているのはまちがい？
---
はい，間違いです．ありがとうございます．修正して下さい．
-
円と円板は、数学の用語として普及して欲しい
---
高次元になったときは，球面と球体の違いに注意しなくてはなりません．球体の表面が球面なのです．
-
連続型直線被覆問題において，点を1つだけ通る直線も考慮する場合とはどのような場合でしょうか．
---
例えば，各点が直線によってちょうど1回ずつ被覆されなくてはならない，という場合には点を1つだけ通る直線も考えることがあります．しかし，講義で扱った問題にはそのような制約がないので，点を1つだけ通る直線を考慮する必要はないのです．
-
なんで今年だけ幾何的被覆問題を扱うことになったのでしょうか。
---
「今年だけ」の部分が強調されていたので，なぜ今年だけなのか，を回答します．毎年違う内容の講義をすることで，日本人全般に対して離散最適化に関する情報を提供することができるからです．離散最適化の基礎は非常に広く，いまの段階でもあと20年ぐらいは毎年違う内容で講義することは可能です．過去の講義の内容はこちらからたどれます．
-
最適化問題に対して、現実の問題に応用できなければ意味ないと言えますか。
---
「現実の問題」や「応用」ということばが想定するものによって答えは変わるかもしれませんが，通常は，応用できなくても意味がないわけではない，と思っています．
試験・評価
- 期末試験により成績評価を行います．
- 期末試験問題 (2/16実施)
- 得点分布
- 受験した人の数は11．
平均点は56.4 (120点満点)．
80点以上 (A) が3名，
80点未満70点以上 (B) が1名，
70点未満60点以上 (C) が1名，
60点未満 (D) が6名です．
- 得点掲示 (辞書順に並べています)
| !msds | 64 |
| 0107 | 85 |
| 2cvmf | 14 |
| 42425 | 42 |
| action | 38 |
| MONO | 82 |
| ranati | 89 |
| xk | 53 |
| いけないボーダーライン | 76 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評：想定していたよりも全然できていなくて衝撃を受けました．問題2, 4, 6は点数を与えるための簡単な問題であるつもりでした． (問題6について，試験開始時に，Markovの不等式が何であるか，板書でヒントとして与えてました．) 演習問題と同じ問題は1と5と6です．問題1は何度も言及していたもの，問題5は授業でやったものなので，もっとできていてほしかったです．ということですので，この成績も妥当である，という気になりました．
公式シラバス
こちらをご覧ください
スケジュール (予定)
- 10/6 (1) 幾何的被覆問題とは？
- 10/13 国内出張のため休み
- 10/20 (2) 最小包囲円問題 (1)：基本的な性質
- 10/27 (3) 最小包囲円問題 (2)：乱択アルゴリズム
- 11/3 文化の日のため休み
- 11/10 (4) クラスタリング (1)：k-センター
- 11/17 (5) 幾何ハイパーグラフ (1)：VC次元
- 11/24 調布祭 のため 休み
- 12/1 (6) 幾何ハイパーグラフ (2)：εネット
- 12/8 (7) 幾何的被覆問題 (1)：線形計画法の利用
- 12/15 (8) 幾何的被覆問題 (2)：シフト法
- 12/22 (9) 幾何的被覆問題 (3)：局所探索法 (準備)
- 1/5 (10) 幾何的被覆問題 (4)：局所探索法
- 1/12 センター試験準備 のため 休み
- 1/19 (11) 幾何ハイパーグラフ (3)：εネット定理の証明
- 1/26 (12) 幾何アレンジメント (1)：浅胞複雑性
- 2/2 (13) 幾何アレンジメント (2)：浅胞複雑性とεネット
- 2/9 休み
- 2/16 期末試験
関連リンク
参考書
この講義は以下の書籍を参考にして構成されています．
- M. de Berg, O. Cheong, M. Overmars, and M. van Kreveld, Computational Geometry: Algorithms and Applications, Springer, 2008. (邦訳あり)
- J. Matousek, Lectures on Discrete Geometry, Springer, 2002. (邦訳あり)
- S. Har-Peled, Geometric Approximation Algorithms, AMS, 2011.
過去の講義
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
