関係データベースとは

アルゴリズムって何だろう

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

１．問題の発端は、大数学者ヒルベルトです

普通われわれが桁数の大きい２数の足し算を行なうときには、10 進表記して下の桁から １桁ずつ順に桁上がりを考慮しながら足していきます。この操作手順は値という概念から は離れて行なわれる機械的なものです。このようにまったく機械的な計算・操作の手順（手 続き）のことをアルゴリズムと言います。アルゴリズムという名称は、９世紀のアラビア の数学者 Abu Jafar Mohammed ibn Musa al-Khowarizmi の名前に由来するそうです。因み に、彼は Kitab al jabr wal-muqabala という著書でアラビア式 10 進記法について記して おり、この書名から algebra （代数）という言葉が生まれたとも言われています(かの TeX をたった一人で設計・実用化した、有名な D.E.Knuth 大先生の百科事典的著書 "The Arts of Computer Programming" の中で述べられていることの受け売りです)。 しかし、今世紀の中頃まではアルゴリズムと言えば数の四則算法、あるいは 「ユークリ ッドのアルゴリズム（２つの自然数の最大公約数を求めるための方法であるユークリッド の互除法のこと）を指すのが普通で、英語の綴りも今日用いられている algorithm ではな く algorism だったようです。アルゴリズムという概念の必要性が学問的にも実際的にも 当時はそれほど無く、アルゴリズムとは何かという数学的な定義などなくても困ることは なかったからです。どんな問題に対してもそれを解くアルゴリズムは必ずあるものだと誰 もが信じていましたし、実際、ほとんどすべての問題はアルゴリズムを示すことができた からでもあります。 アルゴリズムとは何かを数学的にきちんと定義する必要を人々が認識するようになった のは 1930 年代になってからです。その発端は今世紀の大数学者の一人ヒルベルトが 1900 年にパリで開催された国際数学者会議において行なった講演

D.Hilbert, Mathematical problems, Bull. Amer. Math. Soc. 8, pp.437-445, 478-479, 1901.

にあります。この講演の中でヒルベルトは当時の数学が解決すべき重要な問題をいくつか 提示しましたが、その 10 番目の問題は次のようなものでした:

