● 先週の授業のキーポイント 【アルゴリズムとは】

● 先週の授業のキーポイント

【アルゴリズムとは】

• 「アルゴリズム」(Algorithm)とは,特定の目的を達成するための手順を明示したものであり, あらかじめ指定された条件をみたす全ての入力に対して,以下の条件をみたす必要がある.

1. 手順のひとつひとつが「決定的」であること.

2. 手順が必ず実行できること.

3. 有限回の手順で終了すること.

「決定的」とは,「確率1/2でどちらかを行う」などという曖昧な部分がないことを指し,「必ず 実行できる」とは,例えば,場合によっては0で除算を行うような状況が発生しないことを指す.

• プログラム言語でアルゴリズムを実現することを目的とする場合には,「入力」と「出力」が明 示されている必要があり,アルゴリズムに指定された条件をみたす全ての入力に対して,正しい 出力が得られること,および上のアルゴリズムの条件を満たしていることを証明する必要がある.

• アルゴリズムの典型的な例は,次にあげる「ユークリッドの互除法」である.

• アルゴリズムの「計算量」とは,アルゴリズムが終了するまでの間に必要なステップ数（繰り返 し回数,全計算回数など）を,入力されたデータの関数としてあらわしたものである. 一般には, 入力データの値やデータ量が非常に大きくなったときの漸近的な振舞いを示す.

【ユークリッドの互除法】

「ユークリッドの互除法」(Euclidean Algorithm)とは,正の整数a,bの最大公約数gcd(a, b)を 求めるためのアルゴリズムである.

• ユークリッドの互除法は, 次の事実に基づく.

任意の正の整数 a,b と, 任意の整数k に対して, a−kb >0 ならば gcd(a, b) = gcd(b, a−kb) が成り立つ.

• a₀=a,a₁=b とおき,順次割り算を以下のように繰り返す.

a₀=a₁q₁+a₂, a1=a2q2+a3,

...

a_j−1=a_jq_j+a_j+1, ...

a_k−1=a_kq_k.

ここで, q_i は a_i−1 をa_i で割った商,a_j+1 は剰余である. このとき,上の事実から gcd(a0, a1) = gcd(a1, a2) =· · ·= gcd(aj, aj+1) = gcd(ak−1, ak) =ak, a₁> a₂>· · ·> a_j>· · ·> a_k ≥0

が成り立つ.

• 数列{ai}は非負整数の真に単調な減少列であるので,上の除算の列は有限回で ak+1= 0 に到 達する. このとき,

gcd(a, b) = gcd(a0, a1) =ak

が成り立つ.

• これらのことを用いると,ユークリッドの互除法のアルゴリズムは次のようにあわらすことがで きる.

☆ 入力 非負整数a0,a1.

☆ 出力 入力されたa0,a1 の最大公約数gcd(a0, a1).

☆ 手順

1. k= 0とする.

2. a_k−1 を a_k で割った剰余a_k+1 を求める. すなわち,a_k−1=a_kq_k+a_k+1 をみたすq_k, ak+1, 0≤ak+1< ak を求める.

3. ak+1= 0ならば,i←i+ 1 として2に戻る.

この手順が終了したとき, a_k+1 が求めるべき最大公約数である.

• ユークリッドの互除法は,

a₁> a₂>· · ·> a_j >· · ·> a_k≥0 が成り立つことから,有限回のステップで終了することがわかる. また,

gcd(a0, a1) = gcd(a1, a2) =· · ·= gcd(aj, aj+1) = gcd(ak−1, ak) =ak

であることから,正しい結果が得られていることを帰納的に証明することができる.

• 最大公約数を求めるために,ユークリッドの互除法が優れている理由は,その計算量が高速であ ることがあげられる. 実際,aj+2 < aj/2 が成り立つ. したがって,a≥b と仮定したとき,ユー クリッドの互除法の除算回数は O(loga)で上から評価できる. また, 各除算における計算量は O((loga)²)回であるので,ユークリッドの互除法の全体にわたる計算量はO((loga)³)となる.

【拡張されたユークリッドの互除法】

正の整数 a,bを与えたとき,

ax+by= gcd(a, b),

az+bw= 0 (1)

をみたす整数 x,y,z,wが存在する. z,wは互いに素であることを仮定すれば一意に定まる.

このx,y,z,wを一組求める方法を「拡張されたユークリッドの互除法」と呼ぶ.

