[微積分と物理/数学的帰納のバックアップソース(No.13)]

Unity学習帳2冊目微積分と物理 / 数学的帰納のバックアップソース(No.13)

[ トップ ] [ 差分 | バックアップ | リロード ] [ 新規 | 一覧 | 検索 | 最新 | ヘルプ ]

TITLE:数学的帰納
#jsmath

帰納処理とはシンプルに言うと「初期値を与えられた漸化式」みたいなもの
プログラムの帰納関数であれ数学の漸化式であれ以下の性質を持つ

-出発点、初期値の設定が必要
-関数で考える場合、帰納処理する関数は出力と入力が同じになる。また関数内で自分自身を必ず呼ぶ事になる&br;（初期値を設定して初回に呼ぶコードと、自分自身を呼び続けループ処理するコードの2部分に分けて書く事になりやすい）
-関数の機能は自分自身を使って自分を定義する構造になる&br;従って&font(Red){生成される出力値、入力値は全て同じ「性質」を持つ事になる};&br;この「同一の性質」を利用して再帰関数の出力値とは別にクラスや構造体を作ったり、データー構造の制御が出来る
-&font(Red){以上の事から「出発点、初期値の設定の値」はどんな方法であれ必ず「帰納関数の出力値」と同一の性質を持つ様に作る必要がある};
-再帰と帰納は方向が違う&br;「小さなものから大きなものへ」という方向に進むのが帰納&br;「大きいものから小さいものへ」という方向に進むのが再帰

このテクニックの大きな利点は

-&font(Red){はじめに、どれぐらいの大きさになるのか予想が出来ないデーター構造を統一して扱える};
-&font(Red){取り尽くすアルゴリズム。粗いものから細かいものへと精度をあげて行くような計算などが作れる};
-&font(Red){処理の深さを調節できる（まともにやると無限ループに陥るような処理を任意に途中で打ち切れる。あらかじめ深さを決めて置く事も出来る）};&br;たとえば前出力と今出力との「差」の度合いを見て途中で打ち切る等


ＡＩや数学的解析、物事の判定、判断を行う際に、おそらく必ず必要になる
シンプルなアクションゲームでは必要ないがストラテジーやパズルゲームで必要になる
「数学の漸化式」と「C#の帰納関数」は入出力が同一になるという点で非常に相性が良い

-帰納は定義にも使える（数列のみならず、帰納的なアルゴリズムによってある一定の形状なり、動き、法則を持った構造物の作成に利用できる）&br;（例：ハノイの塔。自動生成の迷路等）
//-帰納定義は「自分自身を使って自分を定義する」という考え方
-帰納に関わる入出力値は自明な事として全て「同一の性質」を持っていると断言できる
//-再帰と帰納は方向が違う。「小さなものから大きなものへ」という方向に進むのが帰納。「大きいものから小さいものへ」という方向に進むのが再帰

