情報と知恵
情報という言葉は、世に満ち満ちています。今の世では、その使い方は大変重要なようです。これについて、少し落ち着いて考えてみました。
情報とは、それを知ることで今まで不確かであったことが少しでも確からしくなる知識のことですね。これを得るには、意識して捜さなければなりません。
まず、知りたいことAがあります。初めは、Aについての知識はないとします。そこで、Aについて知っていそうなC1に当たり、Aについての知識B1を得ます。これで、Aのありそうな範囲が狭まります。これを情報と呼びます。
情報処理では、情報を探り出す作業を検索といいます。これには、うまいやり方とそうでないやり方があります。
世の中には一を聞いて十を知る英才もいれば、何度教えても学ばない御仁も居ます。ここで、一を聞いて（すなわち、一つの経験あるいは1回の調査から得た情報を理解して）これをその後の行動に生かすときの検索の効率について考えてみました。
いま、検索効率を、次のように決めましょう。
検索効率 ： 目的のものを見つけるまでの検索の回数
考えの筋道を明らかにするため次のような問題の設定をし、これを通して探索効率について考えてみました。
問題の記述
「n個のデータが書き込まれたファイルがある。データの数nは分かっており､このファイルの中に探したい指定データａがあるがそれがどこにあるか知りたい。
求めるデータの探し方には、検索のためのデータの準備の仕方も含めて、効率的なものとそうでないものとがあります。その効率の測定ですが、既に定義したように、目的のものを見つけ出すまでの探索の回数で測るのが合理的です。記号として、
としておきます。
さてこれから、賢くないやり方のほうから順にとりあげ、その効率について考えてみます。
手当たり次第に調べる方法
まず、どう見ても賢くない方法は、n個のデータからでたらめに選ぶことを当たるまで繰り返す方法でしょう。この方法では、指定のものを見つけるのは偶然しかない。選んだものが偶然に指定のものと一致する確率は 1/nで、nが大きいときは偶然当たる確率は非常に小さい。はずれた次もまた偶然を頼りにデタラメに選ぶということは、１つを選ぶことで得た情報をつぎの探索にまったく使わないことです。したがって、効率は恐ろしく悪い。たとえて言えば、経験からまったく学ばない生き方と同じです。
“バカは死ななきゃ直らない”というやりかたです。
厳密に計算すると、n＝1000のときデタラメに探して1000回以内に偶然見つかる確率は0.6321です。また、99％の確率で見つけるためには、4600回程度の運を天に任せた選択の繰り返しが必要です。
経験の墨守
前の“手当たり次第”よりは少しよい次の方法は、ファイルのデータの任意のものを選んでそれを指定のものと比べ、一致しなければそれを除いたものから次を選ぶことを繰り返す調べ方です。今確かめたデータは求めるものではないのですから、その情報を使いつぎの検索範囲を一つ狭めることができます。これを続けると調べる範囲が着実に狭くなり、ついには調べる範囲が１個になり確実に見つけることができるわけです。すなわち、最大(n-1)回調べれば確実に見つけられます。
指定のものを見つけるまでに最大n回であり、運がよければ1回で見つかることもあるので、平均はn/2回の検索で見つかるとみなせます。大雑把に言えば、データ数nとおなじオーダの検索回数で見つけられる訳です。
T(n)=n
1回の探索から得た情報の利用という観点からいえば、この方法にはもっと工夫の余地がありそうです。経験したそのものを記憶するのみで内容の意味とか理由などを考えようとせず、ただ過去に起きた同じ事を避けようとする愚直な反応によく似ていますね。
0 件のコメント:
コメントを投稿