Aritalab:Lecture/JSBi/Test/CompSci - Revision history

Adm: /* ソート・整列 */

2012-11-24T04:14:33Z

‎ソート・整列

Adm: /* 探索に用いるもの */

2012-11-24T04:13:19Z

‎探索に用いるもの

Adm: /* 配列とリストの違い */

2012-11-24T04:12:14Z

‎配列とリストの違い

Adm: /* 基本データ構造 */

2012-11-24T04:11:12Z

‎基本データ構造

Adm at 03:56, 9 October 2010

2010-10-09T03:56:54Z

Adm: /* データ構造 */

2010-10-08T08:02:51Z

‎データ構造

Adm: /* マルコフモデル */

2010-10-08T06:40:40Z

‎マルコフモデル

Adm: /* アルゴリズム */

2010-10-08T06:34:29Z

‎アルゴリズム

Adm at 05:43, 8 October 2010

2010-10-08T05:43:40Z

Adm: New page: =ハードウェア= ==計算機のCPUについて== CPU (Central Processing Unit) とは中央演算処理装置のこと。略してプロセッサ。一番の基本は01のバイナリ...

2010-10-08T05:42:49Z

New page: =ハードウェア= ==計算機のCPUについて== CPU (Central Processing Unit) とは中央演算処理装置のこと。略してプロセッサ。一番の基本は01のバイナリ...

New page

=ハードウェア=
==計算機の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)やデータベースが開発されている。

===マルコフモデル===
状態遷移において、

=アルゴリズム=
===SVM===

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

@@ Line 53: / Line 53: @@
 * ツリー ...  代表的なものは二分木。構造を絵に描くと一番よく理解できる。 頂点数がn個ある場合、枝の数はn-1本になる。
 * ハッシュ ... 各要素の値から一定のルールで整数値（ハッシュ・キー）を計算し、その値を元に配列中に格納する手法。実用的。
 ==ソート・整列==
 * クイックソート ... 与えられた配列をだいたい半分にしながら並び替え。平均的計算量O(n log n), 最悪はO(n<sup>2</sup>)。実用上いちばん速いといわれる。

← Older revision		Revision as of 04:12, 24 November 2012
Line 35:		Line 35:

	リスト構造の欠点はアクセスの手間です。配列で10番目の要素を知りたい場合、配列であれば先頭アドレス＋データサイズ×10 によって値が格納されるアドレスを計算できますが、リストはこれができません。要素を１つずつ辿っていく必要が生じます。		リスト構造の欠点はアクセスの手間です。配列で10番目の要素を知りたい場合、配列であれば先頭アドレス＋データサイズ×10 によって値が格納されるアドレスを計算できますが、リストはこれができません。要素を１つずつ辿っていく必要が生じます。
		+
		+
		+	===スタックとキューの違い===
		+
		+	スタック、キューともリスト構造の一種です。一昔前になりますが、バネ式のコインケースという商品がありました。硬貨を一枚ずつ上から入れることができますが、取り出すときも上から一枚ずつしか取り出せません。これがスタックです。それに対し、一枚ずつ入れたものを入れた順に反対側から一枚ずつ取り出せるようにしたものがキューです。
		+
		+	{\| class="wikitable"
		+	! 名前 \|\| 動作 \|\| 用途
		+	\|-
		+	\| Stack \|\| 先入れ後出し (LIFO: last-in first-out) \|\| 深さ優先探索
		+	\|-
		+	\| Queue \|\| 先入れ先出し (FIFO: first-in first-out) \|\| 幅優先探索
		+	\|-
		+	\|}

	==探索に用いるもの==		==探索に用いるもの==

@@ Line 21: / Line 21: @@
 * スタック ... 今は昔になってしまった、ばね式のコイン入れの仕組み。最後に入れた要素が最初に取り出される。
 * キュー ... 先頭から入れ、末尾から取り出す筒のこと。最初に入れた要素から順に取り出す。
 ==探索に用いるもの==

@@ Line 4: / Line 4: @@
 一番の基本は01のバイナリ命令を解釈して演算を行う部分 (ALU: Arithmetic Logic Unit) と一時的に値を格納するレジスタが、主記憶メモリとバスでつながれた構造を持つ。
-一般的にマルチコアと呼ばれるプロセッサは、演算処理部分とレジスタのセットを複数が、単一の主記憶につながった構造を持つ。最近耳にするGPU (Graphics Processing Unit) とは、画像処理用にメモリ間のデータ転送や浮動小数点の演算を並列処理で高速化する装置のこと。以前はグラフィックアクセラレータなどと呼ばれていたものが汎用化したもの。
+一般的にマルチコアと呼ばれるプロセッサは、演算処理部分とレジスタのセットを複数が、単一の主記憶につながった構造を持つ。最近耳にするGPU (Graphics Processing Unit) は、画像処理用にメモリ間のデータ転送や浮動小数点の演算を並列処理で高速化する装置のこと。以前はグラフィックアクセラレータなどと呼ばれていたものが汎用化したもの。
 ==プログラムはどうやって動くのか==
-プログラミング言語（ソースコード）は人間が読んでわかる形であるが、最終的にCPUが扱うマシン語レベルではバイナリ(01)列である。人が扱う高級言語から、機械レベルの言語に「翻訳」する手法には大きく分けて2種類ある。
+プログラミング言語（ソースコード）は人間が読んでわかる形だが、最終的にCPUが扱う機械（マシン）語レベルではバイナリ(01)列。
 * コンパイラ ... ソースコードを特定の計算モデル上で解釈し、処理を最適化する翻訳
 * インタープリタ ... 原則、ソースコードのコマンドをマシン語レベルの処理にそのまま対応させる翻訳
