アルゴリズムってなんだろう？

CoderDojo神山 本橋大輔

今日できるようになること

アルゴリズムを見つけられるようになる

アルゴリズムで考えられるようになる

アルゴリズムで迷路を作れるようになる

アルゴリズムで迷路の近道を見つけられる

（おまけ）アルゴリズムで遊んでみる

アルゴリズムってなんだろう？

ミニゲーム

Big or Small

https://scratch.mit.edu/projects/754751496/

二分探索アルゴリズム

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10

『5かな？』
『もっと大きいよ』
『6～10のどれかになるな』
『8かな？』
『もっと小さいよ』
『小さいなら、6か7のどちらかだ！』
『7だ！』
『正解！』

ブルートフォース（ちからまかせ）アルゴリズム

• 1～10の数字を探したいとき
  • 1？
  • 2？
  • 3？
  • 4？
  • 5？
  • 6！ 正解！

ブルート

Popeye (1933). © King Features Syndicate, Inc. / Fleischer Studios.

「ちからまかせ」はコンピューターの得意技

数字をひとつずつ変えて、正解かどうか調べる、を繰り返す

    1 ⇨ 2 ⇨ 3 ⇨ 4 ⇨ ....

アルゴリズムの力試し

1から10まで足したらいくつ？

    1 + 2 + 3 + ... + 10 = ?

アルゴリズムの力試し(2)

1から100まで足したら？

    1 + 2 + 3 + ... + 100 = ?

アルゴリズムの力試し(3)

1から1000まで足したら？

    1 + 2 + 3 + ... + 1000 = ?

こんな計算やってられない

• 1から100まで足す
  • 100回の足し算
• 1から1000まで足す
  • 1000回の足し算
• 1から10000まで足す
  • 10000回の足し算
• 1から100000まで足す
  • 100000回の足し算

「アルゴリズム」で計算すると早い

• 1から100まで足す
  • (1 + 100) x 50 = 5050

1回の足し算と、1回の掛け算で計算できる

「アルゴリズム」で計算すると早い

• 1から100まで足す

  • (1 + 100) x 50 = 5050

• 1から100000まで足す

  • (1 + 100,000) x 50,000 = 5,000,050,000

アルゴリズム

ガウスの計算法

• 1から100まで足す
  • (1 + 100) x 50 = 5050
• 1から10000まで足す
  • (1 + 10000) x 5000 = 50,005,000
    

1回の足し算と、1回の掛け算だけ

アルゴリズムの面白いところ

(1 + 10000) x 5000 = 50,005,000

１つの式で書いてしまえる

ここまでに登場したアルゴリズム

• 二分探索にぶんたんさくアルゴリズム
• 総当りそうあたり（ブルートフォース）アルゴリズム
• ガウスの計算法

おまけのアルゴリズム

ソロバンのお話

1946年

計算機と互角だったそろばん

• 終戦直後、そろばん名人と機械式計算機の対決(1946)
  ⇨ 「名人」の勝利

練習なしに計算できる時代に突入

3月20日　電卓の日｜きょうの蔵出しNHK｜時代｜NHKアーカイブス
https://www.nhk.or.jp/archives/jidai/special/today/0320/

ソロバンを超える高速な計算能力

• １秒間に 10回 くらい
  • そろばん
• １秒間に 7000億回 の計算
  • パソコンやスマホ
• １秒間に 120京回 の計算
  • 世界一のスーパーコンピューター(Frontier)

そろばん「フラッシュ暗算」で世界記録　3桁の数字15個の和を1.60秒で計算 – 早稲田ウィークリー
https://www.waseda.jp/inst/weekly/attention/2016/06/21/8369/

いまからこんなアルゴリズムで遊びます

• 棒倒しぼうたおし迷路構築法めいろこうちくほう
  • 立てた棒を倒しながら迷路の壁を作るアルゴリズム
• 幅優先探索法はばゆうせんたんさくほう
  • 「広さ」を優先して調べるアルゴリズム

アルゴリズムで迷路を作ろう

• 迷路を作っていきます
• 方眼紙をご用意ください

方眼紙に枠を引きます

まずはタテ11マス、ヨコ11マスでやってみましょう

１，２，３，４を書く

• 左下の塗りつぶしマス（柱）の周囲に１～４を書いてください

サイコロをふる

• 1～4が出たら、数のマスをぬります
• 5, 6が出たらもう一度

ぬったマスは迷路の「カベ」です

１～４を書かずにサイコロをふる

• 左下からふたつめの柱の周囲に１～４の数字があると思ってください

サイコロの出た数字のマスをぬる

• 例えばサイコロの３がでたら、3のマスをぬります
• ぬったマスは迷路の「カベ」です
• くりかえすと迷路ができます

ぜんぶの柱から壁を作ろう

次の段はちがうパターン

• 二段目は、三方向にカベを作る
  • 1か2 ⇨ ひだり
  • 3か4 ⇨ うえ
  • 5か6 ⇨ みぎ

ぜんぶの柱から壁をつくれたら

スタートとゴールを書き込んで

自分だけの迷路の出来上がり！

どんな迷路ができましたか？

となりの迷路とくらべよう

もっと大きな迷路も作れそう？

なぞとき編

アルゴリズムで近道を見つけよう

アルゴリズムで近道を見つけよう

• サイコロは使いません
• こんな計算を使います
  • 1 + 1 = ?
  • 2 + 1 = ?
  • 3 + 1 = ?

迷路を作るのも解くのも小さな計算でした

• 迷路をつくる

  • サイコロを振って壁を作る
  • 次の柱に移動する
  • ※くりかえし

• 迷路をとく

  • 足元の数字に1を足したものを四方向のマスに書き込む
  • 次のマスに進む
  • ※くりかえし

コンピューターは繰り返しが得意

• １秒間に 100京回 の計算ができる世界一のスーパーコンピューター

• １秒間に 7000億回 の計算ができる僕のパソコン

• １秒間に....人間は

  • ソロバンだと、5回 くらい行けるかな？

• 一, 十, 百, 千, 万, 億, 兆, 京, 垓 ...

小さな計算をたくさん繰り返すことがとっても得意

コンピューターにやらせてみると…

https://motohasystem.github.io/p5_easy_maze/

おまけ1

AIとゲームを作ってみよう

https://zarigani.click/

おまけ2

https://www.tinkercad.com/codeblocks/edit?doc=7K1rVtzmFda

おまけ3

2023年 (OpenAI)

2024年 (OpenAI)

2025年 (OpenAI)

2025年 (Google)

AIと作ったイラストでTシャツも作れます