群、環、体について

数体ふるい法のアルゴリズムを読んでいると分からない言葉が出てきてすぐ挫折します。。1行読むのにも一苦労。とりあえず、数学力が足りません。ということでちょっとずつ勉強していこうと思う。

今日は、群、環、体について。英語では、group、ring、fieldとよばれます。1つずつ概念を抑えていこうと思います。ここでは具体例を考えながら、その性質を考えていきます。以下では、ここに記載されている定義にしたがって議論を進めます。

まず、全体的な話。これらの概念は、集合+その集合に対する演算をひとくくりにした概念です。集合だけではなく、それにたいする演算も統一的に扱って議論を進めたい場合にこのgroupとかring、filedといった概念が必要になります。

group

　群では、集合S上の要素x, yについて二項演算opを施した結果もまた集合Sに含まれます。たとえば、整数の集合Zを考えます。Zの要素に対して二項演算+を実行します。すると結果は整数になります。

"整数 + 整数 = 整数"なんて当たり前じゃないか、と思うかもしれないですが、これはよく考えるととても面白いことです。

群の定義を見ると、いくつかの例は簡単に思いつきます。例えば、整数の集合と演算子+は群を成します。しかし、正の整数と+は群を成しません。単位元が存在しないからです。正の整数 + {0}の集合にすると、単位元は存在します。しかし逆元が存在しないため、群にはなりません。

　次に、整数の集合と*を考えてみます。単位元は1です。しかし、逆元が存在しません。一般に整数nの逆元は1/nとなりますが、これは必ずしも整数にはなりません。それでは、整数じゃなくて実数集合を考えてみます。これは、群になるような感じがしますが、0に対する逆元は存在しません。よってこれも群ではありません。実数集合から0を除いたものと演算*は群をなします。

　上記では、無限集合を考えましたが、有限集合の場合を考えてみます。{0, 1}という集合を考えます。これに対して演算ORを考えます。これは群をなすでしょうか？

　まず、演算ORは集合に対してclosedです。単位元は0です。演算はassociativeです。但し、1に対する逆元が存在しません。よって、{0, 1}と演算ORは群をなしません。では演算ANDに対してはどうでしょうか？演算はclosed、単位元は1、演算はassociativeですが、0に対する逆元がありません。有限集合で群をなすものはそう簡単には見つけられないのでしょうか。。

　法3の世界を考えます。剰余類の完全代表系は、{0, 1, 2}です。この法の世界において演算+を考えます。演算はclosed、単位元は1、演算はassociativeです。すべての要素について逆元は存在するでしょうか？(0, 1, 2)に対して、(0, 2, 1)が逆元になります。よって、この系は群をなします。

ring

　環は集合Sと二つの演算add、mulを統一的に扱うための概念です。群では考える演算子は1つでしたが環では2つです。それぞれ、足算と掛け算に似たような性質を持つためここではadd、mulと表記します。定義を見ると、(S, add, mul)が環であるとき、(S, add)は群をなすようです。つまり、(S, add)が群であるということは、(S, add, mul)が環であるための必要条件らしいです。

　まず、対象の集合が無限集合である環を考えてみます。整数の集合と+はアーベル群をなすので、これに*を加えると環になるか考えてみます。アーベル群とは、演算がcommutativeな群のことです。

　ちょっと話を脱線します。普通演算子はcommutativeな気がします。commutativeじゃない群（アーベル群じゃない群）ってどういうのがあるんでしょうか？

　"-"はcommutativeじゃありません。整数集合と"-"は群を成すでしょうか？演算は集合に対してclosed、単位元は存在しません。n - 0 = nですが、0 - n = -nとなってしまうので演算-に対する単位元は存在しません。んー、これは困った。除算についても同様の議論で、群になりません。

　行列の演算はどうでしょうか？行列の掛け算はcommutativeじゃないです。正方行列と演算*は群をなすでしょうか？演算はclosedです。単位元は単位行列です。行列の積はassociativeです。逆元の存在はややこしい。行列式が0だと逆行列が存在しないのでダメでは・・・？ぐぬぬ。。ということで集合の設定を変えます。

