2011-01-17

double 型の罠

class Test {
    public static void main(String[] args) {
        for(int i = 0; i < 10; i++) {
            System.out.println(i / 10.0 == 0.1 * i);
        }
    }
}

さて、このプログラムの実行結果はどうなるでしょう ? コンピュータで実数を扱うのって難しいですね(苦笑)。

2011-01-15

素数判定

数学・プログラム

ある整数が素数かどうか判定したいことは良くあると思います。それをプログラムで表すにはどうすればいいか ? というのは、初心の人にはなかなか分からないと思います。

そもそも素数とは、1 と自分自身しか約数を持たない 2 以上の整数のことを指します(負の数は考えないのが一般的です)。ということは、2 から順に 2 , 3 , 5 , 7 , 11 , …となります。これをプログラムでどう実現したら良いでしょう ?

2 以上の整数 n が与えられたとき、n を順々に小さい方から素数で割ってみて、余りが出なければ(= 割り切れれば)、それは素数ではありません。しかし、このような判定を、n より小さい素数全てで行う必要はありません。もし、 $\sqrt{n}$ より大きい数で割りきれたなら、それは必ず $\sqrt{n}$ より小さい数でも割り切れるはずです。従って、判定に用いる素数としては $p\leq\sqrt{n}$ なるものだけで十分なはずです。

まぁ説明はこのくらいにして、実際のソースを見ていただきましょう。

2010-11-23

3 × 5 と 5 × 3 は違う !?

数学教育

5 枚の皿に 3 個ずつリンゴが乗っている。リンゴは全部で何個あるか。

という問題が、今議論を呼んでいるようです。

指導要領的な解釈では、1 枚の皿に 3 個のリンゴが 5 皿あるから「3 × 5」と立式するのが正しく、「5 × 3」ではだめなのだそうですが、果たしてこれは正しい指導のあり方なのでしょうか ?

皿に 1 個ずつリンゴを乗せていく作業を 1 セットと考えましょう。今、皿は 5 枚ありますから、1 セットの作業で 5 個のリンゴが必要になります。これを 3 セット繰り返せば、1 枚の皿には 3 個のリンゴが乗った状態になりますから、結局のところ「5 × 3 = 3 × 5」で何の問題もない気がします。そもそも問題文では「5」が先に出てきますから、「5 × 3」と立式した子供は多かったはずです。

掛け算の順序は交換可能である、という大事な性質を犠牲にしてまで、立式の正しさを強制することに何の意味がありましょう。子供の発想の自由を大切にせずして、豊かな知識を身に付けさせることは不可能と考えます。

2010-11-20

自然数から整数へ、そして有理数へ(その 3)

数学・基礎論

群

$(A,\alpha)$ を単位半群(モノイド)とし、 $e$ を単位元とします。もし、次の法則が成り立つならば、 $(A,\alpha)$ は群であると言います。

任意の $a\in A$ に対し、 $a$ によって定まる $A$ の元 $a^{-1}$ があって
$a\alpha a^{-1}=a^{-1}\alpha a=e$
を満たす。

$a^{-1}$ を $a$ の逆元と言います。

全変換半群と対称群

$A$ を集合とするとき、 $A$ から自身への写像の全体 $A^A$ のことを $I(A)$ とも表します。 $I(A)$ には写像の合成によって演算が定義され、これについて $I(A)$ は単位半群になります(単位元は恒等写像)。 $I(A)$ は全変換半群と呼ばれます。特に $I(A)$ の部分集合で、全単射だけを集めたものを $S(A)$ で表します。これは群になりますが、 $A$ 上の対称群と呼ばれます。

2010-11-19

自然数から整数へ、そして有理数へ(その 2)

数学・基礎論

結合則と可換性、単位元

$(A,O)$ を代数系とし、 $\alpha\in O$ とします。また、 $\alpha(x,y)$ を $x\alpha y$ と書きます。

$(x\alpha y)\alpha z=x\alpha(y\alpha z)$
が任意の $x,y,z\in A$ について成り立つとき、この代数系は $\alpha$ について結合的であると言います。特に $(A,\alpha)$ が $\alpha$ について結合的であるとき、 $A$ は $\alpha$ について半群であると言います。

$x\alpha y=y\alpha x$
が任意の $x,y\in A$ について成り立つとき、この代数系は $\alpha$ について可換であると言います。半群 $(A,\alpha)$ が $\alpha$ について可換なとき、まとめて可換半群と言います。 $\bar{\mathbf{N}}^+,\bar{\mathbf{N}}^\times$ は、それぞれの演算に関して可換半群です。

