計算機科学基礎 ¶

計算機科学基礎

What is this ¶

ここでは, python を使った古典的な計算機科学問題に取り組んでいこうと思います.

古典的な計算機問題には例えばナップサック問題というものがあります. 皆様はこれから無人島に島流しに合います. ここで大きさの決まったナップサックを一つだけ持っていくことができます. 無人島生活には色々なものが必要ですが, ナップサックに入る量は決まっています. この際に, ある目標の価値を上回る品物の選び方はあるのか, ないのか, どの組み合わせが最もよいのか, こういうことを決める問題です.

一見すると, あまり面白い問題ではないようにも見えますが (無人島にナップザック一個で行くとかそうそうない, どうぶつの森でもあるまいし...), この問題は色々な所で使えます. 例えば, 年度の頭には予算決めがあるのですが, 限られた予算で欲しいものを最大幸福的に受け取る計画を立てるなんて, よくある話です.

あるいは限られた時間の中で, どの講義には力を入れ, どの講義は手を抜く(切る)のかなんて皆様も一度は考えたことがあるのではないでしょうか?

世の中には典型的というか、よく出くわす問題 (先程の予算のように)というものがあるのです. こうしたよくある問題をパズルの問題のようにしたものが古典的な計算機科学の問題です. そして, 世のパズルがそうであるように, これらの問題には定石というか, 一般的な解法というものも存在します. こういう一般的な解法のことを, かっこよく言えばアルゴリズムというのです.

計算機科学とは何かいうと要はパズルです. パズル. 最初に頭を使って考えて, 答えに納得したらあとは身に付ければそれでよいと思います. どうぞ, 気楽に楽しんでみてください.

For whom?¶

この文章の中では然程 python そのものに関しての説明を記述しません. それは First Python で既に行っています. それ以上の知識は不要です.

逆に, 上記チュートリアルをまだ行っていない場合には, 必ず一読しておいてください.

準備運動 ¶

フィボナッチ数列 ¶

まずは準備運動としてフィボナッチ数列を解いてみましょう. もしかしたら少しプログラミングに詳しい人にはお馴染の問題かも知れません.

ここで考え、慣れて欲しいことは以下の二つです.

数式が与えられた時にそれをプログラムに直す練習(あと関数の復習)
再帰処理の発想と練習

フィボナッチ数列とは, 先頭の2項 (二つの数字) を除いて, 一般項が前の 2 項の和で示されます.

... 何を言っているのでしょう.

まずは例で考えます.

以下の数列はフィボナッチ数列です:

0, 1, 1, 2, 3, 5, 8 ...

まず, 第一項のフィボナッチ数は 0 です. で, 次の項は 1 ですね.

第三項はというと, 第一項と第二項の和なので, 1 です. 以下, 第四項は第二項と第三項の和なので 2 です. では, ... で省略した次の項はなんでしょう(考えてみてください. 勿論 SLACK で皆様答え合わせしてくれてもいいですよ)?

さて, この数列の任意の n 項目のフィボナッチ数は次式で得られます.

\[\begin{split}F_0 &= 0, \\ F_1 &= 1, \\ F_n &= F_{n - 1} + F_{n - 2} (n \gt 2)\end{split}\]

数式の意味としては, フィボナッチ数列の第一項が 0 で, 第二項が 1 の時に, 2 より大きい n は n の一個前の場合の値と, 二個前の場合の値の和で決まると書いてあります. 言い換えれば, 先頭の2項 (二つの数字) を除いて, 一般項が前の 2 項の和で第 n 項示のフィボナッチ数列が表現されるということですから, 実は定義をそのまま、数式にしたにすぎません.

再帰処理 ¶

なぜ, 言葉の通りの内容を態々小難しい数式なんぞに変えたかというと, 一度数式にすると, そのままコードに変換することができるからです.

ちょっとコードに書いてみましょう:

def fib(n):
    return fib(n - 1) + fib(n - 2)

ほらね, そのままでしょ?

え, これで動くの? のビックリされた貴方. 試してみてください:

def fib(n):
    return fib(n - 1) + fib(n - 2)

print(fib(3))

安心してください. 当然動きません. エラーがでますね.

そのエラーをよく読んでください. 以下のようになっているはずです:

RecursionError: maximum recursion depth exceeded

直訳すると, "'最大再帰深度を超えました" です. 今回のテーマである "再帰" という言葉がでましたね.