ヒルベルトの第 10 問題 (Hilbert's tenth problem)

任意に与えられた整数係数の多項式 P(x1, ..., xn) に対し、P(x1, ..., xn) = 0 が自明

でない（すべてが 0 ではない）整数解をもつかどうかを判定するアルゴリズムを求めよ。

実は、ヒルベルトは数学の体系を完全に形式化・公理化して，数学のすべての定理を機 械的に証明することを構想していました（これは今日、ヒルベルトのプログラムと呼ばれ ています）。

多くの人々が第 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 年、チャーチは

チャーチの提唱 (Church's thesis) チューリング機械によって記述できるものをアルゴリズムと呼ぼう． と提案し、これが受け入れられ、それ以後は、チューリング機械、およびそれと等価なも のがアルゴリズムの定義として用いられるようになり、今日ではこの定義ではダメだと思 う数学者はほとんどいません。集合の定義(公理化)だってほぼ同時期に行われた（その舞 台には、あのフォンノイマンも登場します！）暗い古い歴史をもつのに、その定義を十分 だと思わない数学者はいっぱい(？)いますから、安定感がありますね。

２．チューリング賞はコンピュータサイエンスのノーベル賞です

チューリング機械 (Turing machine) は、1936 年にイギリスの数学者 A.M.Turing が提 案した「アルゴリズムの数学的定式化」の一つです。 チューリングは非常な才人で、今日、 彼の名を冠してチューリング機械と呼ばれている厳密な数学的思考マシンを考えた（コン ピュータが発明される 10 年以上も前に！）だけでなく、人工知能（例えば、チューリング テスト）、暗号、数値解析などの分野でも歴史に残る業績をあげています。そういえば、 コンピュータの歴史に登場する著名な数学者と言えば、プログラム内臓方式の発案者とか 言われて（実際は、もっともっと多大な貢献をしているんですけどね～）有名なフォン・ ノイマン（J. von Neumann）もすごい頭脳の持ち主だったみたいですね。歴史に残るよう な（コンピュータとは無関係の）純粋数学上の優れた業績があるのは勿論ですが、電話帳 の数ページくらい、一回目を通すだけで暗記してしまった！、とかいうエピソードも残っ ているくらい、我々とは脳味噌が違っていたようです。 わき道へそれてしまった話を元に戻しますと、今日、彼の名を冠して「チューリング賞」 と呼ばれている賞がありますが、これは数学におけるフィールズ賞と同様に、ノーベル賞 が無いコンピュータサイエンスの分野では実質的なノーベル賞です。 チューリングについてもう少しだけ詳しく知りたければ、末尾に記したウェブサイトを 覗いてみてください。

３．そのチューリングが考えた思考機械とは

さて、話を本題に戻しましょう。チューリング機械がどのようなものであるかはこのあ と定義しますが、実は、チューリング機械って、一昔前のコンピュータをさらに素朴にし たようなものなんです。というのは、チューリング機械では磁気テープみたいなものを入 出力装置・記憶装置兼用で用いるんですが、テープの読み書き能力は極限的にシンプルに してあります。つまり、1 回の動作でテープから読み出せるのは 1 文字だけですし、1 回の

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

♭

a

2

a

n

a

1

♭

♭

♭

_…

…

…

q0 読み書きヘッド _{空白記号♭は、普通は} 書かない 入力文字列

計算開始直前

で表わすことにします)が書かれていると考えます。ＴＭの制御部には有限量の情報を記憶 することができ（有限ということが重要です！）、制御部に記憶された情報を状態(state) と呼びます。状態も記号で表します。 ＴＭは、  ヘッドが見ている文字を読み取ること  ヘッドが見ているます目に文字を書き込むこと  ヘッドを右または左に１こま移動させるか、同じ位置にとどめること  有限制御部の状態を変えること をまとめて１単位時間で実行します。最初、文字

a

₁,

a

₂, …,

a

_n をテープ上の n 個の連続 するます目に書き込んで与え(この文字列

a

₁

a

₂

…a

_n がＴＭへの入力となります)、各ヘッド をその文字列の左端に置き、ある特定の状態(初期状態といいます)から動作を開始します。 上述の基本ステップを何回か繰り返した後、指定した状態(受理状態といいます)に到達で きるか否かで、入力を "認識" します。δの定義から、ＴＭが受理状態に入ったら、それ 以上動けなくなり、停止します。そのとき、テープ上に残された文字列が計算結果、すな わち出力です。 以上述べたことをきちんと定義すると次のようになりますが、ここは読み飛ばしても差 し支えありません。

（１テープ）ＴＭ (single-tape Turing machine)とは、次のような 6 つ組によって定ま るシステムのことを言います：

Ｍ = (Q,Σ,Γ,δ,q

0

, F)

ここで，各成分は次のようなものです。 ① Q は空でない有限個の文字の集合で、Q の元を状態といいます。 ② ΣとΓは有限個の文字の集合で、Σ⊆Γ, ♭∈Γ－Σ．Σは入力として使う文字の 集合、Γはテープ上で作業用に使う文字の集合を表します。♭はすでに述べたように、空 白を表す記号です。 ③ δは (Q-F)×Γから Q×(Γ×{L,N,R}) への部分関数です。部分関数とは、関数値が 定義されていないことがあるという意味です。δを M の遷移関数(transition function)と か動作関数(next move function)と呼ぶことがありますが、そんな名前はどうでもいいこ とです。 ④ q0は Q の元で、ＴＭが計算を始める最初に取る状態を表し、初期状態(initial state) といいます。 ⑤ F は Q の部分集合で、F の元を受理状態(accepting state)といいます。ＴＭが受理 状態に入ると、計算開始前に与えた入力文字列は受理されたと定義します。そうでないと き、つまり、決して受理状態に至らないとき（それ以上動きようがない状態に入ってしま

うか、または動作がループに陥ってしまう場合）入力は拒否されたと定義します。ＴＭは 与えられた入力を受理するか拒否するかで、認識するのです。 ＴＭをはじめとするコンピュータの数学的モデル（そのようなものをオートマトン (automaton)と呼びます）を研究する人たちの間では「様相(configuration)」という述語 がよく使われます。ＴＭの様相とは、ＴＭがある時刻にどのような状況にあるかを表した もので、  現在の状態は何か  テープ読み書きヘッドはテープ上のどの位置にあるか  テープにはどのような内容(空白以外の文字が書き込まれている各ます目の内容＝ 文字列)が書かれているか によって表わすことができます。ある様相から別の様相へ１ステップで動作する仕方を決 めるのが動作関数δです。 いま、下図のように、ＴＭの現在状態が q で、読み書きヘッドが読んでいる記号が a だ ったとしましょう（下図）。このとき、もし、δが

δ(q, a) = (p, b, L)

と定義されていたとしたら、ＴＭは状態を p に変え、テープ上の a を b に書き換え、ヘッ ドを１こま左に動かします。L は left を表します。同様に、R の場合は right(ヘッドを右 に１こま動かす)を表し、N の場合は nuetral(ヘッドを動かさない)を表します。

a

4

a

a

3

a

2

a

1

…

…

q

動作前

δ(

q

,

a

) = (

p

,

b

,

L)

このような１ステップの動作をつづけて、最後にＴＭが受理状態に入ったら、最初に与 えた入力

a

₁

a

₂

…a

_n は受理されます。また、テープ上に残された文字列が出力です。このよ うに考える場合には、ＴＭは入力文字列を出力文字列に変換する機械と考えることもでき ます。ＴＭを研究道具としている研究者達は実はそのようには考えませんが、そのように 考えても本質は変わりません。 〔例〕例として自然数(正整数)の掛け算を行うＴＭを設計してみましょう。 まず、整数をどのように表現するかを決めましょう。簡単のために、正整数 n は文字「１」 を n 個並べたものと同一視することにします： 整数３ → 文字列１１１ 整数５ → 文字列１１１１１

c

k+1

…

c

k

c

2

c

1

…

…

f

動作完了時

この部分以外は空白こまのみ ｆは受理状態

c

1

c

2

…c

k

c

k+1が出力

a

4

b

a

3

a

2

a

1

…

…

p

動作後

といった具合です。掛ける２つの整数は、それに対応する１の列の間に空白記号♭を１つ だけ挟んだ文字列で表すことにします： ４×６ → １１１１♭１１１１１１ さて、掛け算 n×m は、m のコピーを重ならないように n 個作ることで行ないます。すな わち、１が連続して n×m 個テープ上に残るようにします。上述の約束から、それは整数 nm を表しており、積が求められたことになります。 このように掛け算を行なうＴＭの動作をδ関数で記述しても、その定義式を見ただけで はすぐには理解できませんし、かといって丁寧に説明するのも面倒ですから、実際の動作 を PowerPoint で見てみることにしましょう。 これが「２×３」の計算を開始する前のＴＭの〝様相″です。 計算を開始すると、その実行の過程は TM.ppt（左クリック）となります。 slide9.gif （これが開始時の様相） slide87.gif （これが終了時の様相） 計算が終了したとき、テープ上には６個の１、つまり値６が出力されています。めでたし、 めでたし！ こんな簡単な計算のモデルなのに、これで

万能、つまり、どんなアルゴリズムもチ

♭

1 1

♭

1

♭

1

_…

q

0

３

♭

1

♭

２

ューリング機械で記述することができるのです！

他の計算モデルの例は、例えば http://www.edu.waseda.ac.jp/~moriya/research/math-cs.html を見てください。

５．一般的に解く方法がない問題があるんです！

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

元の頂点に戻ってくる道順はあるでしょうか？ 答えは末尾に示したとおり、yes です。 任意にグラフが与えられたとき、そのような道順があるかどうかを判定する問題はハミ ルトン閉路問題(Hamilton circuit problem)と呼ばれています。これと類似の問題として有 名なのが巡回セールスマン問題(traveling salesperson problem)です。

『頂点を都市、辺を都市と都市を結ぶ道と考え、各辺にはその道の長さを表す数値が 付いているとしたとき、すべての都市をちょうど 1 回ずつたどって出発点に戻ってく るような道順を求めよ』 という問題です。どちらも解く方法(アルゴリズム)はありますが、答えを求めるのにとてつ もない時間がかかる方法しか知られていませんし、それより良い方法は多分無いだろうと 信じられている問題（ＮＰ完全問題(NP-complete problem)といいます）の一例です。 話が、また脇道にそれてしまいました。コーディングに話を戻しましょう。ハミルトン 閉路問題とか巡回セールスマン問題などをコーディングするためには、グラフをどのよう にコード化する(文字列で表す)かが問題になります。ここでは、次のような方法を使うこと にします。 G = (V, E) をグラフとします。ただし、G はグラフにつけた名前、V は G の頂点の集合、 ＥはＧの辺の集合です。 V = { v1, ..., vn }, E = { e1, ..., em } とします。頂点はその添字1～n の 2 進数表現で表すことにします。ｉの 2 進数表現を ｉ で表すことにします。そして、辺 ｅ＝(vi, vj) は、その頂点の添字の2 進数表現の対 ｅ：= ｉ#ｊ で表します。最後に、グラフG は、辺の集合と同一視できますから、そのコードＧは Ｇ＝ｅ1＃＃・・・＃＃ｅm であると定義します。例えば、下図のグラフは Ｇ ＝ 1#100##1#101##01#101##11#10##11#11##100#11##101#110##110#1 ｖi ｖj 辺 (vi, vj)

となります。 詳細は省略しますが、チューリング機械も似たような方法で文字０と１だけを使ってコ ーディングできます。このとき、チューリング機械M のコード Ｍ は２進数だと見ること ができます。チューリング機械のコードになっていないような２進数もありますが、その ような２進数は何もしないチューリング機械のコードであると考えます。コードが x であ るようなチューリング機械を

M

ｘ で表すことにしましょう。 さて、２進数(つまり、０と１の列)ｘをチューリング機械Ｍxに入力として与えたとき、 ｘが受理されないか否かということを判定する問題を考えます。もし、この問題を解くア ルゴリズム、すなわちチューリング機械があったとしましょう。それをＭとします。Ｍの コードを Ｍ＝x0 とします（つまり、Ｍ＝Ｍx0）。このとき、Ｍ＝Ｍx0なので、 ① Ｍはｘを受理する ⇔ Ｍx0はｘを受理する であり、ＭはMxがｘを受理しないかどうかを判定する(Mxがx を受理しないときＭはｘを 受理し、Mxがx を受理するときＭはｘを受理しない)チューリング機械ですから、 ② Ｍはｘを受理する ⇔ Ｍxはｘを受理しない が成り立ちます。したがって、①②より、 ③ Ｍx0はｘを受理する ⇔ Ｍxはｘを受理しない ということが任意のｘに対して成り立つことになります。そこで、Ｍx0に自分自身のコード であるｘ0を入力してみましょう。③より、 Ｍx0はｘ0を受理する ⇔ Ｍx0はｘ0を受理しない という矛盾が導かれてしまいました。 v2 v1 v3 v4 _v5 v6

何と簡単なことでしょう！ 『解くための方法(アルゴリズム＝チューリング機械)が存在しない問題が存在する』 という定理が１時間もかけずに証明できてしまいました！

参考ウェブサイト：

・http://www.em.edu.waseda.ac.jp/~moriya/research/math-cs.html ・http://www.em.edu.waseda.ac.jp/~moriya/research/complexity.html ・http://www.chienowa.co.jp/frame1/ijinden/index.html（コンピュータ偉人伝） ・http://www.chienowa.co.jp/frame1/ijinden2/Alan_Turing.html（A.M.Turing 伝） ・http://www.math.sci.hiroshima-u.ac.jp/aa/sotsuken/1998/turing.html（同上） ・http://www.amazon.co.jp/exec/obidos/ASIN/4320024877/249-4472615-3513120（チュー リング賞受賞講演（翻訳本の紹介） ・http://www1.accsnet.ne.jp/~thoshino/WhoisTuring.html（チューリング伝他）お薦め その他にも、検索エンジンで「チューリング」を検索すると何千件もヒットします。

参考書：

・西野哲朗、『中国人郵便配達問題＝コンピュータサイエンス最大の難関』、講談社選書、 1999． ・守屋悦朗、『チューリングマシンと計算量の理論』、培風館、1997． ・渡辺治、『計算可能性・計算の複雑さ入門』、近代科学社、1992．

Ｍ＝Ｍ

x0

ｘ

_M

_x 受理しない 受理する 受理する 受理しない

a ｂ ｃ ｄ ｅ ｇ ｆ ｐ．11 の問に対する答（ がハミルトン閉路）