情報科学入門「コンピュータにどう考えさせるか？」
九州大学 システム情報科学研究院
教授 稲永 俊介

九州大学 理学部 物理学科

1

理学部
物理学
物理学コース化学

地球惑星生物学

数学

情報理学コース

数理情報講座知能科学講座
２年生前期にコースを選択
計算科学講座

理学部オープンキャンパス 2024

九州大学 理学部 物理学科

2

物理学
物理学コース

情報理学コース
数理情報アルゴリズム，暗号理論など

知能科学

人工知能，計算学習理論など

計算科学

計算機シミュレーションなど

理学部オープンキャンパス 2024

アルゴリズムって？
 コンピュータは、四則演算（＋，－，×，÷）などの単純な計算を高速かつ正確に行える

 しかし、複雑な問題を解くための「手順」をコンピュータ自身が編み出すことはできない

 単純な計算を組み合わせて、より複雑な問題を解くための手順のことをアルゴリズムという理学部オープンキャンパス 20243

アルゴリズムの例（その１）迷路
問題：迷路を脱出せよ！
コンピュータは前後左右に動くことはできるが、いつどの方向に行けばいいか知らない
スタート

ゴール
理学部オープンキャンパス 20244

アルゴリズムの例（その１）迷路
問題：迷路を脱出せよ！
行き止まりになったらどうしたらいいんですか？
スタート

ゴール
理学部オープンキャンパス 20245

アルゴリズムの例（その１）迷路
問題：迷路を脱出せよ！
壁に右手をついたまま進みなさい（右手法）
スタート

ゴール
理学部オープンキャンパス 20246

アルゴリズムの例（その１）迷路
問題：迷路を脱出せよ！

いきまーす！

スタート

ゴール
理学部オープンキャンパス 2024

なぜ右手法で迷路を抜けられるのか？
•

迷路を以下の３つのパーツに分割して考える．

入口

出口
理学部オープンキャンパス 20248

なぜ右手法で迷路を抜けられるのか？
•

迷路を以下の３つのパーツに分割して考える．
(1) 入口から見て右側の壁に繋がっている部分．
(2) 入口から見て左側の壁に繋がっている部分．
(3) その他の部分．
入口
(1)

(2)

(3)

出口
理学部オープンキャンパス 2024

9

なぜ右手法で迷路を抜けられるのか？
•(2)(3) は無視し，(1) のみに着目する．
(1) の壁沿いに歩けば，出口に通じるのは明らか．
入口(1)

(2)

(3)

出口

右手法では「最短経路」はわからない迷路をグラフで表すことで「最短経路」は高速に求まる

理学部オープンキャンパス 202410

アルゴリズムの研究


問題を解く手順を与えれば、コンピュータは人間よりもずっと高速かつ正確に問題を解くことができる

 ただし、問題を解く手順（アルゴリズム）を考案するのは、人間の役割である

 備考：アルゴリズムをコンピュータが理解できるように書いたものがプログラム

理学部オープンキャンパス 202411

アルゴリズムの「良さ」
 同じ問題でも、それを解くためのアルゴリズムは何種類もありえる

解き方は一通りとは限らない 「良い」アルゴリズムの条件
1.

正しく問題を解ける

2.

高速に問題を解ける

理学部オープンキャンパス 202412

アルゴリズムの例（その２）偽コイン発見
問題：９つのコインがあり、その中に一つだけ偽物のコインがある。偽物は本物より重い。
天秤を使って、偽物を発見せよ。
123456789天秤を何回使えば偽物を発見できるだろうか？
出前講義＠福岡高校

13

アルゴリズムの例（その２）偽コイン発見
適当に選んだ１個と残りの８個を順番に比べれば、最悪の場合でも８回天秤を使えば偽物が見つかる

2134より少ない回数でできるだろうか…?

5678

１個づつ天秤に乗せていく
理学部オープンキャンパス 202414

アルゴリズムの例（その２）偽コイン発見

実は、たったの ２回 で発見できる！

1234

56789

出前講義＠福岡高校

15

考え方
コインが３個の場合を考える

123

出前講義＠福岡高校

16

考え方
コインを２個選び、天秤にかける3

