計算機とその周辺: What I Talk About When I Talk About Computers: 8月 2008

2008年8月31日日曜日

【シプサ】5 帰着可能性

毎日、ちょこちょこ読んで慣れを進めてきた。そろそろいけるかな???

「Turing機械で解決可能な問題のいくつかの例を示して」
- これ、なんだっけ?
- おそらく、「問題を言語で表現できて、その言語を判定するためのTuring機械を構成できる」ということだろう。
- そして、「判定可能なアルゴリズムが存在する」ということだろう。
「計算的に解決不可能な問題の一例としてA[TM]を与えた」
- これ、なんだっけ、、、
- A[TM]って何だっけ。
- A[TM]は、言語だ。
- A[TM]={<M,w>|MはTMであり、Mはwを受理する}
- ああ、ここでは「問題の一例としてA[TM]を与えた」と略記しているが、よりくわしくは、「問題の一例として"A[TM]が判定可能かどうか"というものを与えた」ということかな。
- で、これは対角線論法をつかって、判定不可能であることを確認したのだった。
- 結果、ある入力wについて、すべてのTuring機械において受理か拒否かを判定するようなスーパーなアルゴリズムは原理的に存在しない、ということがわかったのだった。
- その肝は、停止するかどうかの判定が不可能なことにあった。
辞書をひくと、帰着の訳にreduceは無いし、reduce (reduction)の訳に帰着は無い。reduceには、減る|小さくなるというニュアンスがあるが、帰着にはないようだ。まあ、いいや。
ここで言う帰着(reduce)というのは、おそらく、判定可能性の観点にて、複数の問題を関連づけられる、ということかな。
で、「AをBに帰着できる」とは「Bが判定可能なら、Aも判定可能」ということ。よってAがBより難しいということはないから、「Aが判定不可能なら、Bも判定不可能」となる。
「問題が判定不可能であることを証明するために我々がとる方法は、すでに判定不可能であることが知られている他のある問題を、その問題に帰着できることを示すことである。」
- これっていわゆる証明問題をとくというときにやってることだよね。
- あと、数学の中での論理の展開ってすべてこういうことではないか。
5.1 言語理論における判定不可能問題
ある「言語」のことを、「その言語が判定可能かどうかという問題」と同一視する記述が散見される。そういう慣習なのかな。
停止問題：HALT[TM] = {<M, w> | MはTMであり、Mは入力wに対して停止する}
とか。
「HALT[TM]は判定不可能である」
- HALT[TM]を判定するTM Rが存在する、とする。
- すると、A[TM]を判定するTM Sを、TM Rを用いて構成できる。
- これは、「A[TM]がHALT[TM]に帰着できる」ということだろう。
- すなわち、HALT[TM]が判定可能ならA[TM]も判定可能ということ。別の言葉でいうと、A[TM]がHALT[TM]よりも難しいということはなく、「A[TM]が判定不可能なら、HALT[TM]も判定不可能」ということ。
- ところで、A[TM]は判定不可能であった。よってHALT[TM]も判定不可能。
- これは、いままでの証明の言い方では「背理法」を使ったということである。
- そうか、逆に言うと、背理法を整備したのが帰着可能性ということかも。
E[TM] = {<M>|MはTMであり、L(M)=空集合}
「E[TM]は判定不可能である」
- E[TM]って何だ? そうか、「どんな入力文字列であっても拒否するTMの表現の集合」だ。
- で、E[TM]とA[TM]は関係している。E[TM]用のTM RをつかってA[TM]用のTM Sを構成できるからだ。このことはちょっと工夫するだけ。割愛。
- 帰着の論理からE[TM]は判定不可能となる。
REGULAR[TM] = {<M>|MはTMであり、L(M)は正規言語}
「REGULAR[TM]は判定不可能である」
- M,wに対して、Mがwを受理するときのみ正規言語を認識するTM M2をMをつかってつくれればよい。
- M2にて、Σ={0,1}とする。
- M2は入力文字列が(0^n)(1^n)のときは受理する。
- M2は入力文字列が前項の形式以外のときは、"Mを入力wに対して動かして、Mがwを受理する"ならば、全部受理する。
- すると、Mがwを受理するときは、(0^n)(1^n)含めて、M2はなんでもかんでも受理する。すなわちΣ*を受理する。これは正規言語である。
- そして、Mがwを受理しないときは、(0^n)(1^n)しかM2が受理しないので、非正規言語に落ち込んでしまう。
- この<M2>をRにかければ、M2が正規か非正規が判定できる。
- それはMがwに受理するかが判定できるということ。
Riceの定理： Turing機械によって認識される言語の任意の性質の検査は判定不可能である。
なるほど。直感的には分かる。
EQ[TM] = {<M1, M2>|M1とM2はTMであり、L(M1)=L(M2)}
「EQ[TM]は判定不可能である。」
- これは簡単。

あせらず、とりあえずここまで。次回は、計算履歴を用いた帰着から。こつこつ。

【例解UNIX】Cの復習(1)：マニュアルの読み方、エラー処理、構造体、共用体

さあ、こつこつ。

この本は、POSIX準拠であり、記載ソースはLinuxとOSXにて動作確認したようだ。とりあえずOSX上で実習していくことにする。困ることがあったらUbuntuに変更することにする。
と、初めた途端に、nmによって表示される内容が本とOSXとでは違いすぎる。やはり本はLinuxが基本なのだ。そこで、UbuntuとOSXを併用して適宜使いわけることにする。
そうか、多値的なことを、Cでは(UNIXでは)外部変数というかグローバル変数に設定して実現するのか。(errno, perror)
この本は、関数をrmdir ("hoge")というように"("の前に空白を入れる習慣みたい。
う、演習1.8、shell上ではBus errorになるケースがあるのだが、同じケースについてGDBではBus errorにならない。。。こういうこともあるのだな。。。
「Cのプログラムはあたかもexit(main(argc, argv))が実行されたかのように起動される」そうだったのか。
cf. : confer | 比較せよ、参照せよ。

うむ。やっぱりC言語自体を学ぶのと、とある環境におけるC言語の利用を学ぶのは、ずいぶん違う。しかしそこそこC言語を訓練してきたので、なんとか対応はできていると思う。しかしプログラミングの訓練にはえらい時間がかかる。やはりどこか学校に行ったほうがいいかもしれない。。。

次回は章末問題。

2008年8月28日木曜日

コンパイラの本をざっとみてみた。
シプサとかぶっている部分があるし、読むのはいけると思う。だけど、シプサが終わってからにしようと思う。
というのは、シプサというか計算理論の基礎的な部分というかをひとかたまりとして理解しちゃったほうがいいな、と感じたからだ。かぶりが多すぎそう、ということかもしれない。

あと、Unix上の「使える」プログラムを早く書きたい、というかOSのAPIをたたいてみたい、というか、なんというか、少しでも早く実践的なプログラムを書けるようになりたい、という気持があるからだ。

なので、UNIXプログラミングをやることにする。
コンパイラはシプサの後続としてやろうと思う。

【C算法】第6章ソート (その8)

週の前半は、、、と毎週いっている。なんとかせねば。なんとか生きて乗り切った、という感じ。
さて、木構造が終わったので、6-8 ヒープソート。。。


順序木　　：兄弟の間に順序関係を有する木。
無順序木　：兄弟の間に順序関係を有しない木。

２進木　　：度数がたかだか2の木。
２分木　　：兄弟に左右の区別がある2進木。

完全２分木：根から下方へむかって、同一レベルでは左から順に詰められている2分木
２分探索木：ノードの値とくらべて、左部分木の値は小さく、右部分木の値は大きい。
ヒープ　　：親の値が子の値以上になっている完全2分木。兄弟の大小関係は任意。
半順序木　：ヒープの別名。

完全２分木に配列の要素をわりあてたときの様相。


a[i]の親はa[(i - 1) / 2]
a[i]の左の子はa[i * 2 + 1]
a[i]の右の子はa[i * 2 + 2]

なんで？？

ためす。


1の親は、(1 - 1)/2 = 0
1の左の子は、1 * 2 + 1 =3
1の右の子は、1 * 2 + 2 =4
2の親は、(2 - 1)/2 = 0
2の左の子は、2 * 2 + 1 =5
2の右の子は、2 * 2 + 2 =6
3の親は、(3 - 1)/2 = 1
3の左の子は、3 * 2 + 1 =7
3の右の子は、3 * 2 + 2 =8
4の親は、(4 - 1)/2 = 1
4の左の子は、4 * 2 + 1 =9
4の右の子は、4 * 2 + 2 =10

たしかにそうなっている。なんでこうなるの?

まず、heapを階層毎にグループにわけると、
{{0},{1,2},{3,4,5,6},{7,8,9,10,11,12,13,14},...}
となる。法則性はある。。。かんがえる。。。
a[n]の子まで添字をふるには、まず、a[n]の階層の残りのノードと、既存のノード*2だけノードを処理する必要がある。
ところで、木の左端の要素の系列は階層で上から下にならべると、a[0],a[1],a[3],a[7],a[15],...となる。これは(2^n) - 1である(n = 0,1,2,...)。
一方各階層のノード数は、2^n (n=0,1,2,...)である。
すると、a[(2^n) - 1]の子供に辿りつく前に添字をふるべきノードは同じ階層の残りだから、(2^n)-1個ある。ゆえに左端のノードについてはa[i]の子のノードがa[i*2 + (1 or 2)]というのはなりたっている。
つぎに2^n個の階層のノードで、(2^n)-1から数えてたどりつくまでにp個のノードを経るような(p=[0,(2^n)-1])ノードに着目しよう。すなわち、(2^n)-1+pという添字のノードだ。
さて子のノードに辿りつくまでに添字をふるべきノードの数は、同じ階層で、(2^n)-p個ある。ひとつしたの階層でもふるべきであり、同じ階層でその対象となるのは、p個だから、2*p個の添字をふる。よって、ふられる添字は、(2^n) - p + 2*p = (2^n)+p。
さて、親の添字は、(2^n)-1+pであり、子の一歩のノードの添字は、(2^n)+p-2+(2^n)+p=2((2^n)-1+p)だから、これもa[i]の子がa[i*2 + ( 1 or 2)]というのがなりたつ。■
これで親から子はわかった。
子から親は、親から子を逆転させればOK。
これで、heapというデータ構造を配列で実現できることがわかった。
あとはちょいちょい。

おお！ついに「新版C言語によるアルゴリズムとデータ構造」を読了した！
これで、

「例解UNIXプログラミング教室」
「アルゴリズムC」
「新コンピュータサイエンス講座コンパイラ」
「Operationg Systems Design and Implementation 3rd Ed.」

のどれでも手をつけられるようになった。
どれからいこうかなぁ。シプサとの関連で、コンパイラにしとこうかな。

2008年8月24日日曜日

【C算法】第10章木構造

だんだん終局が近づいてきた。

n進木：ノードの度数がたかだかnの木。
2進木：ノードの度数がたかだか2の木。
2分木：ノードの度数がたかだか2であり、子に左右の区別がある木。
2分探索木：キー値について、どのノードにおいても、それの左部分木のノードは小さく、それの右部分木のノードは大きい2分木。
2分探索木を深さ優先探索して通りがけ順でみると、キー値の昇順でノードが得られる。

いまさらながら、2分探索木はおなじメンツでも違う構成があることに気付いた。


　　６
　／　＼
２　　　７
　＼
　　３

　　　　６
　　　／　＼
　　３　　　７
　／　
２

