Revision as of 13:11, 24 November 2012

ハードウェア

計算機のCPUについて

CPU (Central Processing Unit) とは中央演算処理装置のこと。略してプロセッサ。 一番の基本は01のバイナリ命令を解釈して演算を行う部分 (ALU: Arithmetic Logic Unit) と一時的に値を格納するレジスタが、主記憶メモリとバスでつながれた構造を持つ。

一般的にマルチコアと呼ばれるプロセッサは、演算処理部分とレジスタのセットを複数が、単一の主記憶につながった構造を持つ。最近耳にするGPU (Graphics Processing Unit) は、画像処理用にメモリ間のデータ転送や浮動小数点の演算を並列処理で高速化する装置のこと。以前はグラフィックアクセラレータなどと呼ばれていたものが汎用化したもの。

プログラムはどうやって動くのか

プログラミング言語（ソースコード）は人間が読んでわかる形だが、最終的にCPUが扱う機械（マシン）語レベルではバイナリ(01)列。 人が扱う高級言語から、機械語に「翻訳」する手法には大きく分けて2種類ある。

• コンパイラ ... ソースコードを特定の計算モデル上で解釈し、処理を最適化する翻訳
• インタープリタ ... 原則、ソースコードのコマンドをマシン語レベルの処理にそのまま対応させる翻訳

コンパイラとインタープリタは翻訳手法であり、言語そのものと結びつく概念ではない。 ただし一般には、プログラムを書いてすぐに動く言語(Lisp, Perl, Ruby, Python, etc.)と、一度「コンパイル」して実行形式ファイルを作成する言語(C, Java, Fortran, etc.)に分けられる。

データ構造

計算機上にデータを記述する際に、利用形態にあわせて適切な表現法を用いると効率よく処理できる。

基本データ構造

• 配列 ... 決まった個数のデータを格納する。データのアドレス（番地）は整数で指定。
• リスト ... 個数が大きく変化するにあわせて伸長・収縮が自在にできる。
• スタック ... 今は昔になってしまった、ばね式のコイン入れの仕組み。最後に入れた要素が最初に取り出される。
• キュー ... 先頭から入れ、末尾から取り出す筒のこと。最初に入れた要素から順に取り出す。

配列とリストの違い

プログラミング言語には配列 (array) という概念があります。メモリ空間の一定領域を確保し、ブロックとして利用するのが配列データ構造です。配列には大きな欠点があります。細切れになったメモリ空間を効率良く利用できないのです。そこで小さな領域を数珠のようにつなぐ対策が考えられます。それがリスト構造です。

リスト構造の欠点はアクセスの手間です。配列で10番目の要素を知りたい場合、配列であれば先頭アドレス＋データサイズ×10 によって値が格納されるアドレスを計算できますが、リストはこれができません。要素を１つずつ辿っていく必要が生じます。

探索に用いるもの

• ツリー ... 代表的なものは二分木。構造を絵に描くと一番よく理解できる。 頂点数がn個ある場合、枝の数はn-1本になる。
• ハッシュ ... 各要素の値から一定のルールで整数値（ハッシュ・キー）を計算し、その値を元に配列中に格納する手法。実用的。

ソート・整列

• クイックソート ... 与えられた配列をだいたい半分にしながら並び替え。平均的計算量O(n log n), 最悪はO(n²)。実用上いちばん速いといわれる。
• マージソート　... 与えられた配列を正確に半分にしながら並び替え。計算量は常にO(n log n)。実用。
• バブルソート ... 配列中で隣り合った組を発見するたびに入れ替えをおこなう。計算量はO(n²)で非実用。
• 挿入ソート ... 新しく追加する要素の位置を、配列中をスキャンして探す。殆ど並んでいるデータを微修正するのには使える。。計算量はO(n²)。

大量データの表現・格納・処理

関係データベース

エクセルのような表を組み合わせてデータを表現する。表を作る際に最低限必要な情報だけを記述し、残りは表計算によって導出する。関係演算と呼ばれる系では、集合演算に加えて、表からの行・列の選択(select, project)、表の結合(join)により汎用的な論理体系と同等の表現能力を持つことが知られている。

オブジェクト型

まとまったデータをカプセル化して隠蔽する概念をオブジェクト指向と呼ぶ。 各オブジェクトは、その中身にアクセスして処理するためのメソッドを備えており、この概念を取り入れたプログラミング言語 (例えばC++, Java)やデータベースが開発されている。

クラスタリング

• k-近傍 (nearest neighbor) ... 各データから最も距離が近いk個を選んでクラス分けをする
• 自己組織化マップ ... 各データを最も近い要素に少しずつにじり寄らせていってクラス分けをする

機械学習

• サポートベクトルマシン (SVM) ... 平面上にばらつく2群を直線で分けるには、両群の各点からその直線におろした垂線の足の長さを最大化する場合が最適になる（マージン最大化）。これを多次元に拡張し、マージンを最大にする超平面を探すアルゴリズムをSVMという。近年はデータ集合を非常に高次元の特徴空間に射影し（射影する関数をカーネル関数と呼ぶ）、特徴空間上で超平面による分割をおこなう手法が主流。
• ニューラルネットワーク　... 脳のシナプス回路をモデルにして作られた機械学習手法。タンパク質の二次構造予測に良く用いられる。

状態遷移

オートマトン

○と→を結んだ状態遷移のチャートそのもの。

マルコフ連鎖 (Markov chain)

○と→を結んだ状態遷移で、次に移動する場所を現在いる状態のみに依存して（つまり今までどの状態を巡ってきたかを無視して）決定する場合をマルコフ連鎖という。