9: 2016-02-22 (月) 02:13:41 osinko  |
10: 2016-02-22 (月) 10:01:11 osinko |
| | -関数で考える場合、帰納処理する関数は出力と入力が同じになる。また関数内で自分自身を必ず呼ぶ事になる&br;（初期値を設定して初回に呼ぶコードと、自分自身を呼び続けループ処理するコードの2部分に分けて書く事になりやすい） | | -関数で考える場合、帰納処理する関数は出力と入力が同じになる。また関数内で自分自身を必ず呼ぶ事になる&br;（初期値を設定して初回に呼ぶコードと、自分自身を呼び続けループ処理するコードの2部分に分けて書く事になりやすい） |
| | -関数の機能は自分自身を使って自分を定義する構造になる&br;従って&font(Red){生成される出力値、入力値は全て同じ「性質」を持つ事になる};&br;この「同一の性質」を利用して再帰関数の出力値とは別にクラスや構造体を作ったり、データー構造の制御が出来る | | -関数の機能は自分自身を使って自分を定義する構造になる&br;従って&font(Red){生成される出力値、入力値は全て同じ「性質」を持つ事になる};&br;この「同一の性質」を利用して再帰関数の出力値とは別にクラスや構造体を作ったり、データー構造の制御が出来る |
| | + | -&font(Red){以上の事から「出発点、初期値の設定の値」はどんな方法であれ必ず「帰納関数の出力値」と同一の性質を持つ様に作る必要がある}; |
| | -再帰と帰納は方向が違う&br;「小さなものから大きなものへ」という方向に進むのが帰納&br;「大きいものから小さいものへ」という方向に進むのが再帰 | | -再帰と帰納は方向が違う&br;「小さなものから大きなものへ」という方向に進むのが帰納&br;「大きいものから小さいものへ」という方向に進むのが再帰 |
| | | | |
| | | | |
| | -&font(Red){はじめに、どれぐらいの大きさになるのか予想が出来ないデーター構造を統一して扱える}; | | -&font(Red){はじめに、どれぐらいの大きさになるのか予想が出来ないデーター構造を統一して扱える}; |
| - | -&font(Red){処理の深さを後から調節できる（まともにやると無限ループに陥るような処理を任意に途中で打ち切れる。あらかじめ深さを決めて置く事も出来る）}; | + | -&font(Red){取り尽くすアルゴリズム。粗いものから細かいものへと精度をあげて行くような計算などが作れる}; |
| - | -&font(Red){粗いものから細かいものへと精度をあげて行くような計算やアルゴリズムが作れる}; | + | -&font(Red){処理の深さを調節できる（まともにやると無限ループに陥るような処理を任意に途中で打ち切れる。あらかじめ深さを決めて置く事も出来る）}; |
| | | | |
| | ＡＩや数学的解析、物事の判定、判断を行う際に、おそらく必ず必要になる | | ＡＩや数学的解析、物事の判定、判断を行う際に、おそらく必ず必要になる |
| | シンプルなアクションゲームでは必要ないがストラテジーやパズルゲームで必要になる | | シンプルなアクションゲームでは必要ないがストラテジーやパズルゲームで必要になる |
| | 「数学の漸化式」と「C#の帰納関数」は入出力が同一になるという点で非常に相性が良い | | 「数学の漸化式」と「C#の帰納関数」は入出力が同一になるという点で非常に相性が良い |
| - | | |
| - | #hr | |
| - | | |
| - | | |
| - | ＜漸化式＞ | |
| - | |等差数列|\({ 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> | |
| - | 等比数列の総和の漸化式は | |
| | | | |
| | -帰納は定義にも使える（数列のみならず、帰納的なアルゴリズムによってある一定の形状なり、動き、法則を持った構造物の作成に利用できる）&br;（例：ハノイの塔。自動生成の迷路等） | | -帰納は定義にも使える（数列のみならず、帰納的なアルゴリズムによってある一定の形状なり、動き、法則を持った構造物の作成に利用できる）&br;（例：ハノイの塔。自動生成の迷路等） |
| | //-帰納定義は「自分自身を使って自分を定義する」という考え方 | | //-帰納定義は「自分自身を使って自分を定義する」という考え方 |
| - | -帰納によって出力された値は自明な事として全て「同一の性質」を持っていると断言できる | + | -帰納に関わる入出力値は自明な事として全て「同一の性質」を持っていると断言できる |
| | //-再帰と帰納は方向が違う。「小さなものから大きなものへ」という方向に進むのが帰納。「大きいものから小さいものへ」という方向に進むのが再帰 | | //-再帰と帰納は方向が違う。「小さなものから大きなものへ」という方向に進むのが帰納。「大きいものから小さいものへ」という方向に進むのが再帰 |
| | | | |
| | ***数学的帰納法による証明 [#h0f4488f] | | ***数学的帰納法による証明 [#h0f4488f] |
| | | | |
| - | 帰納的に定義された対象(つまり数列)は「数学的帰納法による証明」が行える | + | 帰納的に定義された対象は「数学的帰納法による証明」が行える |
| | + | 数学的論理による説明は慣れないうちはその主張がシンプル過ぎて意味がわからない |
| | + | なので論理が主張する意味を追いかけて読み行間から意味を汲み取る必要がある。追いかけて読んでみる |
| | | | |
| | 自然数\(n\in\mathbb{N}\) に依存する命題 \(p(n)\) に対して | | 自然数\(n\in\mathbb{N}\) に依存する命題 \(p(n)\) に対して |
| | が成り立つ。数学的帰納法が成り立つ最低条件がこれとなっている | | が成り立つ。数学的帰納法が成り立つ最低条件がこれとなっている |
| | | | |
| - | +\(p(1)\) が数列の一番端（1や0）が成り立つ事を示す | + | +数列の初期値(この場合\(n=1\))が関数\(P(1)\)で成り立つ事を示している |
| | +任意の自然数\(k\)に対して\(p(k) ⇒ p(k+1)\)が成り立つ事を示す | | +任意の自然数\(k\)に対して\(p(k) ⇒ p(k+1)\)が成り立つ事を示す |
| | //（\(p(k)\)は仮定。\(p(k+1)\)が証明） | | //（\(p(k)\)は仮定。\(p(k+1)\)が証明） |
| | これは「[[プログラマの数学>書評]]」で説明されるドミノのたとえ話を論理的に説明したもの | | これは「[[プログラマの数学>書評]]」で説明されるドミノのたとえ話を論理的に説明したもの |
| | | | |
| - | &font(Red){Ｃ＃にこの論理を当てはめると\(p(1)\)は初期設定関数、\(p(k) ⇒ p(k+1)\)はループする帰納関数部を指している。\(p(n)\)が成り立つとは、この帰納関数の全出力値は同じ性質を持ち、また入力も同じ性質を持たせる必要がある事を説明している}; | + | &font(Red){Ｃ＃にこの論理を当てはめると\(p(1)\)は初期設定関数、\(p(k) ⇒ p(k+1)\)はループする帰納関数部を指している。\(p(n)\)が成り立つと主張する部分では、この帰納関数の全入出力は（自然数\(n\)がどんな値をとっても）関数\(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> |
| | + | 等比数列の総和の漸化式は |
![[PukiWiki]](http://unitylabo.s601.xrea.com/xoops/modules/xpwiki/image/pukiwiki.png "[PukiWiki]")
