自転車をどこにとめたか毎回忘れてしまう人がいたので定式化してみた． 簡単のため，1次元で考えることにする． 6号館の玄関は[-1,1]の位置を占めていて，自転車を停めることができるのは[-M,-1]∪[1,M]であるとする． このとき，t君は原点から出発して移動を…

乱数に対する対角線論法 - yamblogの続き．プログラムの出力で01の文字列をつくってきたが， 頭に"0."をつけて[0,1]の実数の2進展開と対応付けることを考える． 例えば"10101"は"0.10101"となる． ”1”と”01111111…”は同じ値と対応付けられることが気になるか…

また，対角線論法で混乱してしまったので復習のためのメモ． コルモゴロフ複雑は人伝にしか聞いたことがないので，用語などは適当． 適当な0,1の文字列を出力するプログラムを考える． 言語はCでもJavaでもよい． ただし，Turing-completeで逐次的な出力がで…

貸与PCでの，研究室のプリンターからの印刷がうまくできなかったのでその修正法のメモ． 設定時には英語の論文を試しに印刷しただけだったので，気づかなかった． 2台設定したのだが，1台はギリシャ文字などの記号だけが出力されず，もう1台は記号は出力され…

研究中に思いついた問題 [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…

大学の貸与PCを今日受け取った その設定をメモしておく．スペックは lenovo ThinkPad T400s OS: ubuntu, windows vista cpu: Core 2 Duo p9400 @ 2.4GHz memory: 4GB HD: 250GB ubuntu9.10（32bit）を設定していく

makeplex salon：あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ にある問題を解いてみた． 再帰で実装 頭や暗刻は一つの数字につき高々1つであることを利用 1111222333444で1単騎を待ちとしてしまう …