-コンパイラとインタープリタは翻訳の方法であり、言語そのものと結びつく概念ではないが、プログラムを書いてすぐに動く言語(Lisp, Perl, Ruby, Python, etc.)と、一度「コンパイル」して実行形式ファイルを作成する言語(C, Java, Fortran, etc.)がある。
+コンパイラとインタープリタは翻訳手法であり、言語そのものと結びつく概念ではない。
 =データ構造=
+計算機上にデータを記述する際に、利用形態にあわせて適切な表現法を用いると効率よく処理できる。
-==リスト表現==
+==基本データ構造==
-===スタック===
+* 配列 ... 決まった個数のデータを格納する。データのアドレス（番地）は整数で指定。
-今は昔になってしまった、ばね式のコイン入れの仕組み。最後に入れた要素が最初に取り出される。
+* リスト ... 個数が大きく変化するにあわせて伸長・収縮が自在にできる。
-===キュー===
+* スタック ... 今は昔になってしまった、ばね式のコイン入れの仕組み。最後に入れた要素が最初に取り出される。
-先頭から要素を入れ、末尾から要素を取り出す筒の仕組み。入れた順番のまま、最初に入れた要素から順に取り出される。
+* キュー ... 先頭から入れ、末尾から取り出す筒のこと。最初に入れた要素から順に取り出す。
 ==探索に用いるもの==
-===ツリー===
+* ツリー ...  代表的なものは二分木。構造を絵に描くと一番よく理解できる。 頂点数がn個ある場合、枝の数はn-1本になる。
-代表的なものは二分木。構造を絵に描くと一番よく理解できる。
+* ハッシュ ... 各要素の値から一定のルールで整数値（ハッシュ・キー）を計算し、その値を元に配列中に格納する手法。実用的。
-頂点数がn個ある場合、枝の数はn-1本になる。
+==ソート・整列==
+* クイックソート ... 与えられた配列をだいたい半分にしながら並び替え。平均的計算量O(n log n), 最悪はO(n<sup>2</sup>)。実用上いちばん速いといわれる。
-===ハッシュ===
+* マージソート　... 与えられた配列を正確に半分にしながら並び替え。計算量は常にO(n log n)。実用。
-要素それぞれの値から一定のルールで整数値（ハッシュ・キー）を計算し、その値を元に配列中に格納する手法。たいへん実用的。
+* バブルソート ... 配列中で隣り合った組を発見するたびに入れ替えをおこなう。計算量はO(n<sup>2</sup>)で非実用。
-==大量データの表現・格納==
+==大量データの表現・格納・処理==
 ===関係データベース===
 エクセルのような表を組み合わせてデータを表現する。表を作る際に最低限必要な情報だけを記述し、残りは表計算によって導出する。関係演算と呼ばれる系では、集合演算に加えて、表からの行・列の選択(select, project)、表の結合(join)により汎用的な論理体系と同等の表現能力を持つことが知られている。
@@ Line 35: / Line 38: @@
 まとまったデータをカプセル化して隠蔽する概念をオブジェクト指向と呼ぶ。
 各オブジェクトは、その中身にアクセスして処理するためのメソッドを備えており、この概念を取り入れたプログラミング言語 (例えばC&#43;&#43;, Java)やデータベースが開発されている。
 ==状態遷移==
@@ Line 42: / Line 54: @@
 ===マルコフ連鎖 (Markov chain)===
 ○と→を結んだ状態遷移で、次に移動する場所を現在いる状態のみに依存して（つまり今までどの状態を巡ってきたかを無視して）決定する場合をマルコフ連鎖という。

@@ Line 29: / Line 29: @@
 各オブジェクトは、その中身にアクセスして処理するためのメソッドを備えており、この概念を取り入れたプログラミング言語 (例えばC&#43;&#43;, Java)やデータベースが開発されている。
-===マルコフモデル===
+===マルコフ連鎖 (Markov chain)===
-状態遷移において、
+○と→を結んだ状態遷移で、次に移動する場所を現在いる状態のみに依存して（つまり今までどの状態を巡ってきたかを無視して）決定する場合をマルコフ連鎖という。
 =アルゴリズム=

← Older revision		Revision as of 06:34, 8 October 2010
Line 35:		Line 35:
	==ソート==		==ソート==

−	===SVM===	+	==クラスタリング==
		+	===k-近傍 (nearest neighbor)===
		+	各データから最も距離が近いk個を選んでクラス分けをするもの
		+
		+	===サポートベクトルマシン (SVM)===
		+	平面上にばらつく2群を直線で分けるには、両群の各点からその直線におろした垂線の足の長さを最大化する場合が最適になる（マージン最大化）。これを多次元に拡張し、マージンを最大にする超平面を探すアルゴリズムをSVMという。
		+	近年はデータ集合を非常に高次元の特徴空間に射影し（射影する関数をカーネル関数と呼ぶ）、特徴空間上で超平面による分割をおこなう手法が主流。

@@ Line 13: / Line 13: @@
 =データ構造=
-==データの探索==
+==探索==
 ===ツリー===
 代表的なものは二分木。構造を絵に描くと一番よく理解できる。
@@ Line 33: / Line 33: @@
 =アルゴリズム=
 ===SVM===