早稲田大学オープンキャンパス２０１４ 日常を数学する ～知らず知らずに使っている数学～ 早稲田大学オープンキャンパス２０１４ 日常を数学する 　～知らず知らずに使っている数学～ 守屋　悦朗 早稲田大学　教育学部　数学科 皆さん、こんにちは！　早稲田大学オープンキャンパスにようこそ！　今日は、教育学部数学科の模擬授業にお出でいただき、ありがとうございます。今日は、「日常を数学する」というタイトルで話をしたいと思います。 皆さんは数学が好きですか？　数学科の模擬授業に来たのですから、勿論好きですよね？　だから、学校では数学を一生懸命勉強していると思います。でも、そういう学校で習った数学を普段の生活の中で使っていますか？ 皆さんの身の回りで使われている数学を思い浮かべてみてください。

学校で学んだ数学を日常生活の中で 使ったことがありますか？ どんなところでどんな数学を 使っているか考えてみましょう。 もしかしたら、 「微分積分や対数や数列や三角関数や数学的帰納法 といった数学を日常生活の中で使うことなんてない」 と思っていませんでしたか？ いいえ、そんなことはありません！ どんなところでどんな数学を 使っているか考えてみましょう。

日常の中の数学（中学～高校で学ぶこと） ねずみ講、幸福の手紙、複利計算 → 等比数列、等比級数 ねずみ講、幸福の手紙、複利計算　→　等比数列、等比級数 名刺やＡ４用紙の縦横比（Ａ４用紙は折っても折っても縦横比が変わらない）　→　√2，黄金比、フィボナッチ数列 音の高低を表すデシベル、地震の強さを表すマグニチュード　→　対数 気温と桜の開花日、距離と速度とかかった時間、投げ上げたボールの描く軌跡、人工衛星の軌道　→　関数 時計、コンピュータ　→　12進数、60進数、2進数 (8進数、16進数) 木の高さを測る　→　三角関数 宝くじ、賭け　→　確率 1+3=4, 1+3+5=9, 1+3+5+7=16，・・・，1+3+･･･(2n-1)=?　→　数学的帰納法 円の面積、球の体積　→　積分 男生徒と女生徒の人数・メガネを掛けている生徒の数・メガネを掛けていない男生徒の数からメガネをしている女生徒の人数を知る　→　集合　 「ＡならばＢである」ことと「ＢでないならばＡでもない」こととは 　　同じこと　→　命題と論理 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧）

集合を使う １～10000 の中で、2, 3, 5 のどれかで割り切れるものは何個あるか？ 3で割り切れるもの 2で割り切れるもの 3, 6, 9, …, 9999 10000÷3=3333 個 2で割り切れるもの 2, 4, 6, …, 10000 10000÷2=5000 個 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） 2でも3でも割り切れるもの 6, 12, 18, …, 9996 10000÷6=1666 個

集合を使う １～10000 の中で、2, 3, 5 のどれかで割り切れるものは何個あるか？ 2で割り切れるもの 3で割り切れるもの 2, 4, 6, …, 10000 5000 個 3で割り切れるもの 3, 6, 9, …, 9999 3333 個 5で割り切れるもの 5, 10, 15, …, 10000 10000÷5=2000 個 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧）

集合を使う １～10000 の中で、2, 3, 5 のどれかで割り切れるものは何個あるか？ 2で割り切れるもの 3で割り切れるもの 3, 6, 9, …, 9999 3333 個 2で割り切れるもの 2, 4, 6, …, 10000 5000 個 2でも5でも割り切れるもの 10, 20, 30, …, 10000 10000÷10=1000 個 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） 5で割り切れるもの 5, 10, 15, …, 10000 2000 個

集合を使う １～10000 の中で、2, 3, 5 のどれかで割り切れるものは何個あるか？ 2で割り切れるもの 3で割り切れるもの 3, 6, 9, …, 9999 3333 個 2で割り切れるもの 2, 4, 6, …, 10000 5000 個 3でも5でも割り切れるもの 15, 30, 45, …, 9990 10000/15=666 個 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） 5で割り切れるもの 5, 10, 15, …, 10000 2000 個

