シェルでそのままfor文を書いたことがなくてあれだったので。 $ for ((i=0;i<10;i++)) for> do for> echo $i for> done 0 1 2 ... もちろん、 $ for ((i=0;i<10;i++)); do; echo $i; done; $ for ((i=0;i<10;i++)) do echo $i; done $ for ((i=0;i<10;i++))d…

（受験したのは2014年夏です）情報理工のコンピュータ科学の院試体験記もどき。・前提 数学：教養学部で数学1Aと2を履修（評価はどちらも可、しかも1Aは再履修してる） 英語：教養時代は全て評価が可、大学受験以降真面目に触れてない、6月末に受けたTOEIC(…

・論理回路の完備性・完全性(completeness)について いまいち理解がすっきりしなかったのでうんうん考えていた。これは論理学における関数の完全性の概念と同じ。{AND∧,OR∨,NOT¬}の演算子のみで任意の数の引数をとる全ての論理関数を構成できるというもの。c…

所属判定問題 CYK法 ・Gを文脈自由文法とする。入力としてw∈T^*が与えられたとき、w∈L(G)であるかどうかを判定するアルゴリズムがある。 証明： Gについて、A⇒^*εとなるような生成規則を取り除いていけばε∈L(G)かどうかを判定できる。さらにεがあるなら、L(G…

2014computer-s1-3(4) x座標が最小であるQの要素をq0とする。q0.x - p.x 再帰させるだけなので、時間計算量はO(nlog(n))となる。 Inner loopは、lower boundの維持とbreakによるupper boundによってP2の要素それぞれに対してO(1)で動作する。OuterがO(n)だか…

回帰分析 久米・飯塚『シリーズ入門 統計的方法２ 回帰分析』岩波書店、1987年 ・回帰分析は、複数個の変数の間の関係を解析するための代表的な手法。特性と特性の量的関係をつかむ。 目的変数をy、yの挙動を説明していると考えられるn個の変数をと表す。回…

正則表現(正規表現に同じだけど、形式言語においては正則表現と呼んで、実際にプログラミングで使うようなのは正規表現と呼んだりしている)の等式における性質がわかりづらかったので解釈をメモ。以下、正則表現r,sが集合L(r),L(s)を表すとする。記号の定義…

正則言語のPumping Lemma ・L⊆Σ*を正則言語とする。このとき、ある定数N>=1が存在して、Lに属する長さがN以上の任意の記号列xに対して、xの分解x=uvwで次の条件を満たすものがある。 1. 1=NとなるLの記号列xについて、xはMによって受理されるので、xのMによ…

二階線形微分方程式の話。引用：『演習 微分積分』サイエンス社、6.3節 ・定数係数斉次方程式 (1) に対して、二次方程式を(1)の特性(固有)方程式といい、その根を(1)の特性(固有)根という。 特性根をとするとき、(1)の一般解は次のように与えられる。 (i)が…

一階線形微分方程式 の一般解を求める。が0のとき となることが予想されるので、(2)を(1)に代入して、 この間の式は長くなるから消したけど普通に微分すると項が打ち消し合うので これを(2)に代入して で終わり。というか公式として覚えるのではなく解法とし…

AtCoderが日本語だし……と競技プログラミングに初めて手を出して試しに問題を解いてみたのだけど、（簡単な問題は解けるのはいいとして）提出されているコードに「これ使えたら便利だなぁ」と思うものがあったのでメモ。ありがとうございます。これから解いて…

OCamlのfunctorがよくわからなかったので調べて理解した限りのことを書く。間違ってたらすみません。・declaration of structure module Module_name = struct (* implement *) end ・declaration of signature module type SIGNATURE_NAME = sig (* declare…

・正規分布の標準化 正規分布を標準正規分布に変換すること。正規分布は平均と分散という二つのパラメータによって N(μ,σ^2) と表現される。この分布の確率密度関数は、 f(x) = 1/(2πσ^2))^1/2 * exp{-(x-μ)^2 / 2σ^2} であり、累積分布関数（あるいは単に分…

・エントロピーは情報量の期待値。複数のノードの遷移で表現される情報源のエントロピーは、各ノードの定常確率にそのノードからの遷移のエントロピーをかけあわせて合計する。定常確率は漸化式をn→∞で一定値にして合計1との条件でさっさと出す。・たまに区…

群（巡回群）の位数について。群の位数：要素の個数 要素の位数：aが単位元になるまで繰り返す演算の回数群Z/nZの位数はn。 群Z/nZの要素の位数は、(同値類の代表元を)何倍すれば0+nZになるかを表す。ただし最少の値。 たとえば群Z/6Zの要素の位数は、 1+6Z-…

微分方程式が解けない。C^2級の関数f(t)が f*f'' - (f')^2 -8(f)^2 = 0 の解であり、条件はf(0)=f(1)=1で、f(1/2)を求めるのが問題。 この形のままだと解けなさそうなので df/dt = v(f) と置くと、 f'' = dv/df * df/dt = v' * v であるから、 f*v*v' - v^2 …

ocamlで二進表現の型定義どうするのってぐぐってもそれらしい解説がついてるのが見つからなかったんだけど、やっぱり考えぬいて（アニメ見ながら3時間くらい考えた）以下の結論に至った。 type bnats = X | Y of bnats | Z of bnats type bnat = A | B of bn…

OCamlのコンストラクタがよくわからない。オブジェクト指向言語ばかりやってた私にとっては（と言ってもC#とかVB.NETだけど）コンストラクタというのはクラスからインスタンスを作るときに呼び出されるメソッドのことなんだけど、関数型のこの子にとっては違…