完全2分木
- 最下層以外は全て「詰まって」いる。
- 最下層は、左側から詰めていく。
- 根から下流へ、各層を左から右へと添字をふっていくと、配列の添字に対応できる。
```
　　　　０
　　　／　＼
　　１　　　２
　／　＼
３　　　４
```

ん? list10-2で


else if (cond < 0)
  SearchNode(p->left, x);
else 
  SearchNode(p->right, x);

は、次の間違いでは?


else if (cond < 0)
  return (SearchNode(p->left, x));
else 
  return (SearchNode(p->right, x));

最後のほうがぐだぐだになったが木構造がおわった。
次回は6-8 ヒープソート。

【Linux入門】Chapter 10 マニュアル表示とコマンド調査

こつこつ。

whereis, aproposをしらんかった。

この章は短いので、さくっとおわった。

【シプサ】4 判定可能性 (その5)

こつこつ。

演習を終了。
この章は演習が軽かった。その分、問題がたくさんあるようだ。将来、問題をやらないといかんかも。

次回は帰着可能性。あせらず、地道にいこう。

2008年8月23日土曜日

【C算法】第8章線形リスト (その2)

こつこつ。

演習9-1。そうか、enumの要素と関数名も衝突するんだ。
ちょっとだけ、日本語を読み書きするようにC言語を読み書きする感覚がでてきた。ちょっとだけ。
ポインタで書かれたものを頭の中で追ったり頭の中でいじくりまわしたりするのが楽しくなってきた。

おお、線形リストがおわった。次回は「木構造」。

2008年8月22日金曜日

【Linux入門】Chapter 9 ファイルのアクセス制御

ubuntuでは、デフォルトのパーミションは、-rw-rw-r-ではなく-rw-r--r--だった。umaskが0022だった。
sticky: 粘着性のある

こつこつ。次回は、「マニュアル表示とコマンド調査」。

【C算法】第8章線形リスト

シプサでだいぶエネルギーを使ってしまった。このままだと徹夜で出勤なのだが、ちょっとだけ。

list0910までの写経をした。
線形リスト自体は「実践編」で一度やったので無問題。

こつこつ。

【シプサ】4 判定可能性 (その4)

こつこつ。4.2停止問題を丁寧に。

「アルゴリズム的に解決不可能な問題がある」
- うーん。ここで「アルゴリズム的に解決不可能な問題がある」という文章自体何言ってるんだかわからない。
- この文章の説明も、本節で実施するのだろうと考えて先に進む。
解決不可能な問題の一例。
- 2つのものがある。計算機プログラムPと、その仕様書S。
- この2つを入力として動くプログラムUをつくりたい。その仕様は、S通りにPが動作することを検証する、ということ。
- 実は、このプログラムUはつくることができない。
とすると、「アルゴリズム的に解決不可能な問題」というのは、アルゴリズムが存在できない問題、ということかな。
A[TM] = {<M,w> | MはTMであり、Mはwを受理する} なるA[TM]という言語は、判定不可能である。
- まず「言語Aは判定可能である」とは、「言語Aについて判定可能なTuring機械が構成できる」ということであり、これは「任意の入力について、それが言語Aに属する場合は受理し、そうでない場合は拒否するTuring機械を構成できる」ということであり、それは「言語Aを判定可能なアルゴリズムが存在する」ということである。
- 「言語Aは判定不可能である」ということは、「言語Aを判定可能なアルゴリズムは存在しない」ということである。
- 次にここでの言語Aとは何か。
- ある文字列wについて、それを受理する(認識可能)TMの表現文字列(含むwの表現)を集めた言語のことだろう。すると、「wを受理する」ということの述語集合のようなものである。
- では、その述語集合たる言語が判定可能であるとはどういうことか。
- その述語集合を判定可能なアルゴリズムが存在する、ということである。
- それはどういうことか?
- 例えば、どのようなwと、どのようなTMに対しても、それらの組み合わせが受理するか拒否するかを判定するようなアルゴリズムが存在する、ということである。
- こう書いてみると、そりゃ無理だろう、と思う。。。
- すると判定不可能ということは、
- 「どのようなwと、どのようなTMに対しても、それらの組み合わせが受理するか拒否するかを判定するようなアルゴリズム」は存在しない。
- よくわからないのは、何にでも通用する全知全能なスーパーアルゴリズムが存在しない、ということをいっているのか、どのようなwとどのようなTMの特定の組み合わせについても、それをアルゴリズムで判定することはできない、といっているのかだ。
- ああ、わかった。正規言語は判定可能なのだから、前者ということだ。
- ところで、「MはTMであり、Mはwを受理する」ってどういうことだっけ?
- wは何らかの対象を文字列で表現したものであった。通常は、それに対して「何か」を計算というか「何か」を検証するためにTMを構成する。その計算の結果として、受理したり拒否したりループしたりする。
- なので、「MはTMであり、Mはwを受理する」というTMを集める、というのはかなり乱暴な話だね。静的な考えというか。集合論的ではある。
「...まず、A[TM]がTuring認識可能であることを確認しよう」。了解。
- 認識可能って何だっけ?
- 対象言語の文字列はいずれにせよ受理になるということだけは保証されているということだ。よって、処理にステップ数がかかっているときに、それがループしているのか、それが受理になるのか、拒否になるのかはわからない、ということ。
- ということはA[TM]が認識可能、ということは、とあるTMがwを受理するなら、計算を続けていればいずれは受理となるアルゴリズムは存在する、ということ。
- さて、A[TM]用のTMを作ってみよう。
  - U = 「入力<M,w>に対して、(ただし、MはTM、wは文字列)：
    1. 入力wに対してMをシミュレートする。
    2. Mが受理状態に入るならば受理し、Mが拒否状態に入るならば拒否する。」
  - これを万能Turing機械という。
  - 「他の任意のTuring機械の記述を用いてその機械をシミュレートする能力がある」
- さて、これはTMをシミュレートするTMなわけで、ということは結果的な状態は、受理、拒否、ループの3つである。
で、これが判定可能であるかどうかは、ループがループであることを決定する方法があるかないか、ということに依存している。
このあるかないかのことを「停止問題」とも呼ぶ。
よって、万能Turing機械が判定可能かどうかは、停止問題のアルゴリズムが存在するかどうか、である。
停止問題が判定可能かどうかをしらべる前に、「Turing認識可能でない言語が存在する」ことを確認する。
「Turing認識可能でない言語が存在する」とはどういうことか。
- 本来、何か問題を解決しようとしたり、何かを計算しようとして、TMを使う。
- そのとき、問題を表現するための文字列があり、それを計算し、認識したり判定したりするためのTM(の仕様)がある。
- その文字列達を集合論的にながめると、文字列を要素とする集合をなしていると考えられる。それが言語である。
- これを逆に考えて、何らかのルールにしたがって文字列を作り出して言語を成し、それを扱うTMができるかどうかということも考えられる。
- このときに、常にかならずその言語を認識可能なTMを構築できることが理論的に保証されているのかどうか、ということである。
- その何らかのルールというのが、単に文字列をいろいろ生成するためのルールであるのではなく、今、計算したい問題の対象の有意な表現であったとしたら、その問題にアルゴリズムが存在するのかどうか、ということである。
- で、Turing認識可能でない言語が存在する、ということは、「アルゴリズムが存在しない問題が存在する」ということであもある。認識可能⊃判定可能なので、等価な表現ではないが。
準備として、すべてのTuring機械の集合が加算であることを示す。
- 「Turing機械Mは文字列<M>に符号化できるので、すべてのTuring機械の集合は加算である」
  - なぜいいきれる?
  - まず、Mを表現するためのアルファベットをΣとする。ひらがな、でもよいだろう。すると、Σ*は加算である。
  - なぜかというと、Σ*の要素を、長さ0、長さ1、長さ2、...という風に分類するとそれぞれの長さに属する要素は有限でしかない。よってそれらとNの一対一対応が可能である。ゆえに加算。
  - すると、Mの表現というのは、Σ*からTMの表現じゃないものを省いただけなので、加算。そりゃそうだ。
- 「つぎに、すべての言語の集合が非可算であることを示そう。」
  - すべての言語の集合って何だ?
  - 。。。わからん。進もう。
- 「すべての無限長の二進文字列の集合は非可算である」
  - これは自明でしょう。それは実数と一対一対応だから。
- LをアルファベットΣ上のすべての言語の集合とする、Lは非可算である。
  - なるほど。これが「すべての言語の集合」ということか。これはわかる。そして、特性列をつかえば、無限長二進文字列の集合とLとは一対一対応になるのがわかるので、Lは非可算。
- TMの集合は加算無限、言語の集合は非可算無限なので、言語の方がはるかに大きい。すると、これら2つの集合をつなぐ一対一対応は存在しない。
- あれ?しかし、このことからだけではTMに認識されない言語があるとはいえないんじゃないの?
- 超強力TMが存在して、非可算個の言語をひとつで認識可能だったらいいじゃん、というのがある。
- まあ、いいや、たぶんそんなことできないから。(妥協)
停止問題の判定不可能性を確認する。
- 「HをA[TM]に対する判定装置とする。」
  - HはUみたいなものだけど、Uかどうかはわからなくて、とにかくA[TM]を判定できるTMであると宣言してみる、ということ。
- すると、任意のTMたるMと任意の文字列たるwについて、
```
H(<M,w>) = 
      受理  Mがwを受理するとき
      拒否  Mがwを受理しないとき (拒否するとき、ではない！)
```
  というのは悪くない。
- このHをサブルーチンとするTMを考える。その定義は次のとおり。
- D=「入力<M>に対して：
  1. 入力<M,<M>>に対してHを動作させる。
  2. Hが出力するものの逆を出力する。すなわち、Hが受理するならば拒否し、Hが拒否するならば受理する」
- <M,<M>>をやることは自由だが、それが本来のMの機能からして意味がある(受理するにしても拒否するにしても)文字列であることは少ないように思う。
```
D(<M>) = 
      受理  Mが<M>を受理しないとき (拒否するとき、ではない！)
      拒否  Mが<M>を受理するとき
```
- さて、DもTMであるから、Dに<D>を入力することもできる。すると、
```
D(<D>) = 
      受理  Dが<D>を受理しないとき 
      拒否  Dが<D>を受理するとき
```
- これは矛盾である。ゆえにHは存在しない。
- ふむ。背理法はわかった。
- 証明のステップを振り返る。
  - Mがwを受理するときにだけ、Hは<M,w>を受理する。
  - Mが<M>を受理するときにだけ、Dは<M>を拒否する。
  - Dが<D>を受理するときにだけ、Dは<D>を拒否する。