集合を使う １～10000 の中で、2, 3, 5 のどれかで割り切れるものは何個あるか？ 2で割り切れるもの 3で割り切れるもの 3, 6, 9, …, 9999 3333 個 2で割り切れるもの 2, 4, 6, …, 10000 5000 個 2でも3でも5でも割り切れるもの 30, 60, 90, …, 9990 10000/30=333 個 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） 5で割り切れるもの 5, 10, 15, …, 10000 2000 個

集合を使う １～10000 の中で、2, 3, 5 のどれかで割り切れるものは何個あるか？ 1666 3333 5000 333 666 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） 2000 5000 + 3333 + 2000 – 1666 – 1000 – 666 + 333 = 7334

Ａ４用紙やＢ４用紙のサイズ 何度折っても縦横の比が変わらない Ａ４用紙やＢ４用紙のサイズ 何度折っても縦横の比が変わらない 　ここ（真ん中）で折る 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧）

Ａ４用紙やＢ４用紙のサイズ √２ （２の平方根） a : 2b a : 2b = b : a b ∴ a2 = 2b2 真ん中で折る Ａ４用紙やＢ４用紙のサイズ √２　（２の平方根） a : 2b a : 2b = b : a b ∴ a2 = 2b2 　真ん中で折る 比 x = a/b は x2 = 2 を満たす b : a b 　　　　　　∴ x = √ 2 つまり、縦と横の比は 1 : 1.414213・・・ 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） a

Ａ版用紙のサイズ 19世紀末、ドイツの物理学者オズワルドによって提案された。 面積が1m2の「縦横比が 1 ：√2の長方形」を A0 とする。 √2a A0 の縦横の長さ a×√2 a = 100×100 (cm2) ∴ a = 100 / √2 = 84.008965・・・ (cm) √2a = 118.8063・・・ (cm) √2a a a A0 841mm ×1189mm A0 を半分に折ると A1 594mm × 841mm A1 を半分に折ると A2 420mm × 594mm A2 を半分に折ると A3 297mm × 420mm A3 を半分に折ると A4 210mm × 297mm A4 を半分に折ると A5 148mm × 210mm 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧）

Ｂ版用紙のサイズ 日本独自の規格 面積が1.5m2 の「縦横比が 1 ：√2の長方形」を B0 とする。 B0 の縦横の長さ √2b b×√2 b = 1.5×100×100 (cm2) ∴ b ≒ 103.0 (cm) √2b ≒ 145.7 (cm) √2b b b B0 1030mm ×1456mm B0 を半分に折ると B1 728mm ×1030mm B1 を半分に折ると B2 515mm ×728mm B2 を半分に折ると B3 364mm ×515mm B3 を半分に折ると B4 257mm ×364mm B4 を半分に折ると B5 182mm ×257mm 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧）

黄金比 縦横の均整がとれた長方形の縦と横の比は？ 黄金比 　　 縦横の均整がとれた長方形の縦と横の比は？ 名刺のサイズ 横 ： 縦 ＝　55 ： 91 　　　　　 ＝ 1 ： 1.6545・・・ ≒ 1 ： 1.618・・・ 　　　　　 ＝ 1 ： 1+√5 91mm 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） 黄金比 黄金のように美しい比率！？ 55mm

黄金比とフィボナッチ数列（その１） a (a+b) : a (a+b) : a = a : b a ∴ a2 = b(a+b) b ここで折る b 　　　と　　が相似になるには？ 比 x = a/b は x2 - x - 1 = 0 を満たす a a : b 　　∴ x = (1+√5) / 2 = 1.618・・・ ∴ a = (1.681・・・)×b つまり、縦と横の比は a : b = (1.618・・・) : 1 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧）

