プログラマの数学
ゼロの物語 "ない"ものが"ある"ことの意味
ゼロというのは穴というより、穴埋めなのですね。場所を確保してるのですから。 それをプレースホルダと言います。
なにもしないけど、命名されてるものはいろいろありそうかな。。
インターフェースだけ用意しておいて、実装は後回しみたいで、状況によって何か生み出す。 そういうものに出会った時に、何が期待されているかを考える。数字の位取りなら、具体来てな数字があとから入る。
論理 trueとfalseの2分割
命題:
否定、論理積、論理和, 排他的論理和,等値、含意
否定については、単項に対するオペレータ? 必要に応じて()を使って単項化する。
偶数・奇数、 掛け算のプラス・マイナス、長廊下の電気スイッチ, DBの排他ロックもいいかな。
含意
$ A \to B
がTrueになるためには、Aの集合要素はBの中に居ないといけない。
$ A \to Bで true のケースでも、$ B \to Aがfalseのケースはある
16通り
A,Bがtrue, falseの組み合わせなので、4つの領域がある。
なので、2^4 = 16
Aの否定、A&B, A|B, AxorB, A=B, A=>B.... 16通りある。
A=>Bは、 $ (\lnot{A}) \lor{B}
落とし穴の論理 (Aにいるならば、Bにいないといけない。Aにいないなら否定はできない,自由?)
ド・モルガンの法則
双対性 。論理式の中の true - false, A -$ \lnot A, $ \land- $ \lor をそれぞれ(対)を交換して、否定する。 これで等しくなる。言い換えれると、それぞれを交換すると、元のと合わせて(論理和)で全体集合になる
カルノー図
数学的帰納法 無数のドミノを倒すには
順列・組み合わせ 数えないための法則
もれ・だぶりに注意
数えるとは、、自分が数えたいものを整数に対応づける 植木算 あとで、重複組合せの計算の際にもイメージ繋がる?
和の法則。だぶりがないなら、$ |A \cup B| = |A| + |B| だし、あるなら、$ |A \cap B|を引く。
包含と排除の原理 The Principle of Inclusion and Exclusion
積の法則。要素のペアを作って、それを数える。
トランプ: 図形と数字。 サイコロを3つ: $ 6^3 ランプ10個(OnOff) $ 2^{10}
n個のものを順序を考えて並べること。 1つづつ選択肢が減るので、階乗(factorial) $ 5!とか。
順列((permutation)
n個のものからK個選んで順序を考えて並べること。n=6 k=4 $ 6\times5\times4\times3 $ \frac{6!}{(6-4)!}
組み合わせ(combination)
順列から重複組み合わせ分を割れば良い。 上記の例なら、$ \frac{6\times5\times4\times3}{4\times3\times2\times1} $ \frac{6!}{(6-4)!4!}
重複組合せ
再帰 自分で自分を定義する
階乗も再帰か。。気づかなかった...単に、小さい方(0か1か)の方から見るという視点がなかったのか。考えもなかったが。
指数的な爆発 困難な問題との戦い
計算不可能な問題 数えられない数、プログラムできないプログラム
プログラマの数学とは まとめにかえて