• 拡張されたユークリッドの互除法のアルゴリズムは次のようにあわらすことができる.

☆ 入力 非負整数a0,a1.

☆ 出力 入力されたa0,a1 の最大公約数gcd(a0, a1),および(1)をみたすx,y,z,w.

☆ 手順

1. (A1, A2, A3) = (a0,1,0), (B1, B2, B3) = (a1,0,1)と置く.

2. B₁= 0であれば終了する.

3. A1をB1で割った商qを求め, (T1, T2, T3) = (A1, A2, A3)−q(B1, B2, B3), (A1, A2, A3) = (B1, B2, B3), (B1, B2, B3) = (T1, T2, T3)とし, 2に戻る.

この手順が終了したとき,

a0A2+a1A3=A1(= gcd(a0, a1)), a0B2+a1B3= 0

が成り立つ.

• 拡張されたユークリッドの互除法が正しいアルゴリズムであることは,次のようにして示すこと ができる.

– アルゴリズム中の第1成分の計算はユークリッドの互除法そのものであることから,アルゴ リズムが有限回の計算で終了すること, 終了したときにA₁ = gcd(a₀, a₁) であることがわ かる.

– アルゴリズムの繰り返し中で,

a0A2+a1A3=A1, a0B2+a1B3=B1

が成り立つことを帰納的に示すことができる.

∗ 1回目の繰り返しに直前で,それぞれの式が

a₀×1 +a₁×0 =a₀, a₀×0 +a₁×1 =a₁ として成り立っていることに注意しよう.

– したがって,アルゴリズムが終了した時点では,A1= gcd(a0, a1),B1= 0であるので, a₀A₂+a₁A₃= gcd(a₀, a₁)

a₀B₂+a₁B₃= 0 が成り立つ.

• 拡張されたユークリッドの互除法の計算量は,明らかに通常のユークリッドの互除法と同じであ る. すなわち,O(loga)回の繰り返しが行われる.

【２進互除法】

ユークリッドの互除法をプログラムとして実装する場合において, 最もコストがかかるのは「除算」

の部分である. コンピュータ内部では整数値が2進表現され, 「2で割る」という操作は「シフト演 算」というコストがかからない演算で置き換え可能であることを考えると,（理論的には）より高速 なアルゴリズムを考えることができる.

• 明らかに次の基本的な性質が成り立つ.

gcd(a, b) = 2 gcd(a/2, b/2), ifa,bare even, (2)

gcd(a, b) = gcd(a/2, b), ifais even andbis odd, (3)

gcd(a, b) = gcd(b, a−b), ifa≥b, (4)

ifaandbare odd, thenb−ais even. (5)

• この事実を用いると,次のアルゴリズムを考えることができる.

☆ 入力 非負整数a0,a1.

☆ 出力 入力されたa0,a1 の最大公約数gcd(a0, a1).

☆ 手順

1. a₀, a₁ がともに偶数である間, a₀←a₀/2,a₁←a₁/2 と置き, この繰り返し回数をK とおく.

2. k= 0とする.

3. ak,ak+1 のいずれかが偶数ならば, それが奇数になるまで2で割る.

4. a_k≥a_k+1 と仮定する. a_k←a_k+1,a_k+1←a_k−a_k+1 とする.

5. a_k+1= 0ならば k←k+ 1として3 に戻る.

6. a_k を2^K 倍する.

この手順が終了したとき, ak が求めるべき最大公約数である.

• このアルゴリズムが正しいことは次のようにして見ることができる. 以下では,最初に入力した 値をa,bと書く.

– (2)を用いると,手順1が終了した時, gcd(a₀, a₁) = 2^Kgcd(a, b)が成り立つ.

– (3)を用いると,手順3ではgcd(ak, ak+1)の値は変化しないことがわかる.

– (4)を用いると,手順4で gcd(ak, ak+1)の値は変化しないことがわかる.

– 手順 4 においてak, ak+1 のうち小さくない方の値は必ず減少し, それは非負整数である.

したがって,手順2–4の繰り返しは有限回で終了する.

• (5) を用いると, 手順 2–4を2 回繰り返すと, a_k, a_k+1 のうち小さくない方の 2 進桁数は, 少 なくとも1 桁減少することを示すことができる. したがって,手順2–4の繰り返し回数は高々

O(loga)回であることがわかる. このアルゴリズムでは「シフト演算」と「加減算」しか利用