- 表で確認する。
- 入力を<M>に限り、Hの動作を表にする。
- Hの前にUを表にする。
```
　　　＜Ｍ１＞　＜Ｍ２＞　＜Ｍ３＞　＜Ｍ４＞　．．．
Ｍ１　　受理　　　　　　　　受理
Ｍ２　　受理　　　受理　　　受理　　　受理
Ｍ３　　
Ｍ４　　受理　　　受理
．
．
．
```
- ほいで、H。
```
　　　＜Ｍ１＞　＜Ｍ２＞　＜Ｍ３＞　＜Ｍ４＞　．．．
Ｍ１　　受理　　　拒否　　　受理　　　拒否
Ｍ２　　受理　　　受理　　　受理　　　受理
Ｍ３　　拒否　　　拒否　　　拒否　　　拒否
Ｍ４　　受理　　　受理　　　拒否　　　拒否
．
．
．
```
- するとDもTMだからこの中にいる。Dは＜Ｍ，＜Ｍ＞＞が受理するとき拒否するので、この表から＜Ｄ，＜Ｍ＞＞を算出していく、
```
　　　＜Ｍ１＞　＜Ｍ２＞　＜Ｍ３＞　＜Ｍ４＞　．．．
Ｍ１　＊受理＊　　拒否　　　受理　　　拒否
Ｍ２　　受理　　＊受理＊　　受理　　　受理
Ｍ３　　拒否　　　拒否　　＊拒否＊　　拒否
Ｍ４　　受理　　　受理　　　拒否　　＊拒否＊
．
．
．
Ｄ　　　拒否　　　拒否　　　受理　　　受理
．
．
．
```
- すると入力が＜Ｄ＞のときに困ってしまう。
```
　　　＜Ｍ１＞　＜Ｍ２＞　＜Ｍ３＞　＜Ｍ４＞　．．．＜Ｄ＞．．．
Ｍ１　＊受理＊　　拒否　　　受理　　　拒否　　　　　　何か
Ｍ２　　受理　　＊受理＊　　受理　　　受理　　　　　　何か
Ｍ３　　拒否　　　拒否　　＊拒否＊　　拒否　　　　　　何か
Ｍ４　　受理　　　受理　　　拒否　　＊拒否＊　　　　　何か
．
．
．
Ｄ　　　拒否　　　拒否　　　受理　　　受理　　　　　　？
．
．
．
```
- どう困るかというと、？のところは、それ自身の否定でなければならなくて、そんなものは存在しないから困るということ。
- これにて停止問題を判定可能なTMは存在しないことがわかった。
- A[TM]は認識可能だが、判定不可能である。
- 続いて、Turing認識不可能な言語について調べる。
- 「任意の言語に対して、それがTuring認識可能かつ補Turing認識可能であるとき、かつそのときに限り、その言語は判定可能である。」
- これは簡単にわかる。
- これが了解できれば、A[TM]が判定可能でないのだから、A[TM]の補集合はTuring認識可能ではない。
この本が言っていることはわかった。
ここで述べられていること自体は面白いことだ。
でも、それが私に具体的にどう意味があるのかはまだわからない。
まずは演習をやってみて、何か感じるかだろう。その次は先々の章をやるにあたって、これが意味をもつかだろう。

結構タフだった。道のりは長い。。。
次回は演習。

2008年8月21日木曜日

【シプサ】4 判定可能性 (その3)

シプサを勉強しようとすると、実は恐怖心を感じる。疲れていて頭がうごかないんじゃないか、とか。疲れた頭でやっても無意味なんじゃないか、とか。でもちょっとずつでも進まなければ、終わらないというジレンマがある。もう少しおおらかにとりくむにはどうしたらいいか。

疲れているなぁ、というときは、前回勉強したところの本文を復唱する、というのはどうか。一度やったところだから、恐怖心はない。そして、その部分は記憶に残る度合いが大きくなる。そうすれば、新しいところに入る敷居は少しづつ低くなっていくかもしれない。そうすると新しいところに入れるチャンスは増える。今後はこの方式でいってみよう。

前回の本文と自分のメモを見返してから「文脈自由言語に関連する判定可能問題」を開始。
定理4.7で、CFGが特定の文字列を生成するかどうかが判定可能であることがわかった。
CFGについては、PDAとからめつつ、以前すでに調べている。
ここであらためてTMでとりあつかって、判定可能とわかったというのはどういうことか。なぜそんな確認をするのか。
というのは、C言語とかでCFGを取り扱おうと思ったら、CFGやPDAをやったところの知識だけでもできるはずだ。
おそらく、C言語で取り扱うかわりに、TMで取り扱っているのだ。
というは、TMはアルゴリズムの定義にでてくる人だからだ。
よって、文脈自由言語を扱うアルゴリズムの特徴をしらべたい、というときには、C言語よりもTMのほうがいい、ということなのだ。
で、実際にTMで扱ってみて、それが判定可能という事実がわかったということだ。
おそらく、TM以外にもいくつかこういうものがあるのだろう。λ算法とか。
4.2 停止問題
そうか、万能Turing機械は、プログラム格納型(内蔵型)計算機のモデルというかなんというか、なんだ。
おお！Cantorだ。これで集合への30講を事前にやっといたことが役に立つ！
なんとなくの直感なのだが、重要な性質というか内在する特質というのはメタな状況から生まれる、ような気がする。
停止問題、おもしろそうなのだが、メタ度が高い。。。
雰囲気だけおさえた。次回気合をいれて読み解く。

こつこつ。

【C算法】第8章文字列処理 (その4)

こつこつ。今回はBM法。

BM法アルゴリズムの自分なりのまとめ。
テキスト"ABCXDEZCABACABAC"かパターン"ABAC"を探索する。
- テキスト照合位置Tとパターン照合位置Pという2つの変数を使う。
- パターンの文字列長は4文字である。そこで、テキストの4文字目以降にあらわれる最初の"C"を探す。
- "C"がなければパターンは含まれていない。
- "C"があったら、テキストのその位置から前へ照合をはじめる。この例の場合は、T=7, P=3となる。TとPを減算していって、パターンの文字全てが照合して同じならば探索成功。Pのインデックスまたはポインタを返す。
- 照合が途中で失敗した場合は後続するテキスト内にパターンが存在するかどうか、探索を継続する。
  このケースだと、
```
01234567890123456
ABCXDEZCABACABAC\0
    ABAC
```
  なので、"Z"と"A"でいきなり違うので照合はストップする。ストップ時はT=6, P=2。
- ここで、最後に照合に失敗した"Z"を検討対象にする。"Z"の場合はパターンにあらわれないので、パターンの最終照合時に判明した未照合文字数3だけTを進める。T=9, P=2。
- ここでP=2のパターン文字は"A"なので、T=9以降の"A"を探す。するとT=10となる。
- 照合再開。照合はお尻から実施するので、P=3にする。あわせて、T=11とする。
う、ちょっとわかったが一般性がたりないかな。もう一度トライ。
- テキストの長さをTN、パターンの長さをPNとする。
- TN < PNならばマッチしないので終了。そうでなければ次へ。
- テキスト照合位置TPとパターン照合位置PPという2つの変数を使う。
- 初期値をTP= TN - PN, PP = PN - 1とする。
- 照合ループ：
  PPがPN - 1でなければ、適量(Kとする)を加算してPN-1とする。TP += Kとする。
  TPとPPの位置にある文字が同じならば、TPとPPとを減算して比較する。
  PP=0まで同じならば、マッチ。TPの値を返して終了する。
  PP=0になるまでに不一致が発生したなら、ループを抜ける。
- 次の照合位置を決める作業。
- まずTPの位置にある文字を見る(不一致した文字)。その文字によってTPの移動量が異なる。例えば、その文字がパターン文字列に含まれない文字ならば、TP += PP + 1だけ移動する。逆にその文字がパターン文字列に含まれるが、この照合位置では不一致であった場合もある。この場合は、その文字にあわせた移動をする。その移動の幅の計算がなぜ本のようでいいのかがわからない。。。。それは将来Knuthをやったときとかに考えるとして、今は飲みこんでおく
- さらにもう一回移動を勘案する。TP以降で現在のPPの位置の文字と一致するまでTPをインクレイメントする。一致せずTNにいたれば、一致不可能にて終了。一致した場合は、「照合ループへ」
いまいちすっきりしないが、これくらいの理解でCでの実装へ。list0814を写経、上の私の理解とは違うところがあるが、大筋はあってる。
おもうに、C言語を使いこなしている、というのは、このように自然言語でアルゴリズムを書いたり理解したりしようとしてくても、C言語のまま、それが自然言語であるがごとくアルゴリズムを書いたり読んだりできるようなことを言うのかもしれない。そういう感覚でもCを書いていってみたい。

ふー。次回はやっと線形リスト。。。

2008年8月19日火曜日

【Linux入門】Chapter 8 テキスト処理 (その4)

週の前半は業務がきつい。働かざるもの食うべからず。しかたなし。しかし仕事について少し考えないと、学習を続けられないかも。
一歩でも進まないと終わらないので、とりあえず、こつこつ。

えっと、diffです。
-uしないということはこれはedのコマンドということだったはず。すると、diffの-u無しの練習用ファイルを作るというのはedの練習用ファイルを作るということに等しいかも。
この本のこの段階では、そこまでは対象にしておらず、簡単にdiffを紹介するくらいだろう。
なので、そのレベルで練習シナリオを考えることにする。
echoもついでに。

これにて8章完了。
今日はもう体力無し。無駄なあがきはなしで、さっさと寝よう。

2008年8月18日月曜日

【C算法】第8章文字列処理 (その3)

こつこつ。今回は「8-3 文字列探索」

brute forthとあるが、brute forceの誤字と思われる。
少なからぬ時間、Cとアルゴリズムに取り組んで、自分についてわかってきたことがある。
- 数に弱い。基数と序数にかかわる計算に弱いのだ。例えば、30 - 20 = 10ということと、[20,30]に含まれる整数の個数が11個、(20,30]なら10個、(20,30)なら9個ということがどう関係しているかわかっていないのだ。だから配列を取り扱うときに、インデックスの境界での振舞いをすぐに見失う。これは訓練するしかない。
- 頭のメモリというかスタックというか何かが小さい。他人のことはわからないが、おそらく自分が漠然と予想していた自分の能力よりも遥に小さいのが現実であり、そのギャップに対処できていない。だから、アルゴリズムとその実装について考えるときに、追いきれなくて思考停止することが多い。小さいものは仕方ないから、大きくする努力とともに、小さいものでなんとかやっていく工夫が必要。
KMP法の演習をやるなかでの知見。
- 適切な情報を表示させようとprint文を設置しようとすることは、アルゴリズムの理解に有効である。
- それらprint文を#if DEBUGとかでON/OFFするようにしているのだが、Cのマクロ、見ためが汚ない。。。
- ログ出力のよい方法はあるのだろうか? 調べてみるとlog4cというものがあるようだ。使用例がみあたらない。先々調査する。

次回はBoyer-Moore法。

2008年8月17日日曜日

【Linux入門】Chapter 8 テキスト処理 (その3)

こつこつ。今回はlessから。

lvはとりあえずスキップする。日本語ファイルの表示は、nkf or iconv + less を基本としたい。その方が適用可能ホストが多いので。
とりあえず、diffの手前まで。diffは練習用ファイルを用意するのに時間がかかりそう。

【Linux入門】Chapter 8 テキスト処理 (その2)

こつこつ。

tr、けっこうゴツいな。
moreは役割を終えた、とのことなのでスキップ。

次回はless。

微積分はSpivakのCALCULUSにする

頭を鍛えるために微積分をやる。
本は、悩んだが、SpivakのCALCULUSにした。
日本語の本がよかったんだけど、

微積じゃなくて、解析だと良書がいろいろありそうだが、解析は私にはまだ無理だろう。
で、微積となると何故か気合が入った本がない。

ということで、Spivakが、

あくまで微積の範囲っぽい。
グラフの図表の多さの気合の入りよう。
問題数の多さの気合の入りよう。

であったので、泣く泣くこれに決めた。日本人なんだから、基本的なことは、日本人から日本語で学びたいと切実に思う。。。
これは、こつこつどころではなくて、こつ^8くらいでやっていく。
半年以内に第一周を終えるのを目標とする。

【シプサ】4 判定可能性 (その2)

こつこつ。

正規言語に関する判定可能問題、をみていく。
前回、導入部を丁寧に確認しておいたので、とくにひっかかりなく読み進められる。
ここにきて、一巻でオートマトンの各種性質を証明するときに、構成してみせる方法をとっていたことの価値がよくわかる。シプサ先生ありがとう！
構成してみせる、ということは、構成する手順をしめすということであり、それはアルゴリズム的であり、現にそれはTMで構成可能なアルゴリズムなのだ。だから、それらの言語について見てきたことが、ここですべてTM上のアルゴリズムの話に透過的に(自動的に?)写しかえられるのだ。で、それがTMからみて判定可能な言語をなすかどうか(それが判定可能な計算問題かどうか)が議論できる、と。

