ALG2011-01

情報工学概論
(アルゴリズムとデータ構造)
アルゴリズムの概念
～オーダーと計算量～
・コンピュータの基礎
・アルゴリズムの概念
・オーダーの定義と計算量
・ NP完全問題
自己紹介
名前：定兼邦彦
所属：国立情報学研究所 & 総合研究大学院大学
経歴： 1991年理1入学，2000年理学系研究科情報科学専攻終了
2000年東北大学情報科学研究科助手
2003年九州大学システム情報科学研究院助教授
2009年国立情報学研究所准教授
研究分野：データ圧縮，データ構造，情報検索
最近の研究：
• 簡潔データ構造
• 文字列検索のデータ構造
• Webグラフ構造の解析，探索
目的・成績評価・参考書
・アルゴリズム理論による設計は、大規模なデータを高速で処理
する際に特に有効
・部品 (データ構造) を組み合わせてプログラムを作るだけでなく，
部品の中身を理解する
・成績評価はレポート
・参考書：アルゴリズムイントロダクション(近代科学社)など
・メール： [email protected]
ホームページ： http://researchmap.jp/sada/
授業の内容
・コンピュータの仕組み、プログラムの仕組み
CPU、メモリ、OS、メモリ管理、命令、変数
・データ構造（データの記憶方法）
スタック、キュー、ヒープ、２分木、ハッシュ
・基本的なアルゴリズム
再帰呼び出し、分割統治、列挙、動的計画法、ソート、文字列マ
ッチング
・応用アルゴリズム
計算幾何，行列演算，索引構造
コンピュータの基礎
コンピュータの基礎
・コンピュータはいくつかの部品で成り立っているが、メインの
部分はCPUとよばれる演算装置
・車でいえばエンジンのようなもので、これがあるかないか
が、コンピュータであるかどうかの境目のようなもの
・ CPUの他にメモリという、数値を複数記録できる装置がある
CPU
メモリ
プログラム
・コンピュータができることは、
－メモリから数値を読むこと、および書くこと
－足す引く掛けるなどの算術演算をすること
－数の大小の判定をして、行う処理を変えること
・これらの操作のことを命令という
・命令をどのように行うかは、やはりメモリに記録する。これを
プログラムと言う
・プログラムに書かれたとおりに処理を行わせることを、プロ
グラムを実行するという
CPU
メモリ
プログラムの実行
・プログラムは、メモリに書いてある命令を順次実行する
・命令は数値になっていて、それぞれの数値に機能が割当て
られている
・処理中に、次から行う処理の場所を変更することができる
・条件によって処理を変える場合には、この機能を使って、条
件を満たす場合のみ次から実行する命令を変える（条件
分岐という）
CPU
メモリ
プログラミング言語
・ CPUの命令は数値。しかも、１つ１つの処理は非常に単純（これ
をマシン語、あるいは機械語という）
・これを組合せてプログラムを作るのは、かなり大変
・そこで、通常はもう少し抽象化して、人間に見やすくした「高級
言語」とよばれるものを使う
（C，JAVA，Perl, Ruby, Basic, シェルスクリプトなど）
・高級言語で書かれたプログラムを、CPUに実行させるには、プ
ログラムをいったんマシン語に翻訳する（この作業をコンパイ
ルという）か、プログラムどおりの処理をするプログラム（インタ
ープリタという）を使う
概念的な例
１：場所 15 に 0 を書き込む
２：場所 16 に 2 を書き込む
３：場所 15 と 16 の値を足し、それを場所 15 に書き込む
４：場所 17 の値が 10 以上ならば、８へいく
５：３へ行く
８：．．．
・ 3－5のように局所的に繰り返して実行される部分をループ
という
CPU
メモリ
メモリのアクセス
・メモリは1バイトずつ数値が記憶されている
・メモリには、記憶場所に0から始まる番号がついていて、好きな場
所のデータに一手でアクセス（書き込み／読み出し）できる
・このように、好きな場所に一手でアクセスできるメモリをランダムア
クセスメモリという
・ランダムアクセスでない記憶装置は、例えばCDとかビデオテープ
１０１１０１０１
キャッシュメモリ
・コンピュータのメモリのアクセス速度は、演算速度よりかなり遅
い（10倍以上）
・そのため、メモリを読み出すときは、しばらく演算をとめて待つこ
とになる。次の命令を読むときもそう。
・そこで、メモリを読むときはまとめてたくさん読む
・読んだメモリは、CPUに直結した速いメモリにしばらく取っておく
（この操作をキャッシュ、キャッシュに使うメモリをキャッシュメモ
リという）
キャッシュ
CPU
メモリ
メモリ
ディスク
キャッシュによる高速化
・メモリアクセスが、キャッシュに入っている場所ばかりだと計算は
大幅に速くなる
 キャッシュの効率を高めるような保存法が重要
 引き続いて、キャッシュの中を見ることが多い計算をさせると、