さらに、 $A\neq\emptyset$ で
$x\alpha e=e\alpha x=x(\forall x\in A)$
となる $e\in A$ が存在するとき、この $e$ を $\alpha$ についての単位元と言います。 $\bar{\mathbf{N}}^+,\bar{\mathbf{N}}^\times$ は、それぞれ 0 , 1 を単位元に持ちます。

単位元を持つ半群を単位半群、もしくはモノイドと言います。 $\bar{\mathbf{N}}^+,\bar{\mathbf{N}}^\times$ はいずれも可換モノイドです。

2010-11-18

自然数から整数へ、そして有理数へ(その 1)

数学・基礎論

以前、集合論の公理系を用いて自然数の集合 $\omega$ を定義し、その上に加法と乗法という算法を定義しました(べき乗も定義しましたが、今回は特に使いません)。今回は、それを拡張して整数と有理数を構成してみます。

代数系

$A$ を集合とし、 $O$ を $A^{A\times A}$ の部分集合とします(つまり $O$ は $A\times A$ から $A$ への写像の集まりです)。このとき $(A,O)$ を代数系と言います。 $A$ は台集合、 $O$ は算法族と言います。特に $O=\{\alpha\}$ のとき、 $(A,\{\alpha\})$ を単に $(A,\alpha)$ と書き、これを $A$ を台集合とする $\alpha$ 系と言います。

既に知っているように $(\omega,\{+,\times\})$ は代数系です。 $\omega$ をこの代数系の台集合と見るとき、特に $\bar{\mathbf{N}}$ と書きます。特に $(\omega,+),(\omega,\times)$ を $\bar{\mathbf{N}}^+,\bar{\mathbf{N}}^\times$ と表します。

2010-10-30

カオス現象(その 3・最終回)

数学・解析

いきなりですが次の画像をご覧ください。

これは先程と同じ $y_{n+1}=ay_n(1-y_n),y_0=0.1$ を、 $a$ を 3.8 から 3.9 まで $10^{-4}$ 刻みで動かして同じように挙動を調べたものです。くっきりと 3 周期点が見えますね。

実はこの周期 3 こそが全ての(とまでは言いませんが)正体です。一般に、離散力学系 $x_{n+1}=f(x_n)$ において、Sharkovskii の定理というものがあります。 $f:\mathbf{R}\to\mathbf{R}$ が連続のときの周期点の存在に関する定理なのですが、それに先だって、周期点に関する Sharkovskii の順序と呼ばれるものがあります。これは $n=2^r p,m=2^s q$ ( $p,q$ は奇数) について $n\succ m$ であるとは

$r\lt s$ かつ $p\gt 1$
$r=s$ かつ $p\lt q$
$r\gt s$ かつ $p=q=1$

によって決定される $\mathbf{N}$ 上の順序で、この順に数を並べると
$3,5,7,9,\dots,2n+1,\dots,\\2\cdot 3,2\cdot 5,2\cdot 7,2\cdot 9,\dots,2(2n+1),\dots,\\2^2\cdot 3,2^2\cdot 5,2^2\cdot 7,2^2\cdot 9,\dots,2^2(2n+1),\dots,\\\dots,2^n,\dots,2^2,2,1$
となります。定理の主張は、この順序的に前であるところの周期点が存在すれば、後にあたる周期点が存在するというものです。例えば 6 周期点があれば 10 周期点、14 周期点…等が存在することになります。特にこの並びを見てわかる通り、3 周期点が存在すれば、あらゆる周期の周期点が存在することになります。*1

Li と Yorke はこれに加えてもっと強い主張をします。世にいう "Period Three Implies Chaos." (「周期 3 はカオスをもたらす。」)です。1975 年に発表されたこの論文は「決定可能でありながら、事実上の予測が不可能である」という現象が数学に存在し得ることを世に知らしめたものと言えます。*2

現在では「カオス」という現象にはきちんと数学的な定義が与えられ、理論も研究され、株価の動向予測などの経済学の分野にも応用されるなど、現代数学を語る上で外せないトピックであると言えます。今回ご紹介したのはいわゆる 1 次元のカオスですが、Lorenz attractor などに代表される 3 次元カオスもあります。突き詰めて行けば奥の深い分野ですが、今回はその入口を見ていただいたところでお開きとします。興味を持たれた方は、ぜひ参考書を手にとって勉強してみてください。

*1: $f$ の連続性は重要な仮定です。これがないと、例えば $f(x)=(1-x)^{-1}$ は全ての点が 3 周期点ですので反例になります。

*2:この論文が発表されるまでにはいろいろと経緯があるのですが、それについては Li 自身の回想があります。