splotで３次元の出力をしたら見にくかったので， ２次元に切った画像を動画にしてみたときの操作メモ．まずは，c++などでデータを出力 double func(double c, double d){ return 0;//適当な関数 } void outputC(int i, int n){ double c = 1.0*i/n; char fna…

研究中に思いついた問題 [0,1]一様乱数からn個とってきたとき，小さい方からk番目の値はどうなるか？ であるが，答えがあった．順序統計量 - Wikipedia結論としてはベータ分布：Beta(k,n-k+1)になるらしい．期待値は予想通りk/(n+1)．全ての値が等間隔になら…

どちらもMinimum Spanning Treeを求めるGreedy Algorithmであるが，いつもどっちがどっちだったか忘れてしまうのでメモ． 点数をn，辺数をmとする． Kruskal 辺を軽い順に追加していくもの 木マトロイド 普通の実装だとO(mn)，Union Findを使えばO(m α(m,n))…

研究中に練習問題としてちょうどいいレベルの問題がいくつかでてきたのでメモ． 全部簡単だけど，きれいなプログラムにするのは悩む． 問1,3は線形時間でメモリはO(1) 問2,4は線形時間で線形メモリ まずはnotation [n]={0,1,2,..,n} f: [n]->[n] f(k)0), f(0…

論文のファイルがあちこちにちらばって探すのが困難になったことと， BibTeXファイルを毎回作ることが面倒になったため文献管理ソフトを使って管理することにした．BibTeX関連ツール - TeX Wikiで物色した結果 JabRefを使うことにした． Jからはじまることか…

id:tzik-tackによるシャノンゲームの実装が公開された． http://www.misojiro.t.u-tokyo.ac.jp/~tzik/shannon/index.xhtml シャノンゲームとは，無向グラフ上のゲームで， 2人のプレイヤーが交互に短絡除去（SHORT）と開放除去（CUT）を繰り返すことで行われ…

昔演習で出された問題だが， n 個の風船があり，それぞれの容量を1, 1/2, 1/3, . . . , 1/n とする． 各風船は容量を超える空気を入れると割れてしまう． 風船になるべく多くの空気を詰めたい． nが十分に大きい時，空気の入れることのできる量の期待値はど…

The Balloon Popping Problemの続き．昔書いたHaskellのコードを解読したところ， 風船が少ない時について，2通りの戦略で空気を入れたときの最大期待値を求めるものであった． 風船が少ない時についての最適値を求める訳ではない． ただし，DPにすればいい…

の逆関数をLambert W functionというらしい． これがあるとの逆関数なども表せるため，研究で必要になった． に注目すればの解はである． ところで，とがどれぐらい違うかは分からない． wolfram alphaに聞いてみたら， とのことだった．世の中うまくいかな…

論文に出てきたが「正の実数」なのか「非負の実数」なのかがわからなくて数時間悩んでしまった． 0を許すかどうかがNash均衡を議論する上では大事になるので分かりにくくて困る．以下のような記法にすれば勘違いが減るはず 非負の実数 0}=\)"/>正の実数 加法…

自明・明らか＝9割方あってる 自明に明らか＝8割方あってる

自分のした証明が理解できなかった． 誰か教えてください．

グラフ理論での木の定義が本によって違いすぎて分からない． グラフGの部分グラフTが木であるとは 極大な閉路を持たないもの（極大木・全域森） V(G)が連結で閉路を持たないもの（全域木） V(T)が連結で閉路を持たないもの 閉路を持たないもの（林 or 森） …

昨日は研究室輪講での発表があった．そのときの資料を上げておく 発表用PDF 資料PDF

調和級数はdigamma関数を使って表現できるらしい ただし，

調和級数 についてのメモ． 別表現 連続化 単調性 OK 凹関数 OK 双対？

最短経路問題をLPでどう書くかを忘れたので復習．まずは，記号の準備をすると， 有向グラフ 枝の長さ からまでの最短路を求めたい． このとき，最短経路問題はのように記述できる．ここで，完全単模性よりは0,1変数であると考えてよい．は枝を選んだことを意…

論文を読んでいたらという不等式がさも当たりまえかのように出てきた． 累乗和だし，差分をとったらうまくいくかと思いきやなかなかうまくいかなかった． 実は，高校レベルで簡単に示せる．

10/28に研究室輪講で発表をしなければならないので，そのネタ探し中とりあえず，前回price of anarchyをやったので，Network Design Gameというものに手をだしてみる．の評価は鮮やかすぎる． Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vaziran…

図形Cの双対図形は で与えられるらしい．とりあえず，成り立ちそうな補題を考えると， lemma 1 lemma 2 lemma 3 lemma 4 具体例 （立方体の双対は正八面体） なぜか資料が見つからない．