次回は、文脈自由言語に関連する判定可能問題。

【シプサ】4 判定可能性

体調が戻ってきたので、シプサを再開。

久しぶりなので、言葉や概念の定義を丁寧におってみる。
「本章の目的は、アルゴリズム的な解決可能性の限界を探求することである。」
- この文はテーマの表明かと。「アルゴリズム的な解決」が何を意味するかは定義されていない。
- なので、この章では、「アルゴリズム的な解決」の定義を与え、「その限界を探求する」、ということかな。
「アルゴリズム的に解くためには、」
- 非アルゴリズム的に解くとはどういうことだろう?
- 例えば数学の方程式の解を求める問題で、あてずっぽう(乱数)で正解になるまで数をためすとか?
- ヒューリスティック、と呼ばれていることもそうなのかな?
- ヒューリステヒックって何だ?
  - heuristic: 発見[習得]に役立つ; (自己)発見的学習の
  - いまいちわからん。Wikipediaへ。
  - Heuristic。なるほど、雰囲気はわかる。日本語の中では何なんだろう? 「発見的学習」なんて日頃使わないし。
  - 「試行錯誤」「丼勘定」「テキトー」「下手な鉄砲数打ちゃあたる」。。。ちがうなぁ、試行錯誤はheuristicの一手法にすぎないし。
  - Wikithonaryへ。heuristic。そうかギリシャ語のエウレカが語源なのね。
  - 「工夫」「善後策」「横紙破り」「徒手空拳」。。。ちがう。「裏技」、おっ裏技がいいかんじ。
  - 「見切り発車」「結果オーライ」「善処しました」「一定の成果を得た」。。。もう「裏技」でいいや。
  - しかしこんなのもある。Heuristic algorithm
  - 問題に対してアルゴリズムが立案できない状況で、なんらかの「裏技」をつかってよさ気なアルゴリズムを採用してしまう。そのアルゴリズムをHeuristic algorithmと言うようだ。
「本節では、アルゴリズムにより判定可能な言語について、いくつかの例を与える」
- 「アルゴリズムにより判定可能な言語」って何?
- アルゴリズム：とあるTuring機械の仕様
- 判定可能な言語：??? これは未定義かな。なので読み進んで説明をまつ。
「ここではオートマトンと文法に関連する言語に注力する。」
- なるほど。まずここで言っている「言語」は、相変わらず計算理論における言語であり、それはその言語で書かれていると言える文字列の全てからなる集合(巨大です)のことなんだな。
- オートマトンと文法に関連する言語、ということは、その言語の中で、正規言語や文脈自由言語のことだ。
「たとえば、文字列が文脈自由言語(CFL)の要素であるかどうかを検査するアルゴリズムを紹介する。」
- 「文字列がCFLの要素であるかどうかを検査する」というアルゴリズムを紹介する、ということ。アルゴリズムを紹介する、ということは、それを実現するTMを示す、ということであろう。
- では、「文字列がCFLの要素であるかどうかを検査する」というのは何?
- これは前章では認識機構としてのPDAの役目じゃなかったっけ?
- ということは、もったいぶって言ってるけど、PDAをTMがシミュレートできるってことを言ってるのかも。
- 後々明らかになるであろうということで先へ。
「オートマトンと文法に関連する別のある種の問題はアルゴリズムによって判定可能ではない。
- これも「アルゴリズムによって判定可能」の定義がわからんので、現時点では何いってんだかわからない。
「有限オートマトンに関連する計算問題から初めよう」
- 「有限オートマトンに関連する計算問題」って何だっけ?
- 有限オートマトンは、次のようなものだったはず。
  - 有限の状態がある。状態には開始状態と受理状態と、どちらでもない状態がある。
  - 入力文字列というものがある。入力文字列を構成する文字の全てをあらいだして、それら全部を要素とする集合をアルファベットという。
  - 入力文字列を処理する。
  - 入力文字列を処理する、とは、開始状態にあるとして、入力文字列を先頭から1文字ずつ順に処理していく、ということ。
  - ひとつずつ順に処理していく、とは、それぞれの状態で、どういう文字だったらどの状態に移動する、というルールにしたがって入力文字列を消費しつつ状態を渡りあるく、ということ。
  - このルールを遷移関数と呼ぶ。
  - 入力文字列の処理が終わった時点で、受理状態にあれば、「かの有限オートマトンは、この文字列を受理する」と言う。そうでない場合は「拒否する」と言う。
  - なので、有限オートマトンの仕様は、5個組、「Q(状態集合)、 Σ(アルファベット集合)、遷移関数、q0開始状態、F(受理状態集合)」で特定できる。
- で、有限オートマトンの「計算」って何だっけ??? わからないので一巻を見直す。
- そうか、今のべた有限オートマトンの動作定義自体が、「有限オートマトンの計算」の定義なんだ。
- では、「有限オートマトンに関連する計算問題」とは、有限オートマトンがある文字列を受理したり拒否したり、認識したり、というようなよしなし事、ということか。
「言語によりさまざまな計算問題を表現することを選んだ点に注意しよう」
- あれ? どこで選んだっけ?
- というか、ここで言う「言語」は、計算理論における言語か、いわゆる普通の意味での言語なのか???
- たぶん、次の文章(P183)のことを指していると思われる。
  「2番目は、Turing機械がヘッドを動かす方法やテープにデータを格納する方法まで記述するが、それを自然言語で記述する方法である。したがって、より高いレベルの記述だが、実装まで考慮した記述である。このレベルでは、状態や遷移関数の詳細な記述を与えない。3番目は、実装の詳細を無視して、アルゴリズムを記述するために自然な言語を用いた高レベルの記述である。」
- なので、ここの「言語により」というのは「非形式的な記述によって」ということと解釈しておく。
「たとえば、特定の決定性有限オートマトンが与えられた文字列を受理するかどうかを検査するようなDFAに対する受理問題は、言語A[DFA]として表現できる。この言語はDFAとそれが受理する文字列の組を符号化したもの全体で、
A[DFA] = {<B, w> | Bは入力文字列wを受理するDFA}
で定義される。」
- なんじゃこりゃ? これ、計算理論としての言語と、TMを記述するための言語がごっちゃになってないか???
- 考える。
- わかった。まさにごっちゃにしているのだ。メタをやってやがるのです。自分の言葉で書いて、確認する。
  - この文章、ひっくり返して読んだ方がわかりやすい。
  - まず、Bと呼ばれるあるDFAが存在するとする。Ｂが関係する問題をTMで扱いたいとする。すると、TMで扱えるのは文字列だけなので、Bを文字列で表現しなければならない。その文字列を<B>と呼ぶことにしたのだった。ところで、DFAにおける計算は入力文字列の処理であった。なので、Bが関係する問題をTMで扱うには、入力文字列もTMで扱う必要があるであろう。それも表現を考えなければならない。子細は別にして、とある入力文字列wの表現を<w>と呼ぶことにしたのだった。
  - すると、Bにある入力文字列wを計算させるということは、<B, w>という表現(=文字列)でも必要十分であろう。
  - ここまでが、自然な言語でアルゴリズムを記述する、という方の意味での言語。
  - 続けよう。するとここまでの考えでは<B,w>というのは、Bは固定だが、wはいろいろなものがありえる。で、計算した結果、認識したり(=受理したり)、認識しなかったり(=拒否したり)する。
  - すると、文字列たる<B,w>がわらわらいるのだが、それの計算結果が受理なものだけ集めて集合にしちゃえ、と考える。ここで「計算理論の言語」が出てくる。
  - で、A[B] = {<B, w> | 「DFAであるBは固定として、wはいろいろで、Bはwを認識する」というような文字列}
  - さて、ここで、wが固定でBがいろいろ、というのももちろんあり。
  - で、A[w] = {<B, w> | Bは入力文字列wを受理するDFA}
  - この集合には、wを受理するDFAがすべて含まれていることになる。
  - そして、この集合自体が計算理論における言語であって、この言語をTMで取り扱うことが可能である。どこまで取り扱えるかは別として、やろうとすることはできる。
  - それは、うまく行けば、判定可能なTMを構築できるだろう。次善としては、認識可能なTMまでかもしれない。最悪は、認識不可能であり事実上取り扱えない、ということか。
  - で、A[w]に対して、TMを構築できて、それが判定可能であるとする。ということは、任意の表現<B, w>について、それが受理するか否かがそのTMで有限のステップというか何というかで判定できるということだ。
  - ということは、どういうことかというと、これが前半の文「特定の決定性有限オートマトンが与えられた文字列を受理するかどうかを検査するようなDFAに対する受理問題は、言語A[DFA]として表現できる。」ということがわかったということ。
「同様に、他の計算問題についても、言語に対する所属を検査するという言葉で定式化できる」
- 計算理論の言語は文字列の集合であり、それを認識したり生成したりする機構をいろいろと考えて、その性質を調べたりしてきた。その際、文字列が受理するかどうかということ自体を計算の定義とした。
- すると、計算問題というのは、様々な認識機構や生成機構と入力文字列との話題になるわけだ。
- するとそれは、「とある機構と、とある入力文字列」というオブジェクトの表現として、また文字列で表現できてしまう。
- すると、計算問題というのは、機構達や入力文字列達について、かくかくしかじかが成立しますか〜ということを問うていると一般的に考えられるので、それは、それが成立する表現を集めた述語的な集合を考えることができる。で、それは文字列の集合だから言語である(ここがメタ)。なので、その言語を機構で調べることができる。
- というようなことじゃないかなぁ。
なんとなく分かってきた。
先送りしたことを確認。
- 「アルゴリズムにより判定可能な言語」
  - ああ、これはそのまんまだったんだな。
  - TMにて判定可能となる言語、のことだろう。
  - DFAが認識可能な言語が正規言語(という名で呼んでおりその性質は知れている)、PDAが認識可能な言語が文脈自由言語(という名で呼んでおりその性質は知れている)、ということに対して、TMにて判定可能な言語たちってどんなものたち? ということだろう。
- 「たとえば、文字列が文脈自由言語(CFL)の要素であるかどうかを検査するアルゴリズムを紹介する。」
  - これはまだよくわからない。
  - ただ、CFLを調べていた時点では、アルゴリズムという概念が定義されていなかったので、もちろんPDAやCFGを使ってアルゴリズム的な思考はしているわけだが、それをTMでシミュレートすることによってアルゴリズムの定義にしたがって、表現しますよ、ということだと思われる。

2ページしか進んでいない。なんと。でも、まあ面白かったからいいかな。
こつこつ。

2008年8月16日土曜日

【Linux入門】Chapter 8 テキスト処理

こつこつ。

私のtailは、+6がだめで、-n +6や--lines=+6とする必要があった。(tail (GNU coreutils) 6.10)
sortも同様。+1や-3は使えない。(sort (GNU coreutils) 6.10)
う。この章、長いので、uniqまで。

次回は、trから。

【C算法】第8章文字列処理 (その2)

今回は「文字列の比較」

日々すこしづつポインタに慣れていっている気がする。

次回は「文字列探索」。こつこつ。

【Linux入門】Chapter 7 リンクとiノード

こつこつ。

そうかシンボリックリンクというのは、それが置かれている場所からどういけばいいかを指定するんだ。
で、それがiノードに書かれる、と。
inodeの復習になった。