「正則行列集合と演算子*は群を成すか？」正則行列同士の積は正則行列になります。ということで、演算は集合に対してclosed。単位元は単位行列。正則行列なので、逆行列が存在し、これが逆元になります。行列の積はassociative。よってこれは群です。しかし、行列の積はcommutativeじゃないので、これはアーベル群ではありません。出ました！これが群だけどアーベル群じゃない例ですね。

　話を元に戻します。環の話です。整数集合と+, *は環をなすか？まず、整数集合と+はアーベル群を成します。*はcommutativeです。*は+に対してdistributiveです。ということで、これは環ですね。こうやってみると、環は演算子addについては厳しい制約を課しますが、mulについては緩いです。

　

　では、有限集合の環を考えてみます。群のところでみたように、法3の世界でその剰余類の完全代表系と加算+は群をなしました。これに乗算*を加えると、これらは環をなすでしょうか？まず、{0, 1, 2}と+はアーベル群をなします。*はcommutativeで、+に対してdistributiveです。よってこれは環です。

field

　最後、体です。定義によると、体は環です。さらに、体では、演算addに対する単位元以外の要素集合とmulが群をなすことを要求します。環でゆるゆるだったmulに対する条件を厳しくしたものが体であるといえます。

　無限集合の体を考えてみます。整数集合と+, *は環でした。では、これは体でしょうか？つまり、0以外の整数と*は群を成すか？答えはNoです。逆元1 / nが整数になるとは限らないからです。よって、整数集合と+, *は環ですが、体ではありません。

　では、実数の集合と+, *を考えてみましょう。実数集合と+はアーベル群です。また、*はcommutative、+に対してdistributiveなので、これは環です。では、これは体でしょうか？+の単位元0以外の実数集合と*は群を成すでしょうか？これは群のところで議論したように、答えはYesです。よって、実数集合と+, *は体です。

　いよいよ終盤戦です。有限集合の体を考えてみましょう。法3の下で、{0, 1, 2}, *, +は環でした。これは体でしょうか？{1, 2}は法3の下で*に対して群をなすでしょうか？まず、演算が集合に対してclosedか否か。{1, 2}から任意の2つの要素をとって*を適用しても(mod 3)で0にはなりません。よってclosedです。単位元は1で、すべての要素に対する逆元も存在します。また、*はassociativeです。よって、これは体であるといえます。

　どうやら、法の世界での体には面白い法則があるようです。今度は法4の下で同様の議論をしてみます。まず、{0, 1, 2, 3}と+について考えます。以下の表に演算+に対する結果をまとめます。

演算は集合に対してclosedで、単位元0を集合内にもっています。また、表から明らかなようにすべての要素が逆元をもっています。+はassociativeかつ、commutativeです。よって、これはアーベル群です。

+	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

　

　では、{0,1,2,3}, +, *は環でしょうか？*はassociativeかつ+に対してdistributiveです。よってこれは環です。ここまでは法3のときと同じです。

　それでは、{0, 1, 2, 3}, +, *は体でしょうか？つまり、{1,2,3}, *は群でしょうか？法4のもとでの乗算の結果を表に書いてみます。

*	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

　

　対象となる集合は{1,2,3}なので、0のところは一応書きましたが無視してください。ここで、1の行と3の行は、2の行と違っています。よく見てください。1の行は、(0,1,2,3)となっていて、0-3までの数字がすべて出て来ます。3の行も(0,3,2,1)となっていて同様です。しかし、2の行は、(0,2,0,2)となっていて、{1,3}が出てきません。これは法の4と2が共通因数を持っているからです。これが体とどう関係があるのか見てみます。

　{1, 2, 3}と*が群をなすか？まず、演算がclosedになっていません。2*2 = 0 (mod 4)なので、集合{1,2,3}に対して閉じていません。単位元はあります。1です。associativityもOKです。逆元はどうでしょう？2に対する逆元はありません。これは、2と4が互いに素ではないためです。

　