上記コードの問題は, 常に fib 関数が呼ばれ続けてしまうため, いつまで立っても計算が終わらないことです (こういうものを無限再帰と呼びます. 大まかには無限ループのようなものだと思ってくれて構いません).

要は計算ができないのではなく、計算が終わらないことが問題なのです. そのため、終了条件(基底部, 計算を終えるための条件)を用意してやれば, 上記関数は上手く動きます.

では fib の基底部はなんでしょうか? これも実は数式では定義されています. そう, 最初の二項を除いて... の部分です.

素直にコードを書くと以下のようになります:

def fib(n):
    if n < 2:  # 最初の二項では
        return n  # そのまま n を返す
    return fib(n - 1) + fib(n - 2)  # それ以外では再帰的に自身を呼び出す

print([fib(n) for n in range(7)])

このコードを実行すると冒頭で示したフィボナッチ数列がそのまま得られます(内包表記, 覚えていますか?).

その次の値の答え合わせもできますね.

さて, この再帰式, とっても面白い形をしていませんか? 書いてあることは if 文なのにやっていることは for 文です. First Python の中でチラッと, "制御構文の多くはこの if 文から作成されています" と書いていますが, 実は繰り返し系の制御構文は if 文で作成することができるのです.

計算時間 ¶

もう少し, この再帰について教えると, フィボナッチ数列の様な数式のことを数学の言葉では漸化式といいます. これは, 逆に言えば漸化式と言われれば、再帰を書けばとりあえず関数が作れるということを意味します. 例えば、デジタル信号処理なんかでは、この漸化式は非常に良く出てきますし、最適化、機械学習などの実装にもこれはよく使います.

さて、先に作成した fib 関数に話を戻します. この fib 関数には実は問題があるのです.

たとえば n = 35 のフィボナッチ数を計算させてみてください. 大分時間がかかるはずです.

では n = 50 だったら?

多分計算が終わらないでしょう.

これは何故かわかりますか?

ここには再帰の呼出し回数が関わってきます. たとえば, fib(4) の場合の呼出を考えてみると以下の通りです:

fib(4) -> fib(3) + fib(2)
       -> fib(3) -> fib(2) + fib(1)
                 -> fib(2) -> fib(1) + fib(0)
                           -> fib(1) -> 1
                           -> fib(0) -> 0
       -> fib(2) -> fib(1) + fib(0)
                 -> fib(1) -> 1
                 -> fib(0) -> 0

このように n=4 のときには fib 関数は 9 回呼び出されます. では n=5 では何回でしょう. n=10 では? この二つ位は頑張って数えてみましょうか (まだ 1000 は行かないので).

n = 20 くらいになると 20000 回を超える呼出し回数になります. これだけぐるぐると繰り返し処理をしていると, 計算が中々終わりません(n=50 くらいになると多分まず, 終わらないんじゃないかな?)

では, n = 50 際のフィボナッチ数は計算できないのか？というと, 実はそんなことはありません.

この節の最後には、 n = 50 の場合のフィボナッチ数を計算するための方法を二種類紹介します.

メモ化 ¶

一つの方法はメモ化です. もう一度フィボナッチ数列を眺めてみましょう:

0, 1, 1, 2, 3, 5, 8 ...

我々人間はこの数列をみれば次の値は直ぐにわかりますね. なんで、直ぐに分かるかというとその前の結果を記録して覚えておくことができるからです.

同じようにプログラムでも前の結果を記録させて置けば処理は大分早くなります。このように前の処理結果を保存しておいて、必要になった時に保存された結果を使う技法をメモ化といいます.

早速メモ化を試してみましょう:

memo = {0:0, 1:1}  # 基底部

def fib(n):
    if n  not in memo:
      memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print([fib(n) for n in range(7)])
print(fib(50))

このようにするとさっきまで何時迄立っても結果が出なかった fib(50) が一瞬で出てきます.

上のコードでは関数の外に変数 memo を用意します. 今回は辞書型(覚えています？)で値を決めています.

注釈

何故 dict 型なのか?

変数 memo は別に dict 型である必要はありません. list でも問題なく作ることが可能です(チャレンジしてみてください).

なぜ dict 型を選んだかというと key = n, value = 解答の形でメモを整理したかったからです.