されていないので,このアルゴリズムの全計算量はO((loga)²)回となり,通常のユークリッド の互除法よりも高速なアルゴリズムであることがわかる.

• 「2進互除法」をCを用いて実装すると,除算が発生しないかわりに「比較」が余分に発生す る. したがって,通常の int, longなどの値に対して 2 進互除法が高速になる条件は, 比較演 算が除算と比較して高速に動作する（「比較の方が除算よりも安い」という言い方をする）こと が必要である. 2の補数, 1の補数, 符号ビットなどを用いる通常の処理系では,除算の計算量は O((loga)²)であるが,大小比較の計算量はO(loga),偶奇判定の計算量は O(1)なので,桁数が 十分大きい場合には, 2進互除法の方が速くなる.

実際,通常のユークリッドの互除法と2進互除法の比較回数,実行時間を比較すると以下のよう になる. なお, 比較回数は,通常の互除法9 回, 2進互除法55 回であり, gcc の最適化オプショ ンには-O3を用いた.

gcd(40920,24140) = 20を求める. 繰り返し回数10000000回

OS CPU 処理系 通常の互除法 2進互除法

Solaris 9 UltraSPARC III 1.0GHz gcc 3.2.1 6.49s 1.45s

Solaris 9 UltraSPARC III 1.0GHz cc 5.2 4.80s 1.66s

FreeBSD 5.3 Celeron D 3.0GHz gcc 3.4.2 1.78s 0.58s

FreeBSD 4.9 Celeron 2.0GHz gcc 2.95.4 2.40s 0.81s

Darwin 8.1.0 PowerPC G5 2.0GHz gcc 3.3 2.00s 0.89s

Darwin 8.1.0 PowerPC G5 2.0GHz gcc 4.0 1.91s 0.97s

Darwin 8.1.0 PowerPC G4 1.67GHz gcc 3.3 1.31s 1.16s

Linux 2.4.18 Itanium 2 1.5GHz gcc 2.96 3.86s 0.80s

Linux 2.4.18 Itanium 2 1.5GHz icc 8.0 2.95s 0.72s

● 実習内容

【Ｃ言語】

1. 以下のex07-1.cを入力してコンパイルおよび実行を行ってみよう.

これはint型の要素数3 を持つ配列を用意し,それを 3次元ベクトルと思い,内積と外積を計 算している.

• この中で“#define”というものが出てきている. “#define N 3” とは,プログラム中に出

てくる“N” というトークン（単語）を“3”で置き換える「プリプロセッサマクロ」と呼ば れるものである.

• プリプロセッサマクロ“#define” は, 配列要素数（データ数）や, プログラム中で多用す る定数値などを定めるために用いられることが多い.

2. 以下のex07-2.cを入力してコンパイルおよび実行を行ってみよう.

このプログラムでは N個のランダムなデータを与え,それを小さい順に並び替えている.

• このような「並び替え」のアルゴリズムを「ソート」と呼び,最も重要なプログラムの一例 である. このプログラムは「バブルソート」と呼ばれるアルゴリズムを用いてソートを行っ ている.

• ランダムなデータ（乱数）を発生させるには, random関数を用いる. random関数は 0 以 上 2³¹−1以下の整数値からなる,極めて長い周期の数列を発生する. この数列の周期が極 めて長いため,擬似的に乱数と思うことができる. また, 毎回異なった系列の乱数を発生さ せるためにはsrandom関数を用いる. （これを怠ると,毎回同じ系列の乱数が発生してし まう.）

• srandom(time(NULL))は,プログラム起動時刻をsrandom関数に渡すことにより,毎回異 なった系列の乱数を発生させるための「おまじない」である.

• 2 つの変数の値を入れ替えるためには,「中間的に値を保持する変数」を用意して,このプ ログラムのように行うのが通常の方法である.

凝ったことを考えるのであれば,

a[i] ^= a[j] ; a[j] ^= a[i] ; a[i] ^= a[j] ;

なんてのもある. ただし,i==jの場合に正しく動作しないため,気をつけて使わないとバグ を作りやすい. また,速くもないし,読みにくいだけなのでお薦めしない.

3. 以下のex07-3.cを入力してコンパイルおよび実行を行ってみよう.

このプログラムは,標準入力から入力されたテキストデータの中の「各数字」,「アルファベッ ト」,「その他の文字」の文字数を数えるプログラムである. （K&R に同じ目的のプログラム が掲載されている.）

