情報科学入門「コンピュータにどう考えさせるか？」

九州大学 システム情報科学研究院
准教授 稲永 俊介

もくじ
1. 自己紹介
2. 高校時代
3. 情報科学とは？
4. 研究紹介
5. まとめ

大学研究セミナーI＠福岡高校

1

自己紹介

大学研究セミナーI＠福岡高校

2

自己紹介稲永 俊介（いねなが しゅんすけ）
出身：福岡県糟屋郡志免町
学歴：福岡高校 ⇒ 九州工業大学 ⇒ 九州大学大学院
職歴：科学技術振興機構 ⇒ ヘルシンキ大学 ⇒京都大学 ⇒ 日本学術振興会 ⇒ 九州大学

大学研究セミナーI＠福岡高校

3自己紹介（つづき）
現職：九州大学 システム情報科学研究院 准教授
専門：情報科学
平日：学生と共に日々研究に励む
授業もする（理学部，工学部）

大学研究セミナーI＠福岡高校

4

情報科学とは？

大学研究セミナーI＠福岡高校

5

情報科学って何？
 コンピュータ上で行われていることはすべて「計算」である．

 その「計算」と上手に付き合ったり、「計算」をうまく制御するには、「計算」とは何であるかを理解する必要がある．

 そのための科学がComputer Science（情報科学）
 コンピュータ上で何らかの「計算」を行うとき、アルゴリズムの設計が重要となる．

大学研究セミナーI＠福岡高校

6

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



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

単純な計算を組み合わせて、より複雑な問題を解くための手順のことをアルゴリズムという

高速なアルゴリズムの開発は人間（研究者）の役割！
大学研究セミナーI＠福岡高校

7

最大公約数問題
問題
正整数 x と y が与えられたとき、x と y の最大公約数 gcd(x, y) を求めよ．
gcd : greatest common divisor

例• gcd(16, 12) = 4• gcd(63, 14) = 7• gcd(47, 32) = 1
大学研究セミナーI＠福岡高校

しらみつぶし的アルゴリズム naive_gcd
startk ← min(x, y) とする

mod は余りの計算（例: 10 mod 3 = 1）

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

yes

gcd(x, y) = k を出力
finish
大学研究セミナーI＠福岡高校

naive_gcd の実行例
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
大学研究セミナーI＠福岡高校

naive_gcd の実行例
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
大学研究セミナーI＠福岡高校

naive_gcd の実行例
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
大学研究セミナーI＠福岡高校

naive_gcd の実行例
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 とする

yes

gcd(6, 9) = 3 を出力
finish
大学研究セミナーI＠福岡高校

naive_gcd の計算時間見積もり•

n = min(x, y) とすると，余り (mod) の計算回数は最悪の場合で 2n 回•

余り (mod) の計算の1回の計算時間– PC 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 年

待てるわ
けない！

大学研究セミナーI＠福岡高校

高速化への道
最大公約数問題を，「長方形をなるべく大きな正方形で埋める問題」に置き換えて考える．

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

大学研究セミナーI＠福岡高校

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

xy
大学研究セミナーI＠福岡高校

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

gcd(x, y)x• 長方形を埋める正方形の一辺の長さ＝ x と y の公約数y• そのような最大の正方形の一辺の長さ = gcd(x, y)
大学研究セミナーI＠福岡高校

長方形敷き詰め問題(例)24 と 36 の最大公約数
gcd(24, 36) を求めたい

2436• 長方形を埋める正方形の一辺の長さ＝ x と y の公約数
• そのような最大の正方形の一辺の長さ = gcd(x, y)
大学研究セミナーI＠福岡高校

長方形敷き詰め問題(例)24 と 36 の最大公約数
gcd(24, 36) を求めたい

24
12 = gcd(24, 36)36• 長方形を埋める正方形の一辺の長さ＝ x と y の公約数
• そのような最大の正方形の一辺の長さ = gcd(x, y)
大学研究セミナーI＠福岡高校

演習１• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

長い辺を短い辺で割る．
ぴったり割れたら，短い辺の長さが最大公約数．
大学研究セミナーI＠福岡高校

演習２• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

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

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

大学研究セミナーI＠福岡高校

演習３• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

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

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

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

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

大学研究セミナーI＠福岡高校

解答• 長方形の紙をなるべく大きな正方形に分割せよ．
• ただし，最初に定規で辺の長さを測ってはいけない．

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

大学研究セミナーI＠福岡高校

賢いアルゴリズム euclid_gcdrx < y と仮定

startxr ← y mod x とする

r = 0 か？
noy
yes

x を出力
finishy ← x, x ← r とする大学研究セミナーI＠福岡高校

賢いアルゴリズム euclid_gcd
r=0

x < y と仮定

startyr ← y mod x とする

r = 0 か？
nox
yes

x を出力
finishy ← x, x ← r とする大学研究セミナーI＠福岡高校

賢いアルゴリズム euclid_gcd
x < y と仮定

start

このアルゴリズムをユークリッドの互除法というr ← y mod x とする

r = 0 か？
noyesx を出力
finishy ← x, x ← r とする大学研究セミナーI＠福岡高校

34

euclid_gcd の実行例
【問】 7289 と 740 の最大公約数を求めよ．
7289 mod 740 = 629

740 mod 629 = 111

629 mod 111 = 74

111 mod 74 = 3774 mod 37 = 0余りが 0 になったので，37 = gcd(7289, 740)

大学研究セミナーI＠福岡高校

