関係データベースとは

Transcription

1 アルゴリズムって何だろう コンピュータは 今日では日常生活に欠かすことのできない必需品になっています そのコンピュータを使っていろんな処理を行なうとき 我々が知らないバックグラウンドで我々を助けてくれているのは各種のプログラムです ワープロ プレゼンテーションソフト ウェブブラウザ 表計算ソフト データベースソフト 数式処理ソフト さらには ユーザとコンピュータの間を仲介すると同時にそれらのプログラムを管理しているオペレーティングシステム などなど コンピュータは所詮 道具です 道具を使いこなすためには その原理を知っていた方が良いに決まっています ( そうかな? と自問 原理なんて知らなくても使えるものこそ本当の道具だ っていう意見もあるかも ) 自動車の車体構造やエンジンの原理については知らなくても操作法 ( ハンドル 変速ギア ブレーキ ) さえ知っていれば車の運転はできます でも 少なくともエンジンの原理くらいは誰でも知っていますし ( つまり 常識です エンジンという単語を知らない人はいないでしょうから ) 知っていた方が絶対に得です では コンピュータについてはどうでしょう? 寂しいことですけど コンピュータの原理を知っているなんて今のところ常識にまではなっていませんよね だって エンジンという語に相当する語である アルゴリズム について知っている一般人って ごく稀にしかいないじゃないですか 数学を専門にするあなたはいかがですか? アルゴリズムの数学的定義って 知ってます? アルゴリズムの研究は 純粋に数学的興味から始まりました (1930 年代 ) でも コンピュータの発達と相俟って 1960 年代以降になると アルゴリズムあるいはもっと包括的に言うと理論的コンピュータサイエンス ( これは実用に供されることを意識しない 純粋数学的な興味のもとで行われる研究を指します ) の研究が実用的に役立つ場面が増えました 形式言語理論 コンパイラ設計 計算量 ( アルゴリズムの複雑さ ) の理論 暗号 リレーショナルデータベースの理論 データベース設計 これらはほんの一例です こういった事実がさらに研究を活発化し その成果が実用にも還元される という相乗効果的現象が起きています 幾何学と測量との関係がそうであったのと同じように こんな世界をちょっとだけ紹介しましょう 受験校では 数学 B の 数値計算とコンピュータ なんて授業ではカットしてしまうでしょうから 代わりに 授業の中でチョビっとエピソード的に使ってみる程度でもいいかも えっ そんな時間さえ無いですって?

