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

2008年7月31日木曜日

【C算法】第5章再帰的アルゴリズム

Cで再帰。楽しみだ！

う、ユークリッドの互除法自体がわからない。考えてみる。
- 最大公約数の定義は、整数x,yがあって、x=az, y=bzとなるzのうち最大のもの。z = gcd(x, y)とあらわす。
- ここで、gcd(x, y) = gcd(y, x)。どうでもいいけど。
- さらに定義として、gcd(x, 0) = x。
- で、ユークリッド互除法とは、gcd(x, y) = gcd(y, x % y) ということ。なんで?
- 便宜上、x > yとする。すると、x % y = 0ならば、yがgcdであることは自明。
- つづいて、x % y != 0とする。するとyがgcdでないことは自明。
- このとき、とあるAにて、x = Ay + x % y となっている。ここで、Ayの部分はもちろんgcdで割り切れるものである。よって、x % yもgcdで割り切れなければならないことがあらたにわかる。x > y > x % y だから、x,yのgcdを考えることは、より小さな問題である y,x%yを考える問題と等価であるといえる。よって、gcd(x,y)=gcd(y,x%y)。
- で、x < yであっても、gcd(x,y) = gcd(y, x%y)するなかで、大きい方が左の引数に寄っていくので同じ結果となる。
- という感じかなぁ。
とりあえず5-2まで完了。
なんか、再帰を楽しむというより、再帰は悪って感じだなぁ。。。

こつこつ。

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

なんだかオートマトンと随分親しくなってきた。。。

1.14〜1.17はまあ簡単。
1.18でひっかかる。次のものどもの正規表現を作ることができない。。。
- f: {w| wは部分文字列110を含まない}
- h: {w| wは11でもなく、111でもない任意の文字列}
この「否定」をどう正規表現で表現するかが掴めていない。DFAからGNFAを経てCONVERTで作成しようとしたが何故かうまくいかず。
これは一度寝てからまた考えてみる。

こつこつ。

2008年7月30日水曜日

【C算法】第4章スタックとキュー (その2)

今日はキューから。

リングバッファは、実践編ですでに検討済みだったのですんなり。
うむ。だんだん演習がごつくなってきて時間がかかるようになってきた。柴田さんの本は、入門編、実践編につづき三冊目だが、この本が一番レベルが高いかな。これをちゃんと終えれば、C言語入門者を卒業してC言語初級者を名乗ってもいいかもしれない！がんばろう。
うは、デックの実装に時間がかった。両方から出し入れできると、はじめに予想していた以上に先端ポインタと末端ポインタの兼ね合いの振舞がでてくんだな。C言語でやる場合の、作業量見積がまだできない状態ともいえる。

体調悪いが、こつこつ。

2008年7月29日火曜日

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

週明けたら仕事がいそがしい。牛歩戦術じゃないが、こつこつ。

NFA、というか、非決定性がむずかしい。考え方はわかるのだが、実際に具体的なNFAを構成しようとすると、えらくてこずる。非決定性というのは誰にとっても初めはそういうものなのならよいが、私の頭が悪くてそうだとしたら困るなぁ。Prologとかと関係あるのかな、と期待してがんばってみる。
1.13にはまった。。。一応解いたが、正解かどうかわからない。というのは、問題文をうまく理解できないからだ。これは日本語力の問題。すなわち求められている言語仕様を理解できているのかどうかがわからない。
「Fを、{0,1}上のすべての文字列のうち、二つの1の間には奇数個の文字が存在しないような文字列からなる言語とする」
これを日本語として整理すると、
- {0,1}上のすべての文字列のうち、二つの1の間には奇数個の文字が存在しないような文字列からなる言語
- {0,1}上のすべての文字列のうち、二つの1の間には奇数個の文字が存在することがない文字列からなる言語
- {0,1}上のすべての文字列のうち、「もし二つの1があるならば、それらの間には奇数個の文字が存在することがない」文字列からなる言語
で、よいのかな?
そうだとするとこれの補集合たる言語の仕様は、
- {0,1}上のすべての文字列のうち、「二つ以上の1が必ず存在し、それらの1と1の組合せの中には、間に奇数個の文字が存在することが少くとも1つは発生している」文字列からなる言語
で、よいのかな?
日本語力の問題でもあるし、論理力の問題でもある。。。
この仕様理解が正しければ、一応解けた。
ちなみに、はじめは補集合たる言語の仕様を
- {0,1}上のすべての文字列のうち、「二つの1が存在するならば、それらの間には奇数個の文字が存在する」文字列からなる言語
と考えた。これのNFAが結構難しかったけど、4状態でできた。
でも、それをDFAに変換すると6状態になってしまったのでした。

うむー、1.20まで行くつもりだったのだが、、、次回は1.14から。

2008年7月28日月曜日

【C算法】第4章スタックとキュー

こつこつ。

「スタックは、関数呼出しの内部でも使われていますし、再帰的アルゴリズムを非再帰的に実現する際にも使われる、基礎的で重要なデータ構造です。」パタヘネでもハードウエアのリソースの共有には退避復元機構としてスタックが使われていた。
gdbをつかっていると、gdb上でもうちょっとプログラミングができれば、CLのREPLプログラミングとかなり似たかんじなんじゃないかと思えてくる。
関数ポインタを知ったが最後、演習をやっていると「ここを高階関数にして」と頭が自動的に走ってしまう。それがいいことなのかどうかわからなくて、もっと素直な?Cの書きぶりに留めるように努力しつつ進めている。というのは、それならCLで書いてるのと頭の動きはあまり変わならなくて、ポインタとか使う分、手間なだけだから。
Cでプログラムを組むと、「ここでこのiはmax-1になって」とか添字というかインデックスを考えていることが多いような。
なんとか、「4-1 スタック」が終わった。。。

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

演習。

これ、思ってたよりもボリュームがある。4時間やっても1.7までしか進まず。でも、やっぱり演習っていうのは、理解が確実になる気がして、いい感じ。
l.4dの問題文は誤植と思われる。正しくは、「少なくとも一つのbが後ろにくる」。
正規表現で指定した言語のNFAを書くときは、その正規表現を部分に分割した上で部分NFAを作成して、それをまとめていく戦略をとったが、大抵うまくいかなかった。正規表現そのままを前からNFAに変換していく方がうまくいく。

人が何か能力を身につける、というのはやはりえらい時間がかかりそうだ。日々、こつこつ。

2008年7月27日日曜日

目標の整理 (Ver.2.0.2)

