昨日，解法と共に知った問題．メモ． n個の要素が与えられる． また，2つの要素を受け取り，同じか否かを判定する判定機が与えられる． この判定機を用いて n/2よりも多く同じものがあるかを判定したい． 計算時間は判定機の使用回数とする． 例） {A, A, B,…

久々にWindowsを起動したらLinuxと日本語フォントがだいぶ違った．好みの問題をもあるのだろうけど，見ためがかなり違う．まず，Windows Vista．デフォルトフォント．つぎ，Arch Linux．フォントはIPA系，多分．

sed -i "s/錘/錐/g" fundamentals_of_convex_analysis.lyx で証拠隠滅しといた．

どっちなんだー． どっちでもいいのか？

Greedoid Antimatroid Polymatroid Minimum Spanning Treeにおいては Kruskalのアルゴリズムはmatroid的 Primのアルゴリズムはgreedoid的 なんだって．

p乗可積分な関数空間に包含関係はあるのか，ないのか？ (e.g. L2 ⊇ L1 とか） α次平均収束する確率変数列の空間の包含関係はあるのか，ないのか？ (e.g. 3次平均収束したら2次平均収束する とか）どうなんでしょう．包含関係があるなら，教科書とか載ってい…

何度見ても，大抵，数日後には定義すら忘れている． そんな負の連鎖を断ち切るために，メモしておく（あくまで，自分の理解の範囲，間違ってるかもよ）．（メモを見返す ≒ 忘れている， という反論は受けつけない）まず，定義． 概収束 確率収束 概収束のイ…

世の中には単模（たんも）行列なるものが存在する． 参考：完全単模性とその整数性(pdf) まぁ，そのようなものが存在すると，ここまでは良い． なにも問題ない． しかし，気になる． 「たんも」ってなによ？その意味を先日知った．ずばり，単一な（行列式の…

パスカルの3角形は次のコードで生成できる。 pascal = iterate next [1] where next xs = zipWith (+) (0:xs) (xs++[0]) showPascal n = mapM_ print.take n$pascal *Main> showPascal 10とすれば、次のようなパスカルの三角形が得られる。 [1] [1,1] [1,2,1…

分割統治を使ってO(N*log N)になるそうな。 分割統治と聞いたら、反射的に平面を二分して〜 とここまでは誰も思う。と思う。 しかし、この後のマージの処理が説明を読んでも意味不明でした。

前に作ったもの。ラムダ計算のベータ簡約をHaskellで実装。 module Lambda where import Data.List type Val = String data Lambda = V Val | A Lambda Lambda | L Val Lambda instance Show Lambda where show (V x) = x show (A m n) = show' m ++ show'' …

Haskellではリストは以下の3つに分けられる有限リスト [1,2,3,4] , [1,20,30] 無限リスト [1..] そして最後が擬リスト 例えば _|_,1:2:_|_, 10:20:30:40:50:_|_ 要するに、末尾がbotになっている。 上の二つのリストとの関係は擬リストの極限が無限リストと…

h = 1:map (2*) h # map (3*) h # map(5*) h where xxs@(x:xs) # yys@(y:ys) | x==y =x:(xs#ys) | x<y =x:(xs#yys) | x>y =y:(xxs#ys) prime = let p (x:xs) =x:(p (filter ((/=0).(flip rem x)) xs)) in p [2..] fib = 0:1:[i+j|(i,j)<-zip fib $tail fib]</y>

import Data.Array.IArray import Control.Monad (liftM,replicateM) import System (getArgs) import System.Random (getStdGen,randomRs) type Picture = Array (Int,Int) Int step x | x < 0 = 0 | otherwise = 1 inv 0 = 1 inv _ = 0 threshold :: Pictu…

{-- Time-stamp: <2008-10-11 15:24:47> ナップサック問題の動的計画法と分枝限定法 Usage: ./knapsack2.exe bb < knapsack_problem/problem ./knapsack2.exe dp < knapsack_problem/problem 入力データ使用 (アイテム数） （ナップサックの容量）（ナップサ…

すごいきれいな関係がprimal,dualに成り立つことを知った。 これだから、数学は面白い。簡単に書くと以下。 ここで、で、は閉凸錘、はの双対錘。

卒論とは関係ないけど Haskellで行列をうまく扱えるようになろう。

思っていた以上に難しい。 何が難しいかというと、速く動くプログラムの作成。 まぁ、NP困難な問題だから、そんなに簡単に速いものはつくれない。 しかし、1制約は連続緩和を利用した分枝限定法がかなり高速に動作する。 それに比べ2制約は、連続緩和が利用…

import Control.Monad.State (State,get,put,evalState) import Control.Monad import Prelude hiding(lookup) import Data.Map (Map,lookup,insert,empty) import IO import System import Data.List(sortBy) -- ====動的計画法==== type Table k v = Map k…

HaskellでDPを書いたが、復習に時間がかかり、結局DPしか書けなかった。 本当は分枝限定法も実装するつもりだったのに・・・終わらない・・・、時間がない。でも、分枝限定法はDPに終了判定を付加して、深さ優先で探索するようにしてやれば いいような気がす…

わかんね 剛性とか仮想荷重とか 物理を勉強してこなかったツケかとりあえず、教科書がほしいです用語の定義が分からないとか、もうね、どうしようもないよ

3次元空間において、超平面（2次元超平面）にカメラを固定する三脚は、その名の通り脚が三本ある。 言い換えれば、3次元空間においては超平面（2次元超平面）を指定するのには一般の位置にあるベクトルが3本あればよい、ということ。 それ以上は、追加される…

は成立しそうなんだが…、証明が思いつかない。そもそも、相対的内部って扱いにくい。

配列a[0],a[1],..,a[n]の要素をシャッフルしたい。 （つまり、シャッフル後、もともとa[i]にあった要素は等確率でa[0],a[1],..,a[n]のどれかにあることが条件） 次の方法はそれぞれ正しいだろうか？ (swapは要素の交換、rand(i,j)はiからjの整数を等確率で返…

n人でじゃんけんをします。一人の勝者が決まるまでに行うじゃんけんの期待値は？ とりあえず、二人でじゃんけんをする場合はです。 一般の場合にも、漸化式が成り立つので、それを解けば、一般項がもとまるが… 漸化式が複雑で解くのは大変そうだ…

について、その凸包はに属す高々個の点の凸結合全体の集合に等しい。 caratheodoryって、測度論でもでてきたような…空手踊り外測度とか。

型つきラムダ計算を実装しようと思ったが、これが思っていた以上に難しい。単にベータ簡約すればいいだけじゃないからなぁ。 まぁ、コンパイラつくるようなもんだしな。難しい…

次のような一次元ランダムウォークについてステップ移動後の位置の平均値と分散を求めよ。位置から出発し、1ステップ目では確率で位置に確率で位置に移動する。に対しては、ステップ目で正の向きに動いた場合、ステップ目では正の向きへ確率、負の向きへ確率…

なぜあの定義でよいのか？

正定値行列と実ベクトルについて、が正定値となる必要十分条件は？ とコレスキー分解して、を評価か？ なんて式がててきた。予想と違う、もう少しきれいな式が出てくると思っていた。