ただし変数 memo を宣言する場所は必ず fib 関数の外で無くてはいけません。何故だかわかりますか？

一番最初に基底部を決めているので, if 文の中では memo に解答がない場合だけ, 結果を保存するようにすればよいです. この処理をすると、どのような場合でも memo の中には解答が記録されているので、あとはそのまま、 memo の情報を返せば関数は上手く動きます.

注釈

メモ化をもっと楽にする

上記メモ化のコードは内容がとても分かり易いですが少し面倒です. python という言語は簡単なことを簡単にやるのが好きな言語なので、メモ化そのものはもっと手軽に実行できます:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))

上記コードでは関数の内容そのものはメモ化をする前のものと同一です ( fib 関数が何をやるのかはこちらの方が分かり易いでしょう) ただ, 上で少し不思議なことをしています.

まず一行目ではライブラリの読み込みを行っています. ここで使用している functools というライブラリは python が元々持っている便利ツールの一つです. このツールの内, lru_cache という関数を使いますよというのが、一行目の意味です.

@ を使う記法は今回はじめて出てきましたね. これはデコレーターといいます(ほら、ケータイをデコるとかいうじゃないですか、あのデコです).

少し言葉の説明になりますが, 例えばケータイをデコるといったとき(通じる？)、シールをはるのはデコるですよね. でも, 例えばなかのSIMカードを変えることをデコるとは余り言わないかと思います.

何がいいたいかというと、デコレータ, デコレーションという言葉は何かに被せるとか, 上にのせるとかそういう行為をさしていて, 本体を変えるものじゃないということです(別のプログラミング用語としてラッパーという言い方をすることもあります).

同じように, @lru_cache 関数も, fib 関数を覆います. つまり, fib 関数実行時に入力を監視して, もし計算したことがあれば、その結果を返し、計算したことが無い場合だけ, 実際に fib 関数を実施します. また, fib 関数が実行された際には自動でその結果を保存します. つまり, fib 関数の開始と終了で何か決まった処理を行うわけです. こういう関数のことをデコレータ関数(ラッパー関数)といいます.

デコレータ関数は自分で書けると凄く便利なので(実務ではよく使うのですよ. 例えばログを取ったり, 計算させた後で可視化をさせたり, 結果はどうあれ何かをしたい時というのは往々にしてあるものです), 興味のある方は調べてみるとよいですよ.

あと, @lru_cache に関してですが, キャッシュという言葉を聞いたことがある方は居ませんか？なんか, キャッシュが残って変な結果になっているとか. メモ化とは、あのキャッシュを関数レベルで使いましょうという話です. 特にプログラミングに不慣れな方ほど、キャッシュという言葉、ものを毛嫌いする傾向があるのですが, キャッシュを上手く使えると、今迄試したように、計算が終わらないものを一瞬で解決できるようになったりするのです.

反復処理化 ¶

さあ、準備運動第一節で、多分皆様大分お疲れかと思いますが, まだ続きます.

この節の最後に, フィボナッチを反復型(普通の for 文)で解いてみましょう:

def fib(n):
    if n == 0:
        return 0
    last = 0  # 前の値を保存(初期値は fib(0) なので 0 )
    next = 1  # 次の値を保存(初期値は fib(1) なので 1 )
    for _ in range(1, n):
        last, next = next , last + next
    return next

fib(50)

さあ, これでも答えは出てきます. そしてメモ化はしていないのに fib(50) を計算することができます.

まず, このコードでもフィボナッチの計算が何故できるのか説明できますか？そして, なぜメモ化をしていないのに再帰で書く場合とは違い答えが出てくるのかわかりますか?

課題として, まずは n = 0 から n = 5 位までで各行の結果がどうなるのかを考えてみてください. そして、結果として公式通りの処理になっていることを確認してください.

その際に, for 文が何回実行されるのかを考えてみるとよいでしょう.

上記二つに解答できたら、この節は終了です(繰り返しですが SLACK 等で答え合わせとかしてもいいですよ)

まとめ ¶

この節では, 再帰という手法を紹介しました. この手法を使うと、何か数式(漸化式)が与えられた場合に, それをコードに変換することがとても簡単にできるようになります.

一方で再帰を使ってしまうと計算回数がとてつもなく多くなってしまう場合もあります. こういう際には一度, 反復型でコードを書き直してみると計算速度は一気に向上します.

