悪い例

アルゴリズムでない命令列の分かりやすい例として、次の Martin (マーティン) のアルゴリズム1を考えます:

procedure \(\texttt{BeAMillionaireAndNeverPayTaxes}\)()

百万ドル手に入れる

if 徴税人がきて 「税金を払っていませんよ!」 と言う then

「忘れてた」 と言う

このアルゴリズムは単純ですが、一行目が絶望的に実行困難です! 大富豪の CEO、シリコンバレーのベンチャー投資家、ニューヨークのやり手不動産家などにとっては一行目はすぐに実行できる些細な2問題なので、この手続きはアルゴリズムかもしれません。しかしそれ以外の貧しい一般庶民に対しては処理がはっきりと示されておらず、Martin の手続きがアルゴリズムであるとは言えません。

一方で、これは帰着 (reduction) の例としては完璧です。つまり、この手続きは富豪になって税金を払わないという問題を、百万ドルを手に入れるという「より簡単な」 問題に帰着しているということです。帰着はこの本に繰り返し出てきます。何百人という実業家や政治家が示しているように、簡単な方の問題の解き方が分かれば、帰着によって難しい方の問題の解き方が分かります。

Martin のアルゴリズムおよびこれまでにあげたいくつかのアルゴリズムは、計算機科学者が考えるところのアルゴリズムではありません。なぜなら使われている処理をコンピューターで実行するのが難しいからです。この本は (基本的に) 標準的なデジタルコンピューターで普通に実装できるアルゴリズムだけを扱います。この本で説明されるアルゴリズムの各ステップは、多くのプログラミング言語で直接サポートされているもの (算術演算、代入、ループ、再帰など) か、そうでなければあなたがやり方を知っているもの (ソート、バイナリサーチ、木の走査、"\(n\) Bottles of Beer on the Wall" の歌唱など) です。


  1. Steve Martin, You Can Be A Millionaire, Saturday Night Live, January 21, 1978. および Comedy Is Not Pretty, Warner Bros. Records, 1979.[return]

  2. "ブロックチェーンとディープラーニングを使った量子でセキュアな"[return]

広告