　なぜaとbが互いに素でない場合、ax = 1 (mod b)となるようなxは存在しないのでしょうか？これは、目盛りがb個ついている時計を考えれば分かります。この時計の針を毎回a目盛りずつ進めると、どんなにまわしてもgcd(a, b)単位でしか針はまわらないのは明らかです。よってgcd(a, b) = 1出ない限り、ax = 1 (mod b)となるようなxは存在しません。

　ということで、{0, 1, 2, 3}と+, *は環ですが、体ではありません。上記の逆元の存在の理論から、一般に、法pにおける剰余類の完全代表系と+, *からなる系は、pが素数なら体になる。pが素数でなければ、環だが、体ではない。となります。おもしろいですねー。

二項関係とグラフ

"transitive disclosure"（推移閉包）について調べていたら、グラフは二項関係の宝庫だなーと思ったのでメモしておく。

例えば、グラフの頂点集合Vについて二項関係R1を頂点間に辺があると定義する。

例えば上のグラフだと、R1 = {(1,4),(1,6),(2,3), (2,4), (3,2), (3,5), (3,6), (4,1), (4,2), (4,5), (5,3), (5,4), (6,1), (6,3)}である。ここで、集合と順序対の表記の違いについて書いておく。集合は、{}で書かれる。順序対は()で書かれる。集合の場合は、要素の順序や重複は関係ない。つまり、{1,2,3}は、{3,2,1}と同じであり、{1,3,5}は、{1,1,3,3,3,5,5}と同じである。これに対しては、順序対は要素の順序、重複ともに意味がある。

さて、二項関係には特徴的な法則がいくつかある。（詳細はこちら）

• Reflexivity
• Symmetricity
• Anti-Symmetricity
• Transitivity

これらの法則は満たされる場合もあるが、満たされない場合もある。例えば、上記のR1の場合。Symmetricityが満たされる。頂点(v, w)間に枝がある場合は、頂点(w, v)間にも枝がある。無効グラフなので当然である。

次に、以下の有向グラフを考える。

頂点vからwに有向枝が存在するという二項関係をR2と定義する。R2 = {(1,2), (2,3),(3,4)}である。このR2はtransitivity（x R y ⋀ y R z →　x R z）を満たしていない。しかし、(1, 3), (2, 4), (1, 4)の3つの順序対をR2に追加すると、これはtransitivityを満たす。

このように、二項関係Rに要素を追加してある特性pが満たされるようになった場合、この拡張された集合R'をRの特性pに対する閉包と呼ぶ。但し、R'を閉包と呼ぶためには、拡張される要素集合R' - Rは最小である必要がある。

上の例だと、R2がtransitivityを満たすようにするには、最低でもV = {(1, 3), (2, 4), (1, 4)}を追加しないといけないので、R3 := R2 ∨ VはR2の推移閉包であると言える。さてこのR3は(v, w)間に有効路が存在する（v -> wに到達可能）であるという関係になっている。

プログラミング上では、R2はグラフの隣接行列で表される。R3はR2からWarshall-Floydで出すことができる。

const int N = 128;   // number of  verticies
bool conn[N][N];
void transitive_disclosure() {
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                conn[i][j] |= conn[i][k] && conn[k][j];
}

この推移閉包には、おもしろい性質がある。ある二項関係Rの推移閉包は以下のように表さる。

transitive disclosure(R) = R^1 ∨ R^2 ∨ R^3 …

ここで、R^1 = R、R^{i+1} = R^i ◦ Rです。この◦は、compositionの記号で、Haskellとかでやるfunction compositionと同様のものです。二項関係におけるcompositionはここに定義されているとおり。Warshall-Floydのアルゴリズムもよく考えるとこの性質を使っている。

約数が1000個ある最小の数は？

どこかの酔っぱらいに問題を出されたので、解いてみた。

「約数が1000個ある最小の自然数はいくつか？但し答えはintの範囲におさまる。」

答えは、810810000。あってますかね？

ある自然数nの約数の数は、nの素因数p1, p2, ..., pmを用いて

n = p1^(k1+1) * p2^(k2+1) * p3^(k3+1) *....., pm^(km+1)

と書けるので、これを使ってメモ化再帰した。

