トップ 差分 一覧 ソース 検索 ヘルプ PDF RSS ログイン

NHC秋学校2007サポートページ

NHC秋学校2007(非公式)サポートページは、秋学校の講義の内容をより深く理解するための情報を共有し、参加者同士で議論していくための、実験的なページです。

とりあえずは、川原が integer programming の講義について復習、整理したことをどんどんと(わざとくどい文章で)書き込んでいきますので、それについて間違っているところの指摘などをしていただけるとありがたいです。

また、このページは wiki ですので、誰でも(参加者でなくても)自由に書き込んでいってください(新しくページを作っても構いません)。

注意:Integer Programming の復習のページは川原がリアルタイムに復習しながら書いています。途中で証明の間違いや、より適切な論理展開に気づいて、定義や定理などが大幅に書き換わることがあります。fix するのは1ヶ月以上かかりそうです。

管理人:川原 純 (メールアドレス jkawahara at lab2 dot kuis dot kyoto-u dot ac dot jp)

履歴

  • 10/29 Lenstra のアルゴリズムを少し追加
  • 10/26 整数計画法とアルゴリズム的数論を追加
  • 10/24 単体が作る整凸包の節を追加
  • 10/23 端点の定義を追加
  • 10/18 用語変更 extreme point の訳「極値点」→「端点」
  • 10/18 ナップザック多面体の極値点について勘違いしていたので、大幅に書き直し
  • 10/16 「講義のゴール」を加筆
  • 10/16 章構成を整理
  • 10/15 極値点の個数についてを追加
  • 10/15 極値点の定義を追加

講義の復習

講義資料

公式ページの資料へのリンク

Geometry that professors love

Low-distortion embeddings of metric spaces

Integer programming

Computational geometry

その他

Eisenbrand 先生のページより、講義の内容に近いと思われる論文&スライド

論文 / スライド

徳山先生の講義で扱ったモーレの定理(三角形の3つの角から三等分線を引いて正三角形ができること)について

http://homepage2.nifty.com/tangoh/hori040515.html

  • ここで「極値点」とよんでるものは普通「端点」と呼ばれるものですね.それはおいておいて,おそらくextreme pointの定義をちゃんと書き下したほうがよいと思うのです.定義がないので証明を追うことが困難になってる気がします. - okamoto7 (2007年10月18日 16時18分09秒)
  • extreme point の訳は適切なものが見つからず、自分で作りました。「端点」を使わせていただきます。extreme point の他にも、integer hull の訳で迷いました(これは「整凸包」と訳しました)。 - kawahara (2007年10月18日 18時33分26秒)
  • extreme point (vertex)の定義がないのは確かに問題で、私が Eisenbrand さんの講義を聞いていて「x はvertexだから矛盾」という部分でわからなくなった原因のひとつがこれじゃないかと思いました。あまり込み入った話にならないようにシンプルな定義を考えてみます。 - kawahara (2007年10月18日 18時40分14秒)
  • integer hullの定訳はまだない気がします.「整包」「整数包」「整凸包」...どれもよい気がします. - okamoto7 (2007年10月18日 23時02分29秒)