コンピューター科学への導入

電子式コンピューターの歴史は1940年代の真空管を使った初期のコンピューターから始まり、トランジスタ、集積回路、そしてマイクロプロセッサへと発展してきました。この発展の過程で、コンピューターの性能は飛躍的に向上し、サイズは小型化してきました。

スマートフォンで大量の動画などをみるときに

という言い方をします。このギガとはなんなのでしょう？ また、コンピューターを買うときに、メモリが8ギガバイトだとか、ハードディスクの容量が1テラバイトだとかいう言い方をします。このギガ、テラ、バイトが何を指すのか、正確に知っているでしょうか。

たくさんのUSBケーブルが溢れていて、どのケーブルを使ったらいいか迷ったことはないでしょうか。近年は USB-C ケーブルが主流になりつつありますが、実は同じ見た目の USB-C ケーブルも、ケーブルによっては通信ができなかったり、十分な通信速度がでなかったりします。

例えば以下のような経験はありませんか？

本書では、このような日常的な疑問の背景にある技術規格について理解を深めます。

2進法や16進法などの基数の考え方(この章の後半で復習します)をもとに、コンピューター内部でどのように数値が表現されるかを学びます。

整数は「2の補数表現」という方法で表されており、これによりコンピューターは負の数を扱うことができます。また、小数は「浮動小数点表現」で扱われますが、これは絶対的な精度ではなく相対的な精度で数を表現するため、計算によっては誤差が生じることがあります。

これらの表現方法には限界があり、表現できる数の範囲を超えると「桁あふれ（オーバーフロー）」が発生します。また、浮動小数点表現では表現できない数が多数あり、これが「表現誤差」の原因となります。こうした問題は、銀行のシステムや科学計算など、正確な数値計算が必要な場面で重要な課題となります。

今、みなさんが読んでいるこの文書の文字はコンピューター内部では、数値で表現されています。Webページやメールを読むとき文字が意味のない文字や記号の羅列になってしまういわゆる「文字化け」という現象に悩まされたことはないでしょうか。これは、コンピューター内部で文字を扱う方法が一通りではないことに起因しています。

コンピューター内部での文字の表現方法はコンピューター開発のさまざまな歴史を抱え込んで発展してきたため、必ずしも一貫した規則があるわけではなく、あまり美しい部分ではありません。しかし、データを扱う際には必要な知識となります。

画面や印刷物に表示される文字の形(字形)は、コンピューターの中では文字の番号とは別に、フォントのデータとして用意されています。同じ文字でも、明朝体とゴシック体では印象や読みやすさが変わります。書体の仕組みと、文書を作るときの書体の選び方を学びます。

今日のコンピューターは、スイッチのオンとオフに相当する0と1の信号を処理する部品で構成されています。本書では、どのようにして単純な0と1の演算からコンピューターが成り立っているのかを垣間見ることを目標とします。その基礎となるのが、0と1の2つの値だけを扱うブール代数です。 ブール代数では論理和(OR)演算を「+」で表すことがあり、この場合1+1=1となります。これは通常の算術演算とは異なる演算体系です。まずは、普段慣れ親しんだ四則演算から離れて、コンピューターの基礎である論理演算の理論となるブール代数について学びます。

コンピューターはスイッチのオンとオフの組合せによって定義される論理演算によって、どのように計算をしているのか、簡単な論理回路の構成を通して学びます。また、論理回路を用いてコンピューター内でデータを記憶しておく仕組みを、記憶回路の基本となるフリップフロップ回路を通して学びます。

情報理論は、1948年にクロード・シャノンによって創始された、情報の数学的な性質を研究する学問です。ビット単位での情報量の定量化、情報の圧縮、ノイズのある通信路での情報伝送などを数学的に扱います。この理論は現代のデジタル技術の基礎となっています。

アルゴリズムとは、問題を解くための手順や方法を指します。日常生活でも料理のレシピや組み立て説明書などの形でアルゴリズムを利用しています。コンピューター科学では、問題を解くための効率的なアルゴリズムの設計が重要な研究テーマとなっています。