でも面倒な場合にはメモ化(キャッシュ)を上手く使いましょう.

これがこの節で言いたいことの要約になります.

ハノイの塔 ¶

さて, 続いてはハノイの塔というパズルに挑戦していきましょう. ハノイの塔とは以下の写真のようなパズルです.

https://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg

このパズルでは 3 つの塔(写真では棒) と n 個の円盤が出てきます. 初期状態では, 向かって左側の塔に全ての円盤が入っていますね. これを向かって右側の塔になるべく少ない回数で移動させると勝ちです.

ただし、円盤の移動には以下のルールが存在します.

一回に一枚の円盤だけが移動できる
移動できる円盤はそれぞれの塔の一番上だけ
大きな円盤を小さな円盤の上にのせてはいけない

例えば, 写真の例ですと, 最初に移動できる円盤は向かって左にある一番上の円盤1つだけです. これは, 真ん中か右の塔に移動できます.

2 回目に移動できる円盤は, 最初に移動した円盤か, 左の(この段階で)一番上の円盤のみです. ここで、左の円盤は, 最初に移動した円盤の上に置くことはできません(なぜなら二番目の方が大きいからです).

どうです? パズルの内容はご理解いただけたでしょうか？

モデリング ¶

まずは, このパズルそのものをプログラムにしてみましょう. このパズルの登場人物は大きく二つ, つまり塔と円盤です.

塔はいくつかの円盤を持つことができます. 加えて塔は最後の円盤を取り出すことができて、塔は最後に円盤を入れることができます.

このように問題に合わせて登場人物を決定し、その関係を考え、その動きを決める作業のことをモデリングといいます.

さて, 上記モデリングが済んだわけですが、この条件から塔をプログラム的に表現できますか？

実は First Python の中に正に上記条件に一致するクラスを紹介しています. それは list です.

このなぜ塔を表現するのに list が最適か言葉で説明できますか？
できない場合, First Python の list の説明をもう一度読み直してください.

例えば, 上記写真のハノイの塔は以下のように表現できます:

disk_n = 8
tower_a = [i + 1 for i in range(disk_n)]  # [1, 2, 3, 4, 5, 6, 7, 8]
tower_b = []
tower_c = []

向かって左一番上の円盤 (上記例の場合 8 という数字です) を tower_b に移動するには以下のようにすればよいです:

tower_b.push(tower_a.pop())  # tower_b = [8], tower_a = [1, 2, 3, 4, 5, 6, 7]

このように, pop と append のみで操作する配列構造を後入先出法(LIFO) などといいます.

ここまでで, とりあえずパズルそのものをコードにすることができました(不足はあるのですが).

もしモデル化に不十分な点があることにお気付きの皆様は, きちんとクラス化をしてみるといいですよ.
このままでは, できてはいけないことができてしまいます.

ソルバー ¶

さて, ハノイの塔の問題そのものはモデル化できたとして, これをどのように解けばよいのでしょうか？

こういうときにはまず決まりきったこと(基底部)から考えます. 例えば, 円盤が 1 枚だけの場合はどうでしょうか? 簡単ですね. 左にある一枚の円盤を向かって右側の塔に移動させればよいのです:

disk_n = 1
tower_a = [i + 1 for i in range(disk_n)]  # [1]
tower_b = []
tower_c = []

tower_c.append(tower_a.pop())  # tower_a = [], tower_b = [], tower_c = [1]

基底部が決まったら今度は再帰部を考えます. つまり, 円盤が2枚以上の場合を考えましょう. ここでは具体的に円盤が2枚の場合と、3枚の場合を考えてみましょう.

円盤が二枚の場合以下の手順になるはずです.

tower_a の円盤を tower_b に置きます.
tower_a の円盤を tower_c に置きます.
tower_b の円盤を tower_c に置きます.

では, 三枚の場合は? この場合には以下の手順になるはずです.

tower_a の円盤を tower_c に置きます.
tower_a の円盤を tower_b に置きます.
tower_c の円盤を tower_b に置きます.
tower_a の円盤を tower_c に置きます.
tower_b の円盤を tower_a に置きます.
tower_b の円盤を tower_c に置きます.
tower_a の円盤を tower_c に置きます.

ここまで, 大丈夫でしょうか？一つずつ紙にかいてみるとよいです.

この手順を整理すると再帰部は以下の3つのステップに分解できます.