const double inf = (1e+300);
double dp[1024][1024];
bool isPrime[1<<20];
vector<int>primes;
vector<int>facs;

void init() {
    REP(i, 1<<20) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= (1<<20); i++) {
        if (!isPrime[i])
            continue;
        for (int j = i*i; j < (1<<20); j += i)
            isPrime[j] = false;
    }
    primes.clear();
    REP(i, 1<<20) if (isPrime[i]) {
        if (primes.size() > 1024)
            break;
        primes.push_back(i);
    }
}

double rec(int pw, int pr) {
    if (pw == 1)
        return 1;

    if (dp[pw][pr] > 0)
        return dp[pw][pr];

    double ret = inf;
    REP(i, facs.size()) {
        if (pw % facs[i] == 0)
            ret = min(ret, pow(primes[pr], facs[i]-1) * rec(pw/facs[i], pr+1));
    }

    return dp[pw][pr] = ret;
}

int main() {
    int n;
    cin >> n;

    init();
    FOR (i, 2, 1001) {
        if (n % i == 0)
            facs.push_back(i);
    }

    REP(i, 1024)REP(j, 1024) dp[i][j] = -1;
    cout << (int)rec(n, 0) << endl;
}

この結果は面白くて、約数の個数が素数の場合は、その数は合成数個の約数を持つ数と比べて大きな数になることを意味している。

例えば、11個の約数を持つ数。

11はこれ以上因数分解できないため、11個の約数を持つ最小の自然数は上の約数の個数の式より、

2^(10) = 1024となる。

これに対して、12 = 3 * 2 * 2と因数分解できるので、12個の約数を持つ最小の自然数は、

2^2 * 3^1 * 5^1 = 60

となる。

約数の数が1000個である最小の自然数と、約数の数が101個である最小の自然数はどちらが大きいでしょうか？

という問いを考えると、約数の個数が多い1000個の方が大きく思える。しかし実際は、

1000個の場合は、810810000。（答えがあってれば。）

101個の場合は、2^100 ≓　10^30

と101個の方がケタ違いに大きな数となる。

文字列に関するcoding tips

ちょっとしたtipsを紹介します。

1. accumulate()で文字結合
2. mapは使わない
3. 文字をint型に代入する

まず、1.番目。vectorで与えられた入力をconcatenate して新しい文字列を作成せよ。よくありますね。これをどう書くか。

vector<string> x;

void init() {
    x.push_back("acchan");
    x.push_back("yuko");
    x.push_back("yukirin");
    x.push_back("mayuyu");
}

int main() {
    init();

    string y = "";
    REP(i, x.size())
        y += x[i];

    cout << y << endl;
    return 0;
}

でもいいけど、accumulate()を使うとちょっとだけかっこよく書けます。accumulate()はdefaultでは演算子+を用いる。stringに対する+は文字の結合なのでそのまま使えます。

int main() {
    init();

    string y = accumulate(ALL(x), string());

    cout << y << endl;
    return 0;
}

次に、2.番目。文字の出現回数を数えています。char -> intへの写像なので、mapを使うのが自然に見えます。

int main() {
    string x = "riverponiiteerutoshushuheavyrotationeverydaykachusha";

    map<char, int> cnt;
    REP(i, x.size())
        cnt[x[i]]++;
}

でも、charなんて高々[0, 256)までなので、配列に入れるのもありです。C++の配列はランダムアクセスなので、こっちの方が計算量は安いです。[0, 256)と書きましたが、ASCIIコード表を見ると、実際に使われるコードは[0, 128)で十分のようです。AKBのメンバーの名前を覚える暇があったら、ASCIIコードを覚えましょう。（→自分）

int main() {
    string x = "riverponiiteerutoshushuheavyrotationeverydaykachusha";

    int cnt[128];
    memset(cnt, 0, sizeof(cnt));
    REP(i, x.size())
        cnt[x[i]]++;
}

最後に、3.番目。これは、文字をインクリメントして走査したい場合です。それぞれの数字がdigit中に何回出てくるかを標準出力に表示します。

int main() {
    string digit = "1234254723075027659279743057423953";

    for (char i = '0'; i <= '9'; i++)
        cout << count(ALL(digit), i) << endl;
}