高速化できる
・ディスクのアクセスにも、同じようにキャッシュを使う
CPU直結メモリの代わりに、通常のメモリを使う。メモリのほうが
ディスクよりアクセス速度が速いので、高速化できる
CPU
メモリ
HDD
変数
・高級言語では、数値を記憶する際に変数というものを使う
・変数には、何か値が１つ入る
・コンパイルして実行するときに、各変数にメモリの場所が割当て
られる。以後、変数をアクセスするときには、その場所にアクセ
スするようになる
配列
・大量のデータを扱う場合、全てのデータに直接変数を割当てる
のは、大変。プログラムを書くのも大変
・そこで、配列を使う
・配列を使うと、変数＋添え字、という形でデータにアクセスでき
る。添え字のところは変数を入れられるので、例えば、100個の
変数を0にする、といった作業も、ループを使って楽にできる
A[0] = 1
A[1] = 0
A[2] = 1
…
１０１１０１０１
OS
・コンピュータは、機種によって、入出力の方法が違う
・ディスプレイに文字を書くためには、文字の形になるよう、デー
タを書き込まなければいけない
・こういった、ハードウェアによる違いを吸収する、低レベルの処
理を行う、実行するプログラムの管理、などをするプログラム
がある
・これをOSという（Windows、UNIXなど）
・固有の接続機器を、標準的な入出力方法を用いて扱うプログラ
ムをデバイスドライバという
・メモリの管理もOSが行う
メモリの確保
・普通、コンピュータでは、複数のプログラムが同時に実行されて
いる（含デバイスドライバ）
・そのため、メモリの適当な場所に適当に数値を書き込むと、他の
プログラムの実行を阻害する（下手をすると動きが止まる）
⇒まともなOSはそのような動作を禁止している
・そのため、メモリを使いたいときには、OSにお願いして、必要な
分だけ使える場所をあてがってもらう（これをメモリを確保すると
いう）
数値の表現（バイト）
・メモリは数値を覚えられるが、実は 0 と 1 しか覚えられない
（ビットという）
・しかし、大量に 01 の数値を記憶できる
・実際は、01しか記憶できないのでは用をなさないので、01
の数値を8個セットにして、それを2進数とみなす。（0-255が
表現できる）
－これを１バイトという
・足す引く掛けるの算術演算の結果、 2進数9桁目に繰り上
がったとき、あるいはマイナスになったときは、その部分は
無視して計算する
１０１１０１０１
128+32+16+4+1 = 181
データの記憶
・メモリには、記録されている数値が整数か、文字か、といった、
データの種類を覚えておく機能はないので（数値として付加的
に記録することはできるが）、自分（プログラム）が何を書いた
か管理する
・つまり、「何のデータはどこに書いた」ということを決めておく。プ
ログラムでは、データの計算をする際には、場所を決めて書く
・常に0か1の値が書いてあるので、「書き込まれていない」という
ことも検出できない
点数
点数
20
点数
20
20
１０１１０１０１
整数小数文字
－整数： 01の数値をいくつかセットにして、それを2進数とみなす。
通常、32ビット＝ 4バイト。 (0-40億くらい)
－実数：整数と小数点の位置をセットで記憶。小数点は2進数の
位置で記憶。通常、整数が56ビット、小数点が8ビット（256桁分）
演算誤差が生じる (1/3 * 3 = 0.999999…)
－文字：文字と整数値を対応させたコード表があり、それを使っ
て整数値として記憶する
１０１１０１０１
+
128+32+16+4+1 = 181
０１０１
(4+1)/16 = 0.3125
負の数の表現（バイト）
－負の数：最上位のビットが1になった数は、256を引いて、
負の数とみなす。通常の数と思って計算したときと、負の
数と思って計算したときの結果が同じなので、結果を変換
する必要がない
例： 255 は-1 になる。1を足すと、
1111111 + 1 = 100000000。9桁目は無視するので、0
これは、実際の -1 +1 の答えと一致する
例： -2 は 254、-5 は 251。両者を足すと、505。256の剰余を
求めると249。これは-7に対応。両者を掛けると 63754。剰
余を求めると 10。
C言語では
• char: 符号ありバイト
-128 から 127 を表す
• unsigned char: 符号なしバイト
0 から 255を表す
桁あふれ (overflow) に注意
符号なし: 30 * 5 = 150
符号あり: 30 * 5 = -106 間違い
アルゴリズム
• アルゴリズムとは
– 入力 (input): ある値(の集合)
– 出力(output): ある値(の集合)
– 明確に定義された計算手続き
• 明確に定義された計算問題を解くための道具
• 問題の記述とは
– 望むべき入出力関係を指定すること
ソーティング問題の形式的定
義
• 入力: n 個の数の列〈a1, a2, ..., an〉
• 出力: a’1 a’2  …  a’n であるような入力
列の置換〈a’1, a’2, ..., a’n〉
• 入力例 (具体例, instance)
– 入力〈31, 41, 59, 26, 41,58〉
– 出力〈26, 31, 41, 41, 58, 59〉
ソーティング
• 計算機科学における基本的な操作
• 多くのアルゴリズムが開発されている
• 入力例によって優劣が異なる
– ソートすべきデータの数
– どの程度までデータがすでにソートされているか
– 用いる記憶装置の種類 (主記憶, ディスク, テープ)
アルゴリズムの正しさ
• アルゴリズムが正しい (correct)
⇒全ての具体例に対して正しい出力とともに停止する
– 与えられた計算問題を解く (solve) という．
• 正しくないアルゴリズム
– ある具体例に対して望ましい答えを出力せずに停止
– ある具体例に対して全く停止しない
• 確率的アルゴリズムも存在
– 高い確率で正しい答えを出す or 早く停止する
挿入ソート
• 入力: 長さ n の配列 A[0..n-1]
• 出力: ソートされた配列 A[0..n-1]
void INSERTION-SORT(data *A, int n)
{
data key;
int i, j;
for (j=1; j < n; j++) {
key = A[j];
// A[j] をソート列 A[0..j-1] に挿入する
i = j – 1;
while (i >= 0 && A[i] > key) {
A[i+1] = A[i];
i = i -1;
}
A[i+1] = key;
}
}
5
2
4
6
1
3
2
5
4
6
1
3
2
4
5
6
1
3
2
4
5
6
1
3
1
2
4
5
6
3
1
2
3
4
5
6
入力
出力
C言語の場合
#include <stdio.h>
#include <stdlib.h>
typedef int data;
void INSERTION_SORT(data *A, int n)
{
data key;
int i, j;
for (j=1; j < n; j++) {
key = A[j];
// A[j] をソート列 A[0..j-1] に挿入する
i = j - 1;
while (i >= 0 && A[i] > key) {
A[i+1] = A[i];
i = i - 1;
}
A[i+1] = key;
}
}
int main(int argc, char *argv[])
{
data A[14] =
{27,17,3,16,13,10,1,5,7,12,4,8,9,0};
int i,n;
n = 14;
INSERTION_SORT(A,n);
for (i=0;i<n;i++) printf("%d ",A[i]);
printf("\n");
}
Rubyの場合
def insertion_sort(a)
for j in 1..(a.length-1) do
key = a[j]
i = j-1
while i >= 0 && a[i] > key do
a[i+1] = a[i]
i = i-1
end
a[i+1] = key
end
end
a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0]
insertion_sort(a)
pa
Fortran 90の場合
program main
do j = s+1, t
key = a(j)
i = j-1
do
if (.not. (i >= s .and. a(i) > key)) exit
a(i+1) = a(i)
i=i-1
end do
a(i+1) = key
end do
end subroutine insertionsort
integer :: a(14) = (/ 27,17,3,
16,13,10,1,5,7,12,4,8,9,0 /)
print *, "a = ", a
print *, "insertion sort"
call insertionsort(a)
print *, "a = ", a
contains
subroutine insertionsort(a)
integer a(:)
integer i, j, key
integer s, t
end program main
s = lbound(a,1); t = ubound(a,1)
アルゴリズムの解析
• アルゴリズムの実行に必要な資源を予測したい
– メモリ量
– 通信バンド幅, 論理ゲート
– 計算時間
• 解析を行うにはモデルを仮定する必要がある
• RAM (random access machine) モデル
– 命令は1つずつ実行
– どのメモリ番地も一定の時間で読み書き可
挿入ソートの解析
• INSERTION-SORTの手続きに要する時間は入
力によって変わる.
• 一般に, プログラムの実行時間は入力のサイズ
の関数で表す.
• 入力サイズの定義
– ソーティング, 離散フーリエ変換など: データ数
– 整数の積の計算など: 入力のビット数
– グラフの問題: グラフの頂点と辺の数
実行時間の定義
• 実行される基本的な演算の回数
• プログラムの第 i 行の実行に ci 時間かかるとす
る (ci は定数)
• 注: サブルーチン呼び出しは定数時間ではない
void INSERTION-SORT(data *A, int n)
{
data key;
int i, j;
for (j=2; j <= n; j++) {
key = A[j];
// A[j] をソート列 A[1..j-1] に挿入する
i = j – 1;
コスト
回数
c1
c2
n
n-1
c4
n-1
n
while (i > 0 && A[i] > key) {
c5
t
j 2
n
A[i+1] = A[i];
c6
 (t
j
 1)
 (t
j
 1)
j 2
n
i = i -1;
c7
j 2
}
A[i+1] = key;
c8
j
n-1
}
}
tj : while ループが j の値に対して実行される回数
INSERTION-SORTの実行時間
T (n)  c1n  c2 (n  1)  c4 (n  1)
n
n
n
j 2
j 2
j 2
 c5  t j  c6  (t j  1)  c7  (t j  1)  c8 (n  1)
