12 January 2009

プログラマの数学

プログラマの数学

プログラマの数学

結城浩さんの本はほんとうにおもしろい。簡単な文章で高度な概念をわかりやすく説明してくれる。なるほど!という感動が次々でてくるので、とても楽しく読むことができる。現在読んでいる「Java言語で学ぶデザインパターン入門」もおもしろいが、この「プログラマの数学」も名著だとおもう。次は「数学ガール」にもいってみたい。

増補改訂版Java言語で学ぶデザインパターン入門

増補改訂版Java言語で学ぶデザインパターン入門

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

問題を解くときには、複雑な問題をそのままにしておいてはいけない。問題をよく調べることで、構造を見抜く、グループに分ける、周期性を見つけることができる。問題がわかると、複雑な問題をより簡単な小さな問題に分割することができる。あとは小さな問題をそれぞれ解くことで、問題全体を解くことができる。

問題を調べたり、分割したり、分割したそれぞれの小問題を解くときには、数学が便利なツールとして使える。

ゼロ

存在しないものを、「ないという状態がある」と定義することで、一貫性のあるシンプルなルールを作ることができる。

論理

論理を使うことで、問題をtrueとfalseの2つへ分解できる。組み合わせることで複雑な分解も可能。逆に複雑に分解された問題を考えやすくするためのツールもある(論理式、真理値表、ベン図、カルノー図)。

剰余

周期性のある解は、剰余でグループ分けできる。

数学的帰納法

ループを考える際の基礎となる。N回のループは、問題をN分割しているのと同じこと。Nこの問題すべてをきちんと回りきるためには、ループは有効。

順列・組み合わせ

問題の構造を見抜くことで、大きな数も数えることができる。大切なのは、問題の性質を考え、小さい数で考えて見て、それを一般化し全体に適用すること。

再帰

繰り返し構造の中にも、周期的に値が変化するものだけではなく、性質は同じで大きさだけ違うというものもある。このような再帰的構造は、様々な問題の中にあらわれる。

指数爆発

指数的な特徴をもつ問題には注意する。逆に指数的な性質を持つ、バイナリサーチなどのアルゴリズムは強力だ。

計算不可能な問題

計算機では絶対に解けない問題が存在する。この章は少し難しいが、興味深い内容。