1

a. 1 のほうに傾けば、1 が偽物
b. 2 のほうに傾けば、2 が偽物

2c. 釣り合えば、3 が偽物
出前講義＠福岡高校

17

考え方
コインが３個のときは、天秤を １回 使えば偽物を発見できる

3

1a. 1 のほうに傾けば、1 が偽物
b. 2 のほうに傾けば、2 が偽物

2c. 釣り合えば、3 が偽物
出前講義＠福岡高校

18

考え方
コインが９個のときは、コインが３個のときのやり方を応用する

123456789出前講義＠福岡高校

19

考え方
コインを３つのグループに分ける

1231456278出前講義＠福岡高校

9320

考え方
グループを２つ選び、天秤にかける7

1231485936
2

a. 1 のほうに傾いたら、1 の中に偽物がある
b. 2 のほうに傾いたら、2 の中に偽物がある
c. 1 と 2 が釣り合えば、3 の中に偽物がある
出前講義＠福岡高校

21

考え方
偽物が入ったグループを見つけるのに１回
そのグループから偽物を見つけるのに１回
よって、コインが９個のときの天秤の使用回数は ２回

123467895

出前講義＠福岡高校

22

コインが 27 個のとき
３グループに分け、２つを天秤にかける112310 11 12

19 20 2145613 14 1522 23 24

78916 17 18
225 26 27
3

天秤を１回使って、偽物が入ったグループを発見
あとは、コインが９個の場合と同様の手順⇒ 天秤を ３回 使用すれば偽物を発見できる
理学部オープンキャンパス 202423

天秤の使用回数 (コインの個数 n = 3k のとき)
コインの個数天秤の使用回数

3
92781

1
2
34…

…

nlog3 n

天秤を１回使うと偽物の候補の数が3分の１になる．

n ≠ 3k のときはどーすんの？？
理学部オープンキャンパス 202424

コインが５個のとき

12345

出前講義＠福岡高校

25

コインが５個のときコインを２個、２個、１個の３つのグループに分ける

12134253出前講義＠福岡高校

26

コインが５個のときコインが２個のグループを天秤にかける

53121342

a. 1 のほうに傾いたら、1 の中に偽物がある
b. 2 のほうに傾いたら、2 の中に偽物がある
c. 1 と 2 が釣り合えば、3 の中の 5 が偽物
出前講義＠福岡高校

27

コインが５個のとき
場合 a のときは，1 と 2 を比べる
場合 b のときは，3 と 4 を比べる

12
場合 a

34
場合 b出前講義＠福岡高校

28

コインが５個のとき
場合 a, b のとき，天秤の使用回数は２回
場合 c のとき，天秤の使用回数は１回
よって、コインが５個のときの天秤の使用回数は高々 ２回

12345出前講義＠福岡高校

29

log3 n vs n - 1600

log3 n = n を 3 で繰り返し割って1 以下になる回数

天秤の使用回数

500
400

log3nnlog_3n-1n-1300
200

log3 n は最適解

10001100200300

コインの個数

400500 log3 n より少ない天秤の使用回数
で偽物を見つけることはできない

理学部オープンキャンパス 2024

30

31

アルゴリズムの例（その３）最大公約数問題
問題
入力：正整数 x と y
出力：x と y の最大公約数 gcd(x, y)• gcd : greatest common divisor

例• gcd(16, 12) = 4• gcd(321, 99) = 3• gcd(47, 32) = 1

32

最大公約数問題を解くアルゴリズム
1. しらみつぶし法• 解の候補を大きいほうから順に試していく．
• 膨大な計算時間がかかる．

2. ユークリッドの互除法

数学A 「整数」
共通テスト頻出問題• 明示的に記述された最古のアルゴリズム (BC300 年頃)．
• やり方は高校で学ぶが，計算時間は言及されていない．

3. 素因数分解に基づく手法• 中学校で学ぶ．

• 簡単と思われがちだが，実は，現在知られているアルゴリズムでは膨大な計算時間がかかる．

33

アルゴリズムの例（その３）最大公約数問題
問題
入力：正整数 x と y
出力：x と y の最大公約数 gcd(x, y)• gcd : greatest common divisor

