ITエンジニアが修めるべきコンピュータサイエンスの基礎（ソフトウェア編）

0.はじめに

本記事では、3つのコア技術（ハードウェア・ソフトウェア・コミュニケーション）に関するトピックで構成しました。
「IT技術者が修めるべき」といったタイトルにしていますが、内容としては非常に基礎的で、基本的なアイデアをまとめたものです、というのも現在のシステムは、今から10年後には陳腐化してしまっているでしょうが、基本的なアイデアを理解しておけば、未来のシステムも同様に理解できるからです。
それでは、始めて行きます。

目次

1.アルゴリズム
2.プログラミングとプログラミング言語
3.オペレーティングシステム
4.おわりに

1.アルゴリズム

アルゴリズムは、コンピューターで計算を行うときの「計算方法」のことになります。
広く考えれば、何か物事を行うときの「やり方」のことだと言っていいでしょう。
その「やり方」を工夫して、より良いやり方を見つけようとすることは、コンピュータサイエンスの中核部分をなしています。
それでは、具体例を見ていきましょう。

1-1.線形アルゴリズム

部屋の中で、一番背が高い人が誰なのかを知りたいとしましょう。
周りを見回して推測することも出来ますが、アルゴリズムの場合は知性のないコンピュータでも実行できるように、各計算ステップを正確に記述する必要があります。
基本的なアプローチは、順番に各人に慎重について尋ね、それまでに出てきた最も背の高い人の身長を覚えておくことです。
アルゴリズムの重要な特性の一つは、それらがどれくらい効率的に動作するか、つまり高速か低速かということです。
上記の例では、実行すべきステップの数（仕事を実行するのにかかる時間）は、処理するデータの量に正比例します。
もし部屋の中に2倍の数の人がいた場合、最も背の高い人を見つけるには2倍の時間がかかることを意味します。
このように、計算時間がデータ量に正比例（線形に比例）する場合、そのアルゴリズムは線形と呼ばれます。
私たちが日常で合うアルゴリズムの多くは線形です。

1-2.バイナリー探索（二分探索）

線形探索よりもうまくやる事は出来るでしょうか。
昔ながらの紙の電話帳をイメージしてみて下さい。ある人物の名前(例として「鈴木一郎」)を探す際、まずはほぼ中央を開いてみます。開いたページの人物の名前が「内藤太郎」だった場合、「鈴木一郎」は半分より前にあることがわかります（昔の電話帳は、五十音順に並べられている=ソートされている）。この時点で、電話帳の後半か完全に無視できることになります。次は前半のページの半分（電話帳の初めから1/4）を開きます。名前は五十音順に並んでいるので、各ステップでは次にどちらの半分を見ればよいかわかります。
この探索アルゴリズムは、「バイナリー探索(二分探索)」と呼ばれます。
1,024個の名前で始めるとしましょう。1回の比較で512この名前を削除できます。次の比較では256個になり、以後128、64、16、8、4、2となって最終的に1になります。それは10回の比較で探索が完了することを意味します（ $\log_2 1024 = 10$ ）。
バイナリー探索の重要な点は、データ量が増えても必要な作業量がゆっくりとしか増えないことにあります。例えば、10億個の名前から目的の名前を探すのには、30個の名前を比較するだけでよいのです。(1,000,000,000 ≒ 2^30)

1-3.ソート(整列)

しかし、そもそもどうやってそれらの名前を五十音順に並べるのでしょうか。その最初のステップがなければバイナリー探索は使用できません。そのためには、基本的アルゴリズムである「ソート」が必要になります。

1-3-1.選択ソート

以下の16個の名前をアルファベット順にソートしてみましょう。

Intel 　Facebook　Zillow　Yahoo　Pinterest　Twitter　Verizon　Bing　Apple　Google　Microsoft　Sony　PayPal　Skype　IBM　Ebay

最初の項目から始めます。Intelが一番目です。
まだ1つしか見ていないので、今の所これがアルファベット順でも1番目です。
これを次の名前のFacebookと比較すると、Intelよりも前に来るので、Facebookが仮の1番目になります。
その次のZillowはFacebookの前にはなりませんし、その後もBingが出てくるまではどれもFacebookの前になりません。
Bingが見つかって、Facebookの代わりに1番目の項目になります。
その後、BingはAppleによって置き換えられます。残りも調べますが、Appleより前になるものはありません。
よってAppleがリストの本当の1番目の項目になります。
Appleを先頭に移動して、残りの名前はそのままにしておきます。
この時のリストは次のようになります。

Apple

Intel 　Facebook　Zillow　Yahoo　Pinterest　Twitter　Verizon　Bing　Google　Microsoft　Sony　PayPal　Skype　IBM　Ebay

さて、今度は2番目の名前を見つけるために、まだソートされていないグループの最初の名前であるIntelからはじめて、同じプロセスを繰り返します。
2回目のプロセスが終わると、結果は以下のようになっています。

Apple　Bing

Intel 　Facebook　Zillow　Yahoo　Pinterest　Twitter　Verizon　Google　Microsoft　Sony　PayPal　Skype　IBM　Ebay

このプロセスをさらに14回繰り返すことによって、ソートされたリストを作り出します。
このプロセスの計算量は、$16 + 15 + 14 + ・・・ + 3 + 2 + 1 = 136$ 回名前を見る必要があるのです。
一般の場合、$N + (N-1) + (N-2) + ・・・ + 3 + 2 + 1 = N*(N-1)/2$ 回の計算量となります。
つまり、選択ソートの仕事量は $N^2$ に正比例します(多項式の場合、最高次数を計算量とする決まり)。
これは、ソートする項目が10倍あると、100倍もの時間がかかることを意味し、あまり好ましくありません。
もっと良い方法はないのでしょうか。