黄金比とフィボナッチ数列（その２） (a+b) : a = a : b は 横→縦 = 横 → 縦 b → a = a → a+b 横→縦 = 横 → 縦　　 b → a = a → a+b と順に変わる。 (a+b) : a a b → a = a → a+b は b=fn-1 → a=fn → a+b=fn+1＝fn-1+fn と見ることができる。 b a : b a この 　　　　fn+1＝fn-1 + fn がフィボナッチ数列で、f1=f2=1とすると 　　　　 1　 1+√5 n √5 　 2 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE（単位：J（ジュール））、マグニチュードをMとすると log_{10}E = 4.8 + 1.5M という関係がある。マグニチュードが1増えるとエネルギーは10＾1.5＝31.62倍になる。 ｄＢは、基準値と比較して何倍、或いは何分の１であるかという事を対数を用いて表すための単位。音量（ｄＢ）＝２０×ｌｏｇ（対象の音圧／基準音圧） fn =

日常の中の数学（学校で学ばないこと） 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？

高校ではやらない数学　① 　　グラフ ５ 辺 ２ ７ 頂点 ３ 重み

ケー二ヒスベルクの橋 Ａ Ａ B B C C D D 図はWikipedia（http://ja.wikipedia.org/wiki/%E4%B8%80%E7%AD%86%E6%9B%B8%E3%81%8D）から引用

一筆書きできるか？ あ　ん　川　木　田　中　 Ａ　Ｂ　Ｃ　Ｒ　Ｗ

すべての辺を１回だけ通って戻ってこれるか？ 可能！ c a b d e g f i h j m n k

自明でない連結な(多辺)グラフ Ｇ が一筆書き 定理（Ｌ．オイラー，１７３６） 　自明でない連結な(多辺)グラフ Ｇ が一筆書き 　できるための必要十分条件は、 Ｇ が奇頂点 　(接続している辺の本数が奇数の頂点のこと)を 　もたない(＝０個持つ)か、またはちょうど２個 　持つことである。 　０個のときには、書き始めた所に戻ってくる 　ことができる。

では、辺に向きがあるとき、 すべての辺を１回だけ通って戻ってこれるか？ a e b d c

では、辺に向きがあるとき、 すべての辺を１回だけ通って戻ってこれるか？ a e b d この例の場合、 戻ってはこれないが 一筆書きは可能！ c

ちょっと複雑になると？ c a b d e g f 不可能！ i h なぜ？ j m n k

オイラーの定理（その２） 　自明でない連結な(多辺)有向グラフＧが一筆書きできるための必要十分条件は、Ｇのどの頂点も入次数(入ってくる辺の本数)と出次数(出ていく辺の本数)が等しいか、　または、１つの頂点は出次数が入次数より１大きく、 　もう１つの頂点は入次数が出次数より１大きく、 　それ以外の頂点は入次数と出次数が等しいことである。 　前者のときには、書き始めた所に戻って来ることができる。

では、 すべての頂点を１回だけ通って戻ってこれるか？ c a b d e g f i h j m n k

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

頂点 ～ は生徒の家で、使える道が辺のとき、 すべての家を１回だけ訪問して戻ってこれるか？ 頂点 ～ は生徒の家で、使える道が辺のとき、 すべての家を１回だけ訪問して戻ってこれるか？ a n c a b d e g f i h 不可能！ なぜ？ j m n k

与えられた有向・無向グラフのすべての頂点を丁度 Ｐ≠ＮＰ予想（ハミルトングラフ問題） 　与えられた有向・無向グラフのすべての頂点を丁度 　１回ずつ通って出発点に戻って来る経路を効率よく 　求めるアルゴリズム（方法）は存在しないだろう。 　ハミルトングラフ問題をはじめとする類似の問題を 　ＮＰ完全問題という。 ナップサックに効率よく詰める方法 ジグソーパズル 時間割作成 グラフ上の最も遠い2点間の距離を求める そのほかの何万何千という問題！

定理（ＮＰ完全問題、１９７２） 西暦２０００年のミレニアム問題 　もし、ＮＰ完全問題のどれか１つを解く効率良いアルゴリズムが見つかれば、すべてのＮＰ完全問題を効率よく解くことができる。 西暦２０００年のミレニアム問題 米国　クレイ数学研究所が提唱 　現在未解決の数学の重要問題７つ 　そのうちの１つがＮＰ≠Ｐ予想 　解決すれば１００万ドル（約１０億円）

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