例• gcd(16, 12) = 4• gcd(321, 99) = 3• gcd(47, 32) = 1

34

しらみつぶし法 naive_gcd
start

x mod k= 整数 x を整数 k で割った余り

k ← min(x, y) とする
最も大きい解の候補から順に試していく

r1 ← x mod k,
r2 ← y mod k とする
r1 = 0 かつ
r2 = 0 か？
nok ← k-1 とする

yes

gcd(x, y) = k を出力
finish35

naive_gcd の実行例

x mod k= 整数 x を整数 k で割った余り

start

x = 6，y = 9 のとき

k ← min(6, 9) = 6 とする
r1 ← 6 mod 6 = 0,r2 ← 9 mod 6 = 3 とする
r1 = 0 かつ
r2 = 0 か？
nok ← k-1 とする

yes

gcd(x, y) = k を出力
finish36

naive_gcd の実行例

x mod k= 整数 x を整数 k で割った余り

start

x = 6，y = 9 のとき

k ← min(6, 9) = 6 とする
r1 ← 6 mod 5 = 1,r2 ← 9 mod 5 = 4 とする
r1 = 0 かつ
r2 = 0 か？
nok ← k-1 = 5 とする

yes

gcd(x, y) = k を出力
finish37

naive_gcd の実行例

x mod k= 整数 x を整数 k で割った余り

start

x = 6，y = 9 のとき

k ← min(6, 9) = 6 とする
r1 ← 6 mod 4 = 2,r2 ← 9 mod 4 = 1 とする
r1 = 0 かつ
r2 = 0 か？
nok ← k-1 = 4 とする

yes

gcd(x, y) = k を出力
finish38

naive_gcd の実行例

x mod k= 整数 x を整数 k で割った余り

start

x = 6，y = 9 のとき

k ← min(6, 9) = 6 とする
r1 ← 6 mod 3 = 0,r2 ← 9 mod 3 = 0 とするr1 = 0 かつ
r2 = 0 か？
nok ← k-1 = 3 とする

yesgcd(6, 9) = 3 を出力
finish39

計算ステップ数• 計算ステップ数とは，アルゴリズムが終了するまでに行われる基本演算の回数である．

• 計算ステップ数が少ないほど，アルゴリズムの実行時間は短くなる．

• 最大公約数問題では 剰余 (mod) を基本演算と考える．

40

naive_gcd の計算時間見積もり• n = min(x, y) とする。

naïve_gcd は最悪時には 2n 回の剰余計算を行う。

 計算ステップ数は高々 2n である。

41

しらみつぶし法 naive_gcd（おさらい）
start

x mod k= 整数 x を整数 k で割った余り

k ← min(x, y) とする
x と y が互いに疎なとき2n 回の剰余計算を行う
ただし n = min(x, y)

r1 ← x mod k,r2 ← y mod k とする
r1 = 0 かつ
r2 = 0 か？
nok ← k-1 とする

yes

gcd(x, y) = k を出力
finish42

naive_gcd の計算時間見積もり• n = min(x, y) とすると，計算ステップ数は高々 2n• 剰余の1回の計算時間• パソコン 1ステップ 10-8 秒• スパコン 1ステップ 10-11 秒
n

パソコン

スパコン

10000

0.2 × 10-3 秒

0.2 × 10-6 秒

100万

0.02 秒

0.2 × 10-4 秒

1億2秒

0.002 秒1兆

5.55 時間

20 秒

1京

6.3 年

55.5 時間

43

naive_gcd の計算時間見積もり• n = min(x, y) とすると，計算ステップ数は高々 2n• 剰余の1回の計算時間• パソコン 1ステップ 10-8 秒• スパコン 1ステップ 10-11 秒
nパソコン

スパコン

10000

0.2 × 10-3 秒

0.2 × 10-6 秒

100万

0.02 秒

0.2 × 10-4 秒

1億2秒

0.002 秒1兆

5.55 時間

20 秒

1京

6.3 年

55.5 時間

1050

莫大

6.3 × 1031 年

10100 (≈ 2332)

莫大

6.3 × 1081 年

遅すぎる

44

