解けない問題と遅すぎる問題
計算の限界とは、正しい答えが出せない問題と、出せても遅すぎる問題があることです。前者の代表が、プログラムが止まるかを調べる停止問題です。
後者の代表が、組み合わせを全部試す全探索です。どちらも、コンピュータを速くしても消えません。このレッスンで、その理由を言葉と数字で確かめます。
このレッスンのゴール
メモ
停止問題が解けない理由と、全探索が遅すぎる理由を、説明できる。
重要な言葉
| ことば | いみ |
|---|---|
| 決定可能 | どんな入力にも、必ず正しく答えるプログラムがある |
| 停止問題 | プログラムがいつか止まるか、を答える問題 |
| 全探索 | 組み合わせを、すべて試す方法 |
| 部分和問題 | 数の一部を選び、合計を目標にできるかを問う問題 |
| 計算量 | 入力の大きさに対して、手順の数がどう増えるか |
| 指数的な増え方 | 入力が1つ増えるたびに、手順が2倍になる増え方 |
学生が入力するセルは、このプレビューでは空白です。
動かしても、止まるか分からない
プログラムが止まるかを知りたいとき、動かしてみるのが一番簡単です。止まれば、それで答えが出ます。
ところが、動き続けているときは、永遠に続くのか、もうすぐ止まるのかが分かりません。次のコードの手順は、27から始めると111回で止まります。しかし、どの数からでも止まるかは、まだ誰も証明していません。
止まるまでの回数を数える
# 偶数なら半分、奇数なら3倍して1を足す。これを1になるまで続けます。
n = 27
steps = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
steps = steps + 1
print("1になるまでの回数:", steps)
# n を 7 や 97 に変えて、回数を比べましょう。
停止問題は解けない
どんなプログラムが止まるかを正しく答える halts があるとします。それを使って、trouble を作ります。
trouble は、自分自身を halts に渡します。「止まる」と答えが出たら、わざと無限に続けます。「止まらない」と出たら、すぐ止まります。どちらの答えでも halts は間違えます。だから、halts は作れません。
よくある間違い
注意
コンピュータが速くなれば、いつかどんな問題も解ける、と思いがちです。停止問題は速さの問題ではなく、原理として解けません。全探索も、10倍速くなって解ける品物が3つ増えるだけです。
品物が1つ増えると、2倍になる
全探索は、あらゆる選び方を試します。品物が n 個なら、選ぶか選ばないかの2通りが n 回で、2のn乗通りです。
品物が1つ増えるたびに、通りの数は2倍になります。これが指数的な増え方です。計算機が毎秒10億通り調べる場合を、次の表で見ます。
2のn乗と、かかる時間
| 品物の数 | 選び方の数 | 毎秒10億通りなら |
|---|---|---|
| 10 | 1,024 | 一瞬 |
| 20 | 約105万 | 約0.001秒 |
| 30 | 約10.7億 | 約1秒 |
| 40 | 約1.1兆 | 約18分 |
| 50 | 約1126兆 | 約13日 |
| 60 | 約115京 | 約36年 |
学生が入力するセルは、このプレビューでは空白です。
2のn乗を計算する
python3 -c "print(2 ** 10, 2 ** 20, 2 ** 30)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
品物が40個と50個
python3 -c "print(2 ** 40, 2 ** 50)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
50個は何日かかるか
python3 -c "print(2 ** 50 // 10 ** 9 // 86400)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
5個の選び方を数える
python3 -c "import itertools; print(sum(1 for k in range(6) for c in itertools.combinations([3, 5, 7, 11, 13], k)))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
部分和問題を全探索で解く
部分和問題の例です。品物が120円、250円、330円、480円で、合計をちょうど600円にしたいとします。答えは、120円と480円の1通りです。
品物ごとに、選ぶ1、選ばない0を決めます。n 個なら n 桁の2進数で、0から 2のn乗 - 1 までの数が、あらゆる選び方を1回ずつ表します。
選び方を全部並べる
# 品物が3つ。選ぶ、選ばないを、0と1の3桁で表します。
prices = [120, 250, 330]
for mask in range(2 ** len(prices)):
total = 0
for i in range(len(prices)):
if mask // 2 ** i % 2 == 1:
total = total + prices[i]
print("組み合わせ", mask, "の合計:", total)
# prices にもう1つ品物を足すと、行の数はいくつになるでしょうか。
問題の3つの種類
| 種類 | 例 | 手順の増え方 |
|---|---|---|
| 速く解ける | 最大の値を探す | 入力に比例 |
| 解けるが遅すぎる | 部分和の全探索 | 2倍ずつ増える |
| 解けない | 停止問題 | 手順がない |
学生が入力するセルは、このプレビューでは空白です。
さらに挑戦: 完全なバグ検出
「このプログラムにバグは1つもない」と完全に判定するプログラムも、停止問題と同じ理由で作れません。
それでも、テストやコードの検査は役に立ちます。「完全に判定できない」ことと「役に立たない」ことが、別である理由を説明しましょう。