ＮＰ完全問題よりも難しい問題は？ 解くアルゴリズムが無い問題さえある！ 将棋､囲碁などのゲームの先手必勝法に関する問題 多くはEXP完全な問題 数独はＮＰ完全な問題 尻取りゲームはPSPACE完全な問題 いくらでも難しい問題が存在する！ 解くアルゴリズムが無い問題さえある！ 単語のペア を並べ替えて同じ文章を作れるか？ 　 (ab, a), (bc, bb), …, (aa, caa) →　(ab)(bc)(aa) = (a)(bb)(caa) 不定方程式が整数解を持つか？ 3xy2+5x3yz-7y2z2 = 24

日常の中の数学 日常生活で実際に役立っているものは？ ナビゲーション、駅探索 工事費をできるだけ安くするには？ 一番大きいものを見つける 小さい方からｎ番目のものを見つける 小さい順・大きい順に並べ替える

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

どの経路を通れば一番近いか？ から へ行きたい どの経路を通れば一番近いか？ から へ行きたい a n 15 85 c a b d 9 67 33 56 10 41 e 14 g 12 f 38 11 2 18 i 21 6 h 81 39 22 30 5 j m 20 n 77 k

どの経路を通れば一番近いか？ から へ行ってみよう 　どの経路を通れば一番近いか？ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　から　　　へ行ってみよう h (0;a) (15;ab) 15 25 c (40;abc) a b 9 33 35 10 (10;ae) e g (49;abcg) f 11 (33;af) 2 18 21 6 h (50;abh) 22 j (26;abj) 20 k (39;afk)

どの経路を通れば一番近いか？ から へ行く最短経路 どの経路を通れば一番近いか？ から へ行く最短経路 n 15 85 c a b d 9 67 33 56 10 41 e 14 g 12 f 38→71 11→26 2→63 18 i 21 6→39 h 81 39→110 30 5→66 22→61 j m 20 n 77 k

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

コンビニへ効率よく商品を配送するには？ 15 85 c a b d 9 67 33 56 10 41 e 14 g 12 f 38 11 2 18 i 21 集配センター 81 39 6 22 30 5 j m 20 n 77 k 配送車の 　種別・台数・積載容量 運転手の手配、など

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

工事費を最も安くするには？ 15 85 c 水源 b d 9 67 33 56 10 41 e 14 g 12 f 38 11 2 18 i 21 6 h 81 39 22 30 5 j m 20 n 77 k

工事費を最も安くするには？ 完了！ 25 5 c 水源 b d 3 15 10 41 e g 12 f 11 2 12 6 h 8 22 5 　完了！ 22 5 j m 9 k

工事費を最も安くするには？ 15 85 c 水源 b d 9 67 33 56 10 41 e 14 g 12 f 38 11 2 18 i 21 6 h 81 39 22 30 5 j m 20 n 77 k

工事費を最も安くするには？ 15 85 c 水源 b d 9 67 33 56 10 41 e 14 g 12 f 38 11 2 18 i 21 6 h 81 39 22 30 5 j m 20 n 77 k

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

一番大きいものを見つけるには？ ルール： ２つのものの大小比較しかできない。 n個のデータ a1, a2, ･･･, an の中から、２個ずつの大小比較だけで最大のものを見つける。 これらのデータは、どの2つも大小関係がある（全順序）。 これらのデータは最初はでたらめな大きさの順に、ある場所に置かれていて、どのデータも同じ一定時間で「取り出すこと」「比較すること」「別の場所に移すこと」ができる。 作業用に別の場所を使ってもよい。

あなたの方法を考えてください 計算の方法（手順）のことをアルゴリズムといいます あなたの方法を考えてください 計算の方法（手順）のことをアルゴリズムといいます

順 次 探 索 比較回数は n－1 回 逐次処理 ａ１ ａ2 ａ3 ・・・ ａi ・・・ ａn ａmax 順　次　探　索 ａ１ ａ2 ａ3 　 ・・・ ａi 　　・・・ ａn ａmax １．はじめに 　に a1 を入れておく。 ２．　　　　　　　と a2, a3, ・・・, an を順次比べ、大きい方を　　　　　　　　に残す。 ａmax ａmax ａmax 比較回数は　n－1　回 逐次処理