高速化への道 ～ユークリッドの互除法• 最大公約数問題を，「なるべく大きな正方形で長方形を埋める問題」に置き換えて考える．

問題
縦の長さ x ，横の長さ y の長方形が与えられた
とき，長方形を敷き詰める最大の正方形 S を求めよ．
x ，y は正整数

45

長方形敷き詰め問題問題
縦の長さ x ，横の長さ y の長方形が与えられた
とき，長方形を敷き詰める最大の正方形 S を求めよ．
x ，y は正整数
gcd(x, y)x• 長方形を埋める正方形の一辺の長さ＝ x と y の公約数y

• そのような最大の正方形 S の一辺の長さ = gcd(x, y)46

例１• 以下の長方形をなるべく大きな正方形に分割せよ．

• ただし定規を使ってはいけない!!

47

例１（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．

• なるべく大きな正方形を作る。

48

例１（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．

• 正方形を入るだけ入れる＝長い辺を短い辺で割る．
• ぴったり割れたら，短い辺の長さが最大公約数．

49

例１（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．

27
9• 正方形を入るだけ入れる＝長い辺を短い辺で割る．
• ぴったり割れたら，短い辺の長さが最大公約数．

50

例２• 以下の長方形をなるべく大きな正方形に分割せよ．

• ただし定規を使ってはいけない!!

51

例２（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．

• なるべく大きな正方形を作る。

52

例２（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．

余った長方形• 正方形を入るだけ入れる＝長い辺を短い辺で割る．
• ぴったり割れないときは，余った長方形の長い辺を短い辺で割る．

53

例２（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．
余った
長方形の短い辺• 正方形を入るだけ入れる＝長い辺を短い辺で割る．
• ぴったり割れたら，短い辺の長さが最大公約数．

54

例２（解答）• 以下の長方形をなるべく大きな正方形に分割せよ．

25

10

5

余った
長方形の短い辺• 正方形を入るだけ入れる＝長い辺を短い辺で割る．
• ぴったり割れたら，短い辺の長さが最大公約数．

55

例３• 長方形の紙をなるべく大きな正方形に分割せよ．

• ただし定規を使ってはいけない!!

56

例３（解答）• 長方形の紙をなるべく大きな正方形に分割せよ．

• ただし，最初に定規で辺の長さを測ってはいけない．

• 長い辺を短い辺で割る．

• ぴったり割れないときは，余った長方形の長い辺を短い辺で割る．

57

例３（解答）• 長方形の紙をなるべく大きな正方形に分割せよ．

• ただし，最初に定規で辺の長さを測ってはいけない．

• 長い辺を短い辺で割る．

• ぴったり割れないときは，余った長方形の長い辺を短い辺で割る．

58

例３（解答）• 長方形の紙をなるべく大きな正方形に分割せよ．

• ただし，最初に定規で辺の長さを測ってはいけない．

• ぴったり割れたら，短い辺の長さが最大公約数．

59

例３（解答）• 長方形の紙をなるべく大きな正方形に分割せよ．

• ただし，最初に定規で辺の長さを測ってはいけない．

25155• ぴったり割れたら，短い辺の長さが最大公約数．

60

賢いアルゴリズム euclid_gcd
x < y とする

startxr ← y mod x とする
r = 0 か？
noy ← x, x ← r とする

yyes

x を出力
finishr61

賢いアルゴリズム euclid_gcdx < y とする

start

yr ← y mod x とする
r = 0 か？
noy ← x, x ← r とする

yes

xx を出力finish62

賢いアルゴリズム euclid_gcd
x < y とする

r=0

start

yr ← y mod x とする
r = 0 か？
noy ← x, x ← r とする

yes

xx を出力finish63

ユークリッドの互除法の計算ステップx < y とする

start

この mod 演算の回数= ユークリッドの互除法の計算ステップ数r ← y mod x とする
r = 0 か？
noy ← x, x ← r とする

yesx を出力
finish64

ユークリッドの互除法の計算ステップ
x = 5, y = 15 のとき
ステップ１： 15 mod 5 = 0

ステップ１

 計算ステップ数 = 1

