図 1 情報学の広がり情報学の広がり 1

計算と情報の原理

どんな手順なら速く解けるのか、そもそも解ける問題なのか。コンピュータを使う前の「考え方」を、数学の言葉で確かめる分野です。

ひとことで言うと

料理のレシピを、だれが作っても同じ味になるように書く

同じカレーでも、レシピの書き方しだいで、手早く作れたり、失敗しやすかったりします。計算と情報の原理は、問題を解く「レシピ」をどう書けば速く、まちがいなく、むだなく進むかを考える分野です。

アルゴリズム: 問題を解く手順

アルゴリズムは、問題を解くための手順を、だれが実行しても同じ結果になるように書いたものです。乗り換え案内が経路を選ぶのも、通販サイトがおすすめの商品を並べるのも、裏ではアルゴリズムが動いています。

同じ問題でも、手順によって速さが大きく変わります。たとえば 1,000 人分の名簿を名前順に並べるとき、となりどうしを比べて入れ替える方法(バブルソート)では約 50 万回の比較が必要ですが、半分に分けて並べてから合わせる方法(マージソート)なら 1 万回ほどで済みます。

大学では、手順が正しいことを証明する方法と、データが増えたときに時間がどう増えるか(計算量)を見積もる方法を学びます。

速いプログラムの多くは、コードを書く前の「手順の選び方」で決まります。

計算の理論: コンピュータにできること・できないこと

どんなに速いコンピュータでも、解けない問題や、現実的な時間では解けない問題があります。それを数学で明らかにするのが計算の理論です。

1936 年、アラン・チューリングは、テープに記号を読み書きするだけの単純な機械(チューリングマシン)を考え、「どんなプログラムについても、いつか止まるかどうかを正しく判定する方法」は作れないことを示しました。これは停止問題と呼ばれています。

答えを確かめるのは簡単なのに、答えを見つけるのは難しいように見える問題もあります。たくさんの都市を 1 回ずつ回る最短の道を探す問題(巡回セールスマン問題)では、都市が増えると調べる道の数が爆発的に増えます。こうした問題を本当に速く解く方法がないのかは「P≠NP 予想」と呼ばれ、いまも未解決です。クレイ数学研究所は、この問題に 100 万ドルの懸賞金をかけています。

図解都市を 1 回ずつ回る道の数

15 都市12 通り
210 都市18 万 1,440 通り
320 都市約 6 京通り
4現実の工夫「十分よい答え」を速く出す近似の手順を使う

ブレッチリー・パークに展示されている暗号解読の装置ボンブの円筒が並ぶ様子 — イギリスのブレッチリー・パークに復元されたボンブ。第二次世界大戦中、チューリングらが暗号の解読のために設計した電気機械式の装置です。写真: Ian Petticrew(CC BY-SA 2.0・Wikimedia Commons)

情報理論: 情報の量をはかる

情報理論は、情報の量をはかり、むだなく、まちがいなく伝える方法を考える分野です。1948 年にクロード・シャノンが発表した論文から始まりました。

情報の量の単位はビット。「はい/いいえ」で答えられる質問 1 つ分の情報です。1〜100 の数を当てるとき、「50 より大きい?」のように範囲を半分にする質問をくり返せば、7 回で必ず当てられます(2 の 7 乗 = 128 が 100 より大きいため)。

写真や動画を小さくする圧縮、電波が乱れても正しく届ける誤り訂正、汚れても読める QR コードのしくみも、情報理論の考え方から生まれました。

「何回の質問で必ず当てられるか」を考えるのが、情報の量をはかる第一歩です。

離散数学: つながりと組み合わせの数学

離散数学は、「つながり」や「組み合わせ」のように、とびとびの値を扱う数学です。高校の「場合の数」や「数列」、集合と論理の続きにあたります。

代表がグラフ理論です。駅を点、路線を線で表すと、乗り換え案内の最短経路は、点と線の図の上で一番短い道を探す問題になります。SNS の友だちのつながりや、Web ページどうしのリンクも同じ形で表せます。

グラフ理論の始まりは、18 世紀のケーニヒスベルク(現在のロシアのカリーニングラード)の「7 つの橋」の問題です。「すべての橋をちょうど 1 回ずつ渡る散歩道はあるか」という問いに、1736 年、数学者オイラーが「ない」ことを証明しました。

図解身のまわりの「点と線」

点と線(グラフ)

路線図駅が点、線路が線
SNS人が点、フォローが線
Webページが点、リンクが線
地図アプリ交差点が点、道が線

17 世紀のケーニヒスベルクの町を描いた地図。川の中の島と岸が橋で結ばれている — 17 世紀のケーニヒスベルクの地図。川の中の島と両岸を、7 つの橋が結んでいました。写真: Merian-Erben(Public domain・Wikimedia Commons)

高校生のうちに試せること

トランプで並べ替えの回数を数える
10 枚のカードを、となりどうしを比べて入れ替える方法と、半分に分けて並べてから合わせる方法で並べ、比べた回数を数えてみましょう。手順の違いが数字で見えます。
日本情報オリンピックの過去問を解く
中学生や高校生が参加できるプログラミングのコンテストです。過去の問題と解説が公開されていて、アルゴリズムの考え方を練習できます。参加の条件は年度ごとに公式サイトで確認してください。
日本情報オリンピック
競技プログラミングのコンテストに出る
AtCoder では、初心者向けのコンテストがほぼ毎週開かれていて、無料で参加できます。
AtCoder