2009-03-15

ケータイ小説　計算機科学入門　第1話

なんでこんなキモい話書くの？

計算機科学︵コンピュータサイエンス︶にも﹁常識﹂があるンだけど現代人は忙しいしましてや技術者はデスマーチ︵研究者でもいるけど︶大学の授業受けたり教科書とか読む暇ないでしょ︵書く暇も︶

情報とか計算機︵コンピュータ︶とか

Computer = 日本語では計算機だけど 1+2=3みたいな計算だけじゃない﹁情報﹂を処理することはみんな﹁計算﹂情報って何、とか言い始めると哲学になっちゃうけど知識の表現ってことにしておいてだから文字や文章はもちろん画像とか音声・音楽とかも情報

計算モデル

﹁計算機科学﹂だから計算機︵っていうか﹁計算﹂そのもの︶について﹁科学﹂するんだけどいちいち電子回路から考えてたら大変だし古来、﹁計算︵機︶﹂は電子回路だけじゃないの本質を明確にしたいから抽象化＝一般化して数学的なモデルを考えるわ

有限状態オートマトン

一番基本的な計算モデルから始めてみるわメモリ＝状態(state)は有限なの有限だからq_0, q_1, q_2, q_3, ..., q_nと列挙できるのそれらの集まりQ = {q_0, q_1, q_2, q_3, ..., q_n}を状態集合と呼ぶわ
﹁ある状態q_iから、入力aを受け取ると、ある状態q_jに変化する﹂とき状態q_iから入力aにより状態q_jに﹁遷移する﹂と言うわそういう一つ一つの遷移は(q_i, a, q_j)という三つ組で書けるから遷移の集まりは{ (q_i_1, a_1, q_j_1), (q_i_2, a_2, q_j_2), (q_i_3, a_3, q_j_3), ..., (q_i_m, a_m, q_j_m) }とか書けるわそれが遷移関係T (q_i, a, q_j)がTに属しているとき見やすくするため q_i ---a---> q_j とか書くわ
あと、最初の状態＝初期状態を決めておかないと計算が始められないから普通、q_0を初期状態とするの
初期状態q_0から入力a, b, c, d, ...を受け取って q_0 ---a---> q_i ---b---> q_j ---c---> q_k ---d---> ... とか状態遷移を繰り返すのそれがオートマトンっていう計算モデルここでは状態が有限だから正確には有限状態オートマトンって呼ぶの
…続く…︵また暇になったら／気が向いたら︶ sumii 2009-03-15 00:00