アルゴリズム入門

このドキュメントは http://edu.net.c.dendai.ac.jp/introduction/algorithm.html から入手できます。

今日の問題

渡した用紙に、今日の講義の内容の要約を書きなさい。

採点基準
内容がきちんと書けていることと、私が読んで読み易いこと。

自己紹介

ネットワークシステム研究室
坂本直志

専門分野

研究室の紹介

分散アルゴリズム
複数のコンピュータで同じプログラムを動かし、ネットワーク上で協調させて動かすようなシステムの開発
クライアント/サーバー
WWW などのクライアント/サーバーシステムの評価や改良
ネットワークの評価
Ethernet などのネットワークシステムの評価
コンピュータによるネットワークの管理
コンピュータ管理の自動化
基礎理論
アルゴリズムやネットワークに関する基礎理論
マイコン
センサネットワークなどマイコン関連の装置を製作し、根幹となる基礎技術を学ぶ

アルゴリズムとは

コンピュータプログラムを作る際に必要な知識とは……

  1. プログラミング言語の使い方
  2. プログラミング言語の命令の組合せ方

小説を書く場合の、「言葉」と「表現手法」の関係。

今日はこのプログラミング言語の命令の組合せ方について考える。

コンピュータで解決すべき問題があったとしよう。 その時、どのように解決しなければならないかは、どんなプログラミング言語でも 大体同じ。 (書き易さは違っても、書かねばならない内容は同じ) これは、日本語でも英語でも、同じ内容の小説を書く場合、並ぶ単語の意味は大体同じになるのと同様である。

問題の解決の仕方を「アルゴリズム」と呼ぶ。 文章の書き方と同様、アルゴリズムは科学技術が発展しても、変らない。 (たとえ、プログラミング言語は変化していっても)

今日は「アルゴリズム」の話題について紹介する。


高校までで習うアルゴリズム

高校までに習ってきたと思われる、アルゴリズムを復習する。

筆算の仕方

123×45 は次のようにして計算する。
  1. 一桁×一桁のかけ算はあらかじめ覚えておく
  2. 筆算という手順で、一桁×一桁のかけ算と足し算を組合せて答えを得る
how to multiply

つるかめ算

つるとかめが合計で 10 匹。足の数が合計で30 本の時、つる、かめはそれぞれ何匹いるか?
Answer

方程式の解き方

ax + b = 0 (a≠0)という方程式の解き方

等式の性質

  1. x = y なら x + z = y + z
  2. x = y なら xz = yz
ax + b = 0 性質 1 を使い、両辺に -b を足す(移項)
ax + b - b = 0 - b
ax = - b 性質 2 を使い、両辺に 1/a を掛ける
x = - b / a

二次方程式の実根の判定

ax2 + bx + c = 0 (a≠0, a,b,c とも実数) の解の判定

  1. 判別式 D = b2 - 4ac を計算する。
  2. D の符号を調べる。

組み立て除法

(x4 + 2x3 - x -2) を (x + 2) で割る。

kumitatejoho

有名なアルゴリズム

アルゴリズムの良し悪しは、効率に大きく影響する。ここでは、 大きく効率が変わる例を示す。

探索

問題

書物の中から、ある単語の載っているページを知りたい。

素朴な解決法

1 ページ目から順番に探していく。

1000ページの本だったら、最悪 1000 回探さなければならない。

もしも、その本が辞書だったら……

辞書の場合、単語は辞書順に並んでいる。

辞書順とは……
あ、ああ、あああ、ああああ、……、あい、あいあ、あいああ、……、い、

辞書順は、単語同士に大小関係を導く

ウィンドウズ < マック < ユニックス
辞書の索き方

例えば「電機」という単語を索いてみる。 (辞書も大体 1000 ページ)

  1. 最初のページと最後のページの中間のページ((1+1000)/2=500ページ付近)を開く
  2. 「重要」などの単語が載っている
  3. 「重要」<「電機」なので、今のページと最後のページの中間のページ((500+1000)/2=750ページ付近)を開く
    ……

目的の単語を w とする。 ある範囲(s ページ目から e ページ目) に目的の単語がある時、

  1. 中間のページ m = (s + e)/2 を調べる。
  2. その単語 xw の大小関係を考える。
    1. x = w なら発見!
    2. x > w なら、 wsm の間にある。
    3. x < w なら、 wme の間にある。

このような探索法を「二分探索法」と呼ぶ。

二分探索法の効率

ページを開く回数はどれくらいか?

考え方

注目しているページは毎回半分ずつ減っていく。 全ページ数を N とする。

注目しているページ数
回数注目しているページ数注目しているページ数
0 N 2t
1 N/2 2t-1
2 N/4 2t-2
t-1 2 2
t 1 1

N = 2t より、 t = log 2 N 回となる。 1000ページの本だと、 log 2 1000 ≒ 10 回程度の検索で目的の単語を発見できる。


アルゴリズムのない問題(解けない問題)

どんな問題でも考えれば解き方があるとは限らない!!!

プログラムを書くことができない問題を紹介する。

その前に……

チャーチの提唱

