Twitter

ある問題をより小さな問題に分割し，それらの解をまとめることでもとの問題の解とする考え方を分割統治法といいます。このとき，部分問題を解く面倒までは考えません。

さらに，その部分問題がもとの問題と構造的に同じもので，ただ解く条件が易しくなっているだけであるとき，それは再帰的であると言います。

問題を再帰的に分解できれば，それを繰り返し適用することで問題をいくらでも易しくすることができ，やがては解の自明な問題にたどり着きます。つまり，問題を解くのにそれを再帰的に分解する方法だけを考えればよいわけです。これを再帰法といいます。

再帰法が適用できるのは，問題の中に自己相似な構造があるときです。高校数学では，場合の数や確率の「n番目の～を求めよ」という問題でよく見られます。漸化式を立てて解くタイプの問題です。

n個のものA1,A2,…,Anからr個を選ぶとき，A1を選ぶなら残りのn-1個からr-1個を選ぶことになり，A1を選ばないなら残りのn-1個からr個を選ぶことになります。二項係数の公式 nCr = n-1Cr-1 + n-1Cr はそういう意味と理解しましょう。

nCr = n-1Cr-1 + n-1Cr は漸化式です。これを右辺から左辺が生成される式と見るのはボトムアップの考え方。左辺を右辺に分解している式と見るのはトップダウンの考え方です。先のような解釈はトップダウンの考え方です。

一方でパスカルの三角形を書いていく作業はボトムアップです。でもパスカルの三角形は普通は上から下に向かって書いていくので，ボトムアップの例としては相応しくないかも知れません。

a₁≦a₂≦…≦an，b₁≦b₂≦…≦bnのとき，Σaₓbₓ/n≧(Σaₓ/n)(Σbₓ/n)が成り立ちます。これを「チェビシェフの不等式」といいます。ただし確率論に同名の不等式があるので，区別する場合はこちらを「チェビシェフの和の不等式」とよびます。

a₁≧a₂≧…≧an，b₁≧b₂≧…≧bnでも同様に成り立ちます。つまり(a,b)が(増,増)または(減,減)ならば成り立ちます。(増,減)や(減,増)ならば不等号の向きが逆になって，Σaₓbₓ/n≦(Σaₓ/n)(Σbₓ/n)が成り立ちます。

(左辺)-(右辺)=Σaₓbₓ/n-(Σaₓ/n)(Σbₓ/n)は，(積の平均)-(平均の積)という形になっているので，aとbの共分散です。つまり，(左辺)-(右辺)の符号はa,bの相関の正負を表しています。

もちろん，a,bが単調でなくても共分散や相関係数は存在しますから，チェビシェフの不等式の定理の逆は成り立ちません。(n≧3)

コーシー・シュワルツの不等式 (Σaₓ²)(Σbₓ²)≧(Σaₓbₓ)² は，ベクトルを使って |a|²|b|²≧(a∙b)² と理解しましょう。等号成立条件は cosθ=±1 すなわち a//b です。

両辺を (Σaₓ²)(Σbₓ²) で割ると，1≧(Σaₓbₓ)²/(Σaₓ²)(Σbₓ²)=(Sab/SaSb)²=(Rab)² となって，相関係数 -1≦R≦1 につながります。

空間ベクトルのついでに平面の方程式を習うと，ax+by+cz+d=0の形で書かれていると思います。ベクトルとのつながりでそうなるのですが，場合によってはz=ax+by+cという陽関数表示の方が便利なこともありますので，選択肢として両方持っておくようにして下さい。

平面上の直線について，ax+by+c=0とy=ax+bの特徴はよく知っていると思います。空間内の平面についても同様と考えて使い分けて下さい。

z=ax+by+cのアイデアは3次元空間でなくても使います。座標平面上でax+by+cを扱うときは，それを空間内の平面と考えることで理解しやすくなります。線形計画法，正領域と負領域，点と直線の距離の公式など。

点と直線の距離の公式 d=|ap+bq+c|/√a²+b² を，ベクトルの内積を利用して証明して下さい。

点P(p,q)，直線ax+by+c=0，直線上の任意の点T(x,y)とすると，距離dはベクトルTPと直線の法線ベクトル(大きさ1)との内積です。
d=|(p-x,q-y)∙(a,b)/√a²+b²|=|ap+bq-ax-by|√a²+b²=|ap+bq+c|√a²+b²

絶対値記号をつけるのは，法線ベクトルのとり方が2通りあり，そのうち一方は内積が負になるからです。