Revision as of 17:02, 8 October 2010

ハードウェア

計算機の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.)がある。

データ構造

リスト表現

スタック

今は昔になってしまった、ばね式のコイン入れの仕組み。最後に入れた要素が最初に取り出される。

キュー

先頭から要素を入れ、末尾から要素を取り出す筒の仕組み。入れた順番のまま、最初に入れた要素から順に取り出される。

探索に用いるもの

ツリー

代表的なものは二分木。構造を絵に描くと一番よく理解できる。 頂点数がn個ある場合、枝の数はn-1本になる。

ハッシュ

要素それぞれの値から一定のルールで整数値（ハッシュ・キー）を計算し、その値を元に配列中に格納する手法。たいへん実用的。

大量データの表現・格納

関係データベース

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

オブジェクト型

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

状態遷移

オートマトン

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

マルコフ連鎖 (Markov chain)

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

アルゴリズム

ソート

クラスタリング

k-近傍 (nearest neighbor)

各データから最も距離が近いk個を選んでクラス分けをするもの

サポートベクトルマシン (SVM)

平面上にばらつく2群を直線で分けるには、両群の各点からその直線におろした垂線の足の長さを最大化する場合が最適になる（マージン最大化）。これを多次元に拡張し、マージンを最大にする超平面を探すアルゴリズムをSVMという。 近年はデータ集合を非常に高次元の特徴空間に射影し（射影する関数をカーネル関数と呼ぶ）、特徴空間上で超平面による分割をおこなう手法が主流。