【C算法】第8章文字列処理

こつこつ。

literal: 文字通りの, a literal translation | 直訳; 文字で表現された, a literal error | 誤字;
list0801：何故16進数表示の制度を(CHAR_BIT + 3) / 4とするのかがわからない。
なんか、文字列になっていきなり基本に戻ったような。。。
list0805：そうか、ポインタのポインタを渡すのは、ポインタ自身を書き換えたいんだけどポインタそのものを渡したら、スコープの問題で、関数内での変更が反映されないからか。いまさら、やっと理解した。

今回は「文字列からの文字の探索」まで。次回は「文字列の比較」。

2008年8月15日金曜日

【Linux入門】Chapter 6 ディレクトリの操作

こつこつ。

う、新しい知識は無かった。。。
指の訓練としてはよかった。

【C算法】第7章集合 (その2)

今日はビットベクトル。

BsetMemNum、頭いいなぁ。こういうのを自分で発案できるようになると思えない。
list0705は、bsetlib.hにlist0704の関数のプロトタイプを書いとかないとコンパイルできなかった。gccの使い方がわるいのかな。
演習0705。BsetIsSubsetとBsetIsPropserSubsetを作成。これ、やっぱりコーディング前にどれだけアルゴリズムを確認できるかが作業本体だった。アルゴリズムをCでどう書くか考える部分よりも、そもそものアルゴリズムを考える部分が大きい。
自分の環境でintやunsigned longのサイズを確認しようとして、limits.hを見てみた。しかし、どのifマクロが効いて、結果どのUMAXなどが有効になるのかを追うのが面倒くさそう。そこで、gdb上でp sizeof(int)などとした。やはりgdbはREPL的。
演習0706の可変ビットベクトルの実装に偉い時間がかかった。教訓。
- ポインタにだんだん慣れてきたが、まだ弱い。ポインタが引数の関数に対して、呼び出しもとでオブジェクトを作ってその&を渡してあげるときに、呼び出しもとでもポインタをつくって渡しちゃったりする。それではまった。
- ひとつの関数をつくるのと、ビットベクトルのライブラリを作るように、関数群をつくるのとを比べると、関数群の設計の訓練が足りていないことがわかる。これはどうやって訓練すべきか。
gdb上で関数を再定義して、そのまま走らせられれば便利なんだけどな。できるのかな?

次は文字列処理。こつこつ。

2008年8月14日木曜日

【C算法】第7章集合

ちょっと体調悪し。

演習7-2 で二分探索を活用するところでグダグダになった。
どうしても、再帰的に考えてしまって、Cらしい書きぶりを組めない。
あきらめて、再帰でやったらすんなり書けた。Cらしいアルゴリズムは徐々に、ということにするしかないかな。
多値を使えれば関数のインターフェイスがきれいにできるところがあったが、Cでの多値のやりかたをしらないので諦めた。

こつこつ。次回は「7-3 ビットベクトルによる集合」だ。

2008年8月12日火曜日

【C算法】第6章ソート (その7)

今回はヒープソート。

heap: a heap of bricks | れんがの山; in a heap | 山のように;
ああ、だめだ。本で推奨されているように、第10章で木構造をやってから、やろう。

というわけで、度数ソート。

度数ソートを考えた人、えらい頭いいな。。。

次回は集合。こつこつ。

目標の整理 (Ver.2.1.0)

状態をアップデート。
あと、考えるための基本的な訓練、を足した。

GNU/linuxのptyアプリを書きたい。
- 「詳解UNIX」を勉強する。
  - C言語を勉強する。
    - 「明解 C言語入門編」【完了】
    - 「明解 C言語実践編」【完了】
    - 「UNIXの道具箱」★途中
  - GNU/linuxのAPIの基礎を勉強する。
    - 「例解UNIXプログラミング教室」(Cでアルゴリズムをやった後に実施)
NorvigのAIを読みたい。(Common Lispプログラミングの書きぶりを知りたい)
- アルゴリズムとデータ構造について勉強する。
  - C言語の基礎を勉強する。【完了】
  - C言語でアルゴリズムとデータ構造をやる。
    - 「C言語によるアルゴリズムとデータ構造」 ★途中
    - 「アルゴリズムC」
- Common Lispについて基本を復習する。
  - 「初めての人のためのLISP」★途中
  - 「Common Lisp入門」
  - 「Common Lisp Drill」 (Cでアルゴリズムをやった後に実施)
Common Lispを理解したい。
- コンパイルを理解する。
  - 「パタヘネ」を理解する。
    - 上巻【通読完了】
    - 下巻【通読完了】
  - 「シプサ」を理解する。
    - 「集合30講」【完了】
    - 「計算理論の基礎 1」【完了】
    - 「計算理論の基礎 2」★途中
    - 「計算理論の基礎 3」
  - コンパイラの基礎を学ぶ
    - 「新コンピュータサイエンス講座コンパイラ」
- 「Lisp In Small Peaces」を理解する。
OSの基礎知識を得る
- 「Operationg Systems Design and Implementation 3rd Ed.」
記述論理を理解する。
- 数理論理学の基礎知識をえる。
  - 一階述語論理とホーア論理を理解する。
    - 「ソフトウエア科学のための論理学」
      - 「論理学をつくる」 ★途中 (シプサの後に復帰)
  - 圏論を理解する。
    - 群・環・体の基本を知る。
    - 代数幾何の基本を知る。
    - 圏論の入門書を読む。
考えるための基本的な訓練をする。
- 微積分
- 線形代数
マネージメントを勉強する
- 統計学の基本をおさえる。
  - 「統計学入門」 ★途中
  - 数学的に準備する。
    - 位相の基本を知る。
    - ルベーグ積分を知る。
    - 確率論を知る。
生活環境の改善
- Emacs
  - 「入門GNU Emacs」【通読完了】
- Shell
  - 「詳解シェルスクリプト」【通読完了】
  - 「新Linux/Unix入門」★途中
  - 「Linuxの教科書」
体で覚えるもの
- 「解きながら覚えるC言語」
- 「入門 GNU Emacs」
- 「詳解シェルスクリプト」

【Linux入門】Chapter 5 ファイルの操作

ちょっと間があいた。

そっか、anacronには非通電時間がある場合の対処があるんだ。
この章、結構ボリュームあった。

こつこつ。

2008年8月11日月曜日

【C算法】第6章ソート (その6)

こつこつ。今日はマージソート。

私の環境では"mergesort"がstdlibにあるので衝突した。あり? stdlibにもいろいろあるのかな?
ファイル有効範囲の変数(Symbol?)にStaticをつけると、それは別のソースファイルから見えない(shadow)されるのか。

演習無しの4ページ進むのでお腹いっぱいという感じ。Cでアルゴリズムを書く練習と、Cで書かれたアルゴリズム実装を読む練習が足りてないからだろう。なので、今、練習になっていて、いっぱいいっぱいなのだろう。

【シプサ】3 CHURCH-TURINGの提唱 (その4)

なんとなく、わかったような気がするのでまとめてみる。

まず、Turing機械は、生成機構かつ認識機構であるということだ。これが有限オートマトンやプッシュダウンオートマトンとは違う。それらの生成機構は、正規表現や文脈自由文法という別のものだった。
Turing機械が生成機構である、というのはTuring機械そのまんまで成立している、というのではなくて、Turing機械のrobustnessを経てのことではある。具体的には列挙装置(Enumerator)がそれにあたる。列挙装置はTuring機械と等価である。
列挙装置というものが、私がどうもしっくりこなかった部分にこたえてくれた。
例えば乗算を判定するTuring機械があれば、正しい乗算式を全て出力する列挙装置もつくれる。これは九九の表を出力するようなものである。
また、i * jを入力として答のkを出力するような装置も考えられる。これはTuring機械と列挙装置を組み合わせて新しい装置をつくれば構成可能なことはかんたんにわかる。また、それらの組合せではなく新しい装置も考案できるが、それがTuring機械と能力として等価であるということは想像にかたくない。
なので、計算について動的なイメージをもつか静的なイメージをもつかというのは計算の本質ではなくて、それは装置のあり様によってどちらにでも変換できるものであるということだろう。
また、
- 無限のメモリをもち
- メモリの任意の位置の読み書きができて
- 一つのステップで有限の作業量のみを実行する能力をもつ
という条件をみたした機構(または装置)が判定できること、というのは、どうやら人間が自然言語で手順化して判定できることと等価であるようだ、いや、これと等価であると考えることは悪い選択肢じゃないのでそうしちゃわないか、というのがChurch-Turingの提唱なのだ。そもそも「人間が自然言語で手順化して判定できること」の定義なんて存在しなくて、直感的な理解だったんだから、定義しようとしたら、マシそうなものを選ぶしかないじゃないか、ということだろう。
生成機構としてのTuring機械の記述は、形式的記述、実装記述、高レベル記述がある。ここで高レベル記述は、Turing機械の詳細には触れず、その動作の本質と呼べるようなものを自然言語を使って記述する方式である。これが、日常的直感的なアルゴリズムに該当する。
Cでアルゴリズムを勉強しているが、そこで何をしているかというと、高レベル記述のアルゴリズムを、(Turing機械ではなく)C言語での実装記述を実施するということだ。だからやはり、アルゴリズムの高レベル記述を理解する、ということは、それを理解した上で特定の機構(Turing機械やC言語など)で実装できる能力とは関係はしているが別ものなのだ。
これらがなんとなくわかったこと。
まだしっくりこないことは、
- Turing機械のパワーは、生成機構かつ認識機構であるという、二面を集約した点にあると思う。しかし、それが様相としてどうなのかがわからない。
- Turing機械の高レベル記述での「オブジェクトとその符号化」というところが、Common Lispのreaderとかと関係があるのかないのかがよくわからない。
などなど。

こつこつ。

【シプサ】3 CHURCH-TURINGの提唱 (その3)

演習。

3.1〜3.8を実施。量が少ないのもあるが、初めて一日で終わった。ちょっと簡単なラインナップなような気もするが。
3.3の解答にちょっと納得いかない。辞書式に枝を用意する際にそのアドレスがすでに拒否されていることを判別する機構がないような気がする。なので、アドレステープを"123#123#123#123#"などとして、拒否したところをXに替えていく機構が必要ではないか。これの先頭が"XXX"になれば拒否ということで。

次は「判定可能性」だがそのまえにちょっと自分なりにまとめてみる。

Common Lispを理解するということ

もしかしたら、はずれてるかも、なんですが。

やはり、コンパイラ理論というか技術というかのある程度の理解なしに、Common Lispを理解するというかそのパワーを引き出すのは無理じゃないだろうか。
それは、関数プログラミングだとかラムダ計算だとかを理解することよりも重要に思えてきている。
Common Lispは、どうも「コンパイラのブラックボックス化をやり忘れた言語」というか「コンパイラの内臓がはみ出ちゃった言語」じゃないかなぁ。

今は、


Ｃ　－　アルゴリズム
　　　　　　　　　　＼
　　　　　　　　　　　コンパイラ　－　Common Lisp
　　　　　　　　　　／
集合論　－　計算理論

という流れを地道にやっているが、やはりこれが最短ルートなのではないか。

でも、私はよく間違えるからなぁ。。。

高校二年生レベル

いろんなことの理解に時間がかかるのは、やはり、数学的訓練が足りてないからだと思う。今、自分の数学的地力を冷静に考えてみると、おそらく高校二年くらいじゃないかと思った。というのは、行列とか微積とかの教科書をのぞいてみたら、これがさっぱりわからないからだ。。。ぞっとした。おそらくこのあたりの基本的なことをちゃんと訓練しておかないと、どんなに計算機の勉強をしても砂上の楼閣になるような気がする。近日中にこの2つの訓練(勉強ではない)を開始しよう。