euclid_gcd の計算時間見積もり
euclid_gcd の計算ステップ数 ≈ 2log2n余りの計算 (mod) の1回の計算時間– スーパーコンピュータ 1ステップ 10-11秒
nnaive_gcd
スパコン

euclid_gcd
スパコン

1億

0.002 秒

0.56 × 10-6 秒

1兆20 秒0.82 × 10-6 秒

1京55.5 時間

1.08 × 10-6 秒

1050

6.3 × 1031 年

3.34 × 10-6 秒

10100 (≈ 2332)

6.3 ×1081 年

6.66 × 10-6 秒

euclid_gcd は計算が瞬時に終わる！

大学研究セミナーI＠福岡高校

36

おまけ：
因数分解よりもユークリッドの互除法• x と y をそれぞれ因数分解すれば，最大公約数 gcd(x, y) は求まるが…
• 実は，大きな数の因数分解は難しい！
（高速なアルゴリズムが知られていない）• しかし，ユークリッドの互除法を用いれば，高速に gcd(x, y) を求めることができる^^

研究紹介

大学研究セミナーI＠福岡高校

万物は文字列である
例１） DNA配列

細胞

染色体

A, C, G, T からなる２つの文字列のらせん構造
大学研究セミナーI＠福岡高校

万物は文字列である
例２） 音楽データ

音符と休符の列大学研究セミナーI＠福岡高校

万物は文字列である
例３） 画像データの二次元列色を記号だとみなせば画像も文字列である

大学研究セミナーI＠福岡高校

コンピュータ上のデータ＝文字列
 コンピュータ上のデータは文字列である
 大量に溢れる文字列データをいかに効率よく処理するかがカギ

大学研究セミナーI＠福岡高校

データ圧縮文字列データを圧縮して表現すれば、データの「無駄」を削減できる例１）すもももももももものうち＝すも8のうち
例２）にわにわにわにわとりがいる＝(にわ)4とりがいる
大学研究セミナーI＠福岡高校

研究成果
圧縮された文字列データ上で情報検索を高速に行うアルゴリズムを開発した
大量のデータも圧縮すれば小さくなる
 圧縮することで、情報検索の速度も向上！


圧縮されていないデータ

普通のアルゴリズム

圧縮データ

開発したアルゴリズム
大学研究セミナーI＠福岡高校

研究成果の発表の場＝世界
 国際会議に参加して、自分たちの研究成果を世界中の研究者に報告する（海外出張）

 これまでに海外出張で行った国々：

イギリス，フィンランド，ノルウェー，ポーランド，チェコ，スロバキア，ドイツ，フランス，スペイン，イタリア，ポルトガル，ロシア，ハンガリー，オーストリア，イスラエル，アメリカ，カナダ，チリ，アルゼンチン，コロンビア，オーストラリア，ニュージーランド，インド，シンガポール，韓国，中国
大学研究セミナーI＠福岡高校

世界地図にを立ててみる

大学研究セミナーI＠福岡高校

情報科学の歴史
1822年– 階差機関by Babbage
1936年– チューリング機械
by Turing
1950年代– 情報理論
by Shannon– プログラム言語(Fortran, Lips, Algol, Cobol, ...)
1960-1970年代– ワークステーション，データベース– ワードプロセッサー

1980年代– パソコン– オブジェクト指向言語– コンピュータゲーム
1990年代– インターネット– 携帯電話2000年代– 電子マネー– ユビキタス– モバイル (iPod, iPhone)
2010年代– 3D-TV, iPad,smart phone
大学研究セミナーI＠福岡高校

情報科学の歴史
1980年代

1822年– 階差機関by Babbage– パソコン– オブジェクト指向言語

1936年– チューリング機械
by Turing
1950年代– コンピュータゲーム
1990年代– インターネット• 情報科学は非常に若い分野– 携帯電話– 情報理論
2000年代by Shannon • 学生や若手研究者が世界で– 電子マネー– プログラム言語活躍する余地が十二分にある– ユビキタス(Fortran, Lips, Algol, Cobol, ...)
– モバイル (iPod, iPhone)
1960-1970年代– ワークステーション，
データベース– ワードプロセッサー

2010年代– 3D-TV, iPad,smart phone
大学研究セミナーI＠福岡高校

九州大学の情報系学科

大学研究セミナーI＠福岡高校

48

九州大学 工学部 電気情報工学科
工学部
電気情報工学

物質科学工学

地球環境工学

機械航空工学

建築学

電気電子工学課程

電磁気，電力システム，超電導など

電子通信工学課程

通信ネットワーク，信号処理など

計算機工学課程

アルゴリズム，ソフトウェア，人工知能など

２年生前期に課程を選択
大学研究セミナーI＠福岡高校

49

九州大学 理学部 物理学科
理学部
物理学
物理学コース化学

地球惑星生物学

数学

情報理学コース

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

大学研究セミナーI＠福岡高校

50

九州大学 理学部 物理学科
物理学
物理学コース

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

知能科学

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

計算科学

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

大学研究セミナーI＠福岡高校

51

まとめ

大学研究セミナーI＠福岡高校

まとめ 何かに興味を持ったら、とことんやってみよう

ゲームがきっかけで、准教授になることもある 情報科学は比較的新しい学問分野


若者が活躍するための余地が十分に残されている研究成果を残せば、海外旅行出張に行ける！

 九州大学で情報科学について学ぶなら，工学部 電気情報工学科 または理学部 物理学科 情報理学コース

大学研究セミナーI＠福岡高校