とか、

int main() {
    string digit = "1234254723075027659279743057423953";

    REP(i, 10)
        cout << count(ALL(digit), i+'0') << endl;
}

とかやっていましたが、以下のようにできますね。プロコン界伝統の悪しきマクロで書いてますが、iはintで持っています。charではなく、intで持っていた方が何かと便利です。

int main() {
    string digit = "1234254723075027659279743057423953";

    FOR (i, '0', '9'+1)
        cout << count(ALL(digit), i) << endl;
}

ベイズ推定と最尤推定の違い

ベイズ推定と、最尤推定の違いについて。

まず、両者の違いを説明する前に、確率で使われる用語の説明を少しします。

観測データ: 実際に観測された事象のことです。

例）サイコロを振ったら1が出たとか、5が出たとか。

仮説: 観測されたデータが満たしていたであろうと考えられる条件。

例）投げたサイコロは、すべての目がでる確率が均等だった。

実は偶数の目が出やすいように細工されたサイコロだった。

以下では、観測データをD, 仮説をHi, i = 1,2,..., m.とおきます。

尤度: ある仮定Hiのもとで、事象Dが起こる確率です。条件付き確率で、P(D | Hi)と書きます。

　　　例）すべての目が均等に出るサイコロを振って6が出る確率。

偶数の方がでやすいように細工されたサイコロを振って6が出る確率。など。

事後確率：　ある事象Dが発生した場合、仮説Hiが正しい確率。条件付き確率で、P(Hi | D)と書きます。

例）サイコロを振って6がでたとき、そのサイコロは均等に目がでるサイコロであった確率。

サイコロを振って6がでたとき、そのサイコロは偶数が出やすいようにいかさまされたサイコロであった確率。

この尤度と事後確率の違いは大事です。

最尤推定は、尤度を最大化する仮説を選択する推定法です。これに対して、ベイズ推定は、事後確率を最大化する仮説を選択する推定法です。

ベイズの定理より、

P(Hi | D) = P(D | Hi) * P(Hi) / P(D)

が成り立ちます。この式から、事後確率とは、尤度に事象Hiが起こる事前確率（※）をかけた値に比例することが分かります。P(H1) = P(H2) = ... = P(Hn)が成り立っている場合、 最尤推定とベイズ推定は同じ結果を返します（後半の例題で具体的に説明します。）。このP(Hi), i=1,2,..n.をどうとるかというのは難しい問題で、主観的な判断に任せるをえない場合があります。

※事前確率とは、他になんの情報もない状況で、ある事象が観測される確率のことです。これに対して、事後確率は、ある事象が観測されたことをヒントにして事前確率をより精度の高いものに修正したものであると考えることができると思います。例えば、モンティーホールとかはこのことを実証する良い例だと思います。

実際に例を見てみましょう。参考サイト2に簡単な例題があったのでそれを使います。

部屋Aと部屋Bがあります。

部屋Aには、男1人、女1人がいます。部屋Bには女が2人います。

部屋の外にいるあなたが、「おーい」と呼びかけたら、女の人の声がしました。あなたの呼びかけに答えたのはAの部屋の人？Bの部屋の人？（どちらの方が確率が高いでしょう？）

まず、最尤推定。

女の人が返事をするという事象をDとします。返事をしたのがAの部屋の人であるという仮説をHa, Bの部屋の人であるという仮説をHbとします。

それぞれの尤度は、

P(D|Ha) = 0.5

P(D|Hb) = 1

です。尤度が高いのは、仮説Hbなので、あなたの呼びかけに答えたのは、Bの部屋の人であると判断します。

すごい簡単な例ですが、おもしろいです。

何も情報が与えられなかったら、どちらの部屋の人が答えたのか分かりません。強いて答えろと言われたら、ランダムにAかBを選ぶでしょう。（この場合は、P(Ha) = P(Hb) = 0.5）

そこに、"女の人が答えた"という事象が観測され、それをヒントにすることで、この事前確率P(Ha), P(Hb)をより正しい（尤もらしい）方向に修正できたと言えます。

