Mathematics for Programmer

プログラマに必要な数学

一般的なプログラマに必要な数学は, 離散数学と呼ばれる数学です. もちろん, メディア (音・画像・動画) をあつかうエンジニアになると, 微分積分や線形代数を基礎とした解析学 (フーリエ解析など) も必要になりますが, そうでないプログラマが知っておきたいのは離散数学です.

離散数学を学んだことがなくても, プログラムを書いているのであれば, 無意識のうちに離散数学を利用しています, なぜなら, プログラムという技術が, 離散数学によって支えられているからです.

離散数学の定義となると, (わたしもよくわかっていないのですが …) あつかうトピックスとしては, 以下のようなことがあげられます.

  • 集合
  • 論理
  • 順列・組み合わせ
  • 数学的帰納法・漸化式
  • 背理法
  • オートマトンと形式言語
  • グラフ理論

集合

データベースを支えている数学. また, 集合の概念をプログラムの世界にもちこんだのが Set という型.

論理

ブール型, つまり, true / false という値や, 半加算器・全加算器 (論理和・論理積・排他的論理和などの組み合わせ) のようなデジタル回路にも利用される.

順列・組み合わせ

数え上げを一般化する. 例えば, 配列のインデックスの算出など.

数学的帰納法・漸化式

ループ処理 (再帰) が, 目的を果たすこと, 終了することを保証する.

背理法

停止判定問題の証明などに利用される.

オートマトンと形式言語

コンパイラ (プログラミング言語の開発) や, 正規表現などに利用される.

グラフ理論

ダイクストラ法などのアルゴリズムや, コンピュータグラフィックス (CG) にも利用される.

分割統治

上記にあげた離散数学のトピックスのほとんどで共通することがあります. それが, 分割統治という考え方です. 分割統治とは, 「複雑な問題を, 単純な問題に分割する」, あるいは, 「大きな問題を, 小さな問題に分割する」という考え方です.

例えば, 集合によって, 整数を偶数と奇数という集合に分割します, 論理によって, 真の場合と偽の場合を分割します. 組み合わせは, ある事象が発生する場合と発生しない場合に分割して問題を解決します.

また, 数学的帰納法 (漸化式) は, 2 ステップ (あるいは, n - 1 のステップ) に分割することで大きな問題を解決します.

数え上げとカタラン数

離散数学のなかでも, 特に重要なトピックスが, 数え上げです. なぜなら, コンピュータがどれだけ複雑な処理をしたとしても, 所詮は, 有限回のステップにすぎません. したがって, 数え上げのための思考を習得しておくことはプログラマにとって比較的, 重要なことと考えられます.

このセクションでは, そのトレーニングとして, カタラン数をとりあげてみます.

わかち書き

長い文章というのは読みにくいものです. 一因として, 長くなるほど, いくつかの解釈ができてしまうことが挙げられます. そこで, 読みにくさをある基準で測ることを考えます.

カネオクレタノム

突然ですが, 上記の文をどう解釈されましたでしょうか ?

  • カネ | オクレ | タノム (金送れ, 頼む)

が多いかと思いますが … でも, 以下のように解釈もできなくはないですよね ?

  • カネオ | クレタ | ノム (金をくれた, 飲む)

さて … このように考えると, いったいいくつの解釈があるのでしょうか ?

ここで, 条件をつけて, 切れ目を以下の 4 箇所に限定します. さらに, 生成した文に, 意味はなくても問題ないとします.

  • かね ? お ? くれ ? た ? のむ

切る場合を | , 切らない場合 - をで表すと,

  • ||||
    • かね | お | くれ | た | のむ
  • |-|-
    • かね | おくれ | たのむ
  • -|-|
    • かねお | くれた | のむ

実は, このような条件の場合, 簡単に公式化することができます. それ以上きれない語句の数を $n$ とすると (上記の例だと, $n=5$), $n-1$ 箇所の切れ目 (上記の例だと, 4 箇所) で, 切るか切らないかの 2 とおりを数え上げるので, $2^{n-1}$ とおりとなります (つまり, 上記の例だと, 16 とおり).

構文解釈

ここまではウォーミングアップです. 次は, 以下の 4 つの語句の列の解釈はいくつあるかを考えてみます.

「黒い」「目の」「女の」「子」

(自然言語処理に関連づけると, わかち書きは, 形態素解析, 構文解釈は, 構文解析に関連するトピックスとなります).

よく利用される手段としては構文木があります.

構文木 ( 例)

しかしここでは, 単純に「(」「)」を利用して考えます.

  • ((黒い・目の)・(女の・子))
    • 目が黒い, 女の子
  • ((黒い・目の)・女の)・子)
    • 目が黒い女の, 子 (子ども)
  • ((黒い・(目の・女の))・子))
    • 黒い (服を着ているほうの) 目の女の (役をしている), 子 (子ども)
  • (黒い・((目の・女の)・子))
    • 目の女の(役をしている), 子 (子ども) が, 黒い (服を着ている)
  • (黒い・(目の・(女の・子)))
    • 目の女の子, (その子が) 黒い (服を着ている)

補っている文章は, イメージしやすいようにするためです (わかりづらいので, 詳細はリファレンスを参照してください).

4 つの語句の場合の構文解釈は, 5 とおりであることがわかりました. しかし, 多くの語句がある場合は, このようにエレファントに数え上げることはナンセンスです.

実は, 構文解釈の数え上げは, すでに公式があります.

$n$ 個の語句の構文解釈は, $c_{n-1}$ とおり