x = 8, y = 20 のとき
ステップ１： 20 mod 8 = 4
ステップ２： 8 mod 4 = 0ステップ１

 計算ステップ数 = 2ステップ２

65

ユークリッドの互除法の計算ステップ数yy’

xy’’x’rx’’r’• y と x の更新を２回繰り返すと，元の値の半分未満になる．
• y = zx + r とおく．
• y > x より z ≥ 1  y = zx + r ≥ x + r .

𝑦𝑦• y は x で割り切れていないので x > r  y > 2r = 2y’’  > y’’2
• x についても同様．

66

ユークリッドの互除法の計算ステップ数yy’

xy’’x’
rx’’r’• y と x の更新を２回繰り返すと，元の値の半分未満になる．
• x が 1 になったら，x は必ず y を割り切れる．

 x が 1 になるか，その前までに，必ず計算が終わる．

• よって，n = min(x, y) とすると，ユークリッドの互除法の計算ステップ数は高々 2log2 n である．

67

ユークリッドの互除法の計算時間見積もり• ユークリッドの互除法の計算ステップ数 ≈ 2log2 n• 剰余の1回の計算時間• パソコン 1ステップ 10-8秒• スパコン 1ステップ 10-11秒

euclid_gcd はパソコンでも計算が瞬時に終わる！

nnaive_gcd
スパコン

euclid_gcd
パソコン

euclid_gcd
スパコン

1億

0.002 秒

0.56×10-3 秒

0.56×10-6 秒

1兆20 秒0.82×10-3 秒

0.82×10-6 秒

1京

55.5 時間

1.08×10-3 秒

1.08×10-6 秒

1050

6.3×1031 年

3.34×10-3 秒

3.34×10-6 秒

10100 (≈ 2332)

6.3×1081 年

6.66×10-3 秒

6.66×10-6 秒

68

ユークリッドの互除法の正当性•gcd(r, x) を求めることで，なぜ gcd(x, y) が求まるのだろうか？

定理

数学Aの教科書にも載っています

正整数 x と y について，
y = zx + r かつ 0 < r < x であるとき(つまり y mod x = r かつ r ≠ 0 のとき)，gcd(x, y) = gcd(r, x) が成り立つ．

69

ユークリッドの互除法の正当性【定理の証明の方針】(i) gcd(x, y) ≧ gcd(r, x) と(ii) gcd(x, y) ≦ gcd(r, x) が両方とも成り立つことを示して，gcd(x, y) = gcd(r, x) を導く．

70

ユークリッドの互除法の正当性証明(i): r は gcd(r, x) で割り切れ，y – r は x で割り切れる．
x も gcd(r, x) で割り切れるので，r + (y – r) = y は gcd(r, x) で割り切れる．
よって， gcd(r, x) は x と y の公約数である．
最大公約数の定義より，gcd(x, y) ≧ gcd(r, x) である．

ygcd(r, x)
xy–r

r

71

ユークリッドの互除法の正当性証明(ii): x = a·gcd(x, y), y = b·gcd(x, y) とおくと，y – zx = gcd(x, y)·(b – za) = r > 0 が成り立つ．

ここで b, z, a は整数なので，r は gcd(x, y) で割り切れる．

よって ，gcd(x, y) は r と x の公約数である．

最大公約数の定義より，gcd(x, y) ≦ gcd(r, x)である．

y = b·gcd(x, y)

a·gcd(x, y)= x
gcd(x, y)r

72

ユークリッドの互除法の正当性【証明つづき】gcd(x, y) ≧ gcd(r, x) かつ gcd(x, y) ≦ gcd(r, x)，すなわち gcd(x, y) = gcd(r, x) である．（証明終）
ygcd(r, x)xgcd(x, y)r

まとめ
大学以降の情報系科目では 数学 を駆使します• 例）整数，集合，論理，確率，統計など
計算理論：アルゴリズムの正しさや計算時間を論理的に証明  プログラム性能保証
情報理論：確率統計に基づく情報エントロピー，データ圧縮，暗号理論  情報通信技術
人工知能理論：機械学習のための微分積分，線形代数，確率統計  AI技術

数学抜きで情報科学を正しく理解することはできない  数学はやっぱり大事！