tj の値は入力によって変化する.
最良の場合 = 配列が全てソートされている場合
tj = 1
T (n)  c1n  c2 (n  1)  c4 (n  1)  c5 (n  1)  c8 (n  1)
 (c1  c2  c4  c5  c8 )n  (c2  c4  c5  c8 )
 an  b
n の線形関数 (linear function)
最悪の場合
• 配列が逆順にソートされている場合
– tj = j
 n(n  1) 
T (n)  c1n  c2 (n  1)  c4 (n  1)  c5 
 1
 2

 n(n  1) 
 n(n  1) 
 c6 
 1  c7 
 1  c8 (n  1)
 2

 2

 an  bn  c
2
n の2次関数 (quadratic function)
時間計算量 (Time
Complexity)
• アルゴリズムの実行時間は入力に依存する
• アルゴリズムの解析では通常最悪時の実行時
間を考える
– 最悪時の実行時間は任意の入力に対する実行時
間の上界
– 最悪時の実行時間を保証する
– 「最悪時」は頻繁に起きる (データベース検索など)
– 平均時も最悪時と同じくらい悪い (挿入ソートで数
をランダムに挿入)
増加のオーダ
• 実行時間の解析を容易にするための抽象化
–
–
–
–
–
各行の実行時間 (コスト) を定数 ci とする
最悪の実行時間を an2+bn+c と表す
実行時間の増加率をみるには主要項 an2 で十分
定数係数も無視
(n2) と表す
• 挿入ソートは (n2) という最悪実行時間を持つ
• あるアルゴリズムが他より効率がよい
⇔最悪実行時間の増加率が低い
関数のオーダ
• アルゴリズムの効率を実行時間のオーダ
で特徴付け, 相対的な比較を行う
• 入力サイズ n が大きいときの挙動を知りた
い
• アルゴリズムの漸近的 (asymptotic) な効
率を調べる
漸近記号
-記法
• ある関数 g(n) に対し, (g(n)) は次のような集
合と定義する
(g(n)) = {f(n): 全ての n  n0に対して
0c1 g(n)  f(n)  c2 g(n) となるような
正の定数c1 , c2 , n0 が存在}
( g (n))  { f (n) : c1  0c2  0n0  0n  n0
0  c1 g (n)  f (n)  c2 g (n)}
• f(n) = (g(n)) は f(n)  (g(n)) を意味する
• 2n2+3n+1 = 2n2 + (n) という表現も用いる
1 2
n  3n  (n 2 )を示す
2
1 2
全ての n  n0に対して c1n  n  3n  c2 n 2となればいい
2
1 2
2
2
n で割ると c1n  n  3n  c2 n 2
2
1
c2  なら n  1に対して右辺の不等号が成立
2
1
c1  なら n  7に対して左辺の不等号が成立
14
1
1
よって c1  , c2  , n0  7とすれば成立
14
2
2
6n  (n )を背理法で示す
3
2
全ての n  n0に対して 6n 3  c2 n 2であるような
定数c2 , n0が存在したとする
任意の大きな nに対して 6n  c2となり矛盾
f (n)  an 2  bn  c  (n 2 )
d
任意の d次多項式p(n)   ai n iに対し (ad  0)
i 0
p ( n )  ( n d )
O-記法
• ある関数 g(n) に対し, O(g(n)) は次のような集
合と定義する
O(g(n)) = {f(n): 全ての n  n0に対して
0  f(n)  c g(n) となるような
正の定数c, n0 が存在}
O( g (n))  { f (n) : c  0n0  0n  n0
0  f (n)  cg (n)}
• f(n) = (g(n)) ならば f(n) = O(g(n))
• n = O(n2) も正しい表現
• 挿入ソートの実行時間はO(n2)…正解
• 挿入ソートの実行時間は(n2)…間違い
– ソートされた入力に対しては(n)
• 実行時間がO(n2)であるという場合, 最悪実行
時間について言っている
– 実行時間は入力データに依存するため
– 最悪実行時間はデータ数 n のみに依存
-記法
• ある関数 g(n) に対し, (g(n)) は次のような
集合と定義する
 (g(n)) = {f(n): 全ての n  n0に対して
0  c g(n)  f(n) となるような
正の定数c, n0 が存在}
O( g (n))  { f (n) : c  0n0  0n  n0
0  cg (n)  f (n)}
• f (n), g(n) に対して f(n) = (g(n)) であるため
の必要十分条件は
f(n) = O(g(n)) かつ f(n) = (g(n))
• -記法は下界を表す
• 挿入ソートの最良の実行時間は(n)とは
– このアルゴリズムではどのような入力に対して
も n に比例した時間が必ず必要という意味
• アルゴリズムの実行時間が(n2)とは
– どのような入力に対しても少なくとも n2 に比例
する時間がかかるという意味
o-記法 (リトルオー)
• ある関数 g(n) に対し, o(g(n)) は次のような集
合と定義する
o(g(n)) = {f(n): 任意の定数 c > 0 に対し
ある定数 n0 が存在し,
全ての n  n0に対して
0  f(n)  c g(n)}
o( g (n))  { f (n) : c  0n0  0n  n0
0  f (n)  cg (n)}
f ( n)
lim
 0が成り立つ
n  g ( n)
• -記法
(g(n)) = {f(n): 任意の定数 c > 0 に対し
ある定数 n0 が存在し,
全ての n  n0に対して
0  c g(n)  f(n)}
• n2/2 = (n)
• n2/2  (n2)
f (n)   ( g (n))  g (n)  o( f (n))
f ( n)
lim
 が成り立つ
n  g ( n)

Download Report