2012-04-24
今日はうまく録画ができた． さて，世の中に「ベン図」というものがあるけど，これの定義を誤解している人が多い．私もそうだった．(というか，誤解された定義で教わっていて，そのままになっていた．) Wikipediaから「Venn diagram」と「Euler diagram」． つまり，ベン図はn個の集合を考えるとき，でき上がる領域が2のn乗個ないといけない．例えば，2つの集合AとBがあって，AがBにすっぽり囲われているような図はベン図じゃない．そういうのはオイラー図になる． ところで，オイラー図の国際会議というものがあるらしく，今年は7月2日にイギリスで行われるらしい．なんかわくわくする． A Guide to Experimental Algorithmics 作者: Catherine C. McGeoch出版社/メーカー: Cambridge University Press発売日:
2007-12-10
指名を受けたので記事書こうかと思ったけど, okamoto7先生ので十分だと思ったので止め. (id:smoking186さん) えー． もうこの話題関連から抜け出せなくなってるのかも．若干古いところから引いてきますが． 不正確だったり自己流の表現だから悪いという人は、「わかりやすさ」というものの本質を理解していない。「わかりやすさ」とは突き詰めれば「不正確さ」だ。厳密に正しい説明をするとわかりにくいから、あえて不正確に表現して分かりやすくする。 http://mechag.asks.jp/131404.html あえて極論っぽく書かれてるのかもしれませんが，「不正確でいる」ことと「端折る」ことは全然違うと思うんです．はい． それと，不正確な記述をしていることを意識しているかそうでないか，とか，不正確な部分に疑問を抱かれたときにそれを正確にできるかそうでないか，とか，そういうことが重要なの
2007-12-06 - okamoto7の日記 - 誤解の元凶は「計算量」ということば？
ありがとうございました．これで仕事できます． …結局気になってこればっかりかんがえちゃうから仕事できないじゃないか (笑) まぁA君 (S君？) の舌鋒鋭さに少し引き気味ではあるけども． というわけで，dankogai氏の次の記事のことです．また． アルゴリズム百選 - ベキ乗はO(1)でOK? アルゴリズム百選 - 用語の定義、またはその欠如 私の言いたいことは以前「アルゴリズムとプログラム」で書いたことと変わらなくて，もしこれに同意していただけるなら，こういう書き方にはならない気もするわけです．ここについてはそれだけですが，他の方もはっきりしていない部分があると思うので，書いていきたいわけです． その前に，計算量をオーダー記法で書く必要は全くありません．オーダー記法は計算量を記述するためだけのものでもありません．オーダー記法は関数の漸近的評価をするためのものです．大学でテイラー展開とか
オーダー記法：ちょっとしたクイズ 続き - okamoto7’s blog
数日前に出した「オーダー記法：ちょっとしたクイズ」ですが，いろいろコメントをいただきました．ありがとうございます． たぶん聞き方が悪かったのかと思いますが「どこがまちがっているでしょう？」という問題なので，どこが間違っているのか，その箇所をピンポイントしてもらいたいのです． 例えば， いまからひらがなを五十音順で書きますがどこか違います．どこがまちがっているでしょう？ 「あいうえおかなくけこ」 ならば，まちがっている箇所は「な」です．理由はそこが「き」でなくてはならないからです．(例としてかなり不適切だと思いますけど，これぐらいしか思いつかなかったので．) と，こんな感じで，どこが間違っているのかピンポイントしてもらいたいのです．1つ1つ等式や不等式を追っていったとき，どのステップの等式か不等式が間違っているのか，と．そしてどうしてなのか，と．言い方を変えると，ではどこまでは証明があってる
2007-10-12
1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています． (真実は 1+2+...+n = n(n+1)/2 なので．) どこがまちがっているでしょう？というのがクイズです． 証明 nに関する数学的帰納法． n=1のとき，左辺は1で右辺はO(1)．1=O(1)なので成立． n>1のときを考えると，1+2+...+n=(1+2+...+(n-1))+n = O(n-1)+n = O(n)+n = O(n)． ここで，「1+2+...+(n-1)=O(n-1)」という帰納法の仮定を用いた． 証明終 このクイズはいろいろ示唆に富んでると思うのです．考えてみてください． (誰に向かって言ってるのか不明ですが．) 数学セミナー 2007年 11月号 [雑誌] 出版社/メーカー: 日本評論社発売日: 2007/10/12メディア: 雑誌 クリック: 4回この商
2007-10-05
なんか日常的な生活に戻ったかも． 12月に東工大で行なわれる最適化ワークショップで講演させていただくこととなった． チュートリアル的なもの，ということなので，最近考えている「組合せ最適化理論の三次元描像」というタイトルで組合せ最適化の理論家がどのような考え方をするのかということの私見を講演してみたい． いまのところ予定している内容は以下の通り． 組合せ最適化の理論は「問題指向」のアプローチを取る．これは問題が与えられてから，それに対してどのようにアプローチをしてアルゴリズムを設計するか考える方向．それに対してメタヒューリスティクスや遺伝的アルゴリズムの研究は「アルゴリズム指向」のアプローチを取ってるのではないだろうか？つまり，まずアルゴリズムありきで，それを問題に対してどのように適用するのか考える． 組合せ最適化の理論は問題を分類しようとする．まず，問題がうまく解けるかどうかの分類を行なう
okamoto7の日記 天使と悪魔の問題
解かれたらしい．知らなかった． どういう問題かというと，2次元の無限正方格子のある1点に天使がいる．天使は1回にある決められた量だけ格子にそって動くことができる．しかし，その後，悪魔は格子の1点を(天使がいるところ以外は)どこでも壊すことができる．天使と悪魔が交互に自分の手を指していくが，最終的に天使がある有界の領域に閉じ込められてしまうかどうか，を考える．つまり，天使は悪魔に閉じ込められないようにしたいのである． 天使の1回の移動量が十分に大きいとき，天使は必ず逃げ切れる，というものがConwayによる予想だった．これが肯定的に解かれた，というのがニュース． もう少し詳しいことはwikipediaを参照． ちなみに，天使が1回に1歩しか動けない場合，天使はつかまってしまう． 原稿をようやく書き終えた．結局3ページぐらいになってしまった．端折りすぎたかも．
okamoto7の日記 - Skewed Binary Search Trees
Gerth S. Brodal and Gabriel Moruz Proc. ESA 2006, pp. 708-719 doi:10.1007/11841036_63 今日の勉強会で紹介したら好評だったので，ここでも紹介． 二分探索木は左側と右側がバランスするように構成すると探索時間が短くなる，と思ったら，実はそうでもなかった，という話． ある程度アンバランスにした方が探索時間が実際短くなり，その理由として，左部分木をたどるコストと右部分木をたどるコストが違うというモデルを提案している．コストが異なるようになる理由は分岐予測ミスやキャッシュミス，命令数の違いというものが挙げられている． 言われてみれば当たり前のような気もするが，言われなければ全然気づかないことで，とても面白いと感じた．
2006-12-18
Georgios P. Papamichail and Dimitrios P. Papamichail European Journal of Operational Research Volume 177, Issue 3 , 16 March 2007, Pages 1400-1408 http://dx.doi.org/10.1016/j.ejor.2005.04.011 k-meansクラスタリングとrange treeを融合した． とアブストラクトに書いてあるものの，ただ単にenumerationをrange treeを用いて行なって，その後でk-meansクラスタリングを行なっただけのような気がする． Yves De Smet European Journal of Operational Research Volume 177, Issue 3 , 16 March 200
2006-11-10
Oswin Aichholzer, and Hannes Krasser Computational Geometry Volume 36, Issue 1, January 2007, Pages 2-15 http://dx.doi.org/10.1016/j.comgeo.2005.07.005 SoCG2005の論文だけど，CGTAのこの号はEWCG2005の特集号． 彼らの作っている順序タイプ (order type) のデータベースによって，直線交差数 (rectilinear crossing number) の上界・下界を更新している． データベースについては有向マトロイドの枠組を使っていて，これはFinschi and Fukuda (2002) に似ているのかも． Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Gru
okamoto7’s blog
高等学校情報/情報の科学/負数と小数のデジタル表現 - Wikibooks の「関連する用語」の記述がひどい，と私の中で話題に． そこでは次のように書かれています． さて、情報科学で「ガロア体」（ガロアたい）という用語があるのだが、その正体は、単なる合同式、もしくは、その合同式の理論を必要に応じて定義拡張しただけのものである。 ガロアというと、数学史などでも紹介される偉大な天才数学者だが、しかし「ガロア体」という用語は、かってに情報科学者どもが使ってるだけな用語なので、もし大学などでガロア体という用語を聞いたら「でも単なる合同式だろ」と読者は脳内で置き換えよう。 ※ けっして独自研究でwikibooks編集者の「『ガロア体』なんて概念は無駄だし、存在しない」とか（独自研究で）言ってるのでなく、出版社名は忘れてしまったが2001年ごろに出版されていた離散数学（りさんすうがく）の大学1年レベル
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
2007-11-29