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

2008年9月30日火曜日

【シプサ】7 時間の複雑さ (その3)

こつこつ。今回は7.3 クラスNPから。

clique:小集団,派閥,仲間
クラス NPの概念を理解した。
7.4にはいり、NP完全性のイメージはわかった。

この節はお話的な雰囲気もあり、困難もそんなになかった。またおもしろかった。
「このことは、まだわかっていない」というフレーズが徐々に増えてきて、先端に近づいている感じがした。
7.4 NP完全性のさわりだけ入った。次回は、多項式帰着可能性、から。

2008年9月29日月曜日

【シプサ】7 時間の複雑さ (その2)

シプサは、ちょっと離れると再開する敷居が高い。されど、こつこつ。

まず、前回最後のあたりがぐだぐだになったので、そのあたりから。
「定理7.8 t(n)をt(n)>=nであるような関数とする。このとき、すべてのt(n)時間複数テープTuring機械に対して、それと等価なO((t^2)(n))時間単一テープTuring機械が存在する。」
- まず、この定理がいっていることの理解を深める。
- t:n->R+な関数tについて、TIME(t(n))という言語の集合をつくれる。TIME(t(n))に含まれる言語は、O(t(n))時間Turing機械で判定されるものに限る。これが基本情報。
- ということは、t(n)時間複数テープTuring機械が判定する言語は、TIME((t^2)(n))に属している言語である、という感じなんだな。
- (t^2)(n)が何をあらわしているのかわからない。(t(n))(t(n))ということか? これは説明を読んで理解することにする。
- さて、説明の理解。これは文章ではなくて、紙に絵を書いて理解をこころみる。
- ... お絵描き中 ...
- 雰囲気はわかった。。。(t^n)(n)は、(t(n))(t(n))のことのようだ。先へ進む。
「定理7.11 t(n)をt(n)>=nであるような関数とする。このとき、すべてのt(n)時間非決定性Turing機械に対して、それと等価な2^(O(t(n)))時間決定性単一テープTuring機械が存在する。」
- うーん。これもなんとなく雰囲気をつかんだ。
- 先々、必要になったときに、理解を深めることにする。(今は興味がわかない)
ここから「7.2 クラスP」。
そうか、決定性単一テープTuring機械で多項式時間判定できる言語のクラスがクラスPなんだ。
そして、クラスPである、ということと、現実の電子計算機で計算を実行できるということは経験上等価であると。少くとも第一近似または突破口としてはよし。
クラスPという概念は、「妥当な」計算モデルの変更によって影響を受けない。さらばTuring機械、ということか!?
クラスPの概念を理解した。
気になるところを確認。
「与えられた数の素因数を求める一つの方法は、すてのの可能な序数を調べてみることである。この探索空間のサイズは指数的なので、」
- 素因数って何だっけ?
- 素因数：整数の因数である約数のうち、素数であるもの。
- 因数って何だ?
- 因数：一つの数や整式が、いくつかの数や整式の積の形で表されるときの、その個々の数や整式のこと。
- 探索空間のサイズは?
  - 10進数で入力を表現する。
  - n=1;数=1 -> 1
  - n=2;数=10 -> 10
  - n=3;数=100 -> 100
  - n=4;数=1000 -> 1000
  - なるほど。入力のサイズnに対して調べるべき対象の数は、10^nになっている。
「項目1は、Pが数学的に頑強なクラスであることを示している」
- 頑強(robust)というのは、前にでてきたような、どこだっけ。
- 索引を調べるが、なかった。先へ進む。。。
その計算が多項式時間でいけるかどうかを検討する際のポイント
- 問題の符号化に関連すること(表現から内部表現の構成、他の表現も使うならばそれへの変換、またはこれらの逆変換など)が多項式時間でできるかどうか。
- アルゴリズムのステージ数は多項式時間か。
- アルゴリズムの各ステージの実行ステップは多項式時間か。
気になること。数字の一進表現は指数的だが、二進表現は多項式的?
- まず、一進表現。
- n=1;16進数=1 -> 1
- n=2;16進数=10 -> 16個
- n=3;16進数=100 -> 256個
- まあ、これは指数的。
- 次に二進表現。
- n=1;16進数=1 -> 1個
- n=2;16進数=10 -> 5個 (1 0000)
- n=3;16進数=100 -> 9個 (1 0000 0000)
- おお、n^2程度だ。
う、これから、例としてグラフ理論が多くなるのか。。。
「定理7.14 PATH∈P」
- 気になるところを調べる。
- 全数探索は本当に指数的か?
- グラフ Gの節点数をmとする。
- sからtへの経路が存在するならば、それは各節点をたかだか1回しかとおらない。なぜなら、2回とおるということはループ構造があるということであり、ループしなきゃいいんだから。
- するとG内に存在する経路とは高々m個の節点の列である。
- ではこのような節点の列が何個あるかというと、始点をsとしたものは、(m-1) + (m-1)(m-2) + (m-1)(m-2)(m-3) + ... + (m-1)(m-2)...(2)(1)かな?
- これが指数的か多項式的か?
- わからない。。。
- いかん、グラフ理論または離散数学の勉強をせねば。
- とりあえず今は先に進む。
「定理7.15 RELPRIME∈P」
- これはアルゴリズムとデータ構造のときに検討したので、まあわかる。
「定理7.16 すべての文脈自由言語はPの要素である」
- これ、ぼやぼやしている、日を置いて再度考える。