ト ー ナ メ ン ト 法 比較回数は n－１回 並列処理が可能 ａ１ ａ2 ａ3 ａ４ ・・・ ａn-1 ａn ａ2 ａ3 ａm ａn 　　・・・ ａn-1 ａn ａ2 ａ3 ａm ａn ａ3 ａm ａm 比較回数は　n－１回 １．２つずつ比べ、大きい方を下へ。 ２．最大値は　　　　　　　 ａm 並列処理が可能

再帰的考え方 max{ a1 } = a1 max{ a1,a2, ･･･, an } = max{ a1, max{ a2,･･･, an } } 比較回数　f(1)=1, f(n)=f(n-1)+1 ⇒ f(n)=n-1 max{ a1 } = a1 max{ a1,a2, ･･･, an } = max{ max{ a1,・・・,an/2 }, max{ an/2+1,･･･, an } } 比較回数　f(1)=1, f(n)=2f(n/2)+1 ⇒ f(n)=n-1

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 大きい順に並び替えるには？ ✓

小さい方からｎ番目のものを見つけるには 比較は うまくいけば log2n 回 8個の中の７番目のものをみつけたい find(8,7) 8 3 5 1 7 6 2 4 4 　find(8,7) 3 1 2 4 8 5 7 6 6 　find(4,3) 5 6 8 7 7 　find(2,1) 比較は　うまくいけば log2n 回 7 8 　find(1,1) １．見つけたい中から１つ　　　　　を任意に選ぶ。 ２．１つずつ　　　　　　と比べて、それより小さいグループと大きいグループに分ける。 ３．どちらかのグループの中の何番目かを求めればよい。　　　　　　　

日常の中の数学（学校で学ばないこと） ✓ 一筆書きする方法は？ 無駄なく家庭訪問できるか？ 将棋や碁はなぜ難しい？ どの経路を通れば一番近いか・安いか？ コンビニへ効率よく商品を配送するには？ 工事費をできるだけ安くするには？ 一番大きいものを見つけるには？ 小さい方からｎ番目のものを見つけるには？ 小さい順に並び替えるには？ ✓

小さい順に並び替えるには ソート（sort, sorting）、並べ替え、整列化 まず、あなた独自の方法を考えてみよう 逐次探索と同様な考え方？ トーナメント法と同じような考え方ができる？ 再帰的な方法は？ もっと奇抜なアイデアがある？ あなたの方法では、何回比較を行なうか？

① 選択ソート おそらく、かなり多くの人が考えたやり方 ①　選択ソート おそらく、かなり多くの人が考えたやり方 1 2 3 4 5 6 7 53 24 ７8 19 43 61 36

①　選択ソート 1 2 3 4 5 6 7 53 53 24 ７8 19 43 61 36 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 53 24 24 ７8 19 43 61 36 53 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 53 24 ７8 19 19 43 61 36 24 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 53 24 ７8 19 43 61 36 19 １９　が最小とわかった ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 53 24 ７8 19 43 61 36 19 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 24 ７8 53 43 61 36 ２４　が最小とわかった ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 24 ７8 53 43 61 36 24 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 ７8 ７8 53 43 61 36 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 78 53 53 43 43 61 36 78 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 78 53 43 43 61 36 53 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 78 53 43 61 36 36 43 ３６　が最小とわかった ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 78 53 43 61 36 36 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 53 53 43 61 78 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 53 43 43 61 78 53 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 53 43 61 78 43 ４３　が最小とわかった ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 53 43 61 78 43 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 43 53 61 78 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 43 53 53 61 78 ５３　が最小とわかった ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 43 53 61 78 53 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 43 53 61 61 78 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 43 53 61 78 61 ６１　が最小とわかった ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 36 43 53 61 78 61 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 34 43 53 61 78 ここに一番小さいもの（が入っていた場所）を入れる

①　選択ソート 1 2 3 4 5 6 7 19 24 34 43 53 61 78 ここに一番小さいもの（が入っていた場所）を入れる

