本講義ではコンピュータ・ソフトウェアの基礎を学びますが，より詳しく言う と「アルゴリズム」と呼ばれるものの基礎を学びます．
アルゴリズムとは?
アルゴリズムとは，計算機に何かをさせる手順を記述したもので，要する に，プログラムというのと同じことです．ニュアンスとしては，アルゴリズム は，明確に定められた問題に対するプログラムのことを言い，したがってこの プログラムは正しい・正しくない，というのが正確に議論できるようなプログ ラムのことをアルゴリズム言う，ということになっているようです．たとえば 「整数の素因数分解をする」という問題は明確に定められているので，これを 行うプログラムは「整数の素因数分解をするアルゴリズム」と呼ぶわけです．
一方たとえば，スクリーンセーバはプログラムには違いないでしょうが，そも そも何を持って「正しいスクリーンセーバ」というのかわかりませんから，ス クリーンセーバのことを，プログラムとは読んでもアルゴリズムとは呼ばない のが普通です．もっともこの線引きも，「手書き文字認識」のような問題に当 てはめると妥当かどうかよくわからなくなります．手書き文字認識も正解と不 正解はどこかで曖昧になってきます．一方で，いくつもの「アルゴリズム」が 提案されている問題でもあり，手書き文字認識をアルゴリズム研究の対象外と いうのも，おかしな話です．何か，少しでも難しいことを達成するプログラム に敬意を表して，アルゴリズムと呼んでいる，という程度に思っていてもよさ そうです．いずれにせよ，ここでの主題ではないのであまり深入りするのはや めておきましょう．
中心極限定理によって確率を見つける方法
もうひとつのニュアンスの違いとしてはプログラムというと特定のプログ ラミング言語や，少なくとも計算機による実行というのが想定されているのに 対し，アルゴリズムというのはもう少し計算機という実体や特定のプログラム 言語の文法のようなものとは独立な，抽象的な概念である，という違いもある ようです．たとえば小学校のときに習った筆算での割り算は，プログラムの形 では習いませんでしたが，要するに「この決められた手順に従うと，必ず答え が出る」という曖昧さのない手順という意味で，アルゴリズムと呼んでもよい ものです．要するに，人間特有の，臨機応変で，なぜこのようなことを思いつ くのかわからないけどなぜか解けてしまう，ということには一切期待しない 「この手順(例: 筆算)で必ずこの問題(例: 割り算)は解ける」というような手 順のことをアルゴリズムと呼ぶわけです．数学に出てきたガウスの消去法や， シュミットの直交化法のようなものも，アルゴリズムと呼んで差し支えないも のでしょう．「ある問題はこの手順で必ず(個々の例題に対してなんら新しい ひらめきを要することなく)解ける」ということをきちんと記述しようとすると， それがアルゴリズムということになります．
しかしそうは言ってもアルゴリズムを記述するにはそのためのわかりやすい表 記が必要ですし，それには結局プログラムが一番便利で明確ということになり ます．というわけでさんざん御託を並べた挙句，「アルゴリズム＝プログラム」 と考えても大して差し障りはない，というのが結論です．要するに，何か明確 な問題を設定し，それを達成するプログラムを考えたり，そのプログラムが正 しいことをできるだけ厳密に論証する，というのがアルゴリズムを学ぶという ことの第一歩です．
対象とする問題の例
もっとも初歩的な問題の例をあげておくと，
- 与えられたデータを大小関係の順に並べ替える
- 文字列から与えられた部分文字列を発見する(たとえばこの文章の中から 「アルゴリズム」という文字列を発見する)．
などがあります．もう少し難しそうな問題の例としては，
必要な材料を構築し、それがどのように動作する加速度計
- 方程式 a1 x1 + ... + an xn = b を解く．ただし，ai と bは与えられた 整数で，未知数 x1, ..., xn は 0または1の値をとる．解がなければないと言う．
- 与えれた整数を素因数分解する．
- 整数を係数とする多項式の整数解を見つける．なければないと言う．
- 将棋やオセロゲームの盤面が与えられて， 必勝手があればそれを見つける．なければないと言う．
などがあります．これらも 「明確に定義された問題」のひとつであることはすぐにわかるでしょう．
本講義の目的はアルゴリズムの基礎を学ぶことに主眼を置くので，具体的 に取り上げるアルゴリズムは主に，最初にあげたような「初歩的な」ものが中 心になります．そのようなアルゴリズムを取り上げて，それが正しいというこ とを少し厳密に論証すること，アルゴリズムの記述を実際にプログラムとして 実現して実行すること，などが最初の関門です．
計算量という概念
実は「正しいことの論証」以外にもうひとつ同じくらい基本的，かつ重要な概 念があります．それはアルゴリズムの計算量という 概念です．たとえば「与えられたデータを大小関係の順に並べ替える」という 問題が計算機によって実行可能であるということは，誰が聞いてもほとんど当 たり前のように思うことでしょう．しかしこのような自明と思えるような問題 でも，工夫のないアルゴリズムではたちまち，実行時間が大きすぎて小さなデー タしか処理できない，ということが置き得ます．授業でもそのようなことを実 際に課題として体験してもらいます．速いアルゴリズムと遅いアルゴリズムで は処理時間に何千倍もの開きが出ます．それはつまり，大きなデータに対して 実用上使えるアルゴリズムとそうでないアルゴリズムの差ということになりま す．整列の問題は歴史的にも，アルゴリズムの発明によって劇的な高速化が達 成された問題のひとつです．似たような他の例としては，FFT (高速フーリエ 変換)があります．
座標平面上のパスの最小距離を見つける方法
速いアルゴリズムを発明するというのは，個々の問題に対して新しいひら めきを要することですが，それ以前に基本として身につけておくべき概念が計 算量という概念です．これは要するに，アルゴリズムが実行を開始して停止す るまでに，どのくらい時間がかかるかというものです．もちろんそれは計算機 によってもプログラミング言語によっても違います．そうかといって「やって みないと何もわからない」というのでは話になりません．ここでの目的は，良 いアルゴリズムと悪いアルゴリズムの差を判定できるようになることであって， 計算機やプログラミング言語の癖によってひっくり返ってしまうような微妙な 差(現実的には微妙でないことも多いですが)を捕らえるのはあきらめています． そのようなアルゴリズム間の大きな差を，大雑把に比較するための，経験的， とはいっても数学的に厳密な，枠組みが「計算量」の概念です．大雑把とはい いながら，現実にアルゴリズムを設計する上で基本的で非常に有用な理論です．
易しい問題と難しい問題
アルゴリズムを学んだ結果，身に着けてほしい概念として重要なことの3つ 目は，「世の中そうは言っても難しい問題だらけ」ということです．ここでい う難しい問題というのは「計算機にとって」という意味であって，人間が解法 を思いつくのが難しい，というのとは違います．もちろん両者は結果的に重な る部分もありますが，ポイントは人間にとって難しいかどうかというような主 観的な話ではないということです． 難しい問 題とはどういう問題で，それがどのように定式化されていて，そして一見簡単 そうで実は難しいという数多くの問題を知ることが目標です．計算量について 学ぶことはその第一歩です．
現在計算機によってできないことというのは枚挙に暇がありません．ロボッ トがよちよち二足歩行をしただけであれだけ騒がれるのですから，いかに計算 機というものが未熟かがよくわかるというものです．ただ，そのような問題の 難しさは計算機の本質的な限界によるものなのか，我々が安定した二足歩行の 仕組みをよく知らないこと，つまり二足歩行を計算機に指導する方法を知らな いこと，によるものなのかわかりません．同じような話としては，計算機によ る，人間が書いた文章(自然言語)の理解，自動翻訳，人間らしい自然な音声の 合成，などの，いわゆる「人間っぽい処理の模倣」があります．これらは「計 算機にとって絶対に難しい」といえるのかどうかにははっきりとはしません． 我々人間がうまく教えるすべを知らない，何を教えていいかわからない，という ことなのかもしれません．
一方そうではなく，計算機というものの本質的な限界を端的に示すような， 「単純だが難しい問題」が数多く存在します．ここで難しいといっても二通り の意味があります．ひとつはアルゴリズムを使ってとくことが「絶対に不可能 な問題」というものです．これは二足歩行や自然言語の理解などのように， 「我々が人間の運動や脳の仕組みをもっとよく理解したらできるかもしれない」 というようなものではなく，「必ず正しい答えを出すアルゴリズムを作ること は決してできないことが証明されている」という問題です．それを証明するに はアルゴリズムというものの範疇を正しく定義する必要があり，授業で，それ らがどう定式化され，証明されているのかを学んでいただきたい．
もうひとつは，解けるには解けるが計算時間がかかりすぎる，というもの です．ただご存知のとおり，あることにかかる計算時間というもの自体が日進 月歩，ものすごい勢いで進化しています．10年前に「時間がかかりすぎた」計 算が今はたちどころに終わるというような例は枚挙に暇がありません．ここで も，アルゴリズムの理論的な枠組みで捕らえられるのは，計算機の10年，いや， 100年の進歩でもひっくり返らないような，圧倒的に「時間のかかりすぎる時 間」です．それを捕らえるのに，上で述べた計算量の概念が再び有効になります．
現時点では3つ目のカテゴリとして，「解けるには解けるが計算時間がかかり すぎる... と現時点では強く信じられている」という問題(NP完全問題)があり ます．これは，現時点で誰も，「効率よく」解くアルゴリズムを発見しておら ず，おそらくそのようなものは存在しないだろうと誰もが信じているがその証 明は誰も成功していない，という問題です．そして，少し残念なこととして， 少し気の利いた高度な問題は，非常に多くがこのNP完全問題である，というこ とを学びます．一言で言えば，計算機によって，非常に大きなデータでも効率 よく解ける問題，というのが意外と限られている，ということがわかるわけで す．たとえば上で述べた問題のうちのひとつ: 「a1 x1 + ... + an xn = b を 解く」はそのような問題のひとつです．これを，変数の数，つまり n を非常 に大きくしても，どんな係数であっても効率的に解けるアルゴリズムは世の中 の誰も知らず，実際に存在しないと信じられています．すぐにわかるとおり， この問題を「解く」こと自身は自明といってよいほど簡単です(2^nとおりの可 能性を試せばよい)．ところがnが大きくなると全通り試すのは絶望的に時間が かかります．こんな一見簡単な問題ですらこんな状態ですから，もっとややこ しい組み合わせの問題は多くがこの範疇に属するのではないかと想像がつきます． そのような感覚を実例とともに養ってもらうことも目標です．
0 件のコメント:
コメントを投稿