プログラマの数学を読んで

プログラマの数学を読んで、要点を整理
自分の解釈も織り交ぜているのでそれを踏まえてもらえると
（少しでも気になったら読んでみることをオススメします）

プログラマにとっての数学

• 日々のプログラミングをより良く理解するため
  • 数学を学ぶことで、プログラミングの土台を固めることに繋がる
    • プログラミング < コンピュータ科学 < 数学
  • 普段のプログラミングに、数学的な考え方は取り込める
    • 問題の構造を見抜き、それをシンプルに表現する
      • 高度な数学の知識を必要とすることはそれ程多くない
        • 専門分野によると思うけど

問題の構造を見抜いて一般化する

• 基本的な流れ
  • 問題を単純化して（簡易なケースで）試してみる
  • そこから構造について仮説を立てる
  • その仮説が正しいことを証明する
  • ※ 具体的なテクニックは後述
• 結果が一般化される（式で表現される）ことで、
  • 他の問題にも適用できるようになる
    • 単調な繰り返し作業はコンピュータに任せられる
      • 直接には数えられないほど多くのものを数え上げれる等

具体的なテクニック

上記過程で使える考え方について

問題空間を把握する

• 「難しい」と感じる問題にぶつかったら、まずその問題空間の広さを理解する
  • その空間が広ければ広いほど、解答するのが難しくなる
• 見つけたい解答がそもそも存在しているのか
  • 例えば、「計算不可能な問題」について
    • コンピュータで解ける問題は無限にあるが、その無限はカウンタブルに限られる
      • 全ての問題の集合は、カウンタブルよりももっと大きな無限になる
• その次に探索すべき問題空間を狭められるか
  • 探すのに役立つ前提条件はあるか
  • 例えば、散らかった部屋で本を探す場合、
    • 本棚の中にある
    • 本棚は一列に並んでいる

大きな問題は、小さなまとまりに分けて解く

• 様々な問題の切り分け方がある
  • 問題の構造を捉えるために、問題の分類を試みる
• 「true/false」による2分割
  • ある条件が「成り立つ場合」と「成り立たない場合」
• 「剰余」によるグルーピング
  • 余りが何になるかで、どのグループに入るかが決まる
    • 偶数は２で割ると余りが０になる整数
  • 剰余を上手く使うと、バラバラに見えるものを同一し分類できる
    • 対象が無数にある問題に周期性を見つけ出すと、剰余を使って少ない個数の問題に落とし込める
      • 10^1億日後の曜日
        • 実用的なパリティチェックにも使われている
• 「再帰」による、同形の小問題への分割
  • 小さな規模なら解けるが、大きな規模になると解けない場合、その問題を、一回り小さい問題を使って表現する
    • 一回り小さい問題は「既に解けたもの」として扱う
    • 有名な問題として、ハノイの塔
  • 収束の方向性としては、大きいものから小さいものへ
• 「帰納」による、同形の小問題への分割
  • 数学的帰納法（基数と帰納の2ステップ）を証明することで、無数の証明の代わりになる
    • 大きな問題を同形のn個の小問題に分割しているイメージ
  • 収束の方向性としては、小さいものから大きいものへ

ファンタジーの法則

• 別世界と行き来することで問題を解決する
  • 「こちらの世界」で解けない問題があったら、
  • それを「別世界」に持っていき、そこで解き、
  • 得られた答えを「こちらの世界」に持って来る
• 例えば、「論理の世界」について
  • 自然言語の曖昧さを避けるための道具として、論理式、真理値表、ベン図、カルノー図等がある
    • 特にカルノー図は、論理式をシンプルな形に変換できて便利
  • 現実世界において、一見「複雑なルール」を、
  • 「論理の世界」で「論理式」として扱い、論理式・カルノー図の変換によって「単純化した論理式」にして、
  • 現実世界において、「単純なルール」として利用する
• どれだけの世界を持っているかが重要
  • その分問題を解く際の手がかりになる
  • 例えば、「指数の世界」を持っていれば、大規模な問題を取り扱いやすい形に変換できる
    • 例えば、バイナリサーチによって、大量の情報に対して高速に検索を行える

終わりに

普遍的な話としては、問題理解に尽きるのだと思う。
問題理解できたのであれば、式として表現できる。
様々な問題に取り組む際、それをある種の式で定義して、パラメータ最適化するという流れを意識していきたい。