【C算法】第6章ソート (その5)

ちょっと、アルゴリズムを学ぶことが、なんだかわからなくなっている。

クイックソートのアルゴリズムで、なぜ分割がうまくいくのか、がわからない。
そういう方法で分割できる、ということは覚えれば、覚えられる。
それでいいのか、どうか。
それじゃ足りないとしたら、分割がわかる、というのはどういうことなのか。
アルゴリズムを理解する、ということ自体がわからない。。。
この方法(アルゴリズム)で、分割できることの証明を構築できればいいのかなぁ。
アルゴリズムを文章で書いてみる。
- 配列aがある。大きさはN。型はint。値がすべての要素に入っている。
- pl=0, pr=N-1という2つのインデックスポインタをつくる。
- aの中から一つ要素を選ぶ。その値をxと呼ぶ。
- plはa[pl]>=xが成立する要素が見つかるまで、右側に走査する。
- prはa[pr]<=xが成立する要素が見付かるまで、左側に走査する。
- 走査がおわったとき、pl > prならば、処理完了。そこで、インデックスが0 〜 pl-1がx以下の要素のグループ、pr+1 〜 N-1がx以上のグループ、pl>pr+1ならばpr+1〜pl-1がxに等しいグループの3つに分割されている。
- 走査がおわったとき、pl <= prならば、a[pl]とa[pr]の値を交換して再度走査を開始する。
うーん。これを数学的に証明するのはちょっと面倒そうだ。場合わけが。。。
そして、それはこの本の学習でやるべきことじゃなく思えてきた。それをやるなら、Knuth本とかじゃないだろうか舞台は。
というわけで、クイックソートの数学的理解は、今はやめておこう。
直感的にはわかるんだけどねぇ。
演習6-14でひっかかる。ポインタがからむとやっぱりひっかかる。前より楽になったけど。
GDBをもうちょっと便利につかいたい。UNIXプログラミングの道具箱をみる。
- breakpointは関数名引数で設定すべし。
- 停止毎に表示確認する式はdisplayで登録すべし。
- 中身をよくみる構造体はdefineで手続化すべし。
- 繰返しGDBを起動するような状況なら、作業ディレクトリに.gdbinitをおいて、必要なものはそこに書くべし。
- または、-x fileをgdbにわたして、起動時に実行させるべし。
- または、source fileでプロンプトから読み込むべし。

てな感じ。演習6-14では、こんなんにして、sourceで読み込むことにした。


# gdbinit file for prac0614.c

display left
display right
display pivot
display pl
display pr

define hookpost-next
       set $n = 0
       while $n < nmemb
             print *((int *)base + $n)
             set $n = $n + 1
       end
end

#break quick 
#displayの設定は、そのシンボルが存在するcontextに入らないとできない。
#なので、displayを読ませるには、先にrunする必要あり。
# runする前にbreak quickする必要あり。
#よってbreak quickはプロンプトでやることにする。

バグバグな状態をGDBで調べてみる。
判明、あんまりよく考えないで書いていたからだけだった。。。うむー。
演習6-15。う、関数ポインタやNULLポインタをつかって、高階関数を作るときは、その関数の中身が再帰でかかれているよりも非再帰でかかれていたほうががかなり楽。
演習6-16。また間違えた。変数の値をswapしたいときにポインタをつかっていて、アドレスをコピーしちゃってて値をコピーしていない。

うーん。やっとクイックソートがおわった。クイックソートじゃなくて、ポインタに慣れてきた。それはそれでよし。

2008年8月10日日曜日

【シプサ】3 CHURCH-TURINGの提唱 (その2)

ちょっと考えてみる。

Turing機械というのは、認識装置または判定装置。その対象となっているのは言語。
言語は、文字列の集合である。
文字列は、解決したい課題のモノを表現している。
Turing機械は、この表現を適切に解釈するように実装する。
Turing機械は形式的には7個組で定義される。実装検討の中心はConfigurationと遷移関数だろう。
これは計算のモデルではあることはわかるが、そこにでてくるのは言語(文字列の集合)と受理するか拒否するかということである。いまひとつ一般的なプログラミング言語やプログラムとの関係がわからない。
モノとそれの文字列による表現のところは、多少関連を感じさせられた。
ある課題を解決するために、その課題の対象たるモノを文字列でうまく表現できて、「その課題の解決とは、解決しているモノを受理し、解決していないモノを拒否することを実現すること」というように頭の中で変換できたとする。その表現にもとづいて、その課題を解決する手順をある程度の明確さで記述できたとしたら、Turing機械で実装可能である、ということがChurch-Turingの提唱ともいえる。

【シプサ】3 CHURCH-TURINGの提唱

こつこつ。

Turing機械も、よく見るけど、あまりよく知らない言葉。
あるTuring機械Mが受理する文字列の集りをMの言語という。またはMが認識する言語という。逆にその言語のことを、Turing認識可能とよぶ。別名として「帰納的列挙な言語」がある。
ある文字列を認識するとは、受理状態にいたるConfiguration列が存在することである。
このとき、認識されない文字列とは、拒否状態に入るか、ループするなどにより決して停止状態に辿りつかない場合の二つのあり様がある。
停止状態に辿りつかない、ということが発生せず、常に「受理状態に入るか、拒否状態に入るか」という2択しかおこりえないTuring機械を、判定装置(decider)という。
ある言語がTuring機械MによってTuring認識可能なとき、その機械Mが判定装置ならば、それはTuring判定可能であるという。またそのときその言語を、Turing判定可能であるとよぶ。別名として「帰納的な言語」がある。
定義の変形に対するモデルの不変性を頑健性(robustness)とよぶ。
Turing機械は驚くべき頑健性をもつ。
複数テープTuring機械、非決定性Turing機械、列挙装置らはTuring機械でシミュレーションできる。
量に関して制限のないメモリへの使い方に関して制限のないアクセス機能をもつすべてのモデルは、能力の点で等価である。互いにシミュレートできるので。
「この等価現象は重要な哲学的結論をもたらす。たとえ多くの異なる計算のモデルを想像できたとしても、それらが記述するアルゴリズムのクラスは同じものに留まるだろう。」
アルゴリズムとは何だ?
「ある課題を処理するための単純な命令の集りである」
「毎日の生活におけるありふれた出来事では、手続き(procedure)や処方(recipe)と呼ばれることもある」
procedure: (事を運ぶ)手順、順序、やり方、方法
recipe: 調理法、作り方、方法、秘訣
直感的には、アルゴリズムというのはわかるが、ではその厳密な定義は?
それがChurch-Turingの提唱
「アルゴリズムの直感的概念等価 Turing機械のアルゴリズム」
とあるんだけど、これ右側にアルゴリズムという言葉があると、曖昧なのでは。。。
たぶん、
直感的概念におけるアルゴリズムというのは、Turing機械の構成と等価である。すなわち、ある課題においてアルゴリズムがある、ということは、その課題を解決するTuring機械を実装できるということであると考える。
ここで言語と計算について再考。算術計算をするTuring機械のサンプルについて。これはi * j = kという関係を認識する。すなわち、Turing機械では、計算する、というのは、それを述語として、その述語をみたすものの集まりを正しく判定できるということであり、言語は、その述語をみたすものの集合である。なので、計算ということを集合論的に静的に考えているように思える。
Turing機械を記述する際の言葉には3つのレベルがある。
正式な記述(formal description)
実装の記述(implementation description)
高レベルの記述(high-level description)
高レベルの記述につかう用語を定める。
- Turing機械への入力は常に文字列である。
- 入力として文字列以外のものをあたえたいならば、最初にそれを文字列として表現する。
- Turing機械は、与えられた表現(文字列)が我々の意図したとおりに解釈されるようにその表現を複合されるようプログラムする。
- この、モノの符号化にはいろいろな方法があるだろう。しかし、Turing機械は、つねに一つの符号化を他のものに翻訳できるので、どの符号化を選ぶかは重要ではない。
- モノOを文字列として表現した符号を<O>と書く。モノは英語でObjectという。
- これらを用語として、アルゴリズムは日本語で普通に記述する。

さあ、演習だ！

2008年8月9日土曜日

【シプサ】2 文脈自由言語 (その6)

こつこつ。

2.8〜2.16。カンタンだ！

おお、ついにシプサの第一巻を読了！

正規言語
正規表現
決定性有限オートマトン
非決定性有限オートマトン
文脈自由言語
文脈自由文法
プッシュダウンオートマトン(非決定、有限)

について、手を動かして、理解した。
いざ、第二巻へ。

2008年8月7日木曜日

【C算法】第6章ソート (その4)

クイックソートの分割が何故うまくいくのかが理解できない。。。
一日かけて、こつこつ考えてみることにする。

【シプサ】2 文脈自由言語 (その5)

こつこつ。

文脈自由言語の演習もやはり重い。ひとつひとつでてきた言語を吟味せねばならんから、しかたない。
2.4。問題文の「列」の使い方がおかしいような。この言語は、解答から考えるに、「wは少なくとも三つの1を部分文字列として含む」じゃないかなぁ。しかしCFGは強力だ。
2.5。PDAも強力。NFAとくらべると記述力が高い。
2.6。CFGを考えるのが結構大変。
2.7。2.6のPDA。PDAの方がかなり簡単に構築できる。

4問で6時間くらいつかってしまった。しかたなし。

2008年8月6日水曜日

【シプサ】2 文脈自由言語 (その4)

文脈自由言語のポンピング補題を理解して、ついに本文を読み終わった。演習へ。

2.1、2.3は以前やったが、もう一度やる。
もう一度やると、一回やっただけではいかに定着していないかが、如実にわかる。
2.2 補集合というところで、いつもひっかかる。何に対する補集合? ということ。この本では、述語の否定形がなす集合を補集合としている。そこでアルファベットを文脈で固定しているようだ。

次回は2.4から。こつこつ。

2008年8月5日火曜日

【C算法】第6章ソート (その3)

いまのやり方だと仕事との両立が早晩きつくなるような。昨日も朝までやってたし。。。

今日は「6-5 シェルソート」。
だめだ。シェルソートのアルゴリズムがどういものだかはすぐわかるのだが、それのCによる実装が例示されているソースでよいことがわからない。

変数の動きを追ってみる。


--------------------------------------------------------
n:                2
      0     1
h:          n/2
i:          h
j:    i-h 

--------------------------------------------------------
n:                      3
      0     1     2
h:          n/2
i:          h
j:    i-h
i:                i++
j:          i-h

--------------------------------------------------------
n:                            4
      0     1     2     3
h:                n/2
i:                h
j:    i-h
i:                      i++
j:          i-h

h:          n/2/2
i:          h
j:    i-h
i:                i++
j:          i-h
j:    i-2h
i:                      i++                                                                                                                                                
j:                i-h
j:          i-2h
j:    i-3h

--------------------------------------------------------
n:                                  5
      0     1     2     3     4
h:                n/2
i:                h
j:    i-h
i:                      i++
j:          i-h
i:                            i++
j:                i-h
j:    i-2h

h:          n/2/2
i:          h
j:    i-h
i:                i++
j:          i-h
j:    i-2h
i:                      i++
j:                i-h
j:          i-2h
j:    i-3h
i:                            i++
j:                      i-h
j:                i-2h
j:          i-3h
j:    i-4h
--------------------------------------------------------
n:                                                    8
      0     1     2     3     4     5     6     7
h:                            n/2
i:                            h
j:    i-h
i:                                  i++
j:           i-h
i:                                        i++
j:                i-h
i:                                              i++
j:                      i-h

