● UTF-16

多言語の文字コード

画像の符号化

●

画像を数字に

– 画像を細かい点

(pixel)

の集まりで表現する

ピクセル

色の表現

●

加法混色による色の表現

– 赤

(R)

緑

(G)

青

(B)

の重ね合わせで 色を表現する

– それぞれの色の明るさの段階

●

1

ビット＝

2

段階

(ON/OFF)→8

色

●

8

ビット

=256

段階→

16777216

色

–

RGB

それぞれを

8

ビット

=16

進数

2

桁で表現

●

(R,G,B)=(6B,23,94)→#6b2394

画像符号化

●

画像は情報量が多い

–

1024×768

サイズで

1

ピクセル

3

バイト

→

1

画像あたり

2.3M

バイト

●

画像の圧縮：画像のサイズをできるだけ縮める

– 無圧縮

●

BMP

など

– 可逆圧縮

:

圧縮前の画像に戻せる

●

GIF, PNG

など

● 圧縮率は低い

– 不可逆圧縮：圧縮前の画像に戻らない

●

JPEG, JPEG2000

など

BMP 901kbyte JPEG 102kbyte

JPEG 23kbyte JPEG 11kbyte

音声の符号化

●

音は空気の波

– マイクロフォンで電圧変化に変換される

●

時間的に連続、取る値も連続

– 時間と電圧を離散化→整数列に変換

t

V

標本化と量子化

●

時間的に離散化→標本化

●

電圧を離散化→量子化

標本化と量子化

●

時間的に離散化→標本化

●

電圧を離散化→量子化

標本化と量子化

●

標本化を細かくするほど「高周波数成分」まで再現 できる

●

量子化を細かくするほど「量子化雑音」を減らすこ

とができる

アルゴリズム、計算モデル、計算量

●

コンピュータに計算させるなら、速いほうがいい

– どうやって計算させるのか？⇒アルゴリズム（算法）

● 解を求めるための計算手順

– それはどのくらい早いのか？⇒計算量

● 実行するコンピュータの違いを吸収⇒計算モデル

● 絶対的な速さは求めにくい⇒漸近的計算量

アルゴリズム (algorithm)

●

問題と入力が与えられた時に、解を求める方法

– ユークリッドの互除法：２数から最大公約数を求める

– ２次方程式の解の公式：係数から解を求める

●

同じ問題に対して複数のアルゴリズムがありうる

– 数学の問題に複数の解法があるのと同じ

●

アルゴリズムがない問題もある

– 解が永遠に求まらない可能性がある問題など

アルゴリズムの例

●

ユークリッドの互除法

1. ２つの数を

m,n

とし、

m≥n

とする

2.n=0

ならば、

m

が答えとなり、終了

3.(m, n)←(n, m mod n)

　　※

mod

は剰余

4.2

に戻る

// C言語による記述例

// m>=0, n>=0, m >= nでなければならない int Euclid(int m, int n) {

int new_m;

while (n > 0) { new_m = n;

n = m % n;

m = new_m;

}

return m;

計算の「大変さ」を測る

●

どうやって測るのか

– 計算にかかる時間（ベンチマーク）：

直接的だが問題が多い

● コンピュータによって変化する（

CPU

、クロック、メモリ量など）

● 入力によって変化する

– 入力が多ければ一般に時間がかかる

– ある量の入力サイズで突然遅くなることがある

– コンピュータによって処理できるサイズに上限がある

● 以上から、「絶対的な指標」としては不適当

漸近的計算量と計算モデル

●

実際のコンピュータではなく「計算モデル」を想定

– 理想化されたコンピュータ（メモリの制約がない、等）

●

計算時間ではなく「ステップ数」を対象とする

– ステップ数はコンピュータの種類への依存が少ない

●

ステップ数そのものではなく

「入力の増加に伴うステップ数の増え方」

を考える（漸近的計算量）

– 計算時間が問題なのはデータが多い時なので、データ が巨大になったときどれだけ遅いかを重視

計算モデル

●

理想化された計算機械

– さまざまなものがあるが、最も性能が高いものは、どれ も計算能力は同じであることが証明されている

● チューリングマシン

(TM)

● ランダムアクセスマシン

(RAM)

● 帰納的関数

チューリングマシン

●

Alan Turing による最初の計算モデル

0 ; B

A = 1 = A + 2 ; F

状態

ヘッド

テープ 無限に長い

現在の「状態」と、ヘッドが 読んだ文字に応じて、次の どれかの動作をする

● ヘッドの位置のテープに 指定された文字を書く

● ヘッドを右に１つ動かす

● ヘッドを左に１つ動かす 動作したら次の状態に遷移 する

ランダムアクセスマシン

●

通常のコンピュータの抽象化

– メモリ（レジスタ）があり、アドレスの番号で指定できる

– メモリには任意の自然数が格納できる

– メモリは必要に応じて充分大きい

– メモリはそのアドレスの番号によらず一定時間で読み 書きできる（ランダムアクセス）

– メモリの内容に対して基本的な演算をして、またメモリ に格納することができる

– メモリの内容をアドレスだと解釈して、それが示すメモリ の内容が読み書きできる（間接アドレッシング）

ステップ数

●

計算をするときに行う基本的な演算の回数

●

なにが「基本的な演算か」は場合によって異なる

– 比較演算

– 値のコピー

– 加減算

– 乗除算

漸近的計算量

●