2 1. 問題の発端は 大数学者ヒルベルトです 普通われわれが桁数の大きい2 数の足し算を行なうときには 10 進表記して下の桁から 1 桁ずつ順に桁上がりを考慮しながら足していきます この操作手順は値という概念からは離れて行なわれる機械的なものです このようにまったく機械的な計算 操作の手順 ( 手続き ) のことをアルゴリズムと言います アルゴリズムという名称は 9 世紀のアラビアの数学者 Abu Jafar Mohammed ibn Musa al-khowarizmi の名前に由来するそうです 因みに 彼は Kitab al jabr wal-muqabala という著書でアラビア式 10 進記法について記しており この書名から algebra ( 代数 ) という言葉が生まれたとも言われています ( かの TeX をたった一人で設計 実用化した 有名な D.E.Knuth 大先生の百科事典的著書 "The Arts of Computer Programming" の中で述べられていることの受け売りです ) しかし 今世紀の中頃まではアルゴリズムと言えば数の四則算法 あるいは ユークリッドのアルゴリズム (2つの自然数の最大公約数を求めるための方法であるユークリッドの互除法のこと ) を指すのが普通で 英語の綴りも今日用いられている algorithm ではなく algorism だったようです アルゴリズムという概念の必要性が学問的にも実際的にも当時はそれほど無く アルゴリズムとは何かという数学的な定義などなくても困ることはなかったからです どんな問題に対してもそれを解くアルゴリズムは必ずあるものだと誰もが信じていましたし 実際 ほとんどすべての問題はアルゴリズムを示すことができたからでもあります アルゴリズムとは何かを数学的にきちんと定義する必要を人々が認識するようになったのは 1930 年代になってからです その発端は今世紀の大数学者の一人ヒルベルトが 1900 年にパリで開催された国際数学者会議において行なった講演 D.Hilbert, Mathematical problems, Bull. Amer. Math. Soc. 8, pp , , にあります この講演の中でヒルベルトは当時の数学が解決すべき重要な問題をいくつか 提示しましたが その 10 番目の問題は次のようなものでした : ヒルベルトの第 10 問題 (Hilbert's tenth problem) 任意に与えられた整数係数の多項式 P(x 1,..., x n ) に対し P(x 1,..., x n ) = 0 が自明 でない ( すべてが 0 ではない ) 整数解をもつかどうかを判定するアルゴリズムを求めよ 実は ヒルベルトは数学の体系を完全に形式化 公理化して, 数学のすべての定理を機 械的に証明することを構想していました ( これは今日 ヒルベルトのプログラムと呼ばれ ています ) 2

3 多くの人々が第 10 問題を解くアルゴリズムを求めるために努力しましたが失敗しました なぜなら そのようなアルゴリズムは実は存在しなかったからです そのことはずっと後の 1970 年にロシア人の Ju.v.Matijasevic によって証明されました そんな折 ヒルベルトの弟子のゲーデルが不完全性定理 (Incompleteness Theorem) と呼ばれる衝撃的な定理を証明しました (1931 年 ) それは 自然数の体系を公理化したものを S とすると S が矛盾を含んでいないならば S の中で成り立つことも成り立たないことも示せないような命題が存在する というものであり これにより アルゴリズムが存在しない問題が存在することが証明されたことになり ヒルベルトの構想は挫折してしまいました だからといって 第 10 問題が否定的に解決されたわけではないのですが 第 10 問題に対するアルゴリズムも存在しないのではないかと人々が疑い始めるきっかけになったことは間違いないでしょう アルゴリズムが存在しないことを証明するためには アルゴリズムとは何かを厳密に定義する必要があります ゲーデルの結果以後 アルゴリズムとは何かを数学的に厳密に定義する試みが数多くなされ 1930 年代はアルゴリズム研究の黎明期となりました それらは 1934 年 K.Godel & J.Herbrand: Herbrand-Godel 計算可能関数 (HG-computable function) 1936 年 A.M.Turing: チューリング機械 (Turing machine) 1936 年 S.C.Kleene: 帰納的関数 (recursive function) 1936 (1941) 年 A.Church: λ 定義可能関数 (λ-definable function) 1936 (1943) 年 E.L.Post: ポスト正規システム (Post canonical system) 等ですが それより後に定義された 1954 年 A.A.Markov: マルコフアルゴリズム (Markov normal algorithm) 1956 年 N.Chomsky: 句構造文法 (phrase-structure grammar) 1963 年 J.C.Shepherdson & H.E.Sturgis: ランダムアクセスマシン (RAM, random access machine) 1964 年 C.C.Elgot & A.Robinson: プログラム内蔵方式 RAM (random access stored program machine) 1967 年 A.R.Meyer & D.M.Ritchie: while プログラム (while program) 等も含め これらすべてが アルゴリズム という概念を定義する等価なものであること が証明されています 1936 年 チャーチは 3

4 チャーチの提唱 (Church's thesis) チューリング機械によって記述できるものをアルゴリズムと呼ぼう. と提案し これが受け入れられ それ以後は チューリング機械 およびそれと等価なものがアルゴリズムの定義として用いられるようになり 今日ではこの定義ではダメだと思う数学者はほとんどいません 集合の定義 ( 公理化 ) だってほぼ同時期に行われた ( その舞台には あのフォンノイマンも登場します!) 暗い古い歴史をもつのに その定義を十分だと思わない数学者はいっぱい (?) いますから 安定感がありますね 2. チューリング賞はコンピュータサイエンスのノーベル賞です チューリング機械 (Turing machine) は 1936 年にイギリスの数学者 A.M.Turing が提案した アルゴリズムの数学的定式化 の一つです チューリングは非常な才人で 今日 彼の名を冠してチューリング機械と呼ばれている厳密な数学的思考マシンを考えた ( コンピュータが発明される 10 年以上も前に!) だけでなく 人工知能 ( 例えば チューリングテスト ) 暗号 数値解析などの分野でも歴史に残る業績をあげています そういえば コンピュータの歴史に登場する著名な数学者と言えば プログラム内臓方式の発案者とか言われて ( 実際は もっともっと多大な貢献をしているんですけどね~) 有名なフォン ノイマン (J. von Neumann) もすごい頭脳の持ち主だったみたいですね 歴史に残るような ( コンピュータとは無関係の ) 純粋数学上の優れた業績があるのは勿論ですが 電話帳の数ページくらい 一回目を通すだけで暗記してしまった! とかいうエピソードも残っているくらい 我々とは脳味噌が違っていたようです わき道へそれてしまった話を元に戻しますと 今日 彼の名を冠して チューリング賞 と呼ばれている賞がありますが これは数学におけるフィールズ賞と同様に ノーベル賞が無いコンピュータサイエンスの分野では実質的なノーベル賞です チューリングについてもう少しだけ詳しく知りたければ 末尾に記したウェブサイトを覗いてみてください 3. そのチューリングが考えた思考機械とは さて 話を本題に戻しましょう チューリング機械がどのようなものであるかはこのあと定義しますが 実は チューリング機械って 一昔前のコンピュータをさらに素朴にしたようなものなんです というのは チューリング機械では磁気テープみたいなものを入出力装置 記憶装置兼用で用いるんですが テープの読み書き能力は極限的にシンプルにしてあります つまり 1 回の動作でテープから読み出せるのは 1 文字だけですし 1 回の 4

5 動作でテープに書き込めるのも 1 文字だけです その上 そういうテープ上の文字の読み書き動作をコントロールする制御部だって1 文字で表すだけなんです 機械の 現状態 を 1 文字で表し 現状態とそのとき読んだテープ上の 1 文字とによって テープ上にどんな 1 文字を書き出し 次の状態を何に変えるかを決める これがチューリング機械の1ステップの動作なんです でも こんなシンプルなものでも万能 (universal) つまり 何でもできてしまうんです! これこそ数学の真骨頂じゃないですか! ものの本質を捉えるためには それ以上分解できない ( 他から導くことができない ) もっとも基本的なもの ( これが公理ですよね ) から始めなければいけないんです その基本的なものが何であるかを見極めることこそ難しいことなんですね~ そんなわけでちょっと理解して使いこなすのには骨が折れますが ( チューリング機械と等価で チューリング機械よりもわかりやすい計算モデルだってあるのに~) チューリング機械が今でも計算モデルの主役として用いられている理由は モデルとして非常に単純であること それでいながら高い能力を持つこと そして最大の理由は アルゴリズムの理論の歴史の初期から今日に至るまで標準的な計算モデルとして広く使われてきたために理論的に安定していることなんです 以後 チューリングマシンを TM と略します ここでは テープを 1 本だけ持っている TM を考えましょう 計算開始直前 入力文字列 a1 a2 an q0 読み書きヘッド 空白記号 は 普通は 書かない テープ (tape) とは 図に示したように ます目 (cell, square) が左右無限につづいたものです 各ます目には1つの記号 ( 文字 ) しか書くことができません テープにはヘッド (head) が1つ付いていて このヘッドによって文字を読んだり書き換えたりします テープ上に書くことができる記号をテープ記号といいます ( そんな名称はどうでもいいのですが ) 何も書かれていないテープのます目にも 空白記号と呼ばれる特別の記号( 5

6 で表わすことにします ) が書かれていると考えます TMの制御部には有限量の情報を記憶することができ ( 有限ということが重要です!) 制御部に記憶された情報を状態(state) と呼びます 状態も記号で表します TMは ヘッドが見ている文字を読み取ること ヘッドが見ているます目に文字を書き込むこと ヘッドを右または左に1こま移動させるか 同じ位置にとどめること 有限制御部の状態を変えること をまとめて1 単位時間で実行します 最初 文字 a 1, a 2,, a n をテープ上の n 個の連続するます目に書き込んで与え ( この文字列 a 1 a 2 a n がTMへの入力となります ) 各ヘッドをその文字列の左端に置き ある特定の状態 ( 初期状態といいます ) から動作を開始します 上述の基本ステップを何回か繰り返した後 指定した状態 ( 受理状態といいます ) に到達できるか否かで 入力を " 認識 " します δの定義から TMが受理状態に入ったら それ以上動けなくなり 停止します そのとき テープ上に残された文字列が計算結果 すなわち出力です 以上述べたことをきちんと定義すると次のようになりますが ここは読み飛ばしても差し支えありません (1テープ)TM (single-tape Turing machine) とは 次のような 6 つ組によって定まるシステムのことを言います : M = (Q,Σ,Γ,δ,q 0, F) ここで, 各成分は次のようなものです 1 Q は空でない有限個の文字の集合で Q の元を状態といいます 2 ΣとΓは有限個の文字の集合で Σ Γ, Γ-Σ.Σは入力として使う文字の集合 Γはテープ上で作業用に使う文字の集合を表します はすでに述べたように 空白を表す記号です 3 δは (Q-F) Γから Q (Γ {L,N,R}) への部分関数です 部分関数とは 関数値が定義されていないことがあるという意味です δを M の遷移関数 (transition function) とか動作関数 (next move function) と呼ぶことがありますが そんな名前はどうでもいいことです 4 q 0 は Q の元で TMが計算を始める最初に取る状態を表し 初期状態 (initial state) といいます 5 F は Q の部分集合で F の元を受理状態 (accepting state) といいます TMが受理状態に入ると 計算開始前に与えた入力文字列は受理されたと定義します そうでないとき つまり 決して受理状態に至らないとき ( それ以上動きようがない状態に入ってしま 6

7 うか または動作がループに陥ってしまう場合 ) 入力は拒否されたと定義します TM は 与えられた入力を受理するか拒否するかで 認識するのです TMをはじめとするコンピュータの数学的モデル ( そのようなものをオートマトン (automaton) と呼びます ) を研究する人たちの間では 様相 (configuration) という述語がよく使われます TMの様相とは TMがある時刻にどのような状況にあるかを表したもので 現在の状態は何か テープ読み書きヘッドはテープ上のどの位置にあるか テープにはどのような内容 ( 空白以外の文字が書き込まれている各ます目の内容 = 文字列 ) が書かれているかによって表わすことができます ある様相から別の様相へ1ステップで動作する仕方を決めるのが動作関数 δです いま 下図のように TMの現在状態が q で 読み書きヘッドが読んでいる記号が a だったとしましょう ( 下図 ) このとき もし δが δ(q, a) = (p, b, L) と定義されていたとしたら TMは状態を p に変え テープ上の a を b に書き換え ヘッドを1こま左に動かします L は left を表します 同様に R の場合は right( ヘッドを右に1こま動かす ) を表し N の場合は nuetral( ヘッドを動かさない ) を表します 動作前 a1 a2 a a3 a4 q δ(q, a) = (p, b, L) 7

8 動作後 a1 a2 b a3 a4 p このような1ステップの動作をつづけて 最後にTMが受理状態に入ったら 最初に与えた入力 a 1 a 2 a n は受理されます また テープ上に残された文字列が出力です このように考える場合には TMは入力文字列を出力文字列に変換する機械と考えることもできます TMを研究道具としている研究者達は実はそのようには考えませんが そのように考えても本質は変わりません 動作完了時 この部分以外は空白こまのみ c1c2ckck+1 が出力 c1 c2 ck ck+1 f f は受理状態 例 例として自然数( 正整数 ) の掛け算を行うTMを設計してみましょう まず 整数をどのように表現するかを決めましょう 簡単のために 正整数 n は文字 1 を n 個並べたものと同一視することにします : 整数 3 文字列 111 整数 5 文字列

9 といった具合です 掛ける2つの整数は それに対応する1の列の間に空白記号 を1つだけ挟んだ文字列で表すことにします : さて 掛け算 n m は m のコピーを重ならないように n 個作ることで行ないます すなわち 1が連続して n m 個テープ上に残るようにします 上述の約束から それは整数 nm を表しており 積が求められたことになります このように掛け算を行なうTMの動作をδ 関数で記述しても その定義式を見ただけではすぐには理解できませんし かといって丁寧に説明するのも面倒ですから 実際の動作を PowerPoint で見てみることにしましょう これが 2 3 の計算を開始する前の TM の 様相 です q0 計算を開始すると その実行の過程は TM.ppt( 左クリック ) となります slide9.gif ( これが開始時の様相 ) slide87.gif ( これが終了時の様相 ) 計算が終了したとき テープ上には 6 個の 1 つまり値 6 が出力されています めでたし めでたし! こんな簡単な計算のモデルなのに これで万能 つまり どんなアルゴリズムもチ 9

10 ューリング機械で記述することができるのです! 他の計算モデルの例は 例えば を見てください 5. 一般的に解く方法がない問題があるんです! 昔 (100 年前 ) は 答えを求める方法 ( すなわち アルゴリズム ) が無い問題があるなんて誰も思っていなかった と冒頭で書きました でも今は そういう問題 ( 決定不能問題とか非可解問題 (undecidable problem, unsolvable problem) と言います ) が山ほどあることが分かっています 最初に発見されたそういう問題はゲーデルが証明した不完全性定理なんですが その証明はちょっとここで説明できるほど簡単ではありません ( 大学の数学科の講義で半年ほどかかります ) が チューリング機械を使うとずっと簡単にそういう問題の例を示すことができます はじめに 問題を符号化することを考えましょう 符号化 (coding) とは 特定の文字だけを使って 対象となるすべてのものを文字列 ( 符号語 コード ) として表すことです 次のような例を考えてみます 下図のように 平面上にいくつかの頂点 ( で表しています 頂点の名前を の中に書きました ) があり それらの間を結ぶ辺 ( 向きがあってもなくてもいいですが 下図は辺に向きがあるグラフの例です ) がいくつかあるものをグラフ (graph) といいます a b c d f e g グラフ ( 有向グラフ ) さて このグラフの上を辺の向きに従って すべての頂点をちょうど 1 回ずつたどって 10

11 元の頂点に戻ってくる道順はあるでしょうか? 答えは末尾に示したとおり yes です 任意にグラフが与えられたとき そのような道順があるかどうかを判定する問題はハミルトン閉路問題 (Hamilton circuit problem) と呼ばれています これと類似の問題として有名なのが巡回セールスマン問題 (traveling salesperson problem) です 頂点を都市 辺を都市と都市を結ぶ道と考え 各辺にはその道の長さを表す数値が付いているとしたとき すべての都市をちょうど 1 回ずつたどって出発点に戻ってくるような道順を求めよ という問題です どちらも解く方法 ( アルゴリズム ) はありますが 答えを求めるのにとてつもない時間がかかる方法しか知られていませんし それより良い方法は多分無いだろうと信じられている問題 (NP 完全問題 (NP-complete problem) といいます ) の一例です 話が また脇道にそれてしまいました コーディングに話を戻しましょう ハミルトン閉路問題とか巡回セールスマン問題などをコーディングするためには グラフをどのようにコード化する ( 文字列で表す ) かが問題になります ここでは 次のような方法を使うことにします G = (V, E) をグラフとします ただし G はグラフにつけた名前 V は G の頂点の集合 EはGの辺の集合です V = { v1,..., vn }, E = { e1,..., em } とします 頂点はその添字 1~n の 2 進数表現で表すことにします iの 2 進数表現を i で表すことにします そして 辺 e=(vi, vj) 辺 (vi, vj) vi vj は その頂点の添字の 2 進数表現の対 e:= i#j で表します 最後に グラフ G は 辺の集合と同一視できますから そのコード G は G=e1## ##em であると定義します 例えば 下図のグラフは G = 1#100##1#101##01#101##11#10##11#11##100#11##101#110##110#1 11

12 となります v1 v2 v3 v4 v5 v6 詳細は省略しますが チューリング機械も似たような方法で文字 0と1だけを使ってコーディングできます このとき チューリング機械 M のコード M は2 進数だと見ることができます チューリング機械のコードになっていないような2 進数もありますが そのような2 進数は何もしないチューリング機械のコードであると考えます コードが x であるようなチューリング機械を M x で表すことにしましょう さて 2 進数 ( つまり 0と1の列 )xをチューリング機械 Mx に入力として与えたとき xが受理されないか否かということを判定する問題を考えます もし この問題を解くアルゴリズム すなわちチューリング機械があったとしましょう それをMとします Mのコードを M=x0 とします ( つまり M=Mx0) このとき M=Mx0 なので 1 Mはxを受理する Mx0 はxを受理するであり Mは Mx がxを受理しないかどうかを判定する (Mx が x を受理しないときMはxを受理し Mx が x を受理するときMはxを受理しない ) チューリング機械ですから 2 Mはxを受理する Mx はxを受理しないが成り立ちます したがって 12より 3 Mx0 はxを受理する Mx はxを受理しないということが任意のxに対して成り立つことになります そこで Mx0 に自分自身のコードであるx0 を入力してみましょう 3より Mx0 はx0 を受理する Mx0 はx0 を受理しないという矛盾が導かれてしまいました 12

13 受理しない 受理する x Mx 受理する 受理しない M=Mx0 何と簡単なことでしょう! 解くための方法 ( アルゴリズム = チューリング機械 ) が存在しない問題が存在する という定理が 1 時間もかけずに証明できてしまいました! 参考ウェブサイト : コンピュータ偉人伝 ) 伝 ) 同上 ) チューリング賞受賞講演 ( 翻訳本の紹介 ) チューリング伝他 ) お薦めその他にも 検索エンジンで チューリング を検索すると何千件もヒットします 参考書 : 西野哲朗 中国人郵便配達問題 =コンピュータサイエンス最大の難関 講談社選書 守屋悦朗 チューリングマシンと計算量の理論 培風館 渡辺治 計算可能性 計算の複雑さ入門 近代科学社

14 p.11 の問に対する答 ( がハミルトン閉路 ) a b c d f e g 14