アルゴリズムの効率は、実行に必要な時間（時間計算量）と使用するメモリ量（空間計算量）で評価します。特に問題のサイズが大きくなったときの計算量の増加率が重要であり、これをビッグO記法（O(n)、O(n²)など）で表現します。

本書では、基本的なアルゴリズムとその計算量について学びます。

第11章では、まず、どれほど時間をかけてもコンピューターでは解けない問題があることを示します。その代表が、プログラムが止まるかどうかを判定する「停止性問題」です。

計算量理論はアルゴリズム理論をさらに抽象化し、問題そのものの本質的な難しさを研究する分野です。どんなアルゴリズムを使っても効率的に解けない問題が存在することや、効率的に解けるかどうかがまだ証明されていない問題が存在することを学びます。

コンピューター科学では、

や

といった問題が与えられたとき、その問題の「難しさ」について考える「計算量理論」という分野があります。計算の「難しさ」を語るには、まず、どのようなコンピューターで計算するのかを決めなくてはなりません。これを計算モデルといいます。本書では詳細な形式化は避けますが、具体的には決定性チューリングマシンに相当する計算モデルを想定します。これは一般的なコンピューターでの計算を抽象化したモデルです。

計算量理論でいう計算の「難しさ」は、問題の入力サイズが大きくなるに従って計算時間や途中の計算で必要となる記憶領域がどの程度必要になるかを基準にして定義されます。先ほどの巡回経路の問題では、巡らなくてはならない営業所の数 \(k\) を入力サイズとしたとき、営業所の数 \(k\) が大きくなると、巡回の順番の候補は \((k-1)!/2\) 通り(出発点を固定し、逆回りを同じとみなした場合)と爆発的に増えます(練習問題7)。候補をうまく絞り込む工夫により、数万か所規模の例が厳密に解かれたこともありますが、どんな入力に対しても、\(k\) が大きくなっても現実的な時間で厳密な最短経路を求められる方法は知られていません。

2つの有名な問題を見比べてみましょう。数独とルービックキューブです。 この2つの問題は、どちらが難しい問題だと思いますか？ コンピューター科学の中でももっともコアな領域に属する計算量理論によれば、手順を1つ見つけるという意味では、数独の方がはるかに難しい問題であると信じられています。

数独であればマス目の数は 2⁴, 3⁴, 4⁴,…​の順に大きくなります。このマス目を決定する \(n=2, 3, 4, \ldots\) を数独の問題の入力サイズとします。一方でルービックキューブのキューブの数は 2³, 3³, 4³, …​ の順に大きくなります。この \(n=2, 3, 4, \ldots\) をルービックキューブの問題の入力サイズとします。

数独は問題の入力サイズが大きくなるに従って解くのに要する時間は、入力サイズに対して飛躍的に大きくなるため、大きなサイズの数独を厳密に高速に解くことができるアルゴリズムは知られていません。一方で、ルービックキューブは入力サイズが大きくなっても、数独ほどは入力サイズに対して大きな影響をうけずにすべての面の色を揃える手順を見つけるアルゴリズムが知られています。

ところで、数独もルービックキューブも正解を与えられれば検算はとても簡単です。数独であれば、縦横と各区画に相異なる数字が過不足なく入っていることを確認するだけですし、ルービックキューブであれば、各面が同じ色であることを確認するだけです。

以上の内容をふまえて、コンピューター科学で最も有名な未解決問題の話をすることにします。それは、とてもいいかげんな表現を恐れずにいうと、以下のような問題です。

この問題は「P≠NP予想」として知られており、1971年にスティーブン・クックにより定式化されて以来、だれも証明に成功していません。米国のクレイ数学研究所はこの問題を懸賞問題の１つとして、100万ドルの懸賞金をかけています。

本書では、ここでの怪しい説明よりはほんの少しマシな説明を通して、計算量理論の初等的な話題をいくつか取り扱い、コンピューター科学で扱う「計算」の概念について理解を深めます。