$c$ は, よくある $C$ (組み合わせ) ではないことに注意してください. $c$ は, カタラン数と呼ばれ, 有名な問題では, 格子状の経路数え上げの一般化でも知られています.

$ \begin{eqnarray} c_{n} = c_{0}c_{n-1}+c_{1}c_{n-2}+c_{2}c_{n-3}+\cdots+c_{n-2}c_{1}+c_{n-1}c_{0} \quad (c_{0}=1) \end{eqnarray} $

これは, いわゆる, 漸化式になっています.

  • $c_{1}$ の場合, $c_{1}=1$
  • $c_{2}$ の場合, $c_{2}=c_{0}c_{1}+c_{1}c_{0}=2$
  • $c_{3}$ の場合, $c_{3}=c_{0}c_{2}+c_{1}c_{1}+c_{2}c_{0}=5$

つまり, カタラン数と構文解釈の公式を利用すると,

$4$ 個の語句の構文解釈は, $c_{3}$ とおり, すなわち, 5 とおり

となります.

計算不可能な問題

離散数学のなかで, 比較的プログラムに近いトピックスの 1 つが, 計算不可能な問題 (計算可能性理論 : Computability Theory) ではないでしょうか.

計算不可能な問題とは ?

計算不可能な問題とは, 「解を求めるのに莫大な時間を要する問題」でもなく, 「解が存在しない問題」でもありませんし, 「未解決問題」のことでもありません.

計算不可能な問題とは, プログラムで解くことが原理的に不可能な問題のことです.

計算不可能な問題の代表例が, 停止判定問題 (Halting Problem) です.

停止判定問題

まず, プログラムの定義を「データを入力すると結果を出力する」ものとします. ところが, プログラムによっては, 永遠に停止せずに, 結果を出力しないケースもあります. つまり, プログラムのふるまいは, 必ず以下のどちらかになります (有限時間内というのは, 現実的な時間内でなくてもかまいません).

  • 有限時間内に動作を停止する (エラーの場合も含む)
  • 有限時間内に動作を停止しない (永遠に動作を停止しない)

後者は, いわゆる, 無限ループ がその最たる例でしょう.

while (true) {
    // ...
}

プログラムを調べるプログラム

プログラムを調べるプログラムが存在します. 代表例は, 「コンパイラ」です. 高級言語を機械語 (厳密には, アセンブリ) に変換するプログラムです. 「ソースコードチェッカー」も該当します (JavaScript 好きであれば, ESLint がおなじみですね). 「デバッガ」も人がプログラムを調べるためのプログラムです.

「プログラムの停止判定を実行するプログラム」が実装できると仮定します (便宜上, HaltChecker という関数を実装できると仮定します). 停止判定とは, 「プログラムにデータを入力して実行したときに, 有限時間内に動作を停止するかどうか ?」を判定するということです.

/**
 * @return p に d を入力したとき, p が有限時間内で停止する場合, true を返す.
 *   p に d を入力したとき, p が有限時間内で停止しない場合, false を返す
 */
bool HaltChecker(p, d);

1 つ注意点があります. HaltChecker対象となるプログラムを実際に動作させて判定するという方法は使ってはいけません. なぜなら, 対象となるプログラムが永遠に停止しない場合, HaltChecker も永遠に停止しないからです.

次に, SelfLoop という関数を実装します.

void SelfLoop(void (*p)()) {
  bool halts = HaltChecker(p, p);  // 入力が 2 つとも p であることに注意

  if (halts) {
    while (true) {
    }
  }
}

SelfLoop は, 与えられたプログラム pHaltChecker の入力に渡して, その結果, true であれば, 無限ループに入るという実装になっています.

ここで, SelfLoop の入力として, SelfLoop そのものをあたえます.

SelfLoop(SelfLoop);
有限時間内に停止する場合
この場合, HaltCheckerfalse を返します. すなわち, SelfLoopSelfLoop を入力としてあたえると, SelfLoop は停止しないという意味になります. これは, 矛盾です.
有限時間内に停止しない場合
この場合, HaltCheckertrue を返します. すなわち, SelfLoopSelfLoop を入力としてあたえると, SelfLoop は停止するという意味になります. これも, 矛盾です.

もれなく, ダブりなくのケースで矛盾が発生してしまいました.

これは, HaltChecker が実装可能, つまり, 「プログラムの停止判定を実行するプログラム」が実装可能と仮定したことが問題というわけです.

背理法により, プログラムの停止判定を実行するプログラムは実装できないことが証明できました. 実は, 停止判定問題が計算不可能な問題であることは, チューリングによって証明されています.

停止判定問題の例

プログラムのふるまいを調べる問題の多くは, 計算不可能な問題です.

  • 入力としてあたえた 2 つのプログラムが,
    「任意の入力に対しても同じ動作をするかどうか」を判定するプログラム
  • 入力としてあたえたプログラムが,
    「入力した整数が素数であることを判定できるか」を判定するプログラム
  • 入力としてあたえたプログラムが,
    「任意の入力に対しても 1 を出力するかどうか」を判定するプログラム
  • 入力としてあたえたプログラムが,
    「ある一定時間 T 内に終了するかどうか」を T よりも短い時間で判定するプログラム

リファレンス

離散数学は, 大学の講義でも必修でないことがあり, 特に, 高校数学ではあつかわれない, オートマトンと形式言語や, グラフ理論などは, よほど興味をもつか必要に迫られない限り学ぶ機会が少ないと思います.

最後に, プログラマが (離散) 数学をザクっと学ぶのによさそうな参考書を記載しておきます (数え上げとカタラン数, および, 計算不可能な問題は, 下記を参考にしました).

Share Comments
comments powered by Disqus