状態をアップデート。
基礎的な思考力を鍛えるとともに、アイデアの源泉となる知識が必要なような。OSは、いろいろ悩んだがタネンバウムのMinix3にしようと思う。

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」 (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」
- 「詳解シェルスクリプト」

【詳解シェル】11章シェルスクリプトとセキュリティ

こつこつ。

「Unixにとってセキュリティはとても面倒な問題です。Unixにまつわるほぼすべての作業でセキュリティの問題が発生する可能性があり、システム管理者はその対策に頭を悩めています」そなんだ。Plan9にいけと?
Chet Rameyのテンプレ、ありがたい。
シェルおよびシェルスクリプトでは、もう、基本的にはsetuidもsetgidもつかわん、と。
kshは特権モードがあり、setuidをセキュアに使うことが可能。

お、一応通読は終わった！
これも体で覚えなきゃ、なんだけど。でも嬉しい！

【C算法】第3章探索 (その2)

こつこつ。今日は「3-4 ハッシュ法」から。

このハッシュ法のところ、パタヘネの記憶階層のキャッシュのところと関連が強いな。
うーん。。。ポインタのポインタがいまいちしっくりこない。Node **pp = &h->table[key];とか。
- まず、typedef struct { int size; Node **table; } Hash; なので、Hashはここで定義した構造体の型をあらわすシンボルであり、Hash型のオブジェクトには、Hash h;なときはh.hash, Hash *hなときはh->tableにてアクセスできるオブジェクトが含まれている。ここで、tableはHash型の内部要素に対するシンボルであり、型は(Node **)である。
- さて、Node型について。typedef struct __node { Data data; struct __node *next; } Node;なので、Nodeはこれまたシンボルであり型をあらわしている。Nodeは__nodeの別名である。__node型は自己参照している構造体であり、Node n;のとき、n.nextは(Node *)型である。
- ここで、tableとかnextとかのシンボルは、誰が所有しているのかという疑問がある。おそらく、型の定義として処理系のどこかで一元管理されているのだろう。
- そして、シンボル管理機構では、シンボルと型とメモリ領域に関する情報が管理されている、と。
- なので、Node型のnextというのは型定義がもっており、Node n;としたときに(n,Node, <メモリアドレス>)というシンボル管理には含まれない。
- さて、Node n;のとき、n.nextはNode型の定義を参照して、シンボルnのメモリ領域の後半部分に格納されている値を指すことになる。すると、その値の型は何かという話題がある。それはNode型の定義に記述されており、(Node *)型という。*が付く型はメモリアドレスを値としてもつ。このメモリアドレスが指すメモリ領域はNode型として解釈可能なものとなるようにプログラマはメモリを構成しなければいけない。(ただしNULLも許容するものとする)
- そのことを前提にすると、n.next != NULLのとき、*n.nextによって、n.nextの値にあるメモリ領域についてそれをNode型としてアクセスできる。このとき、そのメモリ領域は、別途 Node n1;などとして構成されたもの、すなわちシンボル管理機構でシンボルとともに登録されているものでもよいし、callocなどで確保されただけの単なるメモリ領域でもよい。
- さて、Hash型に戻る。Hash h;のとき、h.tableは、シンボル管理、(h,Hash,<メモリアドレス>)を起点に処理される｡Hash型の定義の中に、tableは(Node **)型であることが記載されている。*がついてるのでこれもメモリアドレスを値としてもつ。ただし2つあるので、このメモリアドレスに格納されているのもメモリアドレスであり、その先にあるのがNode型で処理できるメモリ領域であるということ。
- ここまでの整理にて、Node **pp = &h->table[key];が理解できるか。
- まず、Node **ppは、(pp, (Node **), とあるメモリアドレス)を意味する。初期化子として式が記載されているので、そのメモリアドレスに格納する値もこの式できまる。
- 値について。&(h->table[key])が何かということ。Hash *hなので、h->tableによって、どこかのメモリ領域をHash型として処理して、そこのtable該当領域の値を指すことになる。table該当領域の型は(Node **)なので、table該当領域の値はメモリアドレスである。
- table[key]演算は、*(*table + key)と同じである。*(*table + key)は、tableが指すメモリ領域が、型Aの配列的な構造であることを期待しており、その先頭アドレスがtableであるところ、先頭Aから型Aの大きさにてkey個分さきのもののメモリアドレスに格納されている値という意味である。
- よって、[key]によって、h->table[key]は(Node *)型であるとしてのメモリアドレスに格納されている値に該当する。
- う、やっぱりわからない。
一応、ハッシュ法は理解したが、ポインタがやっぱりわからない。。。

こつこつ。

2008年7月26日土曜日

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

こつこつ。「1.2 非決定性」から。

NFAの定義を理解した。
NFAとDFAが等価であることを理解した。
正規言語のクラスが正規演算(和集合演算・連結演算・スター演算)について閉包であることを理解した。
クラスがある演算に対して閉包ということは、その演算の安全性が保証されることに加えて、そのクラスのそもそもの構造がうかがい知れるんだな。
正規演算を表現する記法として、正規表現を導入する。これは言語を値とする演算である。
「言語は、ある正規表現で記述されるとき、かつそのときに限り正規である。」
GNFAの定義を理解した。ただし、GNFAが「いくつかの文字を一つのブロックとして入力から読み出す」というところがわからない。「いくつか」って、いくつなの? とりあえずスルー。
ポンピング補題がなんとなくわかった。

これで一章を読んだ。明日は演習をやるぞ。

【C算法】第3章探索

こつこつ。早くプログラミングができるようになりたいなぁ。。。

探索というのは、例えば、OSのメモリキャッシュとかで重要なんだろな。
「線形探索法は、ソート済みでない配列から探索を行うための唯一の方法です。」
「必要となる比較回数の平均はlog nです」すいません、log nといわれてもわからんです。。。
お、関数ポインタだ！嬉しい！
ふむ。関数ポインタを使えば、関数を引数とする関数がCでもできるのだな。
関数名は関数ポインタなのか。なんと。
じゃあ、関数を返す関数もできるかなと思ってためしてみると、、、voidへのポインタ型を返却する関数という形であれば、動いた！！
ちょっとイレギュラーだけど、Cでも高階関数的なことができるんだね。
うむ、演習をやるのにGDBが役立つ。デバッガ、便利だなぁ。
complexityって計算量と訳すんだ。
うーん。やっぱりlog nがわからない。そもそも底は何なの? これはシプサでそのうちわかると思うので、スルーする。

今日は、「3-2 2分探索」まで。おもしろかった！　なかぱっぱ。

2008年7月24日木曜日

【詳解シェル】10章移植性と独自の拡張

こつこつ。

おお、bashはshellの状態を保存できるのか。
teeはしってたけど、プロセス展開ってここまでできるとはしらなかった。
bashの初期設定のファイルの役目が、それがどのようなシェルスクリプトで実現されているかが書いてある。ありがたい。

【emacs入門】13章ヘルプシステム

こつこつ。
これは大事。

help-for-helpは覚えとけ、と。
おお、コマンド名補完中のenter、、しらんかった。便利。

おお、これでemacs入門の通読がおわった。
これは、勉強になった。現時点でも、少し作業効率が改善している。
しかし、重要なのは、訓練だろう。スポーツと同じようなものかな。エディタは。
なので、これからは、

日々基本を訓練して体に覚えさせる。(常時)
新しい知識は、作業の必要に応じて吸収。(オンデマンド)

という方針にする。

【emacs入門】12章バージョン管理

文書リビジョン管理はsvn+svkを運用しているし、Emacsでのバージョン管理の習慣的なものはUnixの道具箱に詳しい。なので、この本の12章はやっても時間の無駄と思う。というわけでスキップ。

目標の整理 (Ver.2.0.1)

状態をアップデート。
集合30講を読了したところで、数学的力が全然足りてないことを痛感した。そんな頭では、プログラミングもへったくれもないような気がする。もう一段基礎から訓練しなおしたほうがいいかもしれない。

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」 (Cでアルゴリズムをやった後に実施)
Common Lispを理解したい。
- コンパイルを理解する。
  - 「パタヘネ」を理解する。
    - 上巻【通読完了】
    - 下巻【通読完了】
  - 「シプサ」を理解する。
    - 「集合30講」【完了】
    - 「計算理論の基礎 1」★途中
    - 「計算理論の基礎 2」
    - 「計算理論の基礎 3」
  - コンパイラの基礎を学ぶ
    - 「新コンピュータサイエンス講座コンパイラ」
- 「Lisp In Small Peaces」を理解する。
OSの基礎知識を得る
記述論理を理解する。
- 数理論理学の基礎知識をえる。
  - 一階述語論理とホーア論理を理解する。
    - 「ソフトウエア科学のための論理学」
      - 「論理学をつくる」 ★途中 (シプサの後に復帰)
  - 圏論を理解する。
    - 群・環・体の基本を知る。
    - 代数幾何の基本を知る。
    - 圏論の入門書を読む。
マネージメントを勉強する
- 統計学の基本をおさえる。
  - 「統計学入門」 ★途中
  - 数学的に準備する。
    - 位相の基本を知る。
    - ルベーグ積分を知る。
    - 確率論を知る。
生活環境の改善
- Emacs
  - 「入門GNU Emacs」 ★途中
- Shell
  - 「詳解シェルスクリプト」 ★途中
  - 「新Linux/Unix入門」
  - 「Linuxの教科書」
体で覚えるもの
- C言語
  - 「解きながら覚えるC言語」

【集合】第30講ゲオルグ・カントル

最終講。カントルの人生のお話。
最後のくだりでコンピュータに触れているのが感慨深い。

つぎに集合30講、読了。
感慨深い。。。

【集合】第29講連続体仮説

こつこつ、あらため、いっきに。

連続体仮説：アレフ1は(もしかして)アレフじゃないか?
一般連続体仮説：2^アレフa = アレフb (b = a + 1)、というのは任意のaについて成立するのでは。
「連続体仮説は、選択公理を仮定しておくならば、実数の集合Rの部分集合の中に、高々加算集合と、連続体の濃度をもつもの以外に、私たちがまだ出会ったことがないようなこの中間の濃度をもつ部分集合があるのか、と聞いていることになる」それはわかる。
「しかし、謎は、予想を越えて、はるかに深かったのである。」またですか。。。
で、集合とは何かをもっと厳密に調べることになった。
演繹体系にのせるために、公理をきめた。一般的なのは、ZF公理系。
すると、なんと、ZF公理系と(一般)連続体仮説は独立であることがわかった。独立であるというのは、ZFが無矛盾であればZFCも無矛盾ということを前提として
- ZFCに連続体仮説を加えたものは無矛盾である。
- ZFCに連続体仮説の否定を加えたものも無矛盾である。
- よって、ZFCによっては、連続体仮説が成り立つかどうか判別できない。

【集合】第28講選択公理からの帰結

選択公理が、無限の世界の基数と序数を結ぶ。
すなわち、基数の知見を序数の話題に利用したり、その逆もできるので、いろいろな定理を導出できる。
では、順序数の無限っぷりについては何かわかるのか。
そこで、濃度と順序数。
順序数の系列を考える。それは全ての順序数を含んでいるわけではないが、十分大きい順序数まで含んでいるとする。それ自体が整列しているのでそれを整列集合Ωと呼ぶ。
で、Ωが、非可算整列集合にたいする超限順序数を含んでいるくらい大きいとき、その非可算整列集合達に対応した超限順序数の全体を考える。それはΩの部分集合であり、S1と置く。
するとS1には最小限w1が存在する。
なので、このw1によるΩの切片に含まれるのは、有限順序数か加算整列集合の超限順序数かである。
ここで、Ωのw1切片に属する順序数を、高々2級の順序数という。おお! 順序数の系列が分類できた。
次に、順序数w1を与える整列集合の濃度をアレフ1とする。
ここでアレフ1は、"アレフ0の次にくる無限濃度である"し、"Ωのw1切片の濃度がアレフ1である"と。う、わからない。
で、この作業を繰返していくと、濃度の系列と超限順序数の系列ができ、かつそれらが一対一に対応していることがわかる。そして「濃度の集合は、大小関係によって、整列集合をつくる」となる。おお、ちょっとわからないところがあるが、見事だ。
「無限の生成」がおもしろい!
- 有限の順序数をすべて並べた集合を考える。{1,2,3,...}
- その濃度は、加算濃度アレフ0であり、その順序数はwである。
- 高々2級の順序数をすべて並べた集合を考える。{1,2,...,w,...,w^w,...,w^(w^(...^(w)...),...,ε0,..,ε0^ε0,...}
- その濃度は、非加算濃度アレフ1であり、その順序数はw1である。
- 以下同様に、より"大きい"無限が生成されていく。
こりゃ、すごいな。

【集合】第27講選択公理のヴァリエーション

こつこつ?

選択公理に同値な命題を、ツォルンの補題という。
前講で、"整列可能定理=>選択公理"を確認した。整列可能定理は選択公理と同値らしい。となると、"整列可能定理<=選択公理"を確認する必要がある。それをやる。
まず、"上端"を定義する。
順序関係はグラフを成すので、順序集合だからといって、またその部分集合がしめるサブグラフのあり様によっては、上端は存在しない。しかし存在するとしたら単一である。上端は部分集合Sに属することもあるし、属しないこともある。
続いて帰納的順序集合を定義する。
Mの任意の空でない全順序部分集合が必ず上端をもつとき、それを帰納的順序集合という。
これは、Mの順序関係をグラフとしてみたとき、順序を辿っていくと必ず端といえるものがある、ということ。それはその部分集合として端とみなしているだけで、グラフがそこで途切れていることをこれ自体が求めているわけではない。
で、帰納的順序集合定理。帰納的順序集合には極大元が存在する。
すると、"選択公理=>帰納的順序集合定理"がいえるとな。
う、極大元の存在の証明ははしょってある。鵜呑みにすることにする。
で、"帰納的順序集合定理=>整列可能定理"がしめせると。
そしていくつかのヴァリエーション。
「集合Mの部分集合に関する性質Pで、有限性の性質をもつものが与えられたとする。このとき、性質Pをみたす、Mの極大な部分集合が存在する」これすごいな。
「コンパクト空間の直積空間はコンパクトである」これもすごい。
「体K上のベクトル空間には、規定が存在する」これなんかは、もう選択公理をみとめるしかないのでは? と思えるが。

【集合】第26講整列可能定理と選択公理

こつこつ。

ほいで、ツェルメロが、「選択公理があれば、整列可能定理を導出できる」ことを示した。
これは、公理として何を置いていいのが数学の嗜みというか節度なの?ということの問題を引き起した。
この点でいうと、私は数学的実在または実在感というのは期待していないので、「便利だったり、それから導出される世界が豊かならいいじゃん」と思ってしまう。だけど、数学を本職でやっている人はそれじゃすまないんだろうね。
実在感を求めると、それはとどのつまり、科学になってしまうのではないか。まあ、物理学とかは、あちらはあちらで迷走してそうだが。
「集合論を、全く抽象的な枠組みの中で取り扱っている限り、選出関数を記述しようにも、記述する方法など何もないだろう。集合論のように、できるだけ普遍的な適応性をもたせようと、抽象化を目指すと、今度は逆に、その理論全体の中で通用するような、対象を具体的に明治する一般的な方法を、しだいに見失ってしまうのである。これは、無限の認識とは、また多少別の問題である。」これはabstract nonsenseであったり、圏論あたりのこともあてはまるのかな。
「整列可能定理=>選択公理」は簡単。

【集合】第25講比較可能定理、整列可能定理

実は、最後のところ、というか25〜30をいっきに読んじゃいました。
でも、なんかモヤモヤしちゃってうまくわかりませんでした。
この本と私の頭だけで、わかりきるのは無理だろうな、とは感じました。数学者さえ、戸惑っているような話題なので。
でも、せっかくなので、もうすこし理解してみたいので、続けます。

まず、切片を用いて順序数の大小関係が定義される、と。
この定義と整列集合の基本定理から、比較可能定理がみちびける。
で、これはそもそもの素朴な順序の概念の性質と一致しているので、いい感じ、と。
ところで、今、何しているんだけっけ?
基数とは別に、序数というものも無限にあるんだけど、その無限を調べているはず。
で、順序数をやっていると。
順序数の和と積を定義した。
ほいで、N={1,2,3,...}に対する超限順序数wを置いた。
そうすると加算集合についての順序数(=整列順序)は無限にわらわらとでてくる。
たぶん、ここで、それを調べていくにはカントル的には整列可能定理が必要に思えたのだろう。
整列可能定理：「任意の集合は、適当な順序をいれることにより、整列集合とすることができる」
ああ、違う観点でみれば、「任意の集合に、濃度が存在する」のと同じように「任意の集合に、序数が存在する」としたかったんだな。そのためには、あやゆる集合が整列可能でなければならんと。
で、基数を考えているときは整列なんぞ考えなくてもよかったが、序数を考え出すと整列を求めることになると。

こつこつ。

【シプサ】1 正規言語

こつこつ。

1.1 有限オートマトン
- 計算のモデルって概念、なんだか、わからない。
- Markov連鎖って有限オートマトンがらみだったんだ。
- 有限オートマトンの定義を理解した。
- たしかにこれはコンパイラ的というか正規表現的なものだ。
- とある言語を受理可能な有限オートマトンを構成する、という方向なのね。
- はじめの自動ドアの例によって、機械を有限オートマトンで記述できることはわかったけど、自動ドアと正規言語の関係がわからない。
- 有限オートマトンの計算、というのがいまひとつわからない。言語Aを認識する、とか文字列wを受理する、ということはわかるが、受理する、ということが計算の定義であるということがわからない。

明日は、1.2 非決定性。

【C算法】第2章基本的なデータ構造

こつこつ。

シプサで、フローチャートがグラフということがわかったので、ちょっとすっきり。
「高速なアルゴリズムは、より多くの記憶域を必要とする傾向がある。」
この章、いまひとつ面白くなかった。はじめちょろちょろ?

2008年7月23日水曜日

【シプサ】0 序論

あらたな本をこつこつ。

0 序章
- 0.1 オートマトン、計算可能性、複雑さ
- 0.2 数学的概念や用語
- 0.3 定義、定理、証明
- 0.4 証明のタイプ
- 演習
- 集合30講をやってるから、すいすいわかる。やっぱり勉強は重要だ。
- フローチャートって何なのかなって思ってたけど、これを読んで、グラフだということがわかった。なるほど。
- 文字列の集合を「言語」というのは、ちょっといきすぎではないか。
- 演習は0.7以外は完了。0.7は数日かけて考えることにする。
- しかし、この本、達者だなぁ！

【シプサ】開始

パタヘネの通読が終わったので、シプサを開始する。
本は、
「計算理論の基礎」
です。一回目は演習はやるが問題はやらないことにする。

【パタヘネ】今後

通読完了しての雑感。

よく書けてる本
MIPSの本
この本の内容はコンピュータに関わるエンジニアは理解しているべき。
今まで漠然とした認識だったものが、具体物として認識できた。

今後。

SPIMをつかってMIPアセンブリを一通り使えるようになるべし。
記憶階層は再読すべし。
あとはのんびり一年くらいかけて問題をやりながら楽しむべし。

2008年7月22日火曜日

【パタヘネ】8章外部記憶装置、ネットワーク、およびその他の周辺装置 (その4)

こつこつ。

8.5 プロセッサ、主記憶、そしてOSと入出力装置のインタフェース
- 翻訳の質がもどった。
- メモリ・マップ入出力という形で、入出力装置アクセスをメモリアクセスとしてしまう。OSのファイルの考え方みたいなのはこの階層にもあるんだ。
- この節、OSに対する要求が他の部分にくらべてとても明確。OSの肝は入出力管理ということか。
- DMAとバス・マスターの意味がわかった。
8.6 入出力性能の測定法
- 余談だが、Amdahl自体はわかるが、Amdahlと収穫逓減の関係がわからない。まず逓減がわからないのでしらべると、逓減=漸減ということで、むずかしい言葉なだけで意味は次第に減るということにすぎない。しかしwikipediaをみてみると限界主義というのが経済学的には中心にあり、それがわからないのでわからない。。。まあ、amadahlの法則はわかるのでいいか。
8.7 入出力システムの設計
- ここの設計でいっていることは、クリティカルパス法と同じかな。
8.8 実例：ディジタル・カメラ
- お、ここで三洋の例とは。
8.9 誤信と落とし穴
- この章の誤信と落とし穴、一番身にしみる。。。
8.10 おわりに
- 「2002年に生み出された情報の量は5エクサバイトであり、過去3年間で全世界の情報量は倍増したとのことである」
- これが2002年までの話で、これからBRICsもあるとすると、(情報)世界は破滅に向っているような。

おお！！　ついにパタヘネ上下とも通読が終わった！！！

【詳解シェル】9章ファイル操作

こつこつ。

stat、標準化されればいいのに。
おお。OSXの内部時計は32bitだ。。。
OSXのtouchはGNUじゃない。BSDってことか? BSDである、っていうことはどういうことなんだろ。
「findコマンドには60種にも上るオプションが用意されいることもあり、」うむー。
OSXは、"find"単体はダメ。"find ."とした。
ありゃりゃ。findは本に書いてあることとOSXでの実際が全然違う。。。両方ともPOSIXなんじゃないの? GNUとBSDの違い???
finkにfindutilsがあったが、私の/sw/bin/にはない。ちょっとしらべたが、fink自身のupdateが必要なもよう。というわけで、finkのselfupdate。compileの間、先の方をみとくかな。
ということで、xargs以降をさきにやっとく。
東大のbindist reposigoryがなんかおかしげで、findutilsのインストール失敗。bindistのrepoをmasterに再設定して成功。
をを！　本のとおり動く。。。
finkをupdateしたら、.bash_profileで/sw/bin/init.shの実行がアクティブになった。これ、中をみるとPATHがprependなので、とりあえずコメントアウトしておく。

【emacs入門】11章 Emacs Lisp プログラミング (その6)

「11.6 既存のモードのカスタマイズ」から。

ここは、hookと、elispのお話を少々。
特にあたらしい知見はなし。

11章はずいぶん刻んだなぁ。次は12章バージョン管理。

【集合】第24講順序数

一歩一歩が目標に辿りつくと信じて、こつこつ。

順序数を定義する。
整列集合が、順序集合として同型のとき、それらは同じ順序数を持つという。
整列集合{1,2,...,n}(順序は通常の大小関係)と同型な整列集合は、順序数で言うとnである、と言う。
すなわち、有限順序数1, 2, ..., n, ...は、整列集合のパターンをしめすものである。
空集合も整列集合とみなすとき、これの順序数を0とする。
整列集合{1,2,....}の順序数をwと定義する。wを超限順序数と呼ぶ。
順序数の和を定義する。
順序数αとβにたいして、和α+βとは、「順序数αである集合Mと順序数βである集合Nをもってきて、MとNの直和集合(M,Nの順)について、Mの元ならNの元よりも常に小さいという順序の拡張のもとにこれに付与される順序数をα+βと呼ぶ」と定義する。
αとβがともに有限順序数のとき、α+βは、ふつうの数としての和に等しい。
これから、順序数への和の拡張は、自然な概念拡張と言える。
αが超限順序数wであり、βが有限順序数nでるとする。
すると、α+β (w+n)なる順序数は、{1,2,...,1,2,...,n}なる集合の順序数である。n+w ≠ wである。
一方、β+α(n+w)なる順序数は、{1,2,...,n,1,2,...}なる集合の順序数である。n+w = w である。
w+n ≠ n+wである！
順序数の積を定義する。
まず、整列集合A,Bがあるとき、その直積集合BxAに対して、辞書的順序を考える。
辞書的順序において、BxAは全順序集合である。
また、同時に、BxAは整列集合である。これは、(b,a)において、まずbでソートして、bが同じならばaでソートということでわかる。AもBも整列集合なのだから、BxAの任意の部分集合について、それのb軸a軸の射影は整列集合であり、さきのソートルールから最小限が存在することがわかる。
さて、順序数の積の定義。
順序数αとβにたいして、積αβとは、「順序数αである集合Aと順序数βである集合Bをもってきて、BとAの直積集合(B,Aの順)について辞書的順序を導入したときの順序数をαβとする」と定義する。
有限順序数の積は、ふつうの数の積になっている。
ちなみに、有限な整列集合の型は、個数(基数)だけで完全にきまる。なので、基数と序数とを一体に考えている。
さて、αが超限順序数wであり、βが有限順序数2であるとする。
すると、αβ (w2)なる順序数は、{(1,1), (1,2), ..., (1,n), ..., (2, 1), (2, 2),..., (2, n), ...}なる集合の順序数である。
これは順序数の和の定義を思い出すと、w+wである。ゆえに、w2 = w + w。
次に、βα (2w)なる順序数は、{(1, 1), (1, 2), (2, 1), (2, 2), ..., (n, 1), (n, 2)...}なる集合の順序数である。これの順序数はw。ゆえに、2w = w。
よって、一般には、αβ ≠ βα。
順序数の系列を考える。
まず、1,2,...,n,...。
次は超限順序数を加える。1,2,...,n,...,w。
和を考える。n+w = w なので、w+nだけ考える。すると、1,2,...,n,...,w,w+1,...,w+n,...。
超限順序数の和も加える。1,2,...,n,...,w,w+1,...,w+n,...,w+w。
積を考える。nw=wだから。wnだけ考える。w2=w+wだから、1,2,...,n,...,w,w+1,...,w+n,...,w2。
和を考える、と繰返していくと次のとおり。
1,2,...,n,...,w,w+1,...,w+n,...,w2,w2+1,...,w2+n,...,w3,...,w4,...,wk,...,ww,ww+1,...,www,...,w^4,...,w^k,...
ここで厳密な定義は本にはないが、順序数のベキがあるらしい。w^wというのも可算集合のある並べ方のパターンらしい。
すると順序数の系列は、...,w^w, ...,w^w^w, ..., w^w^w^w, ..., w^w^...^w,... と延びていく。
さらに、ε0 = w^w^w^... と置くと、ε0, ...,ε0^ε0,...というように系列が延びていく。
これら全てが、可算集合に対するある整列順序に対応している。
まあ、加算集合から連続体にうつるところの過酷さからすれば、加算集合の整列にこれだけのバリエーションがあるのは納得。

2008年7月21日月曜日

【パタヘネ】8章外部記憶装置、ネットワーク、およびその他の周辺装置 (その3)

こつこつ。

8.4 プロセッサ、メモリ、入出力装置間のバスその他による接続
- う、この節になって急に翻訳の質が落ちた。
- バスの意味を再確認できた。

【C算法】第1章基本的なアルゴリズム

思えば、C言語三冊目だ。再度気を引き締めていこう。

双岐選択か。いろいろな言葉があるもんだ。
JIS X0001のアルゴリズムの定義：「問題を解くためのものであって、明確に定義され、順序付けられた有限個の規則からなる集合。」
そうだ、この本を学習するときはGDBもつかうことにしよう。
「中央値（ちゅうおうち）(median) とは代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば５人の人がいるとき、その５人の年齢の中央値は３番目に年寄りな人の年齢である。」(wikipedia)
そうか、中央値となると、それはソートの問題なのね。
フローチャートてなんなんだろ。フローチャートで書かれたことを言語で実装するって何なんだろ。
C言語では、双岐分岐->if文、前判定繰返し->while文、後判定繰返し->do文、とな。
while文とfor文は可換。
繰返し記号->for文。
これ、MIPS上で勉強したら、パタヘネとの関連もできて一石三鳥くらいなんだろうなぁ。

実践Cが終わったので、いよいよアルゴリズムとデータ構造の勉強をすることになった。
本は、「新版 C言語によるアルゴリズムとデータ構造」にした。
理由は、柴田望洋さんの本で入門したので、ある程度力量が上がるまでは同じ著者でいきたい、というのが大きい。

この本はアルゴリズムとデータ構造の分野において基本的な部分に重点を置いていると予測している。なので、この本にかかれていることはきっちりと理解しないと先に進めない。

さて、序章。

体験学習ソフトウエアのUnix用があればなぁ。しぶしぶ、久しぶりにWinXPを起動する。といってもParallelなんですが。
久しぶりのWinXPなので、操作に手間取る。。。
あ、こういう絵的な説明があるのはわかりやすい!

【詳解シェル】8章実践的なスクリプトの例 (その3)

こつこつ。

ログファイルの名前は秒までの日時を含めるとして、分離する。ファイル名の衝突を避けるために、ログファイル生成前には1秒のsleepをかける。頭いいなぁ。
「1度に3つものシェルを扱うというのは非現実的です。」
sshコマンドで、ここまでのシェルスクリプトを渡すという発想がなかった。そしてログはリダイレクトでインストール元に集約できると。

うーん。知らないことが多すぎるなぁ。こつこつ。

2008年7月20日日曜日

【emacs入門】11章 Emacs Lisp プログラミング (その5)

メジャーモードだ！

ちっちゃなもんでもメジャーモードをひとつ作ってみれるのはうれしいなぁ。
う、calc-modeで括弧の位置をまちがえていてデバッグに時間がかかった。elispのデバッグ方法も学ばないと。

「11.6 既存のモードのカスタマイズ」の前まで。

【パタヘネ】8章外部記憶装置、ネットワーク、およびその他の周辺装置 (その2)

今日はHDDに強くなるぞ！

しかし、あらためてHDDの仕組みをみると、えらい機械的な装置だな。よく動いているな。。。
むぅ。あんまり新奇な情報はなし。

こつこつ。

【集合】第23講整列集合の基本定理

こつこつ。

昨日からの続き。
そんな整列集合には次のような性質をもっている。これを基本定理という。
2つの整列集合(M,Nとする)の間の関係は、次の3つのうちのどれかひとつである。
- Mは、Nのとある切片と同型である。
- MとNは同型である。
- Nは、Mのとある切片と同型である。
えっと、切片って何だったかというと
「Mを整列集合とする。そのとき、任意のa∈Mに対してM<a>={x|x<a}とおき、M<a>を、Mのaによる切片という。」
そして、切片の基本的な性質は、Mを整列集合とするとき、
- Mの部分集合Sが、(b∈Sであるbにおいて、(x<b ならば x∈S))という性質をもてば、S=Mか、あるいは、あるa∈Mが存在してS=M<a>。
- M<a>とM<b>が順序集合として同型ならばa=b。
- 切片M<a>はMと同型にならない。
こうやってみてみると、切片というのはある意味、埒外の最大元みたいなものかな。M<a>は整列集合Mの部分集合だからこれまた整列集合であるから、最小元をもつ。ところでM<a>の要素は元aより小さいものを全部集めたものだから、aは最大元みたいなものだけどM<a>自身には含まれていない。
で、それは元に対して一意に決まる。そこで、整列集合の元aを考えたり調べたりするとき、元a自身ではなくて、M<a>を通してやるという手法がある。
元a自身を調べるよりもこの方が便利なことがある。というのは、aの御付きの人であるM<a>は、aに至る順序情報をもっており、単なる元aではなく「整列集合元a」のあり様が含まれているから。
さて、これら基本を確認した上で、基本定理の証明を理解しようとする、が、全然わからない。
そこで、自分なりに少し考える。
あれ？この基本定理はアタリマエじゃないか？
アタリマエか、確認してみる。
- MもNも整列集合なのだから、両者とも、どのような部分集合をとっても最小元をもつ。
- M自身N自身の最小元をそれぞれm1,n1とすると、{m1}と{n1}は同型である。ここでそれぞれの補集合をM1,N1とする。
- 続いて、M1自身N1自身の最小元をそれぞれm2,n2とすると、{m1,m2}と{n1,n2}は同型である。ここでそれぞれの補集合をM2,N2とする。
- これに超限帰納法を適用して言えるのは、"2つの整列集合があるとき、それらの中で最小元から順序にしたがってピックアップした部分集合どうしは同型である"ということ。
- そうすると、構成的に考えれば、「Mの全切片集団に対して、同型なものがNにも存在している」または「Mの切片の中で、Nには存在しないものがある」しかない。
- あり? これだめだな。
- 「切片」とか「整列集合」について、無限というものに対応できるよう概念拡張する前のものを使ってしまっている気がする。
なるほど、切片や整列集合に関する抽象化された性質だけを使って証明せねばならんのか。その観点で証明を追ってみる。
- MとNの切片の対応は次の3つの場合しかおこらない。
  - (A) Mの各切片に対して、それと同型なNの切片が存在する。
  - (B) Mの各切片に対して、それと同型なNの切片が存在し、逆にNの各切片に対して、それと同型なMの切片が存在する。
  - (C) Mの切片で、Nのどの切片とも同型にならないものが存在する。
- ああ、なんで証明がわからないのかわかった。そもそもこの3択にしぼってよいことが理解できないのだ。
- で、ちょっと考えてみたけど、自然数的というか上で述べたように構成的に考えてよいなら、この3つの場合しかおこらないことがいえる。しかし、概念拡張したとして構成的に考えられない状況では、この3つの場合しかおこらないかどうかは私にはわからない。
- というわけで、ここは「よくわからん」ということで後々考えることにする。

数学の勉強というのは、そう簡単には進まないなぁ。まあ自身での概念建築の量と質が他の分野よりも大きいからなぁ。こつこつ。

目標の整理 (Ver.2.0.0)

足りないもの、も多少組み入れて整備。
むむむ。これ本当は専門学校とか大学とか行って学んだ方が早いかも？

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」 (Cでアルゴリズムをやった後に実施)
Common Lispを理解したい。
- コンパイルを理解する。
  - 「パタヘネ」を理解する。
    - 上巻【通読完了】
    - 下巻 ★途中
  - 「シプサ」を理解する。
    - 「集合30講」★途中
  - コンパイラの基礎を学ぶ
    - 「新コンピュータサイエンス講座コンパイラ」
- 「Lisp In Small Peaces」を理解する。
OSの基礎知識を得る
記述論理を理解する。
- 数理論理学の基礎知識をえる。
  - 一階述語論理とホーア論理を理解する。
    - 「ソフトウエア科学のための論理学」
      - 「論理学をつくる」 ★途中 (シプサの後に復帰)
  - 圏論を理解する。
    - 群・環・体の基本を知る。
    - 代数幾何の基本を知る。
    - 圏論の入門書を読む。
マネージメントを勉強する
- 統計学の基本をおさえる。
  - 「統計学入門」 ★途中
  - 数学的に準備する。
    - 位相の基本を知る。
    - ルベーグ積分を知る。
    - 確率論を知る。
生活環境の改善
- Emacs
  - 「入門GNU Emacs」 ★途中
- Shell
  - 「詳解シェルスクリプト」 ★途中
  - 「新Linux/Unix入門」
  - 「Linuxの教科書」
体で覚えるもの
- C言語
  - 「解きながら覚えるC言語」

目標の整理

ちょっと修正と更新。

linuxのptyアプリを書きたい。
- 詳解UNIXを勉強する。
  - C言語を勉強する。
    - 明解 C言語入門編【完了】
    - 明解 C言語実践編【完了】
    - UNIXの道具箱を読む。★途中
NorvigのAIを読みたい。(Common Lispプログラミングの書きぶりを知りたい)
- アルゴリズムとデータ構造について勉強する。
  - C言語の基礎を勉強する。【完了】
  - C言語でアルゴリズムとデータ構造をやる。★途中
- Common Lispについて基本を復習する。
  - 初めての人のためのLISPを読む。★途中
  - Common Lisp Drillをやる。(Cでアルゴリズムをやった後に実施)
Common Lispを理解したい。
- コンパイルを理解する。
  - パタヘネを理解する。
    - 上巻【通読完了】
    - 下巻 ★途中
  - シプサを理解する。
    - 集合30講を読む★途中
  - コンパイラ本を何かやる。
- Lisp In Small Peacesを理解する。
記述論理を理解したい。
- 一階述語論理とホーア論理を理解する。
  - ソフトウエア科学のための論理学を勉強する。
    - 論理学をつくるを勉強する。★途中 (シプサの後に復帰)
マネージメントを勉強する
- 統計学：統計学入門を読む ★途中
生活環境の改善
- Emacs
  - 入門GNU Emacsを読む ★途中
- Shell
  - 詳解シェルスクリプトを読む ★途中
体で覚えるもの
- C言語：「解きながら覚えるC言語」をやる

【実践C】第14章コンソール画面の制御

最終章！

list1401。私の環境では、emacsのshell modeでは駄目で、screen上はOK、ターミナルももちろんOK。
そっか、ソースが複数あるときは、gccに複数渡してあげればいいんだ。gcc -Wall -g list1403.c clearscreen.c -o clearscreen

おお！ついに実践編が終わった！
これでC言語入門者というか入門済みにはなれたかな。

2008年7月19日土曜日

【emacs入門】11章 Emacs Lisp プログラミング (その4)

11.5の手前まで写経。
CLをやっているから、template.elをまあ理解できるが、なんもやってなくてこの本読んでも、この例は理解できないだろうなぁ。いいのかね。

こつこつ。

【パタヘネ】8章外部記憶装置、ネットワーク、およびその他の周辺装置

こつこつ。

8.1 はじめに
- 入出力装置を分類するための三要素。
  - 入出力動作: behavior
  - 入出力の相手: partner
  - データ転送速度: data rate
- 入出力装置の評価指標として何を用いるかは、アプリケーションによる。
- スループットを重視するアプリケーションがある。
- スループットを重視する場合は、もっとも重要な指標は入出力バンド幅である。
- あり?バンド幅って何だっけ? (wikipedia: そもそもは周波数の範囲のこと。デジタルでは曖昧であり伝送路容量を表すことも多い)
- おや?スループットって何だっけ? (wikipedia: 一定時間内に処理できるデータ量のこと。)
- 入出力バンド幅の測定方法は二種類ある。
  - ある時間内にどれだけの量のデータを転送できるか。これが伝送路容量か。
  - 単位時間当たりに何回の入出力操作を行えるか。これはなんだろ、周波数?
- 応答時間を重視するアプリケーションもある。
- この場合、1アクセスあたりの所要時間を小さくすることが有効である。
- ただし入出力リクエストが非常に大量にある場合は、バンド幅にも左右される。
- デスクトップコンピュータなどの単一ユーザの場合は応答時間が重要である。
- 高いスループットと短かい応答時間の両方を必要とするアプリケーションもある。
- Webサーバとか。

【集合】第22講整列集合の性質

こつこつ。

自分が何をやっているのか、よくわからなくなってしまったので、再整理。
まず、自然数は序数の機能ももっている、という経験則。
序数とは順序の数であり、順序という概念を運用するために利用できる数のこと。
で、順序という概念自体そもそも何なのさ、ということをやらねばならない。
自然数Nというのは、{1,2,3,...,n,...}であり、経験則とおりに順番が付いているものとする。
すると加算集合を並べるというのは、Nから対象集合への一対一写像を与えることである。
並べる、という観点から言うと、その一対一写像は次の3つに分類できる。
- ぴったり：{a1,...,an,...}
- 有限あふれ：{a1,...,an,...,*,...,*}
- 無限あふれ：{a1,...,an,...,*,...,*,...}
このように加算集合を並べる、ということは有限集合を並べる、ということとはちょっと違う。
順序数という考えを導入する。nは単一の元を表しているのではなく、1,2,3,...,nという順序のあり様の識別子であるとする。
すると加算集合Nの順序数はなんですか、ということになるが、これをwと定義してしまう。これを超限順序数と呼ぶ。
自然数Nをwとしても並べられるし、w+wとしても並べられる。自然数Nの順序数はwでもあるしw+wでもある。
ここで、順序というものを定義してみる。
集合Mの2つの元の間に成り立つ関係r(x,y)が与えられていて、それが次の性質を満たすとき、関係rを順序と呼び、"Mは順序集合である"という。
- r(x,x)は真である。
- r(x,y)とr(y,x)がともに真ならば、xとyは同一の元である。
- r(x,y)とr(y,z)がともに真ならば、r(x,z)も真である。
さて、順序集合は、"Mの任意の2元について順序が存在する"ことまでは求めていない。
これを求めるものを全順序集合と言う。
順序集合M,Nがあり、それらの間の一対一対応が存在し、なおかつその一対一対応のうち、それぞれの順序関係を維持するものがあれば、"MとNは同型な順序集合である"という。
ここで、同型な順序集合であるためには、MとNとがどのような順序関係を採用しているかによることに注意。
整列集合を定義する。
全順序集合Mにおいて、Mの任意の部分集合S(空集合ではない)が最小元を持つとき、Mを整列集合という。
{1,2,...,n}は有限順序集合であり、整列集合。
N={1,2,...,n,...}は無限順序集合であり、整列集合。
wを適当な記号として、M={1,2,...,n,...,w,w+1,...,w+n,...}という新な集合を考える。順序はこの並びにしたがって定義されているとする。するとこれも整列集合。
同様にして、M'={1,2,...,n,...,w,w+1,...,w+n,...,2w,2w+1,...,2w+n,...}も整列集合。
M'と同型な整列集合の例：
{1/2, 2/3, ..., (n-1)/n,...,1,1+(1/2),...,1+(n-1)/n,...2,2+(1/2),...,2+(n-1)/n,...}
この例って、3w,4w,...と無限に増やせていけるよね。
すると、それぞれの区切り単位ではNと同型な整列集合であるものが、可算個つながっているようなナガーイ順番をもった行列というか整列集合ができる。それは、数直線上の点列と考えられる。
とこで、区間(0,1)とR+={x|x>0}は、y=tan((π/2)x)なる写像によって同型な整列集合である。
するとさっきのナガーイは、区間(0,1)内にそれと同型な整列集合を持つことになる。
そいつと同型なものは、(1,2),(2,3),...にも存在している。なので、それらをつなげていくとトテモナガーイ整列集合ができて、数直線上を無限につながっている。
そのトテモナガーイは、また(0,1)に同型の整列集合をもち、、、、以下(同)
で、この奇妙な再帰構造があることはわかったが、それが何を意味するかはまだわからない。
ちょっと調べてみる。
NとMは、基数でいえば同じ加算集合だが、"同型な整列集合"ではない。
これは、"同型な整列集合同士は、順序をたもつ一対一対応が存在する"ということと、"整列集合では任意の部分集合に最小元が存在する"の2つからほぼ当然。
ところで、集合というのは元という区別できるものからできているということがいろいろきいていて、整列集合から最小元をひとつひとつ(ここが区別できるということ)分離していくことができる。無限集合であれば分離したものがNと同型になったときに尽きるか、Nと同型になってもまだ残りがあって、それについて分離作業をすすめるかというケースがある。
さて、整列集合の性質として、帰納法がなりたつということがある。この"定理"を超限帰納法と呼ぶ。
また、よく考えると、整列集合の性質として次のものがあることがわかる。
- 自分への同型対応となるのは、φ(x)=xというトリビアルなものだけ。
- M,Nが同型な整列集合ならば、MからNへの同型対応はただ1つしかない。
すなわち、順序を保つということと任意の部分集合が最小元ともつということの縛りは強くて、そう勝手に考えられませんよ、ということ。
続いて、"整列集合の切片"の定義。
ある元よりも順序が手前の元を全部集めたものを"aによる切片"という。aは含まない。

というようなことをやっているのか。こつこつ。

【実践C】第13章 2分探索木

線形リストは、Lispのリストとはちょっとしか似てなかった。もしや二分探索木がそうなのかも、と期待して。

おお。やっぱコンスセルにちょっと似てる。
関数も再帰的になっているので、綺麗に見える。
「このように、真に再帰的な関数(関数の中で、二度以上自分自身を再帰的に呼び出す関数)を非再帰的に実現するためには、スタックを用いることになります。」
むむ? 二分探索木でキー値が同じときはどうなるのかな。と思ったら登録できないんですね。
うーん。このくらいの長さのプログラムでも、すでに、頭の中にまとめて入れるのに難儀する。もっと慣れと訓練が必要。

こつこつ。あと一章。

C言語の意味(論)

Cをやってみて感じるのは、意味を考えるとき、メモリとかレジスタとかデータ・パスとか、いわゆるプログラム内蔵式の計算機を考えている自分がいるということですね。意味論というものの価値を私はうたがっており、Cプログラマにおける意味論というのはこの程度で済んでしまってOKなものじゃないかなと思うのです。

まあ、もちろん価値といったとき、誰におけるどのような価値か、ということが重要なのですが。意味論が好き、という人にとってはもちろん意味論の価値は高いのでしょう。私も結構好きですが。

【詳解シェル】8章実践的なスクリプトの例 (その2)

「8.2 ソフトウエアのビルドを自動化する」から。

いわゆるtar玉って「GNUプロジェクトで採用されたパッケージ形式」だったんだ。
おお、"The GNU Coding Standards"というのがあるんだ。うーむ。ものをしらないな。。。
私の環境では、archが"i386"と言う。64じゃないのかleopardは。machineは、というと"i486"。。。
この定型的に繰り返されるオプションのコードパターンは、シェルスクリプトの機能では抽象化できんのか?

う、だめだ。本体コードの写経が終わったところで、頭痛がする。。。ここまで。

【emacs入門】11章 Emacs Lisp プログラミング (その3)

「11.3.3 標準ライブラリは宝の山」から。

find-libraryがすでにあったので(find-func.el)、find-library-fileの導入は止めにした。
言語に関わらず、ソースをみたときの「わかるな」感がちょっとずつ上がっていっているように感じる。

明日は「11.4 自動テンプレートシステムの構築」

2008年7月18日金曜日

【実践C】第12章線形リスト

Cをやってたらリストに出会った。楽しみ。

うん。ポインタ版の方が配列版よりも明快。
並べ替えとか必要なときは、アプリのプログラミングのときはdbmとかRDBをつかっちゃうかも。でももっと下の階層のプログラミングだとそんなもの使えないので、こうやっているんだろうなぁ。
う、探索アルゴリズムに付いていけない。。。アルゴリズムの勉強はこの後やるということで、ここは突き詰めずに進んじゃう。

こつこつ。

【パタヘネ】7章容量と速度の両立：記憶階層の利用 (その4)

こつこつ。

7.4 仮想記憶
- お、プロセス、が出てきた。
- 「ページがいつ置き換えられるかは、あらかじめ知ることができない。したがって、OSは通常、プロセスを作成するときに、そのプロセスのすべてのページ用の領域をディスク上に取る。このディスク領域をスワップ空間という」おお、全部はじめから取っておくのね。
- 「誤解しないように付け加えると、オペレーティング・システムは単に別のプロセスにすぎず、メモリを制御するページ表はメモリ上に置かれる。」うむ。
- そうだよね、仮想記憶というのは記憶保護機構でもあるんだよね。
- コンテキスト・スイッチの説明などを読むと、想像していた以上に、プロセッサとOSは密に連携して機能を成しているのだな。
- 最後の追い込みのところが、ぐだぐだになったけど、昨日よりはマシ。

この節も長かった。明日は7章の最終局面へ。

【集合】第21講整列集合

こつこつ。

順序集合、整列集合と進んでくると、Nが、私が知ってる自然数の概念に近くなってきたな。
「同型な整列集合」というときの、同型というのがあやしい。なんだっけ?
「このようにして、整列集合は、果てしなく延びていく」これは私が知っている自然数の概念ではない。。。
ああ、ここでの同型は「一対一対応で、順序を保つ」ということなのね。

わかったような、わからないような。

【詳解シェル】8章実践的なスクリプトの例

こつこつ。

8.1のpathfindをやる。おもしろい。けど、自分でこれがつくれるようになるかなぁ。shellは難しい。。。

2008年7月17日木曜日

【emacs入門】11章 Emacs Lisp プログラミング (その2)

こつこつ。

「lisp文字列用の正規表現構文とユーザコマンド(replace-regexpなど)用の正規表現構文には重要な違いが存在します。」
ああ、そうか。elispのreaderが読んだ後の文字列が正規表現であるように、'\'を配置するんだ。readerが読んだ結果を、次に渡すと。
それとは違い、mini bufferからの入力はそのままを次に渡す、と。
おお、^$とかを文脈、というのか。
。。。いまいち、この本の説明わからん。。。そこで、infoのelispをみてみる。
- 正規表現には二種類のcharacterがある。ordinary charactersとspecial characters。
- Special charactersは次のとおり。
  - どこでもspecial。
    `.', `*', `+', `?', `[', `^', `$', and `\'
  - 条件によってspecial。
    `]', `-', `[:', `:]'
- [ ... ] は a character alternativeである。
- character alternativeの中では、先のspecialはspecialでなくなる。ordinaryになる。character alternativeの中でspecialなのは、
  `]', `-', '^'
  である。
- character alternativeの中で、specialになっている文字をordinaryとしてcharacter alternativeに含める方法は次のとおり。
  `]' : 先頭に置く : 例 `[]a]'
  `-' : 先頭か末尾に置く : 例 `[-a]' `[a-]'
  `^' : 先頭以外に置く : 例 `[a^]'
- `\'には2つの機能がある。ひとつはここまでに紹介したspecial character(character alternativeの中のものは除く)をエスケープすること。もうひとつは、ここまでに紹介した以外のspecial characterを表現すること。
- `\'との連続によってspecialになるのは次のもの。
  - 文字に関するもの
    `\|' `\{M\}' `\{M,N\}' `$ ... $' `$?: ... $' `\DIGIT' `\w' `\W' `\sCODE' `\SCODE' `\cC' `\CC'
  - 文脈に関するもの
    `\`' `\'' `\=' `\b' `\B' `\<' `\>' `\_<' `\_>'
- elispのread syntaxでは、文字列の構文において、`\'に特別な意味を与えている。直後の文字をエスケープする、という意味だ。よって、正規表現をelispの文字列で表すときには、正規表現の中の`\'を`\'でエスケープしなければならない。
おお、infoの方が本よりわかりやすい。
本がわかりにくいのは、「演算子\\<」とか、書くから。「演算子\<」と書いてくれればよくて、それを正規表現文字列にするときに、"\\<"とかしてくれればよい。

明日は「11.3.3 標準ライブラリは宝の山」から。

【実践C】第11章ライブラリ開発の基礎

おお、ついにライブラリ。

おお、配列上でキューの頭とお尻の位置を動かすのか。頭いいな。
「C言語は、モジュール型プログラミングを言語レベルでサポートしない。」なんと。
ライブラリで使う識別子の頭にいちいち"__"をつけるのは、いかにも汚ない。。。
うーん。この章のサンプルをgccでコンパイルする方法がわからない。。。

。。。こつこつ。

【パタヘネ】7章容量と速度の両立：記憶階層の利用 (その3)

こつこつ。

7.3 キャッシュの性能の測定と改善
- ストール (stall)：航空機が失速すること。自動車などで、エンジンが急に停止してしまうこと。
- CPU時間 = (CPU実行クロック数 + メモリ・ストール・クロック数) * クロック・サイクル時間
- メモリ・ストール・クロック数 = 読み出しストール・クロック数 + 書き込みストール・クロック数
- 読み出しストール・クロック数 = プログラム当たりの読み出し件数 * 読み出しミス率 * 読み出しミス・ペナルティ
- 書き込みの場合は方式による。
  - ライト・スルー方式。
    - ストールの原因は2つ。書き込みミスと書き込みバッファのストール。
    - 書き込みストール・クロック数 = (プログラム当たりの書き込み件数 * 書き込みミス率 * 書き込みミス・ペナルティ) + 書き込みバッファ・ストール
  - ライト・バッファ方式。
    - ストールの発生は、書き込みの頻度だけでなく、書き込みのタイミングにも影響されるので、単純な式にはならない。
    - 十分なライト・バッファならば、ストールはわずかであり、無視してよい。
  - ライト・バック方式。
    - ストールの発生は潜在的である。キャッシュ・ブロックの置き換えのタイミングで発生する。
- 「遺憾なことだが、標準的なアルゴリズム分析では記憶階層の影響は無視されている」

この節、長い。。。後半ぐだぐだになった。まずは通読ということで、先へ進む。

【集合】第20講順序集合

こつこつ。

「カントルは、無限集合に対する序数 -超限順序数- を導入する登山口を、整列集合という大道から近づいて見出そうとしたのであるが、(以下略)」
そうか、大きい小さい、というのは順序が与えていたのね。
山手線(環形態)の駅の停車順は、順序の定義から外れていると。

おお、2/3終わった。残り10講！

2008年7月16日水曜日

足りてなさそうなこと。2

前回のもので確実に必要なのは、、、

位相
代数(群・環・体あたり?)
ラムダ算法
自然言語を対象とした言語学。認知言語学とか。
オブジェクト指向
OSの基礎知識

これらかな。
考え方によるのは、

微積分
グラフ理論
Java
オブジェクト指向
Intelアーキテクチャのアセンブリ言語

かな。必要性が増しているのは、

代数幾何
正規表現
トランザクション
並列プログラミング
英語力
日本語力

全体を俯瞰してみると、OSに対する知識の無さがいかんともしがたい欠落と思える。。。

【実践C】第10章スタックオーバフロー

C言語入門者脱却を目指して、こつこつ。

「プログラムの内部では、スタックが使われています」微妙な表現だなぁ。
パタヘネ上巻が終わっているので、このあたり、よくわかる！
というか、パタヘネの上巻をやってなかったら、この章の理解は違ったものになっていたはず。ということはどういうことなのだろうか。良質の理解をするためには、最下層から積み上げるしかない、ということなのか。

【パタヘネ】7章容量と速度の両立：記憶階層の利用 (その2)

学習が中期にわたってくると、惰性作業の気がでてくる。学習など滅多にできないので、ひとつひとつの事柄に一期一会で接しなければ。こつこつ。

7.2 キャッシュの基礎
- キャッシュとメモリ、メモリ幅とバス幅、SDRAMとDDR-SDRAM、ということの意味と違いがちゃんとわかった。

【集合】第19講加算集合を並べる

こつこつ。

そうか。序数という概念を「無限」に拡張することはまた別の話なのね。
序数では、元の区別を考えず並べる。量子論的粒子ということか。
「基数と序数が一対一に対応している状況は、無限になると崩れてくる」
超順序数w。
2,4,6,...,2n,...,1,3,5,...,2m+1,... は順序数w+wに従う並べ方であると。
整数は、順序のはじまりの点がないので、序数はない。なんと。
無限集合の元を並べていく、という概念は結構難しそうだ。。。

【emacs入門】11章 Emacs Lisp プログラミング

こつこつ。

elisp、25万行！
正規表現、shellとかと表現が違うから面倒なんだよね。。。とりあえず、正規表現の前まで。

【実践C】第9章ファイルの活用

こつこつ。

list0902。私の環境では、標準入力でも問題は解決しません。
あり? bufferについてはサンプルがないの?
EOFってcharなんだね。^dか。

2008年7月15日火曜日

【詳解シェル】7章入出力、ファイル、コマンドの評価 (その2)

実は昨日は頭痛で朦朧としていたので、昨日の分のまとめから。

ファイル記述子。
- POSIX的には最大10個のファイル記述子を1つのプロセスはもてる。
- 0:標準入力、1:標準出力、2:標準エラー出力、とデフォルトで割当てられている。
- とりあえず、1以降は次のような構文。
  1> hoge : ファイル記述子1にhogeファイルを割当て。
  2> piyo : ファイル記述子2にhogeファイルを割当て。
  3< puyo : ファイル記述子3を新規に作る。(入力用)
  3> puyo : ファイル記述子3を新規に作る。(出力用)
  2>&1 :ファイル記述子2の割当てを、ファイル記述子1のものと同じにする。
  0<&3 :ファイル記述子0の割当てを、ファイル記述子3のものと同じにする。
- execで、割り当て変更や新規作成ができる。
  例：
  exec 2> /tmp/hoge
  exec 3< /tmp/piyo
  exec 2> /tmp/moge 3< /tmp/puyo
とりあえずのまとめ。間違ってるかも。
exprは使うな。算術計算なら、算術展開。
eval。こうやってshellのREPL?をみると、reader部分でPOSIXコマンド自体をコード生成に使えているので、ある意味マクロちっくなんですね。
サブシェルとコードブロック。

おもしろかった。
体調がいいときは、楽しめる。こつこつ。

【パタヘネ】7章容量と速度の両立：記憶階層の利用

こつこつ。

7.1 はじめに
- 記憶階層は、局所性の法則にもとづいて考えられている。
- 局所性の法則は、時間的局所性と空間的局所性がある、ということ。

【集合】第18講ベキ集合の濃度

こつこつ。

MとベキMで濃度が違う、というかここが濃度が変わるポイントというのが素朴集合論のキモかな。
さらにベキ集合の無限系列の和集合は、そのベキ系列のどれよりも濃度が高い。
ほいで、いくらでも濃度が高い集合を考えることができる、と。
数学によって、集合と無限と濃度ということが形式化された結果、こういうことが考えられるには考えられるんだけど、これらは我々の概念や思考にどれだけ有効なの?ということ。
ラッセルの逆理も、集合という素朴な概念のおこりと形式化と形式論理と、という中で、不協和音が見えるということ。

【詳解シェル】7章入出力、ファイル、コマンドの評価

こつこつ。

「プログラミング言語としてのシェルの紹介はこの章で最後になります。」ええ?！！
たしかに、標準入出力というのはUnixのソフトウエアツールの根幹だな。
そうか、xsvなら、awk使わなくてもreadで読めちゃうんだ。
お、私のbashは、read -r に対応してた。
今日は7.7まで。

明日はevalから。eval ?

【集合】第17講連続体の濃度をもつ集合 (つづき)

こつこつ。

アレフゼロ^アレフゼロ = アレフ。
これは、実数がアレフということの言い換えみたいなもんなので、納得。
アレフ^アレフゼロ = アレフ。
これも、RxRx...xRx... = R^∞がアレフということなので、R^2, R^3などがアレフなことからの類推でも納得。
違う見方をすると前項は実数列がつくる集合がアレフということ。
連続関数の集合C[0,1]の濃度はアレフ。
これは驚くべきことかもしれないが、集合論ではこんなんばっかりなので、驚けない。逆にこれがアレフよりも濃度が高かったら驚いちゃう。
Tea Timeで解析学の結果が出てきたのが面白い。数学が繋っていく感じ。

2008年7月14日月曜日

【emacs入門】10章 Emacsのカスタマイズ

こつこつ。

うぉ。私のemacsには、dired-view-command-alistが無いみたい。
The very unofficial dotemacs home.
うーん。Customは醜悪だな。。。
端末上のemacsでset-foreground-colorすると、色がかわる。一方、端末(OS X ターミナル)の設定でも文字色が変わる。emacsが端末の配色設定にアクセスしているのかな?
C-h p。こんなんあったんだ。

こつこつ。

【実践C】第8章ファイル処理とテキスト

こつこつ。

章扉の「文字の並びであるテキストファイルは、中身が目で見て分かるものですし、あらやるプログラムから共通に利用できます。」というところは、Unixのshellが採用している考え方と関連を感じる。その観点でこの章をみていこう。
ううむ。ストリーム、というところぐらいかな、その観点と関係するのは。

【パタヘネ】6章パイプラインを用いた性能向上 (その2)

こつこつ。

6.9 高度なパイプライン処理：性能のさらなる向上
6.10 実例：Pentium 4のパイプライン
6.11 誤信と落とし穴
6.12 おわりに
- みっつまとめて。ここもざっと通読。
- 高速化するためにCPUの中の機構はかなり複雑になっている。
- なので、人手でアセンブリプログラムを書いた方が速いコードができるというのは、もう難しいだろう。
- コンパイラが賢くなったから、人手よりも速いものができるようになったというが、CPU側が複雑になったから、というのも理由にあるように思うということ。

さて、ラストの7章8章は「ソフトウエア寄り」もきっちりやらねばいかんところ。がんばろう。

【詳解シェル】6章変数、条件分岐、繰り返し

お、この章はシェルスクリプトのキモかな?

「シェルは基本的には文字列処理のための言語」
export -p や readonly -p すると、declareというのがでてくる。type declareするとbuiltinなので、exportやreadonlyはdeclareのエイリアス的なものかも。
'test'、すげぇ。
やっぱり、対話的に試せる環境がある言語は、簡単に試しながらできるのでやってて楽しい。
getoptsも便利だなぁ。

【emacs入門】9章プログラミング言語の編集

こつこつ。

そうか、言語サポートは共通部分と各言語部分に分離しているのね。
describe-syntax、おもしろいな。
M-;。便利やっぱ";"なのね。
M-j。しらんかった。
個別言語としては、CとLispだけ通読。他の言語は実際にやるときがきたら見る。

ここらへんも、指の躾だなぁ。次は10章。後半戦!

2008年7月13日日曜日

【emacs入門】8章マークアップ言語の編集 (skip)

えっと、この章は、html-mode, html-helper-mode, psgml-mode... を紹介していく感じなんですが、(x)htmlの編集に関しては、自分としてはnxhtml-modeがいいかも、と考えています。なので、ちょっとそれがいけるかどうか確認して、自分の立ち位置を決めた上で、この章はやりたいと思います。というわけで、いったんスキップ。

【実践C】第7章構造体と共用体

こつこつ。

構造体の設計というのはC言語というよりも、プログラミング一般に属する話題と思えるが。
おお、構造等価性と名称等価性という概念があるのか。そして、Cは名称等価性なのね。duck typingではない、と。

ぬ。私の環境では、マクロを使った、構造体相互参照問題解決案(lit0713,list0714など)がうまくいかない。


cc -Wall -g list0710.c
In file included from list0710.c:1:
defy.h:9: error: redefinition of typedef ‘SY’
defx.h:4: error: previous declaration of ‘SY’ was here
list0710.c: In function ‘main’:
list0710.c:7: warning: unused variable ‘t’
list0710.c:6: warning: unused variable ‘s’

とかいわれちゃう。

お、やっと共用体だ。軽く触れる、だな。
「同一の先頭のメンバの並び(common initial sequence)」ってなんつーか、OOの継承みたいなデータ構造のためなのかな。

だいぶ基礎知識はついてきたけど、どう考えてもまだ入門者レベルだな。。。こつこつ。

【パタヘネ】6章パイプラインを用いた性能向上

こつこつ。

6.1 パイプライン処理の概要
- パイプライン、頭いいなぁ。
- この節自体、ざっと、通読という感じになってしまった。

【集合】第16講連続体の濃度をもつ集合

こつこつ。

線分と平面の濃度が同じ件について：物理的なイメージはどれも駄目なのではないか?
なるほど。線分と平面では、集合としてだけ考えていると遜色ないが、元と元の連続性のあり様としては大きな違いがあると。それが次元であり、位相の概念とつながるのだろうな。

【集合】第15講濃度の大小

こつこつ。

一対一写像の概念をもとにして、濃度の大小が定義される。
それは、無限集合も範疇としている。
l<=m, m<=l => l=m ということが無限集合にも成り立つことがわかる。
これを、ベルンシュタインの定理、と呼ぶ。
ベルンシュタインの定理の証明というかあり様がいまいちピンとこない。
それは、進みながら振り返ることにする。まあ、すぐにピンとこないものごともあるもの。

ふー。やっと半分。。。こつこつ。

【パタヘネ】5章プロセッサ：データパスと制御 (その2)

こつこつ。

5.9 実例：最近のPentiumの実現方式の構成
5.10 誤信と落とし穴
5.11 おわりに
- みっつまとめて。
- そうか、PentiumってコアはRISCで、そのまわりにCISCを実現するマイクロコードがあるんだ。
- これらはお話なので、あっさり。

次は6章。パイプラインだ。ここも「ソフトウエア寄り」としてはあっさり。

【emacs入門】7章簡単なテキスト整形機能と特殊編集機能

こつこつ。

fill-individual-paragraphs 便利だな。
しかし、パラグラフや言葉の区切りがどういう定義なのかを再度きっちりおさえないといけないな。特に日本語の文章においての定義。
M-m。これ、忘れてた。便利。
Outline mode が私の環境ではうまく動いてないな。
C-tをScreen にわりあててるけど、替えた方がいいかも。Screenの接頭辞って、そんなにハードにつかわないし。
レジスタって矩形以外にも使えるのかなぁ。
Picture と Artist はざっと読んだだけ。あまり使わないから。

体調悪し、休み休み、進む。こつこつ。

2008年7月12日土曜日

【実践C】第6章関数原型宣言

日々、こつこつ。

list0602：コンパイラからのメッセージ。


list0602.c: In function ‘main’:
list0602.c:10: warning: implicit declaration of function ‘sqr’
list0602.c:10: warning: format ‘%.3f’ expects type ‘double’, but argument 2 has type ‘int’
list0602.c: At top level:
list0602.c:16: error: conflicting types for ‘sqr’
list0602.c:10: error: previous implicit declaration of ‘sqr’ was here

list0603：う、次のような警告はでるが、動作は正常。なぜ?


list0603.c: In function ‘main’:
list0603.c:10: warning: implicit declaration of function ‘pow’
list0603.c:10: warning: incompatible implicit declaration of built-in function ‘pow’

ああ、そうか、たぶんdoubleとintのサイズが私の環境だと同じだからか。

せめて


     struct {
          int x;
          int y;
     } z;

としないと、私の環境ではコンパイルできなかった。

K&Rスタイルでは、
```
int func(a, b)
int a;
int b;
{ ... }
```
とな。なんと。
list0610。うーん、これもちゃんと動いちゃう。
おお。int printf(const char *, ...)というように...で可変数引数を表現できるんだ。
プロトタイプの仮引数の識別子と、本体の対応物の識別子は違っていてもよいんだ。
エラーメッセージとかソースとかで、'__'からはじまる識別子が多い理由がわかった。

プログラマへの道のりは、長いなぁ。。。こつこつ。

【詳解シェル】5章パイプラインの魔法

魅惑的なタイトル。

man 5にデータ構造があったんだ。
うむ。「繰り返し」はシェルは得意なんだと思うけど。
tsv-to-htmlはバグがあるよな? \tは't'にマッチしてしまう。
パイプラインの魔法、というのは、"パイプラインの魔法的な使い方"ではなく、"パイプラインって魔法的"ということだった。
シェルスクリプトとの比較に、C++とJavaはもってきても、perlとrubyはもってこない。

【emacs入門】6章マクロの記述

こつこつ。

ここも、使いこなしている、とはいえない知識だった。。。
勉強になるなぁ。

【パタヘネ】5章プロセッサ：データパスと制御

下巻開始！
下巻はハードウエア寄りの内容が多い。そこで、前書きの示唆にしたがって、ソフトウエア寄りに読む場合に、「注意深く読む」というところだけを通読の対象とする。後は、二周目のお楽しみ。

5.1 はじめに
- う、この節、結構叙述がラフなような。自分なりの理解を書いていってみる。
- データパス作成および制御設計の鍵となる基本原理を明らかにするには、次の3つの命令カテゴリを対象とすれば事足りる。
  - メモリ参照命令：lw, sw
  - 算術論理演算命令：add,sub,and,or,slt
  - branch equal (beq)およびジャンプ(j)
- 以下では、この3つの命令カテゴリのみを対象とすることにする。
- 実現方式の概要を示す。
- 命令のタイプによらず、最初のステップは次の2つである。
  - PCの値をコードが保持されているメモリに送る。
  - 命令のレジスタ・フィールドに指定されている1つまたは2つのレジスタを読み出す。
- 図5.2で考える。
  1. PCは、命令メモリの該当命令アドレスである。
  2. すなわちPCによって、実行すべき命令を得ることができる。
  3. その命令のフィールドによって、使用するレジスタ・オペランドのレジスタ番号が判明する。
  4. レジスタ・オペランドをレジスタからフェッチする。
  5. lwの場合、その値をALUに送って、メモリ・アドレスを計算する。
  6. う、レジスタ・ファイルの定義がない。。。レジスタとの違いがわからない。
  7. 付録Bに定義あり。レジスタ・ファイルは、レジスタ群で構成された状態論理要素。これに対してレジスタ番号を指定することによってレジスタの読み書きができる、というものらしい。
  8. 計算結果にもとづいては、データ・メモリのアドレスからデータを取得する。
  9. 取得したデータは、レジスタ・ファイルに書き込まれる。
  10. 交差点のように結線されている部分にはMUXがある。
  11. MUXとほとんどの各部は「制御」につながっており、制御される。

とりあえずの理解としては、こんな感じかなぁ。

2008年7月11日金曜日

【集合】第14講濃度

こつこつ。。。

濃度の演算は、対象が有限集合のとき、自然数の該当演算に帰着する。よって、この新しい概念は、それら自然数の演算の概念拡張であると言える、ということ。
概念拡張されたものであるから、この新しい概念は、元にした概念のいくつかの性質を受け継いでいる。すなわち、濃度が無限の場合の演算について成り立つ関係式は、そのもととなった有限集合のときの「意味」を受けついでいる部分もあろう。
しかし、概念拡張されているのだから、元にした概念にはあらわれない性質を見せることもあろう。アレフ・ゼロ+アレフ・ゼロ=アレフ・ゼロとか。それを調べることが重要に思える。
ニュートン力学と特殊相対性理論の関係みたいなものかなぁ。

【実践C】第5章ナル

こつこつ。

null ：無価値の、効果のない、重要でない。(ドイツ語で0という意味)
nil ：無
void：無効の、効果がない、からの、空虚な。
null and void ：(法律上)無効の。
Cにもgoto文ってあるんだよね。
null pointerってnilみたいな位置付けなのかね。

体調悪いが、がんばる。

足りていなさそうなこと。

基本的なことで、今の学習プランでカバーできていなくて、やらなければならなくなりそうなこと。

位相
代数(群・環・体あたり?)
微積分
グラフ理論
ラムダ算法
自然言語を対象とした言語学。認知言語学とか。
Java
オブジェクト指向
Intelアーキテクチャのアセンブリ言語
OSの基礎知識

うむむ。学習の工夫をせねば、時間がかかりすぎてしまう。

【詳解シェル】4章文字列処理ツール

こつこつ。

文字列処理ツールとしてsortが紹介されるのが、ちょっと意外。
ん？sort -> uniq -> fmt とくるということは、テキストファイル全体をひとつの文字列と考えているということか。
おお、stringsってナイスアイデア。

【emacs入門】5章作業環境としてのEmacs

こつこつ。

M-|。便利。
C-cC-o。
う、新しい知識がありすぎて、列挙する気になれない。。。
難しいことはもちろんひとつもなくて、指の躾をせねば、ということ。

【集合】第13講直積集合と写像の集合

こつこつ。

この講、おもしろかった。
集合族の直積集合って、写像をベターとしたみたいなものなのね。
しかし、ここにでてくるいろいろな概念というか表現について、その意味を、がんがん無限なものというか連続体にも適用していくところは、ほんとにそれって大丈夫なの?という不安は覚える。
このあたりの写像(関数)の集合を考えるあたり、ラムダ算法とか圏論とつながりがありそうな。

【パタヘネ】4章性能の評価と理解 (その4)

こつこつ。

4.4 実例：2つのSPECベンチマークと最近のIntelプロセッサの性能
- SPEC CPU 2000 の浮動小数点ベンチマークがFortran77で組まれていることに軽い衝撃を受けた。
- この節を読んで、SPECの理解が少し深まった。
もういっちょ。
4.5 誤信と落とし穴
- うむー。Amadahlの法則は、法則と呼ぶ程のものなのか?
- なるほど、MIPS値は慎重に取り扱う必要があり。
もいっちょ。
4.6 おわりに
- 特になし。

おお。パタヘネ上巻通読完了！

2008年7月10日木曜日

【実践C】第4章文字列とポインタ (その2)

こつこつ。

4-2から再開。
やはり、疲れがとれてないが、がんばる。
ここはあんまり厄介なところや新しいことはなかった。
途中、「標準Cライブラリの勉強もしなければならないのでは」と思い至り、どの書籍がよいのか物色した。次のどちらかがよさそう。
- C: A reference library
- 新ANSI C言語辞典

「学問に王道なし」なのだが、C言語ができるようになるまで、時間がかかるなぁ。こつこつ。

【詳解シェル】3章文字列の検索と置換 (その2)

こつこつ。sedから。

えっと、.profileに$HOME/binがPATHに入るように書いたのにPATHに入ってないわな。> OSX
sedをプログラミング言語としてではなく、ライン指向の置換フィルタとして捉える。
おお。shにパイプで渡すと、それが実行すべきコマンドのリストになるのね。
このsedの説明、簡明だなぁ。
sedにおける(正規表現における?)ヌル文字の定義をきっちりおさえないといけなさそう。
フィールド。CSV的なものたちの取り扱い。
おお、awkはあまりにさらっと。
しかしこの本、各章のまとめのまとめっぷりが秀逸。

ここまで読んでの感想は、

やっぱりUnixというかShellというかは、テキスト指向かつ行指向ということを再認識。
階層構造をもっているのってファイルシステムぐらいなのかな。
しかし昨今は階層構造をもった情報が多いからなぁ。どれだけShellが活躍できるか。

【emacs入門】4章バッファとウィンドウおよびフレームの利用

これも、ちゃんと勉強してみたかった部分。

基本概念
- フレーム：GUIのウィンドウに該当。
- ウィンドウ：ひとつのフレームの中で画面分割する機能がEmacsにはあり、その分割された領域のこと。
- バッファ：メモリ上の領域
端末上ではフレームはどうなのか。elscreenはフレームを使っている?? 違うな。elscreen状態でC-x 5 2すると、別のフレームが開いた。
カーソルとポイントは別概念。カーソルは視覚的なもの。ポイントは視覚的表現の有無に関わらず、そのバッファにおける現在位置のこと。
C-x 4を頭につけてコマンドを発行すると、「別のウィンドウ」への指示になる。この「別のウィンドウ」というのがウィンドウが3つ以上ある状況でどうゆうルールできまるのかを、実は知らない。
C-M-v。
C-x s。
M-x rename-buffer。
C-xC-v。
C-xC-q。これは便利。
C-x <とC-x >はdisabledだ。
M-x compare-windows。まあdiff/ediffを使うかな。
ブックマーク、知らんかった。これも便利。

ブックマークは収穫。他は既知が多かった。
やはり昨日がんばったので体調悪し。されど、こつこつ。

【実践C】第4章文字列とポインタ

こつこつ。

おお、私も文字定数の型はcharだと思ってた。intなのね。
```
sizeof(char) = 1
sizeof(int)  = 4
sizeof('A')  = 4
```
ほんとだ。
文字列リテラルの型はcharへのポインタ。なるほど、なんだか禅問答的な世界に入りつつあるような。
「C言語には文字列定数という概念は存在しない」Zen。
list0412。私の環境では、文字列リテラルは書き換え不能。実行時に記憶域保護違反。
文字列というのはメモリ上の状態(char型がつづき最後が\0)のことであって、すなわちハードに近いことであって、それをC言語上でどう扱うかは、それをメモリ上に構成したり、またはそこにアクセスしたりする方式の方に依存しているわけですね。
う、長いなこの章。とりあえず、4-2の手前で一区切り。

2008年7月9日水曜日

【パタヘネ】4章性能の評価と理解 (その3)

こつこつ。

4.3 性能の評価
- ここは特になし。日頃自分が棲息している領域に近いからかな?

【集合】第12講写像

こつこつ。

一対一写像と一対一対応は違う概念なのね。
集合Γからベキ集合β(M)への写像があるとき、その像をMの(Γを添字とする)集合族と呼ぶ。
なんか、ベキ集合というのが、自分が思っていたより重要な概念なような気がしてきた。
ベキ集合というのは、写像の像というものを扱うための俎に思える。
集合族というのは知らなかった。
集合族自体を集合と考えるならば、その元は添字集合Γからもとの(ペキ対象となっている)集合への写像の像である。
この観点に立つとき、集合族があるとき、それに対応した写像族があることになるな。
集合族というのは、添字集合を用いて、複数の集合達の性質を調べる道具に思える。
このとき、添字集合のことを如何によくわかっているかが重要なのだろう。わかっていないもので、わかっていないものを見ても何もわからないから。
集合列は添字集合がNの場合。
上極限集合 lim sup An はなんとかわかった。これは、A1∪A2∪...∪An∪...の話。これに続き、A2∪A3∪...∪An∪...などを無限に考えていき、そのどれにも含まれている元ということ。これは、除外されていく部分に着目すればわかりやすい。すなわち、有限の添字(jとする)までにしか存在しない元はlim sup Anには含まれない。なぜなら、それはAj+1∪...には含まれないから。なので、lim sup Anに含まれる元は、集合列といえば、無限の彼方の集合にも含まれている元ということになる。無限の彼方の集合にも含まれている、ということは、どこかのkでAkに含まれていつつ、それよりも大きなkでAkに含まれていることが発生しなければいけないから、結果として「無限に多くのAkに含まれている元」というのがlim sup Anの元の特徴となる。無限って厄介だな。。。
下極限集合 lim inf An がわからない。。。
考えてみる。まずこれは、A1∩A2∩...∩An∩...の話。これに含まれる元というのは、無限の彼方まで含めて、全ての集合に含まれるものである。そんなものがあったら珍しいものであり、それ以上何を考えるの?と思ってしまうが。。。
で、その系列を考える、A2∩... A3∩...などなど。そしてその系列の和集合をとる。すなわち、前行の元よりは元の数が増える可能性はあるが、減る可能性はない。
除外されていく方に着目する。まずA1が除外されるので、A2∩...はA1∩...よりも条件は緩い。かつ、A1∩...に含まれている元は、必ずA2∩...にも含まれている。
ここで、kを考える。k > 2として、A2∩..に含まれるなら、Ak∩...にも含まれる。よって、実は和集合で順次自然数を舐めていく、というのは意味がない。
kがとんでもなく大きいときのAk∩... に含まれるということが重要。
この状況で、これに含まれない元というのを日本語で表現できるか?
うまく言えない。。。
含まれる元は?
すべてのAkに含まれる元。。。それはA1∩...の元にすぎない。。。
うーん。

【実践C】第3章ポインタについて

う。がんばることが何かを生むかも、と思ってがんばってみる。
経験上では、それは何も生まないんだけど。

自分なりのメモをとりながら。
ポインタの基本の振りかえり。
オブジェクト
&　アドレス演算子。識別子に関連付けられたオブジェクトのアドレスにアクセス。配列の各要素のアドレスにもアクセスできる。
オブジェクトのアドレス値を格納するオブジェクトというものもあり、それをポインタ型という。ポインタ型は指している対象の型に応じた種類があり、int型のオブジェクトのアドレスを格納するオブジェクトをint型のポインタという。
*　間接演算子。識別子に関連付けられたポインタ型オブジェクトが値としてもつアドレスに存在しているオブジェクトの値にアクセスする。寿限無寿限無。。。
C言語では値渡しが基本。値渡しってコピー渡し、という理解。
ptr + iとptr - iという、配列内のオブジェクトを指すptrに対する加減算の定義。
前項から、当然*(ptr + i)が何を指すかということ。
番兵法：配列を処理する関数について、要素数をわたす煩雑さを避けるための手法。
配列全体へのポインタが、他の概念とどう整合しているのかが今一つつかめない。
動的なオブジェクトの生成。お、入門編では触れていなかった内容。
そうか。言語仕様というよりはライブラリなのね。
voidポインタ。任意の型のオブジェクトを指すことができる。なんと。
おお、動的生成、面白い。
なる、C++では言語仕様として動的生成できるのか。
しかしcallocで確保された領域って本当に更地なんだな。。。それがどう扱えるかは、それを指すポインタ側の構造によると。
うーむ、面白い、と思ったところは没頭して進む。

こつこつ。

【パタヘネ】4章性能の評価と理解 (その2)

う、今日は業務がキツくて余力がない。。。
メモとりながら、こつこつ。

4.2 CPU性能とその要員
- CPU性能に議論を限定する。
- 最終的な性能測定基準はCPU実行時間である。
- あるプログラムのCPU実行時間 = そのプログラムのCPUクロック・サイクル数 * クロック・サイクル時間
- あるプログラムのCPU実行時間 = そのプログラムのCPUクロック・サイクル数 / クロック周波数
- CPUクロックサイクル数 = プログラムの実行命令数 * 命令当たりの平均クロック・サイクル数(CPI)
- CPIは、クロック・サイクルについて、"そのプログラムの中で実行された"全ての命令に関する平均値である。
- (あるプログラムの)CPU実行時間 = (そのプログラムの)実行命令数 * (そのプログラムの)CPI * クロック・サイクル時間
- 実行命令数とCPIの入手は難しい。
- 実行命令数の方が測定しやすい。
- CPUクロック・サイクル数の計測や計算に、命令のクラス分けを利用する便法がある。
  CPUクロック・サイクル数 = Σ(i = 1 to n) (CPIi * Ci)
  Ci:実行されたクラスiの実行命令数
  CPIi:そのクラスの命令あたりのクロック・サイクル数
- 命令ミックス：「1本もしくは複数本のプログラムにまたがっての種々の命令の出現頻度の集計値。

【集合】第11講一般的な設定へ

こつこつ。

基本的には、今までに導入してきた概念を、一般的な設定として整理整頓開始。
双対性、って、二つの演算を入れ替えても、演算規則が成り立つって意味だったのね。
ド・モルガンの規則は怪しい。このアヤシサの裏には何かあるはず。それは集合論ではなくて、論理学かな、と思った。

2008年7月8日火曜日

【詳解シェル】3章文字列の検索と置換

こつこつ。
とりあえず、3.2.6 文字列の置換 (sed)の前まで。
これ以上はやっても惰性なので。

効率的に習得していく方法を工夫していかねば。

【emacs入門】3章検索と置換

検索と置換は、一度ちゃんと勉強してみたかったのです。我流なもので。

新しい知識
- C-sC-w。うぉ、これが欲しかった。
- C-sC-y。
- C-sM-y, C-sM-yM-p, C-sM-yM-pM-pM-n。これもナイス。
- C-sEnterC-w。単語検索。
- M-%。
- C-x Esc Esc。なんと。。。
- ispell,flyspell。
- 単語略称機能。
- ほとんど知らなかった、という事実。

こつこつ。。。

2008年7月7日月曜日

【実践C】第2章型変換

こつこつ。

うう。「通常の算術変換」、複雑です。
符号付き整数の表現については、入門編でもパタヘネでもやったので無問題。
うう。「汎整数拡張」、複雑です。
えっと、C言語における暗黙の型変換がとても複雑だということがわかりました。
なので、明示的な型変換を心掛けつつ、明示的な型変換のルールも複雑なので、注意深くやることを肝に命じます。

なんとか一章やったけど、やっぱきつい。。。
でも、一日一章進んでいくのは進みが速くて魅力的。。。

【パタヘネ】4章性能の評価と理解

こつこつ。

用語の定義いろいろ。
特に新しい知見はない。

4章は速く進むかも

【集合】第10講実数の集合

こつこつ。

ついに実数の集合です。
集合R(0,1)は加算集合ではない。もっと濃度の濃い無限。
それを連続体の濃度アレフという。
無理数の集合はアレフ。
任意の線分はアレフ。
カントル集合はアレフ。

ヌゥ。いまいち心に入ってこない。

2008年7月6日日曜日

【実践C】第1章見えないエラー

とにかく、信じてこつこつ。

お、list0101/list0102がコンパイルエラーにならない。調べたら、Emacsの中の誰かがファイル保存時に勝手に末尾の改行をいれているみたい。

全角空白問題は私の環境ではこんなエラー。


gcc -Wall -g list0102.c
list0102.c: In function ‘main’:
list0102.c:11: error: stray ‘\227’ in program
list0102.c:11: error: stray ‘\128’ in program
list0102.c:11: error: stray ‘\128’ in program
list0102.c:11: error: stray ‘\227’ in program
list0102.c:11: error: stray ‘\128’ in program
list0102.c:11: error: stray ‘\128’ in program

Compilation exited abnormally with code 1 at Sun Jul  6 22:02:44

strayって野良犬のことらしいけど、どういう意味だろ>GCC。
あり、入門編では、main関数の仮引数はvoidだけだったけど、実践編では違うのが説明なしにでてきた。ギャップ無しで接続しているわけじゃないのね。
でも、入門編の勉強がいきているからdetab.cもすんなりわかる！
どわ。関数呼び出しって、(func_name)(1,2)とかでもいいんだ。。。
うむ。しかし、maxと(max)じゃ、シンボル的にいうとすでに別物のような。
そうだ。注釈は、ソースを調整するためのものじゃない。ごもっとも。
おわ、ヘッダの二度読みにも工夫が必要なのか。。。
ちょっとまて。C++じゃないか。。。
えっと、C++の部分は雰囲気だけ、ということで。
自動記憶域期間という意味では、Cのメモリ管理も自動化されている部分もあるんだよね。なんでメモリリークとかが問題になるんだろ? ポインタが鍵なのかな?
うーん。Cの多重配列の初期化方式は仕様ミスだと思う。

一日一章はきつい。明日からはのんびり。

目標の整理

ちょっと更新。

linuxのptyアプリを書きたい。
- 詳解UNIXを勉強する。
  - C言語を勉強する。
    - 明解 C言語入門編【完了】
    - 明解 C言語実践編 ★途中
    - UNIXの道具箱を読む。★途中
NorvigのAIを読みたい。(Common Lispプログラミングの書きぶりを知りたい)
- アルゴリズムとデータ構造について勉強する。
  - C言語を勉強する。★途中
  - C言語でアルゴリズムとデータ構造をやる。
- Common Lispについて基本を復習する。
  - 初めての人のためのLISPを読む。★途中
  - Common Lisp Drillをやる。(Cでアルゴリズムをやった後に実施)
Common Lispを理解したい。
- コンパイルを理解する。
  - パタヘネを理解する。
    - 上巻 ★途中
    - 下巻
  - シプサを理解する。
    - 集合30講を読む★途中
  - コンパイラ本を何かやる。
- Lisp In Small Peacesを理解する。
記述論理を理解したい。
- 一階述語論理とホーア論理を理解する。
  - ソフトウエア科学のための論理学を勉強する。
    - 論理学をつくるを勉強する。★途中 (シプサの後に復帰)
マネージメントを勉強する
- 統計学：統計学入門を読む ★途中
生活環境の改善
- Emacs
  - 入門GNU Emacsを読む ★途中
- Shell
  - 詳解シェルスクリプトを読む ★途中
体で覚えるもの
- C言語：「解きながら覚えるC言語」をやる

【集合】第9講 2進法、3進法、...

こつこつ。

なんだか、何やってんだかわからなくなってきたので流れを確認。
えっと、素朴集合論を勉強しているのです。
なんでかというと、
- まず、数というものは計算機の基礎にある。整数、有理数、実数などは素朴集合論の中で整理される(部分もある)。
- 集合(set)という考えは、現代数学の基礎概念のひとつになっており、これがわかっていないと他の知識を習得するのに障壁がある。(圏論による構成についてはとりあえず無視)
- また、無限な対象を形式定義するための再帰の基礎知識になっている。
- 素朴集合論の無限の考え方は、メタ数学というか数理論理学の理解の基礎にもなる。
ということで、素朴集合論を理解することは3度も4度もおいしい。
で、この本は、
素朴集合論を、無限集合の探求の視点で解き明かしてく。
というもの。
- まず、「集合」という考え方の形成。
- 「自然数」という考え方の形成。基数と序数。無限集合の存在の是認。そして自然数の集合N。
- 集合の基礎概念(演算)の整備。部分集合、ベキ集合、和集合...
- 集合の個数の概念の導入。
- 個数の概念の無限への拡張。(一対一対応) Nと一対一という加算集合の概念。
- 加算集合の性質の調査。
- 数直線の導入。
- 有理数が可算集合であること。有理数の性質の調査。
- 実数の概念の導入。少数展開による定義。
こうしてみると、数直線が出たところから、なんで数直線だろー、とか、実数が出てきたところで、何でいきなり定義やねん、とか思ったような気がする。
まあ、これは導入だからさっぱりテキトーにということなんだろう。
で、この節は2進法、3進法とみていく。
再度それらによる実数の定義?をみていくと、それが部分集合の系列というか収束として数を定義していることが印象に残る。
進法という表記(notation)ではなく、その考え方ということ。
カントル集合は、線分で考えると2/3 * 2/3 * 2/3...とどんどん短くなっていくので「霞」のような存在だが、そのなかに実にたくさんの実数があることがわかる。
また、自然数展開というか自然数進法も考えられて、そのあり様は直感的にはわからないものである。

【詳解シェル】2章さあ始めよう

こつこつ。

「シェルスクリプトはシステム管理関連の作業や、既存のプログラムを連結してちょっとした処理をこなすといった目的に主に使われます」
.profileにパスを追加。$HOME/local/binにした。
他は基礎事項かな。
「2.9 まとめ」がよくまとまってて、書くことなし。

【emacs入門】2章テキストの編集

こつこつ。

新しい知識
- refill-modeとauto-fill-modeの違いが明確になっていなかった。refill-modeは今まで使っていなかった。
- というか、私の環境ではrefill-modeにすることはできるが、まともに動作してくれない。
- M-},M-{。段落間移動。
- page-delimiterという考え方。と、C-x [,C-x ]。
- おお、^Lってテキストファイルにおけるページデリミタだったのか。C-qC-l。
- うぉ。M-nって知らんかった。いつもC-u nしてた。
- M-hで段落をリージョンに。C-x hでバッファ全体をリージョンに。
- キルリングが保持するのは最近の30件。
- OSXで、他アプリ->Emacsのコピベは、M-x clipboad-yank。[Edit]->[Paste]は機能せず。
- M-t、C-xC-t。単語と行の入れ替え。transpose系列。
- M-c, M-l, M-u。。。
- M-x overwrite-mode。

勉強になるなぁ。

パタヘネの使い方

3章まで読んで、この本は、とても大事な本だと思う。
CDの内容まで含めると、おそらく1年くらいかけてじっくりと自分の中で練り込んでいくべき内容な気がする。
まず他人の馬を走らせて、そして自分の馬として錬成する、ということ。
そのためには、適度な深さの通読がまず必要。
そして、その後、各章に攻め込む。

【パタヘネ】3章コンピュータにおける算術演算 (その5)

こつこつ。

3.7 実例：IA-32における浮動小数点演算
- お話し、という感じ。
- 「IA-32の浮動小数点アーキテクチャは世界中の他のどのコンピュータとも異なっている。」
- 「IA-32ファミリの浮動小数点性能はかつて、他のコンピュータよりも大きく遅れをとっていた。」
- 「IntelはSSE2においてどちらかと言えば旧式の浮動小数点アーキテクチャを採用している。」
お話し、なのでもう少々。
3.8 誤信と落とし穴
- Pentium問題の話など。興味深い。
3.9 おわりに
- MIPSアセンブリ命令 = MIPSコア命令 + MIPS算術コア命令 + 残りのMIP-32 (+ 疑似MIPS)
- 本書では、MIPSコア命令を主に扱う。

3.10と3.11は2周目対象。
上巻の読了が見えてきた。あと一章！

2008年7月5日土曜日

【集合】第8講実数の構造 - 少数展開

こつこつ。

「この無限少数を表わす数直線上の点が存在するという考えが数学の中に確定してきた」
実数の定義、美しくない。怪しすぎる。。。
デデキントの'実数の連続性'というのがわからない。というか、この形であれば、有理数も連続していると言えるのではないか?? まあ、Tea Timeなので、とりあえず、置いておく。

【パタヘネ】3章コンピュータにおける算術演算 (その4)

こつこつ。

3.6 浮動小数点演算
- 浮動小数点形式は、IEEE754浮動小数点規格で標準化されている。
- あり? ではCでintとかdoubleとかのサイズが環境毎に違うのは何故なんだ?
- 整数の命令を使い回せるようにした、浮動小数点形式の定義っぷりが頭いい。
- guard, stickyのあたりは雰囲気だけで精確には理解していない。
- CからMIPSアセンブリへの翻訳も雰囲気だけ。
- 「ビット・パターンが何を表すかはそれを操作する命令によって決まる」

2章と3章は、MIPSアセンブリプログラミングができることを目指して遊びながらやるべきものに思えてきた。SPIMを使いつつ。そしてその裏にあるハードウエアの構造を想定しつつ。

あと2節で3章クリア！

【集合】第7講数直線上の加算集合

こつこつ。

「有理点は数直線上に稠密に存在する」
analytic number (代数的な数)の定義をはじめて知った。
「代数的な数全体がつくる集合は加算集合である」そ、そうなのか。ちょっと考えればそうなんだけど。ちょっと衝撃。

【詳解シェル】1章イントロダクション

Unixシステムの歴史。

新しい知識
- 単機能な小さなアプリをいろいろつくる、というのは、当初は、思想的なことではなくPDP-11が貧弱だったから。
- '初期POSIX' ⊂ 'XPG5' = 'POSIX(XSI入り)' = 'Single Unix Specification'。

シェルを勉強しなおす

シェルを勉強しなおす。
本は、詳解シェルスクリプトにする。
さすがに、単にシェルだけでは食い足りない気がするので。

【emacs入門】1章 Emacs入門

Emacsの起動/終了。ファイル操作の基本コマンド。

新しい知識。
- M-`でテキストメニュー。
- C-xC-vで、find-alternate-file。
- C-x iでファイル挿入。

Emacsを勉強しなおす

Emacsにはだいぶ慣れているけれど、一度ちゃんと勉強しなおすことにする。
本は「入門GNU Emacs」にする。
道具箱との関連に気をつけながらやる。
知識の習得の他に指の訓練も実施する。

「新版明解 C言語入門編」読了

読了しました。
これで、C言語の基本の勉強は完了！とする予定でしたが、共用体と関数ポインタが割愛されていたので、実践編を読了したところで、基本の勉強完了としたいと思います。それが終わったら、データ構造とアルゴリズムに入ります。

2008年7月4日金曜日

コンピュータを使いこなすために

道具としてのコンピュータの使いこなしの訓練をしないといけない気がしてきた。
それにはまず、

Emacsの使い方を覚える。
　Emacs Lispを覚える。
シェルの使い方を覚える。
　シェルスクリプトを覚える。

ということが必要なような。
Unixが生活環境だとすると、他のことは、まずはこの上にのっかってくるように思う。
これらは、その「他のこと」の上にのっかってるんだけど。

【集合】第6講可算集合の和集合と直積集合

体調悪いが、無理をしてみる。

「有限集合のときには、たとえば100個からなる'ものの集り'が、同じ個数100個のものを2つ合わせてできるなどということは、絶対におこり得ない。したがって、この点では加算濃度アレフ・ゼロは、有限個の'個数'とは、全く異なる状況を示すのである。」
加算集合の中には、加算集合が加算個あるのか。。。タチが悪い！
アレフ・ゼロの壁、というか、そこそこの集合演算であれば、加算集合たちに加算個の演算を実施しても、アレフ・ゼロを超えられないという状況。アレフ・ゼロ、あなどれじ。

雰囲気はわかったが、理解は緩いかも。
うむー、体調が悪いので、頭でわかっても、心まではいらない。甘えなのか?

【パタヘネ】3章コンピュータにおける算術演算 (その3)

こつこつ。

3.5 除算
- 割り算をそもそもちゃんと理解していないことに気付いた。
- なので、この節は抵抗感が強い。
- こうしてみると、筆算という計算アルゴリズムを適用できるように、整数の進数表現というのが組み立てられたんだなぁ、というのをよく感じる。
- しかし、そもそもなんでこんなこと学ばなければ(考えなければ)いけないんだろ? と思えてきた。
- それはコンピュータにおいて割り算ってそもそも実現可能なの? またはどのように実現されているの? ということに答えられるためかなぁ。
- それを理解することによって、コンピュータ上の割り算の性質というか仕様が理解できる。それはソフトウエアを書くのに必要なことだということ。MIPSアセンブリで書くなら必須だし、高級言語でも有用だろう、ということ。
- で、ここでやってることは「コンピュータの古典的な5つの構成要素」の中のデータパスの部分。データパスは「制御」に制御されながら演算を担当する部分。
- ここの話は、ここだけで終わる話ではなくて、先々、プロセッサの全体の関連を考えていくときや性能を考えていくときに有用となるんだろうな、と予測する。

う、体調悪い。脂汗がでてきた。こつこつ。

2008年7月3日木曜日

【集合】第5講加算集合

こつこつ。

自分なりの理解を書いてみる。
- 集合の元の個数とは、基数の概念と直結している。
- なので、前講では有限集合の元の個数とは自然数を使っての話となった。
- では、無限集合の個数とは?
- 無限だから個数はわからないので、基数の概念を拡張する。
- まず基数はすでに数の匂いがあるから、濃度という用語を導入する。
- 2つの集合が一対一対応するとき、同じ濃度である、と言うことにする。
- すると、集合Mの基数が3であるとは、それと自然数の部分集合たる{1,2,3}の濃度が同じであるということである。
- で、濃度は一対一対応をベースにしており、個数に言及していないので、無限集合にも適用できる。
- いちいち、「この無限集合は自然数と同じ濃度である」というのがめんどくさい。
- そこで、自然数の濃度をアレフ・ゼロと名付けてしまう。
- 自然数は基数の概念から生まれたが、その自然数の基数(アレフ・ゼロ)という新しい概念がうまれたということ。
そうか。M={a1,a2, ..., an, ...}としたとき、これはMの元とNを一対一対応させているのか。うむーシンタックスとセマンティクス。

【パタヘネ】3章コンピュータにおける算術演算 (その2)

こつこつ。

3.4 乗算
- 「乗算ハードウエアの改善バージョン」は頭いいなぁ。
- 整数のかけ算は、複数回足し算の構文糖衣であると理解していたが、N進数というか進数という数の表記方法は、筆算というアルゴリズムをみてもやはり合理的にできてるなぁと感じた。さらに、その中でも2進数というのは進数のもつメカニズムと整数のもつ性質がもっとも直結していると思える。違う言い方をすると、2進数という整数のリテラルはリテラルの規約が最小限な分、進数のもつメカニズムとそれに対応した整数の性質が直接的にリテラルで表現した値に現れている。

2008年7月1日火曜日

【集合】第4講有限集合の演算、個数の計算

こつこつ。

この講、ちょっと停滞した。
というのは、手を動かすのがおっくうだったから。
おっくう、って感じるってことは、なんなんだろうなぁ。
集合の考え方が、直積集合、写像の集合とひろがっていくのが面白い。

次は加算集合。

当面の目標の整理

ちょっと目標を見失いがちになってきた。。。
そこで整理する。

linuxのptyアプリを書きたい。
- 詳解UNIXを勉強する。
  - C言語を勉強する。★途中
  - UNIXの道具箱を読む。★途中
    - gcc/gdbを勉強する。
NorvigのAIを読みたい。(Common Lispプログラミングの書きぶりを知りたい)
- アルゴリズムとデータ構造について勉強する。
  - C言語を勉強する。★途中
  - C言語でアルゴリズムとデータ構造をやる。
- Common Lispについて基本を復習する。
  - 初めての人のためのLISPを読む。★途中
  - Common Lisp Drillをやる。(Cでアルゴリズムをやった後に実施)
Common Lispを理解したい。
- コンパイルを理解する。
  - パタヘネを理解する。★途中
  - シプサを理解する。
    - 集合30講を読む★途中
  - コンパイラ本を何かやる。
- Lisp In Small Peacesを理解する。
記述論理を理解したい。
- 一階述語論理とホーア論理を理解する。
  - ソフトウエア科学のための論理学を勉強する。
    - 論理学をつくるを勉強する。★途中 (シプサの後に復帰)

全部じゃないけど、まずはこんな感じ。
こつこつがんばる。

【パタヘネ】3章コンピュータにおける算術演算

こつこつ。

3.3 加算と減算
- 3章に入って、文章が少しわかりにくくなった。原文がそうなのか、訳文がそうなのか。
- 「32ビットの数値を2つ加算または減算すると、結果を完全に表現するには33ビットを必要とする場合がある」うーん。わからん。
- 自分なりに考える。
- まず符号付き整数の場合。
- 正の整数で表現できる最大は、01...1。では01...1 + 01...1は、というと、1...10。ということで、これは32ビット符号付き整数の観点では、負の数になる。なので、これを正の数として正しく表現するにはこれの頭に符号ビットがあるべきであり、すると33ビット必要ということ。
- 続いて、負の整数で表現できる最小は、10...0。10...0 + 10...0は、というと(1)0...0。ということで、桁上がりしたものを格納するビットがない。よってこの演算において結果が正しく表現されるには、そもそも33ビットにて符号付き整数を定義しておく必要があったと考えられる。
- 理解できた。
- 「減算においては、正の数から負の数を引いた結果が負の場合、または負の数から正の数を引いた結果が正の場合に、オーバフローが発生したといえる」
- わからない。。。
- 自分なりに考える。
- 前者は正の数どうしの足し算なので、わかる。
- 後者は負の数どうしの足し算なんだけど、上の例で、(1)0...0となったときの最上位ビットが"0"というのが判定条件になる、ということがここまでの話の中身のみで自明だと言えるとは思えない。
- "32ビット符号付き整数の負数a,bがあるとき、a+bが33ビット目に桁上がりするならば、32ビット目は必ず0である"ということを確認or証明するということ。
  - このとき負数は、最上位ビットが必ず1であり、残りのビットは0でも1でもよい、という形式である。
  - よって、負数を加算したとき、必ず架空の33ビット目への桁上がりが発生する。
  - すると、負数の形式から、正しく結果を表現できるときは、31ビット目までの0と1のあり様がどのようなものであっても32ビット目に桁上がりすることを証明せねばならない。これはちょっとわからない。。。
  - なので、「修正2の補数」の考え方をつかって正の数で考えてみる。
  - 10...0以外の負数は、「修正2の補数」の手順に従って同じ大きさの正の数に変換できる。
  - aとbが10...0以外だとする。それらを正の数に変換したものをAとBとする。
  - するとA+Bの結果が正しく表現できないのは、32ビット目に桁上がりして負数の表現になってしまう場合である。すなわち1?...?の形式となる場合。
  - さて、その負数となってしまった表現をCとする。
  - また架空の33ビット目を考えて33ビットによる表現に拡張して議論する。
  - すると、その拡張解釈ではCは負数ではないし、正しい結果の表現である。
  - そのCに対応する負数を「修正2の補数」で考える。
  - するとそれは、(1)0?...? + 1となる。
  - ここで、+1によって、32ビット目に桁上がりするのは、(1)01...1の場合だけである。され、これはCが10...0の場合である。これ以外は32ビット目への桁上がりがないので、32ビット目が0、すなわち、32ビット符号付き整数の形式にて正になっている。
  - Cが10...0の場合は、一応例としてあげると
```
　0111 1111 1111 1111  1111 1111 1111 1111
＋0000 0000 0000 0000  0000 0000 0000 0001

　0111 1111 1111 1111  1111 1111 1111 1101
＋0000 0000 0000 0000  0000 0000 0000 0011
```
    などの場合である。
  - さて、この場合は、32ビット符号付き整数の正の整数の加算としてはオーバフローしているが、32ビット符号付き整数にて負数は正数よりもひとつ多く、10...0も正しい負数として表現できるので、この桁上がりのケースは正しく結果を表現できているとしてよい■
  - 以上にて、
    「負数どうしの減算がオーバフローするときは必ず最上位ビットが0になる、といえる」
- なんかすっきりしないなぁ。

一応これでよしとする。
次は乗算。

【道具箱】第9章 GDB

ひさしぶりに道具箱。

私の環境では、


GNU gdb 6.3.50-20050815 (Apple version gdb-768) (Tue Oct  2 04:07:49 UTC 2007)

だった。

ざっと読んだ。
使い方は、いわゆる?デバッガと同じかんじ。
だけど使いこなすには時間がかかりそうだなぁ。

登録: 投稿 (Atom)