次に、ベイズ推定で解いてみます。

P(Ha), P(Hb), P(D|Ha), P(D|Hb)は最尤推定で出したので、P(D)を求めます。（実はP(D)はiによらない値なので、本来求めなくてもいいです。が、ここでは計算しておきます。）

P(D) = P(D|Ha) * P(Ha) + P(D|Hb) * P(Hb) = 0.5*0.5 + 1*0.5 = 0.75

この場合は4人の人それぞれが返事をする確率が一様なので、部屋のことは忘れて単純に4人いてそのうち3人が女性なので、3/4と出してもいいです。

Ha, Hbの事後確率を求めます。

P(Ha) = P(D|Ha) * P(Ha) / P(D) = 0.5 * 0.5 / 0.75 = 1/3

P(Hb) = P(D|Hb) * P(Hb) / P(D) = 1 * 0.5 / 0.75 = 2/3

で、ベイズ推定の場合も仮説Hbを解に選択します。

上の式を見て分かるように、P(D)はどちらにもかかってるfactorなので、無視できます。また、P(Ha) = P(Hb) = 0.5なので、このfactorも無視できます。

すると、事後確率と尤度が同じ（スケールが違うだけ）になっています。これ（事前確率が一様であること）が、最尤推定とベイズ推定の結果が同じになる条件です。

じゃあ、事前確率が一様じゃないときは？やってみましょう。

Aの部屋の人が答える確率と、Bの部屋の人が答える確率を無意識のうちに0.5ずつとしていましたが、以下の条件が与えられたらどうでしょう？

Aの部屋の2人はとても社交的である。Bの部屋の2人は内向的で部屋に引きこもりがちで居留守をよく使うらしい。

この条件をもとに、以下のような事前確率を設定します。（このように事前確率の設定は主観的なものになりがちです。このことが最尤派とベイズ派の論争の中心となってるようです。[参考サイト1]）

P(Ha) = 0.7

P(Hb) = 0.3

最尤推定は、事前確率を判断材料に用いないので前回の結果と変わりません。

ベイズ推定の場合は、結果が変わります。

P(D) = P(D|Ha) * P(Ha) + P(D|Hb) * P(Hb) = 0.5*0.7 + 1*0.3 = 0.65

P(Ha) = P(D|Ha) * P(Ha) / P(D) = 0.5 * 0.7 / 0.65 = 0.54

P(Hb) = P(D|Hb) * P(Hb) / P(D) = 1 * 0.3 / 0.65 = 0.46

で、P(Ha)の方が大きいので、Aの部屋の人が返事をしたと判断します。このように、事前確率が一様でない場合は、最尤推定とベイズ推定の結果は異なります。ベイズ推定の方がより多くの情報を活かした推定となっています。しかし、今回のように主観的な確率を用いた場合は、その結果が本当に客観的に確かなのか疑問が残ります。また、事前確率が統計的に求められる場合にも、このfactorが問題を引き起こす場合もあるようです[参考サイト3]。

ちょっと長いpostになってしまいましたが、読んでいただきありがとうございます。間違ってる場所がありましたら、ご指摘いただけると助かります。

参考サイト：

1. 「ベイズ統計入門＆モンテカルロ法と逆問題」

2. 「事後確率と尤度――系統推定における最尤法とベイズ法の最前線」

3. 「ベイズ推定　臨床検査における偽陽性」

C言語の4つのメモリー領域

ちょっと気になることがあったので勉強しなおした。プロコンやってる人はヒープか、スタックなのかはよく気にすると思います。ヒープはメモリ領域が広く、スタックはメモリ領域が狭いからです。スタックのメモリオーバーしてクラッシュするとかよくあります。

　例えば、1000*1000のint[]配列をmain()関数内で宣言すると、プログラム実行時にクラッシュします。そこで、この1000*1000の配列を外部変数にしてあげます。すると、プログラムはクラッシュしません。

これは、メモリ領域が広いヒープに格納されているからだと思っていましたが、グローバル変数が格納される場所は”静的領域”と呼ばれるそうです。

ということで、勉強したことを書きます。