***数学的帰納法による証明 [#h0f4488f]

帰納的に定義された対象は「数学的帰納法による証明」が行える
数学的論理による説明は慣れないうちはその主張がシンプル過ぎて意味がわからない
なので論理が主張する意味を追いかけて読み行間から意味を汲み取る必要がある。追いかけて読んでみる

自然数\(n\in\mathbb{N}\) に依存する命題 \(p(n)\) に対して

\( (\quad (p(1))\quad \wedge \quad (\quad (\forall k\in \mathbb{N})\quad (p(k)\Rightarrow p(k+1))\quad )\quad )\quad \Rightarrow \quad (\quad (\forall n\in \mathbb{N})\quad (p(n))\quad )\)

が成り立つ。数学的帰納法が成り立つ最低条件がこれとなっている

+数列の初期値(この場合\(n=1\))が関数\(P(1)\)で成り立つ事を示している
+任意の自然数\(k\)に対して\(p(k) ⇒ p(k+1)\)が成り立つ事を示す。これは離散的に連続するすべての自然数を入力とした関数が同じ性質を持っている事を示している
//（\(p(k)\)は仮定。\(p(k+1)\)が証明）
+1.2.が同時に成り立つ事が示せることから任意の自然数\(n\)について\(p(n)\)が成り立つ事を結論づける

//『「\(n\)が一番端（1や0）が成り立つ」＆「任意の自然数\(k\)に対して【\(p(k)\)ならば\(p(k+1)\)】が成り立つ」』ならば、「自然数\(n\)に対して依存する命題\(p(n)\)が存在する」
//\(p(n)\)の出力は実数。
これは「[[プログラマの数学>書評]]」で説明されるドミノのたとえ話を論理的に説明したもの

&font(Red){Ｃ＃にこの論理を当てはめると\(p(1)\)は初期設定関数、\(p(k) ⇒ p(k+1)\)はループする帰納関数部を指している。\(p(n)\)が成り立つと主張する部分では、この帰納関数の全入出力は（自然数\(n\)がどんな値をとっても）関数\(p\)の性質を持ち続ける事を結論付けている。この論理式の条件を満たす関数は「数学的帰納法」に適合したものであると、この論理式は定義付けている};

＜メモ＞
「ホーン節」という面白い考え方があるらしい。上記の解釈は我流であり本当はこれを理解した上でやるべきなのかもしれない。以下、資料
[[ホーン節:https://ja.wikipedia.org/wiki/%E3%83%9B%E3%83%BC%E3%83%B3%E7%AF%80]]
[[９．５ ホーン節と導出原理:http://www.ipc.hokusei.ac.jp/~z00102/SeminarII/2000/Lecture24/Horn.htm]]
[[論理プログラミング:https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0]]
ちょっと理解が出来ていないが一度しっかりやってみる必要があるかもしれない…

εδ論法はεとδが対応する関係にあった
この命題も対応する関係を含意によって証明（裏に隠れた関数が同じものだという事を証明）している訳だからよく似た事をしている？


//＜考察＞
//逆にこれが成り立たない関数の形とはどんなものだろうか？
//たとえば\(p(0)\)が一番端だとして\(p(i)=\frac{1}{i}\)の時、\(0\)の除算が発生してその計算は成り立たない
//又、この論証から数列が帰納的な性質を持っているという事が分る
//数列の総和や極限で表現された微分や積分は必ず帰納的に考える事が出来る
//つまり形式的微分や形式的積分で求められた関数から起源である数列の関数\(p(n)\)が必ず求められる筈だとも考えれる？
//＜メモ＞
//自然数の場合は数列で実数でも単調であれば同じこと？・・・総和であれば漸化式？・・・
//依存すると対応するの違いはあるのか？

***証明の例 [#uf20558d]
以下の漸化式が奇数になる事を証明する
\(\begin{cases} { a }_{ 1 }=3 \\ { a }_{ n+1 }=2{ a }_{ n }-1 \end{cases}\)

規則P:　どの\({a}_{n}\)も\(2\)で割ると\(1\)余る（奇数になる）
規則R:　\({a}_{n+1}\)は\({a}_{n}\)に対する漸化式

＜証明＞
basis:
+\({a}_{1}=3\)であるから\({a}_{1}\)は\(2\)で割ると\(1\)余る

induction step:
+\({a}_{n}\)を\(2\)で割ると\(1\)余る数だと仮定する&br;つまり\({a}_{n}=2k+1\)とする（\(\forall k\in \mathbb{N}\)）
+そのとき&br;\({a}_{n+1}=2{a}_{n}-1\)&br;　　　\(=2(2k+1)-1=4k+2-1\)&br;　　　\(=4k+1\)&br;であり規則Rが規則Pの性質を保存している。よって\({a}_{n+1}\)も\(2\)で割ると\(1\)余る

以上により、どの\({a}_{n}\)も2で割ると1余り奇数となる

***漸化式の証明のまとめ [#rfddfa61]

＜漸化式の特徴＞
漸化式は一般項を\(n\)の式で表せない数列も定義できる

＜漸化式の証明のまとめ＞
-basis:　出発点\({a}_{1}\)が性質Pを持っている事を示す
-induction step:　既に得られた項\({a}_{n}\)から次の項\({a}_{n+1}\)を作る規則Rが性質Pを保存している事を示す
-以上を示せばすべての項が性質Pを持っている事が証明される

重要なのは再帰的なプログラムコードや関数も、これを意識すると非常に性質を制御しやすく作りやすくなるという点

***バックアップストッカー [#jaa1e2ee]

＜漸化式＞
|等差数列|\({ a }_{ n+1 }-{ a }_{ n }=d\)|\(d=\)公差|
|等比数列|\(\frac { { a }_{ n+1 } }{ { a }_{ n } } =r\)|\(r=\)公比|
|階差数列|\({ a }_{ n+1 }-{ a }_{ n }=f\left( n \right)\)|　|

数列の漸化式は帰納的定義となる

例えば等差数列の総和の漸化式は以下の形となる
<TODO>
等比数列の総和の漸化式は

« Prev Next »

微積分と物理/数学的帰納のバックアップ一覧
微積分と物理/数学的帰納のバックアップソース(No. All)
- 1: 2015-08-21 (金) 20:23:05 osinko
- 2: 2015-08-21 (金) 20:58:57 osinko
- 3: 2015-08-22 (土) 22:39:21 osinko
- 4: 2015-08-23 (日) 02:26:05 osinko
- 5: 2015-08-26 (水) 22:22:52 osinko
- 6: 2015-08-27 (木) 00:09:58 osinko
- 7: 2016-02-21 (日) 16:24:26 osinko
- 8: 2016-02-21 (日) 22:51:51 osinko
  - Rewound to 2 ages ago. at 2016-02-21 (日) 22:31:28
- 9: 2016-02-22 (月) 02:13:41 osinko
- 10: 2016-02-22 (月) 10:01:11 osinko
- 11: 2016-02-22 (月) 20:09:41 osinko
- 12: 2016-02-22 (月) 23:22:33 osinko
- 13: 2016-02-24 (水) 23:56:08 osinko
- 現: 2016-02-26 (金) 23:46:11 osinko

微積分と物理​/数学的帰納 のバックアップソース(No.13)

微積分と物理/数学的帰納のバックアップソース(No.13)