Download presentation
Presentation is loading. Please wait.
1
早稲田大学オープンキャンパス2014 日常を数学する ~知らず知らずに使っている数学~
早稲田大学オープンキャンパス2014 日常を数学する ~知らず知らずに使っている数学~ 守屋 悦朗 早稲田大学 教育学部 数学科 皆さん、こんにちは! 早稲田大学オープンキャンパスにようこそ! 今日は、教育学部数学科の模擬授業にお出でいただき、ありがとうございます。今日は、「日常を数学する」というタイトルで話をしたいと思います。 皆さんは数学が好きですか? 数学科の模擬授業に来たのですから、勿論好きですよね? だから、学校では数学を一生懸命勉強していると思います。でも、そういう学校で習った数学を普段の生活の中で使っていますか? 皆さんの身の回りで使われている数学を思い浮かべてみてください。
2
学校で学んだ数学を日常生活の中で 使ったことがありますか? どんなところでどんな数学を 使っているか考えてみましょう。 もしかしたら、
「微分積分や対数や数列や三角関数や数学的帰納法 といった数学を日常生活の中で使うことなんてない」 と思っていませんでしたか? いいえ、そんなことはありません! どんなところでどんな数学を 使っているか考えてみましょう。
3
日常の中の数学(中学~高校で学ぶこと) ねずみ講、幸福の手紙、複利計算 → 等比数列、等比級数
ねずみ講、幸福の手紙、複利計算 → 等比数列、等比級数 名刺やA4用紙の縦横比(A4用紙は折っても折っても縦横比が変わらない) → √2,黄金比、フィボナッチ数列 音の高低を表すデシベル、地震の強さを表すマグニチュード → 対数 気温と桜の開花日、距離と速度とかかった時間、投げ上げたボールの描く軌跡、人工衛星の軌道 → 関数 時計、コンピュータ → 12進数、60進数、2進数 (8進数、16進数) 木の高さを測る → 三角関数 宝くじ、賭け → 確率 1+3=4, 1+3+5=9, =16,・・・,1+3+・・・(2n-1)=? → 数学的帰納法 円の面積、球の体積 → 積分 男生徒と女生徒の人数・メガネを掛けている生徒の数・メガネを掛けていない男生徒の数からメガネをしている女生徒の人数を知る → 集合 「AならばBである」ことと「BでないならばAでもない」こととは 同じこと → 命題と論理 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE(単位:J(ジュール))、マグニチュードをMとすると log_{10}E = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧)
4
集合を使う 1~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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) 2でも3でも割り切れるもの 6, 12, 18, …, 9996 10000÷6=1666 個
5
集合を使う 1~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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧)
6
集合を使う 1~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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) 5で割り切れるもの 5, 10, 15, …, 10000 2000 個
7
集合を使う 1~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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) 5で割り切れるもの 5, 10, 15, …, 10000 2000 個
8
集合を使う 1~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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) 5で割り切れるもの 5, 10, 15, …, 10000 2000 個
9
集合を使う 1~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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) 2000 – 1666 – 1000 – = 7334
10
A4用紙やB4用紙のサイズ 何度折っても縦横の比が変わらない
A4用紙やB4用紙のサイズ 何度折っても縦横の比が変わらない ここ(真ん中)で折る 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE(単位:J(ジュール))、マグニチュードをMとすると log_{10}E = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧)
11
A4用紙やB4用紙のサイズ √2 (2の平方根) a : 2b a : 2b = b : a b ∴ a2 = 2b2 真ん中で折る
A4用紙やB4用紙のサイズ √2 (2の平方根) a : 2b a : 2b = b : a b ∴ a2 = 2b2 真ん中で折る 比 x = a/b は x2 = 2 を満たす b : a b ∴ x = √ 2 つまり、縦と横の比は 1 : ・・・ 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE(単位:J(ジュール))、マグニチュードをMとすると log_{10}E = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) a
12
A版用紙のサイズ 19世紀末、ドイツの物理学者オズワルドによって提案された。
面積が1m2の「縦横比が 1 :√2の長方形」を A0 とする。 √2a A0 の縦横の長さ a×√2 a = 100×100 (cm2) ∴ a = 100 / √2 = ・・・ (cm) √2a = ・・・ (cm) √2a a a A mm ×1189mm A0 を半分に折ると A mm × 841mm A1 を半分に折ると A mm × 594mm A2 を半分に折ると A mm × 420mm A3 を半分に折ると A mm × 297mm A4 を半分に折ると A mm × 210mm 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE(単位:J(ジュール))、マグニチュードをMとすると log_{10}E = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧)
13
B版用紙のサイズ 日本独自の規格 面積が1.5m2 の「縦横比が 1 :√2の長方形」を B0 とする。 B0 の縦横の長さ √2b
b×√2 b = 1.5×100×100 (cm2) ∴ b ≒ (cm) √2b ≒ (cm) √2b b b B mm ×1456mm B0 を半分に折ると B mm ×1030mm B1 を半分に折ると B mm ×728mm B2 を半分に折ると B mm ×515mm B3 を半分に折ると B mm ×364mm B4 を半分に折ると B mm ×257mm 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE(単位:J(ジュール))、マグニチュードをMとすると log_{10}E = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧)
14
黄金比 縦横の均整がとれた長方形の縦と横の比は?
黄金比 縦横の均整がとれた長方形の縦と横の比は? 名刺のサイズ 横 : 縦 = 55 : 91 = 1 : ・・・ ≒ 1 : 1.618・・・ = 1 : 1+√5 91mm 黄金比とは、線分を a, b の長さで2つに分割するときに、a : b = b : (a + b) が成り立つように分割したときの比 a : b のこと。 地震が発するエネルギーの大きさをE(単位:J(ジュール))、マグニチュードをMとすると log_{10}E = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) 黄金比 黄金のように美しい比率!? 55mm
15
黄金比とフィボナッチ数列(その1) 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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧)
16
黄金比とフィボナッチ数列(その2) (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 = M という関係がある。マグニチュードが1増えるとエネルギーは10^1.5=31.62倍になる。 dBは、基準値と比較して何倍、或いは何分の1であるかという事を対数を用いて表すための単位。音量(dB)=20×log(対象の音圧/基準音圧) fn =
17
日常の中の数学(学校で学ばないこと) 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには?
18
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには?
19
高校ではやらない数学 ① グラフ 5 辺 2 7 頂点 3 重み
20
ケー二ヒスベルクの橋 A A B B C C D D 図はWikipedia(
21
一筆書きできるか? あ ん 川 木 田 中 A B C R W
22
すべての辺を1回だけ通って戻ってこれるか?
可能! c a b d e g f i h j m n k
23
自明でない連結な(多辺)グラフ G が一筆書き
定理(L.オイラー,1736) 自明でない連結な(多辺)グラフ G が一筆書き できるための必要十分条件は、 G が奇頂点 (接続している辺の本数が奇数の頂点のこと)を もたない(=0個持つ)か、またはちょうど2個 持つことである。 0個のときには、書き始めた所に戻ってくる ことができる。
24
では、辺に向きがあるとき、 すべての辺を1回だけ通って戻ってこれるか?
a e b d c
25
では、辺に向きがあるとき、 すべての辺を1回だけ通って戻ってこれるか?
a e b d この例の場合、 戻ってはこれないが 一筆書きは可能! c
26
ちょっと複雑になると? c a b d e g f 不可能! i h なぜ? j m n k
27
オイラーの定理(その2) 自明でない連結な(多辺)有向グラフGが一筆書きできるための必要十分条件は、Gのどの頂点も入次数(入ってくる辺の本数)と出次数(出ていく辺の本数)が等しいか、 または、1つの頂点は出次数が入次数より1大きく、 もう1つの頂点は入次数が出次数より1大きく、 それ以外の頂点は入次数と出次数が等しいことである。 前者のときには、書き始めた所に戻って来ることができる。
28
では、 すべての頂点を1回だけ通って戻ってこれるか?
c a b d e g f i h j m n k
29
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
30
頂点 ~ は生徒の家で、使える道が辺のとき、 すべての家を1回だけ訪問して戻ってこれるか?
頂点 ~ は生徒の家で、使える道が辺のとき、 すべての家を1回だけ訪問して戻ってこれるか? a n c a b d e g f i h 不可能! なぜ? j m n k
31
与えられた有向・無向グラフのすべての頂点を丁度
P≠NP予想(ハミルトングラフ問題) 与えられた有向・無向グラフのすべての頂点を丁度 1回ずつ通って出発点に戻って来る経路を効率よく 求めるアルゴリズム(方法)は存在しないだろう。 ハミルトングラフ問題をはじめとする類似の問題を NP完全問題という。 ナップサックに効率よく詰める方法 ジグソーパズル 時間割作成 グラフ上の最も遠い2点間の距離を求める そのほかの何万何千という問題!
32
定理(NP完全問題、1972) 西暦2000年のミレニアム問題
もし、NP完全問題のどれか1つを解く効率良いアルゴリズムが見つかれば、すべてのNP完全問題を効率よく解くことができる。 西暦2000年のミレニアム問題 米国 クレイ数学研究所が提唱 現在未解決の数学の重要問題7つ そのうちの1つがNP≠P予想 解決すれば100万ドル(約10億円)
33
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
34
NP完全問題よりも難しい問題は? 解くアルゴリズムが無い問題さえある! 将棋、囲碁などのゲームの先手必勝法に関する問題
多くはEXP完全な問題 数独はNP完全な問題 尻取りゲームはPSPACE完全な問題 いくらでも難しい問題が存在する! 解くアルゴリズムが無い問題さえある! 単語のペア を並べ替えて同じ文章を作れるか? (ab, a), (bc, bb), …, (aa, caa) → (ab)(bc)(aa) = (a)(bb)(caa) 不定方程式が整数解を持つか? 3xy2+5x3yz-7y2z2 = 24
35
日常の中の数学 日常生活で実際に役立っているものは? ナビゲーション、駅探索 工事費をできるだけ安くするには? 一番大きいものを見つける
小さい方からn番目のものを見つける 小さい順・大きい順に並べ替える
36
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
37
どの経路を通れば一番近いか? から へ行きたい
どの経路を通れば一番近いか? から へ行きたい 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
38
どの経路を通れば一番近いか? から へ行ってみよう
どの経路を通れば一番近いか? から へ行ってみよう 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)
39
どの経路を通れば一番近いか? から へ行く最短経路
どの経路を通れば一番近いか? から へ行く最短経路 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
40
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
41
コンビニへ効率よく商品を配送するには? 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 配送車の 種別・台数・積載容量 運転手の手配、など
42
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
43
工事費を最も安くするには? 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
44
工事費を最も安くするには? 完了! 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
45
工事費を最も安くするには? 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
46
工事費を最も安くするには? 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
47
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
48
一番大きいものを見つけるには? ルール: 2つのものの大小比較しかできない。
n個のデータ a1, a2, ・・・, an の中から、2個ずつの大小比較だけで最大のものを見つける。 これらのデータは、どの2つも大小関係がある(全順序)。 これらのデータは最初はでたらめな大きさの順に、ある場所に置かれていて、どのデータも同じ一定時間で「取り出すこと」「比較すること」「別の場所に移すこと」ができる。 作業用に別の場所を使ってもよい。
49
あなたの方法を考えてください 計算の方法(手順)のことをアルゴリズムといいます
あなたの方法を考えてください 計算の方法(手順)のことをアルゴリズムといいます
50
順 次 探 索 比較回数は n-1 回 逐次処理 a1 a2 a3 ・・・ ai ・・・ an amax
順 次 探 索 a1 a2 a3 ・・・ ai ・・・ an amax 1.はじめに に a1 を入れておく。 2. と a2, a3, ・・・, an を順次比べ、大きい方を に残す。 amax amax amax 比較回数は n-1 回 逐次処理
51
ト ー ナ メ ン ト 法 比較回数は n-1回 並列処理が可能 a1 a2 a3 a4 ・・・ an-1 an a2 a3 am an
・・・ an-1 an a2 a3 am an a3 am am 比較回数は n-1回 1.2つずつ比べ、大きい方を下へ。 2.最大値は am 並列処理が可能
52
再帰的考え方 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
53
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 大きい順に並び替えるには? ✓
54
小さい方からn番目のものを見つけるには 比較は うまくいけば log2n 回 8個の中の7番目のものをみつけたい 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) 1.見つけたい中から1つ を任意に選ぶ。 2.1つずつ と比べて、それより小さいグループと大きいグループに分ける。 3.どちらかのグループの中の何番目かを求めればよい。
55
日常の中の数学(学校で学ばないこと) ✓ 一筆書きする方法は? 無駄なく家庭訪問できるか? 将棋や碁はなぜ難しい?
どの経路を通れば一番近いか・安いか? コンビニへ効率よく商品を配送するには? 工事費をできるだけ安くするには? 一番大きいものを見つけるには? 小さい方からn番目のものを見つけるには? 小さい順に並び替えるには? ✓
56
小さい順に並び替えるには ソート(sort, sorting)、並べ替え、整列化 まず、あなた独自の方法を考えてみよう
逐次探索と同様な考え方? トーナメント法と同じような考え方ができる? 再帰的な方法は? もっと奇抜なアイデアがある? あなたの方法では、何回比較を行なうか?
57
① 選択ソート おそらく、かなり多くの人が考えたやり方
① 選択ソート おそらく、かなり多くの人が考えたやり方 53 24 78 19 43 61 36
58
① 選択ソート 53 53 24 78 19 43 61 36 ここに一番小さいもの(が入っていた場所)を入れる
59
① 選択ソート 53 24 24 78 19 43 61 36 53 ここに一番小さいもの(が入っていた場所)を入れる
60
① 選択ソート 53 24 78 19 19 43 61 36 24 ここに一番小さいもの(が入っていた場所)を入れる
61
① 選択ソート 53 24 78 19 43 61 36 19 19 が最小とわかった ここに一番小さいもの(が入っていた場所)を入れる
62
① 選択ソート 53 24 78 19 43 61 36 19 ここに一番小さいもの(が入っていた場所)を入れる
63
① 選択ソート 19 24 24 78 53 43 61 36 24 が最小とわかった ここに一番小さいもの(が入っていた場所)を入れる
64
① 選択ソート 19 24 24 78 53 43 61 36 24 ここに一番小さいもの(が入っていた場所)を入れる
65
① 選択ソート 19 24 78 78 53 43 61 36 ここに一番小さいもの(が入っていた場所)を入れる
66
① 選択ソート 19 24 78 53 53 43 43 61 36 78 ここに一番小さいもの(が入っていた場所)を入れる
67
① 選択ソート 19 24 78 53 43 43 61 36 53 ここに一番小さいもの(が入っていた場所)を入れる
68
① 選択ソート 19 24 78 53 43 61 36 36 43 36 が最小とわかった ここに一番小さいもの(が入っていた場所)を入れる
69
① 選択ソート 19 24 36 78 53 43 61 36 36 ここに一番小さいもの(が入っていた場所)を入れる
70
① 選択ソート 19 24 36 53 53 43 61 78 ここに一番小さいもの(が入っていた場所)を入れる
71
① 選択ソート 19 24 36 53 43 43 61 78 53 ここに一番小さいもの(が入っていた場所)を入れる
72
① 選択ソート 19 24 36 53 43 61 78 43 43 が最小とわかった ここに一番小さいもの(が入っていた場所)を入れる
73
① 選択ソート 19 24 36 53 43 61 78 43 ここに一番小さいもの(が入っていた場所)を入れる
74
① 選択ソート 19 24 36 43 53 61 78 ここに一番小さいもの(が入っていた場所)を入れる
75
① 選択ソート 19 24 36 43 53 53 61 78 53 が最小とわかった ここに一番小さいもの(が入っていた場所)を入れる
76
① 選択ソート 19 24 36 43 53 61 78 53 ここに一番小さいもの(が入っていた場所)を入れる
77
① 選択ソート 19 24 36 43 53 61 61 78 ここに一番小さいもの(が入っていた場所)を入れる
78
① 選択ソート 19 24 36 43 53 61 78 61 61 が最小とわかった ここに一番小さいもの(が入っていた場所)を入れる
79
① 選択ソート 19 24 36 43 53 61 78 61 ここに一番小さいもの(が入っていた場所)を入れる
80
① 選択ソート 19 24 34 43 53 61 78 ここに一番小さいもの(が入っていた場所)を入れる
81
① 選択ソート 19 24 34 43 53 61 78 ここに一番小さいもの(が入っていた場所)を入れる
82
比較回数は 最初 n-1 回の比較 2回目 n-2 回の比較 ・・・ n-1 回目 1回の比較 合計 n(n-1)/2 回の比較が必ず必要
83
その他の方法 体で体験する人間ソート 挿入ソート バブルソート クイックソート マージソート シェルソート ヒープソート 2分探索木と中間順
特殊な方法 基数ソート バケツソート カウンティングソート ソーティングネットワーク 体で体験する人間ソート
84
② バブルソート 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-1)/2回
85
③ 挿入ソート 比較回数は 最悪の場合 n(n-1)/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-1)/2回 うまくいった場合 n-1回 ⇒
86
③ クイックソート 比較回数は 最悪の場合 O(n2) 回 うまくいった場合 O(n・log2n) 回 quick(1,8) 8 3 5 1
③ クイックソート quick(1,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 比較回数は 最悪の場合 O(n2) 回 うまくいった場合 O(n・log2n) 回
87
④ マージソート MS(1,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
88
マージソート (つづき) 比較回数は 最悪の場合 O(n・log2n) 回 うまくいった場合 O(n・log2n) 回 1 2 3 4 5
マージソート (つづき) 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 比較回数は 最悪の場合 O(n・log2n) 回 うまくいった場合 O(n・log2n) 回
89
ソーティングネットワーク
90
(0) 用意!
91
(1a) 比較
92
(1b) 移動
93
(2a) 比較
94
(2b) 移動
95
(3a) 比較
96
(3b) 移動
97
(4a) 比較
98
(4b) 移動
99
(5a) 比較
100
(5b) 移動
101
ステップ数は? 比較総回数は? n n-1
102
富士通キッズイベント2010(http://jp. fujitsu. com/about/kids/events/20100731/
富士通キッズイベント2010(
103
まとめ 日常のあらゆるところに数学がある! 日常生活に役立つ数学 日常生活とは無縁だけれど科学の進歩に欠かせない数学もある
日常のあらゆるところに数学がある! 日常生活に役立つ数学 日常生活とは無縁だけれど科学の進歩に欠かせない数学もある 真理を追い求める、役立たない数学があってもいい 大学で学ぶ数学は高校までの数学とは違うところも多い 基礎的なことは(高校で)ちゃんと学んでおこう
104
模擬授業への参加 ありがとうございました! 少しは数学への興味を増してくれたなら 嬉しいです!
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.