まず、Cには4つの記憶領域があります。

• プログラム領域
• 静的領域
• ヒープ
• スタック

　プログラム領域は、プログラム（マシン語）が格納される場所です。「なんじゃそりゃ？」と思われる方もいるかと思いますが、ノイマン型コンピュータでは、プログラム内蔵方式でプログラムが実行されます。つまり、命令自体もメモリに格納されていて、プログラムカウンタという現在実行している命令が格納されているアドレスを保持するものが参照している場所の命令が実行されます。

メモリに命令を書くと言う感覚は分かりにくいですが、アセンブリをやってみると分かります。

　次に、静的領域です。静的領域は、その名のとおりプログラムの実行中に変化しない変数を格納する領域です。具体的には、グローバル変数やstatic変数が置かれます。この静的領域の大きさはプログラム実行時に確保され固定サイズです。（プログラム実行中にサイズが大きくなったり、小さくなったりしません。）

　そして、ヒープ。ここは、new とか malloc() とかで動的確保するところです。ヒープのサイズはプログラム実行中も変化します。ただし、一般に１つのアプリケーションが使用できるメモリは2GBまでですので、これ以上のサイズのメモリを確保することは普通はできません。

　最後に、スタック。これは局所変数が置かれるところです。スタックのサイズは固定です。このポストの冒頭で書いたように大きなメモリをスタック上に確保すると、すぐにクラッシュします。また、一般にスタックのメモリは大きい方から小さいほうに伸びます。逆にヒープの場合は、小さい方から大きいほうに伸びます。具体的にいうと、スタックの場合は、関数内でint x, int yを宣言した場合、後に宣言したyの方が若いアドレスを持っています。

　んー、ただこれはC言語の構造上のメモリ分類であって、それが物理的にハードウェア上でどのように実現されているかというところまで抑えないと、なんか本質を理解してないような気がする。。

でも、少なくとも上の言葉の分類を知っていれば、技術者同士のコミュニケーションが円滑に進みます。そういう意味では、言葉を覚えるというのは大事ですね。

P2P通信NAT超え調査メモ

前回、Javaでソケット通信をして遊んだ。

簡単なP2Pチャット（片方のノードがグローバルIPを持っている OR LAN内での使用限定）を作ってみたり、接続したリモートPCを遠隔操作して遊んだりしたけど、やはりNATを超えたい衝動が抑えられないので、ちょっと勉強してみた。

調べた感じだと、たぶん自分で実装できそう。

今後のためにメモしておく。

[リンク集]

NATの仕組み、パケットのヘッダデータ書き換え

http://www.n-study.com/network/nat.htm

IPマスカレード(NAPT)

http://www.asi.co.jp/techinfo/unix/nat.html

NATトラバース(STUN)

http://www.itmedia.co.jp/enterprise/articles/0505/30/news070_3.html

ルータのタイプいろいろ

http://www.skame.nu/P2Pmeeting/0409sunouchi.pdf

Full Cone 開いたポートに送られるパケットは送信元がどこでも受け取る

Restricted Cone 送ったことのあるIPアドレスから送られるパケットのみ受け取る

Port Restricted Cone 送ったことのあるIPアドレス/ポートから送られてくるパケットのみ受け取る

Symmetric 最初に送った宛先以外からは受け取らない （同一ソケットから別の宛先に送った場合は、ルータに別のポートがマップされる）

[考えたこと]

P2PでNATの奥の端末同士が通信している間も、STUNとの通信はオープンになっている？

一度、STUNサーバーにつなげば、通信したい相手側のルーターのglobal IP、portが分かるので、

そこに捨てパケットをなげてやる。これで、次回からは通信可能となる。

-> Restricted Cone、Port Restricted ConeでもNAT超えられる。

P2P間で接続ができたら、その時点でSTUNサーバーとのコネクションはクローズしてもいいように思える。

開けたままだと、通信の内容がSTUNサーバーにも漏れてしまうことになりそうなので、

プライバシーの問題からおそらくクローズするの妥当だろう。この辺は実験して確認する。symmetricでは、NAT traverseは無理。