比較回数は 最初　　　　 n-1 回の比較 ２回目 　　　n-2 回の比較 ・・・ n-1 回目　1回の比較 合計　n(n-1)/2 回の比較が必ず必要

その他の方法 体で体験する人間ソート 挿入ソート バブルソート クイックソート マージソート シェルソート ヒープソート ２分探索木と中間順 特殊な方法 基数ソート バケツソート カウンティングソート ソーティングネットワーク 体で体験する人間ソート

②　バブルソート 7 2 5 2 7 3 2 5 2 3 4 2 4 8 1 8 1 6 6 1 7 5 3 4 3 4 8 2 6 8 2 2 6 1 7 5 4 3 8 8 6 3 6 3 2 1 7 5 8 4 8 6 4 4 4 6 3 2 1 ⇒ 比較回数は　n(n－１)/2回

③ 挿入ソート 比較回数は 最悪の場合 n(n－１)/2回 うまくいった場合 n－1回 2 2 7 7 7 5 3 4 1 8 6 2 7 ③　挿入ソート 2 2 7 7 7 5 3 4 1 8 6 2 7 5 5 5 5 7 3 4 1 8 6 2 3 3 5 5 3 7 3 7 3 4 1 8 6 2 3 5 4 4 4 7 5 4 4 7 1 8 6 比較回数は 最悪の場合　n(n－１)/2回 　　　　　 うまくいった場合 n－1回 ⇒

③ クイックソート 比較回数は 最悪の場合 Ｏ(n2) 回 うまくいった場合 Ｏ(n・log2n) 回 quick(1,8) 8 3 5 1 ③　クイックソート 　quick(1,8) 1 2 3 4 5 6 7 8 8 3 5 1 7 6 2 4 4 　quick(1,3) quick(5,8) 3 1 2 2 4 8 5 7 6 6 　quick(7,8) 1 2 3 5 6 8 7 7 7 8 比較回数は 最悪の場合　Ｏ(n2) 回 　　　　　 うまくいった場合 Ｏ(n・log2n) 回

④　マージソート 　MS(1,8) 1 2 3 4 5 6 7 8 8 3 5 1 7 6 2 4 　MS(1,4) MS(5,8) 8 3 5 1 7 6 2 4 MS(1,2) MS(3,4) MS(5,6) MS(7,8) 8 3 5 1 5 6 2 4 MS(1,1) MS(2,2) ・・・ MS(7,7) MS(8,8) 8 3 5 1 5 6 2 4

マージソート （つづき） 比較回数は 最悪の場合 Ｏ(n・log2n) 回 うまくいった場合 Ｏ(n・log2n) 回 1 2 3 4 5 マージソート　（つづき） 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 8 2 4 5 6 3 8 1 5 5 6 2 4 8 3 5 1 5 6 2 4 比較回数は 最悪の場合　Ｏ(n・log2n) 回 　　　　　 うまくいった場合 Ｏ(n・log2n) 回

ソーティングネットワーク

(0) 用意！

(1a)　比較

(1b) 移動

(2a) 比較

(2b) 移動

(3a) 比較

(3b) 移動

(4a) 比較

(4b) 移動

(5a) 比較

(5b) 移動

ステップ数は？　比較総回数は？ ｎ ｎ－１

富士通キッズイベント２０１０（http://jp. fujitsu. com/about/kids/events/20100731/ 富士通キッズイベント２０１０（http://jp.fujitsu.com/about/kids/events/20100731/?kidsevent=2010_11）の教材を借用しましした

まとめ 日常のあらゆるところに数学がある！ 日常生活に役立つ数学 日常生活とは無縁だけれど科学の進歩に欠かせない数学もある 　日常のあらゆるところに数学がある！ 日常生活に役立つ数学 日常生活とは無縁だけれど科学の進歩に欠かせない数学もある 真理を追い求める、役立たない数学があってもいい 大学で学ぶ数学は高校までの数学とは違うところも多い 基礎的なことは（高校で）ちゃんと学んでおこう

模擬授業への参加 ありがとうございました！ 少しは数学への興味を増してくれたなら 嬉しいです！