n - 1 枚の円盤を tower_a から tower_b に tower_c を経由して移動 (1-3)
n 枚目の円盤(一番下の円盤) を tower_a から tower_c に移動 (4)
n -1 枚の円盤を tower_b から tower_c に tower_a を経由して移動 (5-7)

ではこの再帰部と基底部を使ってハノイの塔を解く、ソルバー(何か問題を解くための関数をソルバーと呼びます) を作ってみましょう:

def hanoi(begin, end, tmp, n):
    if n == 1:
        end.append(begin.pop()) # 基底部
    else:
      hanoi(begin, tmp, end, n - 1)  # 再帰部(a から b に c を経由して移動)
      hanoi(begin, end, tmp, 1)  # 再帰部 (n番目の円盤を a から c へ移動)
      hanoi(tmp, end, begin, n - 1)  # 再帰部(b から c に a を経由して移動)

disk_n = 8
tower_a = [i + 1 for i in range(disk_n)]  # [1, 2, 3, 4, 5, 6, 7, 8]
tower_b = []
tower_c = []
hanoi(tower_a, tower_c, tower_b, disk_n)

これでハノイの塔が解けていることを確認してください.

どうなっていたら解けているのでしたっけ？

また, disk_n の数を変更しても問題なく解けるでしょうか？

まとめと応用のヒント ¶

本章では, First Python の復習として, 二種類の問題に挑戦しました.

フィボナッチ数列とハノイの塔です. フィボナッチ数列の問題では, 再帰というテクニックを紹介しました。

このテクニックを利用すると, 小難しい数式をそのままコードに変換することができるということをみました.

一方で再帰を利用するとしばしば計算量が多くなってしまい、いつまでたっても, 計算が終わらないという問題も確認しました. こういう場合にメモ化というテクニックを利用すると, とても簡単に計算速度を向上させることができることを確認しました.

第二の問題であるハノイの塔では, まず問題をモデル化するということを行いました. その上で実際の解法を確認し、それを再帰を使って解いてみることを試しました.

この章で練習をした再帰(そう基底を先に考え, その後, それ以外の処理を考え, そのまま実行するのです)は, 例えば, 論文に出て来る新しい方法を自分で試してみる際には必須のテクニックになります.

また、数式を怖がってはいけません。基本的に python を使っている限り, 数式さえわかれば、あとはそのままコードに書けばよいのです.

こういう体力をつけるためには、例えば高校生の頃の教科書がいい練習材料になります. 各種公式をコード化してみてください. そしてそのコードで教科書の問題を全問正解できるか挑戦してみてください. それだけでコードを書くための基礎体力は付いてきます.

上記公式に従うと, \(\pi\) が次の無限級数の収束値になります(式はずっと続くけど解ければその解が \(\pi\) です)

\[\pi = \frac{4}{1} - \frac{4}{3} + \frac{4}{5} - \frac{4}{7} + \frac{4}{9} - \frac{4}{11} \cdots\]

この式では分子は常に 4 です. また, 分母は 1 から始まり, 2つずつ増えます. 更に各項では, 加算と減算が繰り返されます.

この式をプログラムにし, n = 1000000 の場合の値を計算してください.

注釈

ヒント

無限級数は基本的には再帰ではなく for 文で考えた方が素直かと思います.

どうしても分からない方は以下のコードを穴埋めするのが良いでしょう:

def cal_pi(n):
    pi = 0
    m = □
    d = □
    o = □
    for i in range(n):
        pi = pi + □
        d = d + □
        o = o * □
    return pi

cal_pi(10000000)  # 3.1415925535897915

□ の部分が穴埋め箇所です.
□ は一文字とは限りません.

サイン波 (発展問題)¶

音を扱う人間が知っていなければいけないものにサイン波という波があります.

これは以下の数式で決定されています

\[s(n)=A \sin\left(\frac{2{\pi}A}{f_s}\right)\]

この数式を関数にしなさい. また, 以下のページを参考に任意のサイン波を鳴らしなさい.

この課題に取り組むためには scipy を導入する必要があります.
- 従ってこの課題は自身でライブラリの導入が行える( pip コマンドが使える) 方のみの課題とします.
課題に取り組む場合, 何か適当な歌(キラキラ星などでもいいですし, 某エポナの歌とかでもよいです) を再生できるプログラムを書くことを目標にするのがよいでしょう.