を参照していく。
前回
2. コンピュータ科学の基本
2.1 コンピュータの基本原理
2.1.1 ハードウェアの構成
オペレーティングシステム()を搭載した
を考える。こうしたコンピュータには中央演算処理装置(
)があり、それは小さな命令を高速で次々と処理することを目的としている。処理速度を示すのに、1秒間に何回命令処理をこなすことができるかを表すクロック周波数を用いる。最近はその性能表示に
を用いる。
通常、上のデータはメインメモリ（主記憶装置）上にある。電源を落とすとデータは失われるため、他に外部記憶装置が搭載されている。
も内部にレジスタと呼ばれる計算用の小さなメモリを持っている。しかしほとんどのデータはメインメモリ上にあるため、
とメインメモリの間の通信は重要である。そのためバス（bus）と呼ばれる高速な接続環境が用意されている。バスにはコントローラを介してディスプレイやキーボードなどの周辺機器及び外部記憶装置が接続されている。
メインメモリはとも呼ばれ、データの場所さえ分かれば広大なメモリ領域から非常に短い時間でデータの読み書きが可能である。データの場所は番地（アドレス）と呼ばれる。
はこのアドレスとそのデータに対する処理命令を受け取り次々に計算を実行する。
2.1.2 ビットとバイト
半導体は電圧の高低により2種類の状態を保持できる仕組みになっている。電圧の高い状態を、電圧の低い状態を
としよう。これはビット(
)という単位で表現される。また
としてバイト(
)という単位も良く使われる。
が1階の計算で扱うデータのサイズは
が主流になっている。
は
という単位で表現することもある。
2.1.3 2進数と性数
コンピュータはを用いて状態を表現するため、2進数を用いる。
# bin(x)で2進数表示されたxを返す print(bin(2)) print("****************************************************************") # 接頭辞0bを付けるとPythonの処理系に2進数をそのまま渡すことができる print("2進数の0b1111は10進数で") print(0b1111) print("である。") print("****************************************************************") # 2指数を2倍すれば桁数が1つ増える print(bin(5)) print(bin(5 * 2)) print(bin(18)) print(bin(18//2)) print("****************************************************************") # bitshift演算子 << を用いても同じ計算ができる print(5 << 1) # ビットを左に1つズラす print(18 >> 1) # ビットを左に1つズラす print("****************************************************************") ############################# ### 2進数で少数を表示する ### ############################# # 小数は2^(-n)で表される：0.1など正確に表すことができない小数がある from decimal import Decimal 0.1 + 0.1 + 0.1 == 0.3 # Falseになる # 誤差が存在する print(abs(Decimal.from_float(0.1 + 0.1 + 0.1) - Decimal.from_float(0.3))) print(abs(Decimal.from_float(0.1 + 0.1 + 0.1) - Decimal.from_float(0.3))/Decimal.from_float(0.3))
2.2 配列で見るデータ構造
2.2.1 メモリの構造
メモリはメモリセルと呼ばれる小さな領域が連続して並んだ構造をしており、各メモリセルには番地(アドレス)が割り当てられている。はアドレスを指定することにより計算に必要なデータを取得する。
2.2.2 データ構造
で整数を保持するリストは以下で定義できる。
my_array = [10, 20, 30, 40, 50] my_array[2]
このようにデータをひとまとまりで扱う構造を考える。
2.2.3 データの並びを保持する構造
順番を保持してメモリに記録する最も単純な方法は連続するメモリ領域を必要な分だけ確保することである。またデータの格納場所がどのアドレスから始まるかを別に保持しておく。このようなデータ構造を配列()という。
# 配列(Pythonではリスト)を定義 my_array = [10, 20, 30, 40, 50] print(my_array[2]) # 配列(リスト)にデータを挿入 my_array.insert(2,100) print(my_array[2])
配列のある位置にデータを挿入する場合、配列の後のアドレスが空いているならば、挿入位置以後のデータを挿入するデータの個数だけ後ろにズラせば良い。しかしもし配列の後にデータが既に存在するならば、それらすべてが後ろのアドレスに移らなければならない。したがって配列は、要素へのアクセスは容易であるものの、要素の挿入に手間が掛かる。
2.2.4 連結リスト
要素の挿入を高速化するデータ構造として連結リストがある。その中でも最も簡単な一方向連結リストは、各メモリセルにデータ自体と次の要素のアドレスを保持するものである。連結リストの始まりの位置は別に格納されているものとし、話を簡単にするのに1つのメモリセルに整数値と次のメモリセルのアドレス(これをポインタという。)を一緒に保存できるものとする。
連結リストに新しい要素を挿入する場合、挿入される要素は挿入されるデータおよび前後のアドレスを格納し、挿入される前後のメモルセルは新たなポインタに書き換わる。これによりすべてのリストを書き換えず一部のデータを書き換えるのみで挿入ができる。
2.3 計算量の考え方
アルゴリズムは何らかの目的を達成するための一連の計算手順である。計算の実行には時間が掛かり、その速さがアルゴリズムの良さを判断する1つの尺度になるため、それを表現するための手段を検討する。
2.3.1 通常の時間表示がなぜ不適なのか
コンピュータによるアルゴリズムでの計算は、①アルゴリズムの設計のみならず②マシンの性能に応じて実行速度が大きく変わり得る。今回はアルゴリズムの良さを評価するためのものであるから、通常の時間表示は不適である。
マシン性能に左右されない単位として計算のステップ数を考える。ここでは特定のアドレスへのメモリセルへのアクセスを1ステップと考える*1。
2.3.2 入力サイズと作業量
アルゴリズムの実行時間に関して何ステップの計算が必要かを考えるのが計算複雑性(computational complexity)の理論である*2。計算複雑性を計算量とも呼ぶ。計算量は入力データのサイズに応じてステップ数がどのように変化するかを表現する。この表現方法には漸近記法を用いる。
2.3.3 計算量の漸近記法
扱うデータのサイズに依存した計算量の変化を表現すべく、漸近記法と呼ばれる手法が用いられる。漸近記法は次の2つのルールに従って計算量を表記する方法である：
| (1) | 複数の項で計算時間が表記される場合、入力サイズに対して増加率が最大の項のみを残す。 | |
| (2) | 残った項の定数係数は無視する。 |
たとえば連結リストにおける要素へのアクセスでは最悪の場合、すなわち一番最後の要素にアクセスする場合でステップが掛かる。したがってこのアルゴリズムの計算量を
と書く。これは入力サイズが大きくなれば、連結リストにおいて要素へアクセスするアルゴリズムの計算量は、入力サイズに対して線形に増大することを意味する*3。なお入力サイズにかかわらず一定時間が掛かる場合はと記述する。
2.3.4 配列とリスト
配列はプログラミング言語に応じて意味や定義が変わるが、1つの分類として、いったん宣言（定義）すると配列の長さを変更できない配列を静的配列(static array)といい、定義した後に長さを適宜変更できるものを動的配列(dynamic array)という。
のリストでは各要素へのアクセスは
で、要素の挿入は
の計算量が必要になる。