1-3-2.クイックソート

再びソートされていない名前の例をあげましょう。

Intel 　Facebook　Zillow　Yahoo　Pinterest　Twitter　Verizon　Bing　Apple　Google　Microsoft　Sony　PayPal　Skype　IBM　Ebay

このリストを、まず一度全部名前を見て、A~Mで始まる名前を1つの山に積み、N~Zで始まる名前を別の山に積みます。
この作業でそれぞれの山には8個の名前が積まれています(それぞれ半分の名前が別になるように、名前の分布が偏っていないことを想定しています)。
この結果、以下のようになります。

Intel　Facebook　Bing　Apple　Google　Microsoft　IBM　Ebay

Zillow　Yahoo　Pinterest　Twitter　Verizon　Sony　PayPal　Skype

今度はA~Mまでの山を見て、A~Fまでを1つの山に、G~Mを別の山に入れます。
またN~Zの山に対しては、N~Sまでを1つの山に、T~Zを別の入れます。
この時点で、名前を2回通して見ています。
この結果、以下のようになります。

Facebook　Bing　Apple　Ebay

Intel　Google　Microsoft　IBM

Pinterest　Sony　PayPal　Skype

Zillow　Yahoo　Twitter　Verizon

次にそれぞれのの山を同様に2つに分け、2つの名前を持つ8つの山があります。
最後にもう1度繰り返すと、1つだけの名前を含む16個の山を手に入れ、これがアルファベット順にならべられていることに気付くと思います。

クイックソートの仕事量は、各プロセスでは、16個の名前をそれぞれ調べました。
また、分割により山に含まれる名前は8、4、2個と減っていきます。
これは16の2を底とする対数、つまり4です。したがって、16個の名前に対して必要な作業量は $16log_2 16$ 回です。
一般の場合、 $Nlog_2 N$ になります。

以下のグラフは、データ量の増加につれて、計算量がどれほど増加するかを表したものになります。

2.プログラミングとプログラミング言語

プログラミング言語は現在様々なものが存在します（例：C, C++, C#, Java, PHP, Perl, Ruby, Lisp, Prolog, BASIC, etc）。
しかし、これらのプログラミング言語はあくまでも人間がプログラムを組むために作られた言語でコンピュータ(CPU)が直接理解できるわけではありません。
CPUが直接理解できるプログラムはマシン語と呼ばれる数字の並び(2進数表記)で構成されたものだけです。
機械語以外のプログラミング言語で記述されたプログラムは、必ず機械語で記述されたプログラムに変換されてから実行されます。

例えば、C言語で記述されたプログラムは「コンパイラ」と呼ばれる変換プログラムを使って、C言語の表現を「マシン語」のプログラムに変換し、CPUに理解させているのです。

2-1.アセンブリー言語

コンピュータは数字の並びである機械語しか理解できませんが、これを人間が書くのは分かりにくく大変です。
機械語を人間でも分かりやすくするために簡略化した英単語や記号を一対一に対応させたものをアセンブリ言語といいます。
アセンブリー言語は一般的に「低級言語」と呼ばれ（低級とは、コンピュータの生の動作に近いという意味）、マシン語に一対一で対応しています。つまりアセンブリ言語でプログラムを書くことは機械語を書くことに等しいといえます。

他のプログラミング言語は、一対一には対応せず、機械語を意識しなくてもプログラミングを行えるようになっているのが普通なのです。

2-2.高級言語

上記のアセンブリ言語に対し、私たちがよく聞く、C言語やJavaは「高級言語」と呼ばれ、高級とは人間の感覚に近い（コンピュータの生の動作からは遠い）という意味で、コンピュータのハードウエアの知識がなくてもプログラムが作れます。
高水準言語のプログラムは，アセンブラのプログラムより行数が少なく、効率的に作成できます。そのため、現在ではアセンブラはめったに使われず、ほとんどのプログラマが高水準言語を使っています。

3.オペレーティングシステム

オペレーティングシステム(OS)とは、コンピュータのハードウェアを管理し、アプリケーションと呼ばれるほかのプログラムを実行できるようにするソフトウェア基盤です。
具体的には、PCを立ち上げ、メールをチェックし、バックグラウンドで音楽を再生しながらネットサーフィンをしている時、OSは各プロセスにCPUを次々に割り当てて処理していっているのです。
クライアントPC向けではMicrosoftの「Windows」やAppleの「Mac OS」、モバイル機器向けではGoogleの「Android」やAppleの「iOS」があります。
オープンソースの「Linux」は、サーバ、PC、組み込みシステムなどに幅広く採用されている。

3-1.オペレーティングシステムの役割

• CPUの管理：現在使用中のプログラムがいつ実行されるかを決めるスケジューリングと調整を行います。

• RAMの管理：すべてのプログラムを実行するのに十分なRAMがない場合には、一時的にそれらを二次記憶に追い出して、余裕が出来た時に再びRAMに読み込むといった管理を行います。

• ディスクの管理：ファイルシステムと呼ばれるOSの主要なコンポーネントが、コンピュータの使用時に見られるフォルダとファイルの階層を提供します。

• デバイスの管理：コンピュータに接続されているデバイス（周辺機器）の動作を管理・調整します。

4.おわりに

以上、「ITエンジニアが修めるべきコンピュータサイエンスの基礎（ソフトウェア編）」でした。
ITエンジニアだけでなく、教養としてコンピュータサイエンスを修めたい方向けに、内容は非常に基礎的かつ非常に重要な要素だけをまとめさせて頂きました。