またまた最後ぐだぐだになったが、とりあえずクラスPがおわった。
次回はクラスNP。

【CLドリル】1 Basic Constructs

もともとは日本語の書籍だが、日本語版は古本屋でもみつからなかった。英訳版を偶然古本屋でみつけたので購入したもの。内容は、Common Lisp入門と対応している。Common Lisp入門の復習をしながら、取り組んでいくことにする。

1 Basic Constructs
- 1-1 A Common Lisp System
- 1-2 Functions
- 1-3 Variables and Symbols
- 1-4 Lists
- 1-5 Evaluation and Forms

ちょっともやもや。
(setq x '((a b) (c d)))
として、例えば、
(cons (car x) nil)
がなぜ、
((a b))
となるのか?
評価をたどると、
(cons (a b) nil)
となってここで、(a b)を関数呼び出しとならないのか???
直接、
(cons (a b) nil)
を評価すれば、(a b)は関数呼び出しとなって、aは関数として未定義なので、エラーとなる。

まずansiによるとconsは関数である。そだったんだ。
そして、consの値は、"a cons"である。これは"a compound data object having two components called car and the cdr"という意味でのcons。
すなわち、(cons ...)を評価した値はそれがスペシャルフォームや関数呼出フォームの形であっても、あくまで、a consであるとして、次の関数に渡されるということか。

次にcarはaccessorである。まあsetfに使えるからね。
listを引数で受け取り、objectを値とする。objectは"any lisp datum"である。。。
う、ここらへん、実はもやもやしている。整理する。

記法として、evalされて返されたlist objectのみ、と表記することにする。
(cons (car (quote ((a b) (c d)))) nil)の場合。
まず、これをreaderが読み込んでlisp objectに解釈する。それは概念的には次のようなもの(object)になる。
(<symbol cons> (<symbol car> (<symbol cons> (<symbol cons> <symbol a> (<symbol cons> <symbol b> <symbol nil>) (<symbol cons> <symbol c> (<symbol cons> <symbol d> <symbol nil)))) <symbol nil>)
そして、evalにわたされる。
evalは、まず、consがfunctionの名前なので、function formと判断する。
function formはsubformを左から右へ先行評価するので中身の評価にはいる。
ちょっとずるして先に二つ目をやっちゃう。二つ目はnilのsymbolなので、nilが返る。
一つ目は、
(<symbol car> ... )
なので、これもfunction formで中身へ。
(<symbol cons> ...)
なので、consのfunction form。この中身へ。
(<symbol cons> ...)
なので、function form。subformをそれぞれ評価する。ひとつめは
(<symbol cons> <symbol b> <nil>)
function callすると、
<list-obj {<symbol b>} >
という感じのものがかえる。ひとつ上にもどると、
(<symbol cons> <symbol a> <list-obj {}>)
なので、function call。結果は、
<list-obj {<symbol a> <symbol b>}>
ひとつ上にもどって評価した結果は、
<list-obj {<list-obj {<symbol a> <symbol b>}> <list-obj {<symbol c> <symbol d>}>}>
となる。これが
(<symbol car> ...)
のsubformの結果なので、carの関数呼び出し。その結果、
<list-obj {<symbol a> <symbol b>}>
が返る。なので結局、はじめのfunction form consのsubformの評価結果は、
<list-obj {<symbol a> <symbol b>}>
<nil>
の2つ。この評価結果たちにたいしてconsをfunction call。
<list-obj { <list-obj {<symbol a> <symbol b>}> }>
が結果として返る。これが((a b))のこと。
(cons (a b) nil)の場合。
まずこれをreaderが読みこむと次のようなlisp objectになる。
(<symbol cons> (<symbol a> <symbol b>) <symbol nil>)
これをevalが評価する。

まず、頭のconsはfunction nameだからfunction formと解釈する。
subformの評価に進む。
(<symbol a> <symbol b>)
を解釈しようとするが、この<symbol a>に該当する

special operator
macro name
function name

が存在しない。またこのcarがcompoud formでlambdaなら解釈のしようがあるが、そうでもない。
よって、これは解釈不可能ということでエラーになる。
要約する。何がポイントかというと
(cons (car '((a b) (c d))) nil)を評価する、とかいうとき

(cons (car '((a b) (c d))) nil)
=>(cons (a b) nil)
=>((a b))

とか書くとなんだか変である。

(cons (car '((a b) (c d))) nil)
=>(cons '(a b) nil)
=>'((a b))

の方がよさ気。
しかし、根本的に言うと、この疑似的に評価プロセスを手書きするという手法は曖昧なものである。というのは、「readerに入力する構文表記のままで、evalしている」からだ。readerは頭の中にある、という解釈もあるが、evalした結果がreadされる前の構文表記に戻っているのがいただけない。

まあわかっているものどうしの便法、野暮なことは言うなということ、なんでしょうね。

こつこつ。

2008年9月28日日曜日

目標の整理 (Ver.2.1.1)

状態をアップデート。

GNU/linuxのptyアプリを書きたい。
- 「詳解UNIX」を勉強する。
  - C言語を勉強する。
    - 「明解 C言語入門編」【完了】
    - 「明解 C言語実践編」【完了】
    - 「UNIXの道具箱」★途中
  - GNU/linuxのAPIの基礎を勉強する。
    - 「例解UNIXプログラミング教室」★途中
NorvigのAIを読みたい。(Common Lispプログラミングの書きぶりを知りたい)
- アルゴリズムとデータ構造について勉強する。
  - C言語の基礎を勉強する。【完了】
  - C言語でアルゴリズムとデータ構造をやる。
    - 「C言語によるアルゴリズムとデータ構造」【完了】
    - 「アルゴリズムC」
- Common Lispについて基本を復習する。
  - 「初めての人のためのLISP」★途中
  - 「Common Lisp入門」【完了】
  - 「Common Lisp Drill」 ★途中
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」
- 「詳解シェルスクリプト」

【CL入門】付録2 Lispプログラムのデバッグ

こつこつ。

aclでは、ブレイク・レベルにて、環境の参照を素朴には実施できない。:localをつかえば一覧表示はできる。
aclでは、
- バックトレースは:bt。
- トップレベルにもどるのは:reset。
そうか、print文を埋め込む方式を「デバッグ・ライト」と呼ぶのか。
#+debug (print x)
お、頭いいな。
aclでbreakから実行再開するには:cont 0。

おお、湯浅先生のCommon Lisp入門を読了した。
CLtL1ではありますが、処理系実装者らしさを適度におりまぜたよい説明が随所にありました。読んでよかったです。
次のターゲットは、この本と双子であるCommon Lisp Drillです。

【CL入門】付録1 実際的なLispプログラムの例 (その2)

こつこつ。今日も写経。

クロス・リファレンスってこういうことなんだ?
とりあえず、loadは通るようになった。
将来、つくりこもう!

次回は付録2 Lispプログラムのデバッグ。

2008年9月26日金曜日

【シプサ】7 時間の複雑さ

気分一新、第三巻。

asymptotic: asymptote 漸近線
漸近線: ある曲線が、原点から無限に遠ざかるにつれて、限りなく近づいてはいくが、決して交わらないし、接しもしない直線。
おお。big-O記法というのは、大きい入力における近似の考え方だったんだ。
うーん。logがわからない。wikipedia。。。
- 任意の正の実数x について、x=a^p (a != 1) をみたす実数pが唯一存在する。このpを p = log[a] x と書く。
- ここで、aを底と呼ぶ。底は、2, e(ネイピア数), 10などをとることが多い。それぞれのとき底を省略するために、Log, ln, lgなどと書くこともある。
- xy = a^pのときp=log[a](xy)。x=a^q, y=a^rのときq=log[a]x,r=log[a]y。xy=(a^q)(a^r)=a^(q+r)だから、log[a](xy) = log[a]x +log[a]y。
- nが自然数のとき、前項をつかって、log[a](x^n) = nlog[a]x。これはたぶん実数でもなりたって、log[a](x^p) = plog[a]x。
- (log[a]x)(log[b]a) = log[b](a^(log[a]x)) = log[b]xより、log[a]x = (log[b]x)/(log[b]a)。なるほど定数倍だ。
5n^3+2n^2+22n+6 = O(n^3)。
- nが十分大きければ、n^3 > 2n^2+22n+6。
- よって、nが十分大きければ、6n^3 > 5n^3+2n^2+22n+6。
3nlog[2]n+5nlog[2]log[2]n+2 = O(nlogn)
- loglognはlognよりもはるかに発散が遅い。ゆえにnが十分に大きければ、4nlog[2]n>3nlog[2]n+5nlog[2]log[2]n+2。
O(n^2)+O(n) = O(n^2)。
- nが十分に大きければ、定数倍の値に関わらず、O(n^2)+O(n^2) > O(n^2)+O(n)。
f(n)=2^(O(n))の意味は?
- nが十分に大きいとき、2^(Cn)がf(n)の上界になっているということ。
- なんで、O(2^n)ってかかないんだろう??
f(n)=2^(O(logn))の意味は?
- nが十分に大きいとき、2^(Clogn)がf(n)の上界になっているということ。2^(Clogn) = 2^(log(n^C)) = Dn^Cだからn^Cが上界ということ。
- なんで、O(n^C)と書かないんだろう?
n^O(1)とは?
- O(1)は、定数より大きくならない。よって、n^C。なので2^(O(logn))と同じ。
n^5、n^3、nなどの上界を多項式境界という。
2^(n^6)、2^(n^2)、2^(n)などの上界を指数境界という。
small-o 記法。
f(n)=o(g(n)) <=> lim f/g = 0 。なるほど。これはbig-Oよりも「ずいぶん大きい」境界だな。
あ、big-Oとかsmall-OのOって、たぶんOrder(規模)のOなんだろうな。なっとく。
う、言語0^k1^kの修正アルゴリズムで、走査回数がたかだか1+log[2]nになるのがわからない。考える。
- n=2、01とのき。q01#Xq1#Xxq_#Xqx_#qXx_#qXx_。これは5回?
- 1 + log[2]2 = 1 + 1 = 2。あり?
- n=4、0011のとき。q0011#Xq011#X0q11#X0xq1_#X0x1q_#X0xq1_#X0qx1_#Xq0x1_#qX0x1_#Xq0x1_#Xxqx1_#Xxxq1_#Xxxxq_#Xxxxq_。これは13回?
- 1 + log[2]4 = 1 + 2 = 3。あり?
- なんかおかしい。1+lognになるのはここではないのかな?
- まず、はしからはしまでの一回の動作のステップは、常にn。
- じゃあ、何回、はしからはしまでをやりますか、というと、
- n=2のとき、1回。log[2]2 = 1
- n=4のとき、2回。log[2]4 = 2
- n=6のとき、2回。log[2]6 = 2.58
- n=8のとき、3回。log[2]8 = 3
- n=10のとき、3回。log[2]10 = 3.32
- n=16のとき。log[2]16 = 4
- 1を足しているのがよくわからないが、対数的にはなっている。
- なぜ、底を2とした対数的になっているのか?
- 底を2とする対数ってなんだ?
- a = log[2]b のとき、2^b = a。
- そうか、今あるNがあるとき、「2の何乗がNですか」ということは、「Nに1/2を何回掛けると1になりますか」ということであり、これは「N個の作業対象があり、毎回作業対象が前回の半分になるときに、何回作業すると作業対象が0になりますか」ということと同義なんだ。
- やっと、毎回半分になる作業が、log[2]n回の繰返しになるということが理解できた。

最後ぐだぐだになったが、とりあえず7.1がおわった。
次回は、7.2 クラスP。こつこつ。

登録: 投稿 (Atom)

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

2008年9月30日火曜日

【シプサ】7 時間の複雑さ (その3)

2008年9月29日月曜日

【シプサ】7 時間の複雑さ (その2)

【CLドリル】1 Basic Constructs

2008年9月28日日曜日

目標の整理 (Ver.2.1.1)

【CL入門】付録2 Lispプログラムのデバッグ

【CL入門】付録1 実際的なLispプログラムの例 (その2)

2008年9月26日金曜日

【シプサ】7 時間の複雑さ

ラベル

自己紹介

ブログアーカイブ

2008年9月30日火曜日

2008年9月29日月曜日

2008年9月28日日曜日

2008年9月26日金曜日

ラベル

自己紹介

ブログ アーカイブ

ブログアーカイブ