続 atsushifxの七転八倒

ウツ、発達障害の闘病記とIT関係のつれずれを書いていきます

「プログラマの数学 7章 指数的な爆発」まとめ

プログラマの数学 7章 指数的な爆発」のまとめです。
7章は「指数的な爆発」がテーマ。問題が現実の時間内に解けるかどうかを扱います。

まずは「指数的な爆発」について


  • 問題の中には、数が1つ増えることに調べる数が途轍も増えていく問題がある。こういった数の急激な増加を「指数的な爆発」と呼ぶ。

  • 指数的な爆発は組み合わせを調べる場合でおこることが多い。たとえば、プログラムの設定オプションなどの組み合わせがその例となる

  • 組み合わせ問題などは基本的にしらみつぶしにすれば解ける。しかし、解決に千年単位の時間がかかることもあるため現実的ではない

  • 指数的な爆発を利用することで、効率のよいアルゴリズムができる。二分検索などがその例となる

つぎは「対数」について


  • 大きな数の問題を扱うときには、数の桁数で問題を扱う。数の桁数を対数と呼ぶ

  • 対数から指数法則を導き出すことができる。指数法則を使うと大きな数の計算が大体どのくらいの数になるかを足し算で導き出すことができる

最後は指数的な爆発への対処について


  • どんな問題でも「解けたかどうかの判定方法」と「順番に試すための手順」があればしらみつぶしで問題を解くことができる。これを『パズル原理』と呼ぶ

  • 上記による解ける問題であっても指数的な爆発を含んでいると、期限内に解けない。まずは問題に指数的な爆発があるかどうかをチェックする必要がある

  • 指数的な爆発を含む問題を効率よく解く方法としては「変換して解く」・「近似的に解く」・「確率的に解く」という方法がある

  • 「変換して解く」とは、問題の性質に着目し、解決が容易な問題にして解くという方法。3章のパリティなどがその例

  • 「近似的に解く」とは、問題を完全に解くのではなく、近い解を探すという方法。星と星の間の距離を対数で使って解いたのがその典型

  • 「確率的に解く」は乱数を求めて解を出し、それを評価することで解を探し出す方法。「遺伝的アルゴリズム」がその例となる

なお、コンピュータの世界では「計算複雑性理論」で扱っています。