アルゴリズム入門

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

今日の問題

本日の講義内容の要約をA4用紙の表面にまとめなさい。

なお、気が向いたら講義の感想を裏面に書いていただけるとありがたいです。

自己紹介

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

専門分野

• 分散アルゴリズム
• 乱数を使った計算
• 計算量理論
• ネットワークシステムの評価
• マイコン
• 通信行動工学

研究室の紹介

分散アルゴリズム

複数のコンピュータで同じプログラムを動かし、ネットワーク上で協調させて動かすようなシステムの開発

クライアント/サーバー

WWW などのクライアント/サーバーシステムの評価や改良

ネットワークの評価

Ethernet などのネットワークシステムの評価

コンピュータによるネットワークの管理

コンピュータ管理の自動化

基礎理論

アルゴリズムやネットワークに関する基礎理論

マイコン

センサネットワークなどマイコン関連の装置を製作し、根幹となる基礎技 術を学ぶ

通信行動工学

通信記録などを分析し、利用者行動を把握する

アルゴリズムとは

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

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

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

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

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

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

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

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

筆算の仕方

1. 一桁×一桁のかけ算はあらかじめ覚えておく
2. 筆算という手順で、一桁×一桁のかけ算と足し算を組合せて答えを得る

つるかめ算

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

方程式の解き方

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

等式の性質

1. $x=y$ なら $x+z=y+z$
2. $x=y$ なら $xz=yz$

$\begin{array}{cc}ax+b=0& \text{性質 1 を使い、両辺に}-b\text{を足す(移項)}\\ ax+b-b=0-b\\ ax=-b& \text{性質 2 を使い、両辺に}\frac{1}{a}\text{を掛ける}\\ x=-\frac{b}{a}\end{array}$

二次方程式の実根の判定

$a{x}^2+bx+c=0$ ($a\ne 0$, $a,b,c$とも実数) の解の判定

1. 判別式 $D=b^2-4ac$ を計算する。
2. $D$ の符号を調べる。
   • $D>0$ なら二つの実根
   • $D=0$ なら実根の重解
   • $D<0$なら二つの虚根

組み立て除法

$(x^4+2x^3-x-2)$ を $(x+2)$ で割る。

有名なアルゴリズム

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

探索

問題

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

素朴な解決法

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

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

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

辞書順とは……

あ、ああ、あああ、ああああ、……、あい、あいあ、あいああ、……、い、

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

ウィンドウズ < マック < ユニックス

辞書の索き方

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

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

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

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

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

二分探索法の効率

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

考え方

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

注目しているページ数

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

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

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

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

その前に……

チャーチの提唱

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

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

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

停止問題

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

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

• プログラムが正しいか間違っているかを自動的に判断するプログラム。
• 間違っているプログラムを自動的に修正するプログラム。
• プログラムと仕様を入力し、そのプログラムが仕様を満しているかを判断するプログラム。

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

ポストの対応問題

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

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

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

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

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

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

対角線論法の例

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

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

各実数を無限小数で表すとする。 1 番目の実数の小数第一位を $a_1$、 2 番目の実数の小数第二位 を $a_2$、 3 番目の実数の小数第三位 を $a_3$ 、 …… とする。 $b_i=9-a_i$ とする。

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

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

(この証明は不完全である。 0.29999999 と 0.30000000 など同じ数で2種類の表示の 一方排除するような吟味が必要である。)

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

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

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

巡回セールスマン問題

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

入力例

目的地

東京、渋谷、新宿、池袋、上野、秋葉原

交通費

東京、渋谷間 xxx円、東京、新宿間 xxx円、東京、池袋間 xxx円... 上野、秋葉原間 xxx円

予算

1000円

出力

• 予算内で全ての目的地に行けるなら「yes」
• この予算では全ての目的地に行けないなら「no」

ナップザック問題

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

入力

荷物の体積

$v_1,v_2,...v_n$

ナップザックの容量

$C$

出力

• 荷物をいくつか選ぶと丁度体積が $C$ になるなら「yes」
• 体積が $C$ になるような荷物の選び方がないなら「no」

NP完全問題

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

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

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

なお、囲碁では最終ポイント集計において、後手に6.5ポイント加算す ると経験的、統計的に互角になるとされ、一般の対局ではこのハンデが加算さ れる（コミ）。

なお、「オセロゲームが後手必勝か？」については、解明されたとの報告がある。

• 6x6 盤面なら後手必勝(1993) Feinstein, Joel. "Perfect Play in 6x6 Othello from Two Alternative Starting Positions"
• 8x8盤面なら引き分け(2023) 滝沢拓己 "Othero is solved"