h:                n/2/2
i:                h
j:    i-h
i:                      i++
j:          i-h
i:                            i++
j:                i-h
j:    i-2h
i:                                  i++
j:                      i-h
j:          i-2h
i:                                        i++
j:                            i-h
j:                i-2h
j:    i-3h
i:                                              i++
j:                                  i-h
j:                      i-2h
j:          i-3h

h:          n/2/2/2
i:          h
j:    i-h
i:                i++
j:          i-h
j:    i-2h
i:                      i++
j:                i-h
j:          i-2h
j:    i-3h
i:                            i++
j:                      i-h
j:                i-2h
j:          i-3h
j:    i-4h
i:                                  i++
j:                            i-h
j:                      i-2h
j:                i-3h
j:          i-4h
j:    i-5h
i:                                        i++
j:                                  i-h
j:                            i-2h
j:                      i-3h
j:                i-4h
j:          i-5h
j:    i-6h
i:                                              i++
j:                                        i-h
j:                                  i-2h
j:                            i-3h
j:                      i-4h
j:                i-5h
j:          i-6h
j:    i-7h

--------------------------------------------------------

ここでhは、「h離れたものどもでソート」であり、幅のようなもの。ここでは4,2,1という数列。
iは[h,n)における1刻みの数列を作る。i(q) = h + q, {q= 0, 1, ..., n - p - 1}
これは幅hで離れたもの「ども」の尻尾にあたる要素を列挙しているのだが、それだけではない。そのモノドモごとに、単純挿入ソートをおこなうのだから、1つのモノドモをソートしきるには、そのモノドモに含まれる要素数と同じ回数だけモノドモ(の部分)をなめなければならない。iが[h,n)というように結構多いなぁという数なのはそれを尽くすためである。
よって、その尽くすためのi達おのおのから幅hで減算していく数列が単純挿入ソートの対象添字セットであり、それがj。
ああ、やっとわかった。
わかりにくい原因は、「シェルソートのイメージはモノドモ毎にソートを完了していくというものだが、Cの実装ではソートがモノドモをまたがってインターリーブされている」というところだ。
わかったこと。
- このCの実装は「成すべき処理を、いかに効率よく生成するか」というものである。
- なので、アルゴリズムの結果として成すべき処理が一覧されたとして、それをどう組替えるともっとも単純にそれら処理を生成できるものになるか、ということ。
- そして、Cでこのように考える、ということは、おそらく「慣れ」の問題。ただし、その慣れを得るのにCでいろいろやるのがいいか、離散数学を勉強するのがいいかは要判断。
- CLからプログラミングを学びはじめたので、私はこの手の思考に弱い。
- ここでやった分析は手で実施したのだが、これ自体をプログラムに出力させればよい。手でやるのはアホ。
演習6-9で、(*s)++とすべきところを、*s++としてしまって、ちょっとはまった。いかんなぁ。
演習6-9。1000個の要素に0〜9999をランダムに入れてソートさせると2の倍数だと15000強の交換、3倍して1足す方だと14000強、というかんじだった。

こつこつ。

2008年8月4日月曜日

【Linux入門】Chapter 4 ファイルとディレクトリの基礎知識

こつこつ。

うむ。指の訓練にいい感じ。
.や..を展開させずに.頭の一覧を得るには、echo .*でいいんじゃないかなぁ。
こうやって基本を訓練しているときは心が安らぐなぁ。

【Linux入門】Chapter 3 仮想コンソールを使う

こつこつ。

OSXでは/dev/tty*は134個ある。
Ubuntu8.04では、/dev/tty*は325個。/dev/tty[0-1]*は12個。
whoすると、OSXではsshかターミナルかを問わずにttys003のような形式。Ubuntuでは、sshでは、pts/0など。
ホスト管理者ではないので、直接コンソールをホストにつないで作業ということはないと思うが、予備知識として、altとファンクションキーをつかってコンソールのttyを切り替えられることを覚えておく。
このあたりをはじめの方にちゃんと説明しておく、というのはこの本、よいかも。

【C算法】第6章ソート (その2)

ちょっと焦っているのが、よくないと思えてきた。焦ってやったことは、後々役に立つようにはならない。自分に力量が無いから、思うように進まず、焦るのだ。そして、焦ってしびれをきらして、無理して速く進んだとしても、それは身の丈にあっていないわけで、力量不相応なことをしており、力量が無いことのなんの解決行為にもなっていない。力量の無さを受け止めた上で、こつこつやるしかないのだ。

「6-3 単純選択ソート」から。
離れた場所の要素を交換すると安定性が崩れるようだ。
「6-4 単純挿入ソート」。シャトルソート! なんだかかっこいいかんじ。
単純ってstraightの訳なのね。
そういやトランプって最近やってないなぁ。こんどやってみよう。
これはデータ構造として、配列ではなくて線形リストとかに向いたアルゴリズムじゃないかなぁ。
演習6-7のbinary insertion sortの実装にやたら時間がかかる。再帰を使えばすぐにかけるのです。せっかくCなので、再帰を使わないで、配列と繰返しでやろうとすると、途端に、値の振舞と添字の振舞がいろんなケースでどうなるのか、ということが追えなくなるのです。やっぱり、数学に弱い、とくに離散数学に弱いのが原因だと思う。
さて、ここで開きなおります。C上で直接アルゴリズムを考えるのではなく、離散数学の問題の解答として再帰的表現をなるべく使わないものを立案してから、それをCで実装することにする。
ふむ。そのようにやったら、デバッグなしで一発で正しく書けた。しかしながら、その結果としてのCによる実装のあり様はある意味きたないというか、それが正しく動くものかどうか、ぱっと見で判断できないようなものだ。これは何を意味しているのか。
CLとかSchemeのときは、再帰とか高階関数とかマクロとかをつかいながら、アルゴリズムを考える過程としてそれを書き進めることができるが、Cではそうやってはいけないまたはできないということかもしれない。アルゴリズムを考えてから、それのCによる実装を考えるという二段階を踏むべきということか。単なる慣れの問題かなぁ。

こつ、こつ。

【シプサ】2 文脈自由言語 (その3)

文脈自由文法(CFG)とプッシュダウン・オートマトン(PDA)の等価性をなんとなく理解できた。理解できるまで4時間くらいかかった。たぶん頭のよい人は5分くらいでわかるんだろう。5分で理解できるようになるにはどうしたらいいんだろう。以下はメモを多少。

まず、計算理論における「言語」の指すものがわかった。それは例えば日本語をここでいう「言語」というとき、「日本語として認められるすべての文字列の集合」という巨大な集合を考えておりその集合を言語と呼んでいるのだ。だからC言語を「言語」として考えるとき、それは「C言語で書かれていると認められる全ての文字列を含む集合」を考えている。Common Lispを「言語」として考えるとき、それは「Common Lispで書かれていると認められる全ての文字列からなる集合」のことである。こういう考え方をするとき、マクロがビルドインされているCLはとんでもないことになるのでないか、という不安と期待を感じる。現時点では正直不安の方が大きいのだが。。。
言語はそのようにいくら巨大とはいえ「文字列の集合」にすぎないのだが、それを調べるのに2つの方法論がある。ひとつは、ある文字列が与えられたとき、それがその集合に属するかどうかを判定できる判定機構をつくり、その機構のあり様をみてみるというやり方。もうひとつは、その言語に属する文字列を全て生成可能なような生成機構をつくり、その機構のあり様をみてみるというやり方。
正規言語と呼ばれる言語クラスを考えてみる。まず、その言語クラスに属する言語たちを特定するために、それは有限オートマトン(DFA)が存在するような言語であるとする。すると、正規表現という生成機構で表現可能な言語どもは正規言語であるし、逆も真であることがわかる。これが等価性。
正規言語: {判定機構:DFA, 生成機構:正規表現}ということになる。
さて、次に、生成機構としてCFGを採用したときに表現可能な言語のすべてを総称して文脈自由言語と呼ぶことにする。正規言語のときとは定義の仕方が逆になっているが、まあそれはどうでもいいこと。
で、文脈自由言語: {判定機構:PDA, 生成機構:CFG}ということを確認したい、ということ。
文脈自由言語(CFL)はCFGが生成するものとして定義されているので、これを確認するには、
PDAが認識(判定)できるものはCFLである、ということと、CFLならばPDAで認識できる、ということを確認すればよい。
いいかえると「PDAが認識できる言語に対して、CFGを構成できる」ということと、「CFGが存在する言語に対して、PDAを構成できる」ということ。
後者の方が簡単なので、本書では後者から確認している。
「CFGが存在する言語に対して、PDAを構成できる」
- ポイントは非決定性。
- CFGの変数および終端文字はスタック・アルファベットとする。
- はじめのセットアップとして、スタックに開始変数をいれておく。
- これが種となって、PDAは、CFGに従って、入力をまたず、非決定にがんがん勝手に分岐していく。生成規則に従って変数を左辺の表現にどんどん替えていくのだ。これがCFGにて認識可能なすべての文字列をつくってしまう。(非決定性の力はすさまじい。。。)
- するとそれらの分岐はそれぞれにスタックを持ち、その中には認識可能な文字列が入っている、というイメージ。
- 実際にはちょっと違っていて、S->aTbとかの分岐においては、aがスタックの先頭にいるので、Tの分岐ができない。
- なので、その分岐は入力を待つ形になる。で、入力として、aがくればa->εしちゃって、Tが先頭になり、また分岐地獄が始まる。
  bがくればその枝は破棄する。
- で、スタックが空になったタイミングではいつでも自動的に受理状態に遷移する。すると、そこで入力文字列が終わっていれば受理されるし、まだあれば、その枝は破棄される。
「PDAが認識できる言語に対して、CFGを構成できる」
- これのポイントは「PDAに含まれる2つの状態の組の全てに対して、その組ごとに、それらの間の一方から一方に遷移するような文字列を生成するCFGを構成できる」ということ。
- おまけ条件があって、「遷移にあたってどちらの状態もスタックは空である」を満しているものとする。
- ポイントはそれとして、まずPDAを別のPDAに等価変形する。
  - ただ一つの受理状態をもつようにする。
  - 受理する前にスタックを空にする。(受理状態はスタックが空である)
  - 全ての遷移は、ポップかプッシュのどちらかであるようにする。これには状態を足したり遷移を足したりすることが必要になることもある。
- このPDAをPと呼ぶ。P = {Q,Σ,Γ,δ,q_0,{q_accept}}とする。これに対して、CFGたるGを次のように構成する。
  - p,q∈Qについて、ApqをGの変数とする。
  - 開始変数はAq_0q_acceptとする。
  - ΣをGの終端記号とする。
  - 規則の構成。
    - App -> ε。
    - Apq -> AprArq
    - p,q,r,s∈Q; t∈Γ; a,b∈Σεに対して、「δ(p,a,ε)が(r,t)を含み、δ(s,b,t)が(q,ε)を含む」ということがあるなら、Apq -> aArsb
- さて、これによってPDAからCFGを構成する「とある方法」を明確にした。
- で、どうしたいかというと、この「とある方法」にて構成したCFGにおいて、
- 「Apqが生成する文字列は全て、スタック空の状態pからスタック空の状態qに遷移するようにPDAが計算する」
- と、その逆たる
- 「スタック空の状態pからスタック空の状態qに遷移するようにPDAが計算する文字列の全てを、Apqが生成できる」
- ということが実は成立している、ということ。
- これが成立していること自体は、帰納法を使えばかんたんにわかる。
- で、これが成立しているということがどういうことかというと、
- ここで確認したことをAq_0q_acceptにに適用すれば、
- 「Aq_0q_acceptが生成する文字列たちと、スタック空の状態q_0からスタック空の状態q_acceptに遷移するようにPDAが計算する文字列たちとは等価である」
- が言えたということ。これは確認したかったこと、そのもの。