4. 以下のex07-4.cを入力してコンパイルおよび実行を行ってみよう.

このプログラムは,aに「１０以下の奇数の集合」, bに「１０以下の３の倍数の集合」をセッ トし, 「１０以下の奇数かつ３の倍数」および「１０以下の奇数または３の倍数」を求めてい る. このプログラムでは,「配列の要素」が「集合に含まれるか否か」をあらわす変数として用 いられていることに注意しよう.

電子メールで「今日の講義の感想や意見」を送ってください.

★

ex07-1.c

/* $Id: ex07-1.c,v 1.10 2005-05-31 13:14:43+09 naito Exp $ */

#include <stdio.h>

#define N (3)

int main(int argc, char **argv) {

int a[N]={1,2,3}, b[N]={2,1,3}, c[N] ; int ip=0, i ;

for(i=0;i<N;i++) ip += a[i]*b[i] ; printf("Inner Product = %d\n", ip) ; for(i=0;i<N;i++)

c[i] = a[(i+1)%N]*b[(i+2)%N] - a[(i+2)%N]*b[(i+1)%N] ; printf("Outer Product = (%d,%d,%d)\n", c[0], c[1], c[2]) ; return 0 ;

}

★

ex07-2.c

/* $Id: ex07-2.c,v 1.8 2005-05-31 14:56:22+09 naito Exp $ */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N (10)

#define M (100)

int main(int argc, char **argv) {

int a[N] ; int i, j, temp ;

srandom(time(NULL)) ; /* 乱数を初期化 */

for(i=0;i<N;i++) a[i] = random()%M ; /* a[i] に 0 -- M-1 のランダムな値を代入 */

for(i=0;i<N;i++) printf("%d\t", a[i]) ; printf("\n") ; for(i=0;i<N-1;i++) { /* a をソート */

for(j=0;j<N-1-i;j++) { if (a[j+1] < a[j]) {

temp = a[j+1] ; a[j+1] = a[j] ; a[j] = temp ; }

} }

for(i=0;i<N;i++) printf("%d\t", a[i]) ; printf("\n") ; return 0 ;

}

★

ex07-3.c

/* $Id: ex07-3.c,v 1.1 2005-05-27 10:01:01+09 naito Exp $ */

#include <stdio.h>

#define DIGIT (10)

int main(int argc, char **argv) {

int a[DIGIT], other=0, alphabet=0 ; int i, c ;

for(i=0;i<DIGIT;i++) a[i] = 0 ; while((c = getchar()) != EOF) {

if ((c >= ’0’)||(c <= ’9’)) a[c-’0’] += 1 ; else if ((c >= ’A’)||(c <= ’Z’)) alphabet += 1 ; else if ((c >= ’a’)||(c <= ’z’)) alphabet += 1 ; else other += 1 ;

}

for(i=0;i<DIGIT;i++)

printf("%c\t%5d\n", i+’0’, a[i]) ; printf("alphabet\t%5d\n", alphabet) ; printf("other\t%5d\n", other) ; return 0 ;

}

★

ex07-4.c

/* $Id: ex07-4.c,v 1.1 2005-05-27 10:26:27+09 naito Exp $ */

#include <stdio.h>

#define N (10)

int main(int argc, char **argv) {

int a[N] = {1,0,1,0,1,0,1,0,1,0} ; int b[N] = {0,0,1,0,0,1,0,0,1,0} ; int c[N] ;

int i ;

/* 論理積 */

for(i=0;i<N;i++) c[i] = a[i]&b[i] ; for(i=0;i<N;i++) {

if (c[i]) printf("%d\t", i+1) ; }

printf("\n") ; /* 論理和 */

for(i=0;i<N;i++) c[i] = a[i]|b[i] ; for(i=0;i<N;i++) {

if (c[i]) printf("%d\t", i+1) ; }

printf("\n") ; return 0 ; }

【課題】

☆ exercise-07-1 標準入力から入力されたテキストデータに含まれる「アルファベットの各文字」

の頻度を,大文字と小文字を区別せずに求めるプログラムを書きなさい.

☆ exercise-07-2 エラトステネスのふるいを用いて, 100000以下の全ての素数を求めるプログラ

ムを書きなさい.

☆ exercise-07-3 与えられた非負整数の2進表示を出力するプログラムを書きなさい.

☆ exercise-07-4 集合Aの補集合A,差集合A\B を求めるプログラムを書きなさい.