アルゴリズムデザイン その1

以前購入したアルゴリズムデザインにやっと手をつけたので学習記録を残します。

ただいま学習している項目は”安定マッチング”

このセクションでは安定化マッチング問題から、アルゴリズムの設計プロセスにおける様々なプロセスから問題を提示し、その問題が何であるかを明確にしたあと数学的な証明法によってアルゴリズムの正当性を検証している。

読んでいるうちに気付いたことは僕には基礎的な数学能力が欠けているということ。
アルゴリズムについて背理法を使って証明を必要とするケースがあるので証明方法についても学習しなければいけない。

背理法のサンプル
もし、素数が有限個とすると、最大の素数Ｎが存在する。このとき、２からＮまでの全ての
素数の積に １ を加えた数Ｍを作ると、ＭはＮより大きい整数で、ＭはＮ以下の全ての素数
では割り切れない。ということは、Ｍは素数かまたはＮより大きい素数で割り切れる。いず
れにしても、これは、Ｎが最大の素数であることに矛盾する。よって、素数は無限個ある。
（ユークリッド原論）

中学生の時ぐらいから数学が嫌いだったのだが、思えばわからない部分が積み重なってしまった結果である。わからない部分を掘り下げて一つ一つ理解していくと何とも楽しい。