という感じかなぁ。こつこつ。

2008年8月3日日曜日

【シプサ】2 文脈自由言語 (その3)

PDAがしっくりこないのがくやしくて、ねばってみた。

言語{0^n1^n|n>=0}のPDA(例2.14)を調べてみた。
わからなさの根源は、PDAの定義の理解にあることがわかった。(やった！)
というのはPDAの定義は、定義というより「諸元表記法」というニュアンスがあり、PDAの動作の仕組みは、それの計算というか受理方法にあったからだ(受理を考えるときに、文字列の列が出てきて、それがスタックの記憶域を実現している)。それはPDAの定義には含まれていない。だけどその計算方法が前提となっていれば、PDAの定義と言われるものを指定すれば、たしかにPDAの振舞はきまるから定義されるといえる。だから諸元的。
そしてPDAの遷移関数は、スタックについて言うと、その文字列の先頭の置換を定義している。
ミソは置換の際に、空列をうまくつかっていることだ。すなわち、空列から文字への遷移は、スタック文字列の先頭に空列がひとつあるとして、それを文字へ置換することによって「スタックへのpush」を表現している。逆に文字から空列への遷移はpopを表現している。
あー、すっきりした。これで眠れる。

じわじわ。

【Linux入門】Chapter 2 テキストログインでの操作

こつこつ。

起動モードとか、このあたりはLinuxがないと意味なし。
QemuでUbuntu8.04 serverをうごかしてみよう。
oszooがおかしいので、自分でインストールしてみる。
64bit(amd64)版をDL。
amd64用にqemuを設定すると仮想PC自体が起動しない。なんと。これを深掘ると横道なのでほっとくことにする。
l32bit(i386)版をDL。インストールはすんなり完了。serverアプリケーションはとりあえずOpenSSHのみ。
qemuの場合、qemu内のユーザスペースで仮想ネットワークを構成していて、それにホストからアクセスするには、ホストにポートリダイレクトするように引数を調整してやるようだ。sshまでできるようになった。とりあえずOK。
これ以降、Linuxの仕組みに関することはここで確認する。Fedoraじゃないからいろいろ違うと思うけど。

【シプサ】2 文脈自由言語 (その2)

こつこつ。文脈自由文法とPDAの等価性にチャレンジ。

玉砕。そもそも、文脈自由文法とPDAのそれぞれ自体に慣れていない。
そこで、演習を多少やってみることにする。
2.1、2.2をやった。変数が変数自身をderiveするという定義を見落してた。それ以外はOK。

もう少し慣れが必要だけど、とりあえずここまで。

【C算法】第6章ソート

こつこつやってたら、半分まで来た。こんな調子でプログラマになれるのか?という疑問もあるが、とにかくこつこつやるしかない。

内部ソートと外部ソートの存在をしった。
ソートの三大要素は交換・選択・挿入である。
バブルソート、シェーカーソートとかは交換なのね。

次回は「6-3 単純選択ソート」。

2008年8月2日土曜日

【シプサ】2 文脈自由言語

こつこつ。

引き続き、計算理論において何故「言語」をやらなければいけないのかが理解できていない。それはそれで楽しいし、コンパイラとかに役立ちそうだからやるのはいいんだけど。それが「計算」とどう関係しているかはまだわからない。
おそらく、第二巻以降で計算を考えていくときのツールになるのだろうと予測して、できるだけ慣れておくようにしたい。
文脈自由文法(CFG)の定義を知った。BNF記法とかいわれているものと同じ表記かな?
プッシュダウン・オートマトン(PDA)の定義を知った。
構文解析木(parse tree)が意味を与える、ということがわからない。parse treeの構造が複数存在したって意味は同じということだってあるんじゃないの？また、girl とか boy の意味はどこであたえられるのか? 述語 love や前置詞 with の意味はどこであたえられるのか。それらの意味があたえられていれば、文の parse tree がひとつに定まったとき、その文を一通りに解釈することはできる。その構造はCFGによって定義されている、ということもわかる。しかし、だ。
意味という言葉自体の曖昧さが、元凶と思われるのだが。。。

次回は、CFGが記述できる言語クラスとPDAが記述できる言語クラスが等価であることの探求から。

【シプサ】1 正規言語 (その7)

こつこつ。

ポンピング補題をじっくり考えて理解した。
これで、正規言語、正規表現、DFA、NFA、GNFA、FSTの基本を理解した。うれしー。

次は文脈自由言語だ！いろんなところで目にする言葉だけど知らなくてヤな感じだったので、とても楽しみ。

2008年8月1日金曜日

【C算法】第5章再帰的アルゴリズム (その2)

こつこつ。

ハノイの塔。非再帰的にも書けたが、いまいちしっくりこない。フレームスタックをもっときっちり作ってしまう手法の方がすっきりするかも。

う、8王妃列挙の再帰アルゴリズムですら理解できない。。。考える。。。がなんだかもやもや。再帰といいつつfor文もつかっているからわかりにくいのかな、それともbranchingという再帰の使い方になれてないからかな？再度考える。

3王妃列挙に縮小して考える。
3王妃列挙では、一行で、とある配置を表現する。例えば、"111"など。これは全列とも行1に王妃がいる配置を表す。

理解するためにset(i=0)をどんどん展開していく。


{i=0; for(j0=0 to 2) {pos[i]=j0; set(i=1);}}

{i=0; for(j0=0 to 2) {pos[i]=j0;
                                 {i=1; for(j1=0 to 2) {pos[i]=j1; set(i=2);}}}}

{i=0; for(j0=0 to 2) {pos[i]=j0;
                                 {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                  {i=2; for(j2=0 to 2) {pos[i]=j2; print()}}}}}}

{i=0; for(j0=0 to 2) {pos[i]=j0;
                                 {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                  {i=2; for(j2=0 to 2) {pos[i]=j2; for(k=0 to 2) {print pos[k]}}}}}}}

{i=0; for(j0=0 to 2) {pos[i]=j0; 
                                 {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                  {i=2; for(j2=0 to 2) {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}

{i=0; for(j0=0 to 2) {pos[i]=j0; 
                                 {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                  {i=2;
                                                                        {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                        {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                        {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}

{i=0; for(j0=0 to 2) {pos[i]=j0; 
                                 {i=1;
                                       {j1=0; {pos[i]=j1;
                                                          {i=2;
                                                                {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}};
                                       {j1=1; {pos[i]=j1;
                                                          {i=2;
                                                                {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}};
                                       {j1=2; {pos[i]=j1;
                                                          {i=2;
                                                                {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}
{i=0;
      {j0 = 0;{pos[i]=j0;
                          {i=1;
                                {j1=0; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                {j1=1; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                {j1=2; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}
      {j0 = 1;{pos[i]=j0;
                          {i=1;
                                {j1=0; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                {j1=1; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                {j1=2; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}
      {j0 = 2;{pos[i]=j0;
                          {i=1;
                                {j1=0; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                {j1=1; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                {j1=2; {pos[i]=j1;
                                                   {i=2;
                                                         {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                         {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                         {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}}

これをみて分析すると。
まず、列iは再帰によって繰り返しを生じている。
列iの繰り返しと行j*の繰返しは交互に生じている。
j0は列0の行配置、j1は列1の行配置、j2は列2の行配置、を生成している。
理解したいのはset(i)の作業を日本語で何というか、だ。
まずset(i)は列iに関する作業であるといえる。
ただし、それは列i+1に関する作業も含んでいる。
その連鎖によって、set(0)は列0、列1、列2のすべての作業を含んでいる。
ところで、「列iに関する作業」というのは具体的に何かというと、列iの各行jのどこに王妃がいるかを印字すること。
うーむ。よくわからない。
そうか！set(i=0)を列0に関する作業、と考えるからいけないのだ。これは「列0を起点に、分岐して、王妃を全部列挙する作業」と考えるのか。
すると、
```
{i=0; for(j0=0 to 2) {pos[i]=j0; set(i=1);}}
```
は、列0については、0〜2の通りがあるけど、それはそれぞれの通りについて、「列1を起点に、分岐して、王妃を全部列挙する作業」があるもんだよ、といっている。
これを繰返していく、と。
なるほど、再帰による分岐は、階乗とかの再帰とかとはニュアンスがちょっと違う。勉強になった。

分割統治法って、再帰的である分割に限るのかな?
うーん。8王妃の分岐限定法アルゴリズムを完全に理解できたわけではないが、分岐限定法自体の考え方は多少わかるので、先に進もう。

【Linux入門】Chapter 1 Linuxひとめぐり

1.1 Linuxとは
- 商用とフリーという、2つの系統の分け方が微妙かなぁ。
- LinuxはBSDとSystemVのいいとこどり。
1.2 ディストリビューションとは
- 特になし
1.3 Linuxを体験する
- この本、インストールは紹介しないのね。ページに無駄がなくてその方がよいですね。
- ファイルとディレクトリの基本操作。指の訓練！
1.4 UNIXの小知識
- アカウントってそのまんま勘定って意味だったんだ。
- 端末上でのC-sとC-q、しらんかった。
- shell上ではC-dで端末終了なのね。ちょっとこわい。

こつこつ。

【Linux入門】開始

シプサとC算法が結構重いので、ちょっと息抜きがてらできるものを並走させることにした。シェルスクリプトを勉強しているなかで、そういえば、Unixコマンドをちゃんと勉強したことがないなぁと気付いたので、一度一通りやってみることにした。本は、

改訂新Linux/UNIX 入門

にした。選定の基準は、

日本人が書いたもの
古典じゃなく最近のもの
初心者向けだが丁寧に仕組みを説明しようとしているもの

ほいで、いろいろ物色して、この本にしました。自分的には矛盾もあって、

そもそも生活環境はOSX
Linuxを使うときはDebian系 (この本は、ディストロに寄る部分はRedhat系らしい)

なんだけど、まあいいや、ってことで。シェルスクリプトのときにOSXがBSD系ということでfindとか難儀したので、やばいと思ったらFinkのバイナリ群にきりかえることにする。

【シプサ】1 正規言語 (その6)

こつこつ。

1.28まで完了。ちょっとがんばった。
やっているなかで、「学びにおいて、楽しい、ということに勝るものはない」ということをふと再考してみた。たぶん、何かが楽しい、と感じるとき、それはその対象に意識が完全にフォーカスしているからなのだろうと思えた。
昨日できなかった正規表現ができた。GNFAを使ってDFAから正規表現を作成する方法を理解しきれていなかっただけだった。
ポンピング補題は、本文をもう一度じっくり検討しないととてもできそうにない。次回やることにする。

登録: 投稿 (Atom)

2008年8月31日日曜日

2008年8月28日木曜日

2008年8月24日日曜日

2008年8月23日土曜日

2008年8月22日金曜日

2008年8月21日木曜日

2008年8月19日火曜日

2008年8月18日月曜日

2008年8月17日日曜日

2008年8月16日土曜日

2008年8月15日金曜日

2008年8月14日木曜日

2008年8月12日火曜日

2008年8月11日月曜日

2008年8月10日日曜日

2008年8月9日土曜日

2008年8月7日木曜日

2008年8月6日水曜日

2008年8月5日火曜日

2008年8月4日月曜日

2008年8月3日日曜日

2008年8月2日土曜日

2008年8月1日金曜日

ラベル

自己紹介

ブログ アーカイブ

ブログアーカイブ