速度や、効率や、手法などが異なるとしても、 コンピュータで yes, no を判別できることと、人間が yes, no を判別できることは 同じであると考えることにしよう。

これはチャーチが勝手に言ったことで、別に根拠も証明もないが、深く考えると、 それほど間違っているようには思えないと思う人は多い。

つまりこの章で紹介する「アルゴリズムの無い問題」は「人間も解くことができない問題」であると考える。

停止問題

あらかじめコンピュータプログラムを読んで、そのプログラムが停止するか停止しないかを判断することはできない。これは理論的に証明されている。 これを「停止問題」といい、代表的な決定不能問題である。

したがって、どんなにコンピュータや科学が進歩しても、次のようなプログラム(ソフトウェア)は現れない。

但し、プログラムの書き方などを制限すると判断可能にすることもできる。

ポストの対応問題

ポストの対応問題とは次のような問題である。

次のようなカードが何種類かあったとする。

cards

これらのカードを何枚も使用してよいという前提で、上下の記号の列が等しくなるようにできる組合せがあるかないかを判別する。

cards

停止問題を解くプログラムがない理由

背理法と対角線論法により証明する。

  1. プログラム x と値 y を入力すると、そのプログラムに値 y を入れた時、停止するかどうかを判定するプログラムがあったと仮定する。(そのプログラムを P と置く)
    <var>P</var>
  2. プログラム P を改造する。
    1. まず、プログラム x に値 x を入れた時だけを判定するようにする。
    2. 次に、P は「停止する」と判定した時停止するが、これを「停止する」と判定した時止らないようにしてしまう。 「停止しない」と判定する時はそのまま停止する。
    このように改造したプログラムを Q とする。
    <var>Q</var>
  3. P にプログラム Q と値 Q を入れることを考える。 P は「停止する」または「停止しない」のどちらかを出力する。
    <var>P</var> on <var>Q</var> and <var>Q</var>
    1. 「停止する」と出力されたとする。 すると、これは、プログラム Q に値 Q を入れた時、停止することを意味している。 しかし、それは、「QQ を入れた時、停止しない」と判定していることを示す。 つまりこの判定が正しくないことになり矛盾。
    2. 「停止しない」と出力されたとする。 すると、これは、プログラム Q に値 Q を入れた時、停止しないことを意味している。 しかし、それは、「QQ を入れた時、停止する」と判定していることを示す。 つまりこの判定が正しくないことになり矛盾。
    いずれにしろ、仮定に反する。 したがって停止問題を判定するプログラム P は存在しない。

対角線論法の例

0 から 1 までの実数を数え上げることはできない。

数え上げられたとして、矛盾を導く。

各実数を無限小数で表すとする。 1 番目の実数の小数第一位を a1、 2 番目の実数の小数第二位を a2、 3 番目の実数の小数第三位を a3、 …… とする。 bi = 9 - ai とする。

さて、 小数第一位が b1, 小数第二位が b2, 小数第三位が b3, …… という数 x を考える。 x は 0 から 1 の間に入る数であるが、数え上げられていない。 実際、もし i 番目に数え上げられていたとすると、小数第 i 位は ai でなければならない。 しかし、 x の小数第 i 位は bi = 9 - ai で、これは必ず ai と異なる。 したがって、実数を数え上げられたとする仮定に矛盾する。

1:0.4124867591...
2:0.8234971634...
3:0.1498471681...
x=0.5704817516...

(この証明は不完全である。 0.29999999 という形の表示を排除するように書き換える必要がある。 )


速いアルゴリズムのなさそうな問題

世の中には速いアルゴリズムがなさそうな問題がある。

これから紹介する問題は、一見単純で、検証も簡単ではあるが、速いアル ゴリズムが無さそうだと信じられている問題である。 もし、速いアルゴリズムを作ることができたら、画期的な大発見になる。

巡回セールスマン問題

目的地が幾つかあり、目的地間の交通費がそれぞれ判っているとき、 全部の目的地に行くのに、かかる交通費が予算より多いか少いかを判断する問題。

入力例

目的地
東京、渋谷、新宿、池袋、上野、秋葉原
交通費
東京、渋谷間 xxx円、東京、新宿間 xxx円、東京、池袋間 xxx円... 上野、秋葉原間 xxx円
予算
1000円

出力

ナップザック問題

荷物を選んで、ナップザックに丁度一杯になるように詰められるかどうかを判断する問題。

入力

荷物の体積
v1, v2, ..., vn
ナップザックの容量
C

出力

NP完全問題

今紹介した問題は、「条件を満す特定の組合せかたがわかれば、その組合せで yes になることが容易にチェックできる」という構造を持つ。 このような問題は「NP完全問題」と呼ばれる。 (「NP完全問題」は数学的に厳密に定義されているが、ここでは省略する)

NP 完全問題より難しい問題

例えば、「オセロゲームが後手必勝か?」のような問題だと、必勝手順は相手 の手により様々に変化するので、短時間にはチェックできない。 つまり、正解を知っても効率良く検証できない。 したがって、このような「ゲームの必勝手順があるか無いか?」のような問題 は NP 完全問題より難しいと考えられる。


坂本直志 sakamoto@c.dendai.ac.jp