「ある入力に対するステップ数」ではなく，「入力の 変化に対するステップ数の変化」を見る

– 入力サイズが

2

倍になった時に

● ステップ数同じ

● ステップ数が定数回増える

● ステップ数が

2

倍

● ステップ数が

4

倍

● ステップ数が

8

倍

● ステップ数が

2

乗

O ( 1 )

O ( log n ) O ( n )

O ( n

²

) O ( n

³

) O ( 2

ⁿ

)

オーダー記号

オーダー記号

●

入力のサイズに対してステップ数がどのように大き くなるかを示す記号

–

O, Ω, Θ

などの種類がある

●

数学的定義

– 入力のサイズを

n

，ステップ数を

T(n)

とする

– 関数

f (n)

について，定数

N

と

α

が存在して，

n ≥ N → T ( n )≤α f ( n )

アルゴリズムの（漸近的）計算量は

O( f (n))

オーダー記号

α f ( n )

T ( n )

N n

こちらでは

T ( n )≤α f ( n )

O ( f ( n ))

問題のサイズが十分に大きいときのステップ数の上限

その他のオーダー記号

α f ( n ) T ( n )

N n

T ( n )≥α f ( n )

Ω( f ( n ))

問題のサイズが十分 に大きいときのステッ

α

₂

f ( n ) T ( n )

N n

α

₁

f ( n )≤ T ( n )≤α

₂

f ( n )

Θ( f ( n ))

α

₁

f ( n )

問題のサイズが十分 に大きいときのステッ

オーダーの例

T ( n )= 3 n + 10 O ( n ) (α= 4, N = 10 ) T ( n )= n

³

+ 2 n + 100 O ( n

³

) (α= 2, N = 5 )

T (n)

の中で最も早く発散する項を

f (n)

とすると，

O( f (n))

多項式時間と指数時間

●

多項式時間アルゴリズムの計算量

●

指数時間アルゴリズムの計算量

●

指数時間アルゴリズムの計算時間は多項式時間 アルゴリズムよりも遥かに早く増加する

– 大きい

n

についてはほとんど実用にならない

O ( n

^k

)

O ( k

ⁿ

)

最悪時計算量と平均時計算量

●

入力によって計算量が異なる場合がある

– 例：データを探索する場合

● たまたま最初に捜したところに目的のデータがあれば，すぐ に終わる

● 目的のデータが最後まで見つからなければ時間がかかる

●

最悪時計算量

– もっとも都合が悪い入力に対してかかる計算量

●

平均時計算量

– 入力に対して仮定を置いたとき（たとえば探索される要 素がある位置にある確率が一様）の計算量の期待値

探索問題

●

同じ問題に対して異なる計算量のアルゴリズムが ある典型的な例

– 探索（データの中に特定の要素が含まれるか調べる）

– ソート（データを順番に並べ替える）

– 最短経路探索

●

ここでは簡単な探索問題を扱う

– データ

x

₁

, x

₂

, ..., x

_nの中に

y

があるかどうか探す

– 線形探索（簡単な方法）

– 二分探索

線形探索

●

最も簡単な探索法

– 最初から順番に捜す．見つかったら終わり

線形探索：

i

を

1

から

n

まで変化させながら，

　　もし

x[i]=y

ならば「見つかった」を返し，終了 を繰り返す

「見つからなかった」を返す

i

線形探索の計算量

●

最悪時計算量

–

●

平均時計算量

– どの位置で見つかる確率も同じだと仮定

–

i

番目に見つかる確率：

T ( n )= n

P ( i )= 1 / n

̄

T ( n )= ∑

i=1 n

P ( i ) i = 1

n ∑

i=1 n

i = n ( n + 1 )

2 n = n + 1 2 O ( n )

O ( n )

もっと高速な探索

●

もしデータが順番に並んでいたとしたら？

– 小さいデータ→大きいデータ：昇順

(ascending)

– 大きいデータ→小さいデータ：降順

(descending)

●

最大値と最小値はすぐわかる

– 探索値が小さければ前の方を，大きければ後ろのほう を探せばよい

●

高速な探索

– 探索値がデータの前半と後半のどちらにあるのかを調 べる

二分探索

●

入力 x

₁

≤ x

₂

≤ ...≤ x

_n

と仮定する

●

真ん中あたりの値を調べる ^h = ⌊ ^{1 + 2 n} ⌋

x

_h

= y x

_h

< y x

_h

> y

探索値が見つかった

探索値は中央より後にある 探索値は中央より前にある

次の探索範囲が半分になる

二分探索

1 2 5 8 11 16 19 20 21 29 16

探索値

右にある

1 2 5 8 11 16 19 20 21 29

左にある

1 2 5 8 11 16 19 20 21 29

当たり

二分探索

二分探索：

b←1, e←n

繰り返し，

　　

h←(b+e)/2

　　もし

x[h]=y

ならば，「見つかった」を返し，終了

　　そうでなく

b≥e

ならば，「見つからなかった」を返し，終了 　　そうでなく

x[h]<y

ならば，

b←h+1

　　そうでなければ

e←h-1

を実行する

ドキュメント内 プログラマから見えるCPU 一番下のレベルでコンピュータ上のプログラムがど のように表現されているかを理解する プログラムがどう表現されているか プログラムはコンピュータのメモリ上に載っている コンピュータのメモリには数字しか格納できない したがってプログラムは数字である どう表現されているのか 数 (ページ 160-193)