アルゴリズムイントロダクションの練習問題やってみた

アルゴリズムイントロダクション

MITでの計算機アルゴリズムの教育用に著わしたテキストの原書3版です。
以前勉強会で使用したため、今回このテキストの練習問題を解いてみました。
アルゴリズムイントロダクション

本記事の利用方法

あくまで個人的な解答の為、ご参考程度に閲覧していただければと思います。
なお、プログラムを用いた回答にはC言語を使用しています。(好きなので。。)

---

練習問題1.1-1

ソートを必要とする実社会での応用あるいは凸包の計算を必要とする実社会での応用を説明せよ。

ソート: 学校での生徒の成績順位の確認

凸包: ポリゴングラフィックの描写

凸包調べました。。
凸包とは、下記の例のように全ての要素(点)を内包する最小の凸多角形です。
例:

練習問題1.1-2

実社会の枠組みの中で用いられる計算速度以外の効率の尺度をあげよ。

トラフィック量

練習問題1.1-3

以前に見たことがあるデータ構造についてその長所と欠点を述べよ。

データ構造 : 配列

長所: 添字からそこに格納されている値を参照できる

欠点: 途中に要素を挿入したり追加したりするには元あった要素をずらす必要がある

練習問題1.1-4

上で述べた最短経路問題と巡回セールスマン問題の類似点を説明せよ。また、相違点は何か。

類似点 : いくつかあるルートから最短経路を見つける点

相違点 : 巡回セールスマン問題は、全ての点を通らなければならない点

練習問題1.1-５

最適解しか意味を持たない実社会の問題を示せ。また、「近似解」でも十分に意味を持つ問題を示せ。

最適解: 電子商取引のディジタル署名

近似解: 検索エンジンによるサイト検索

練習問題1.2-1

割愛(議論せよという問い?なので。。)

練習問題1.2-2

同じ計算機上で挿入ソートとマージソートの実現を比較する。サイズnの入力に対して、挿入ソートの実行には8n^2ステップかかり、一方、マージソートの実行には64nlog2nステップかかるとする。挿入ソートがマージソートに優れるnの値を調べよ。
n>43

1.2.2.c

#include <stdio.h>
#include <math.h>

int main(void)
{
  int n, hoge, insertion, merge;
  for(n=1; n<100; n++){
    insertion = 8 * (n * n);
    merge = 64 * n * log2(n);
  if(insertion <= merge){
    hoge = n;
  }
}
  printf("%d \n", hoge);
  return 0;
}

練習問題1.2-3

同じ計算機上で、実行時間が100n^2のアルゴリズムが、実行時間が2^nのアルゴリズムより高速に実行できる最小のnの値を求めよ。
15

1.2.3.c

#include <stdio.h>
#include <math.h>

int main(void)
{
  double y1, y2;
  int hoge = 0;
  for(int n=1; n<100; n++){
    y1 = 100 * (n * n);
    y2 = pow(2.0, n);
  if(y1 > y2){
    hoge = n;
  }
}
  printf("%d \n", hoge);
  return 0;
}

練習問題2.1-1

図2.2を手本にして、配列A={31,41,59,26,41,58}上でのINSERTION-SORTの動作を説明せよ
こう動きます。笑

練習問題2.1-2

INSERTION-SORT手続きは非減少順でソートする。これを書き換えて非増加順でソートするようにせよ。

2.1.2.c

#include <stdio.h>
#include <math.h>

int main(void)
{
  int i, j, key, a[7];
  a[1] = 5;
  a[2] = 2;
  a[3] = 4;
  a[4] = 6;
  a[5] = 1;
  a[6] = 3;


  for(j=2; j<7; j++){
    key = a[j];
    i = j-1;
    while (i>0 && a[i]<key){
      a[i+1]=a[i];
      i=i-1;
    a[i+1]=key;
    }
}
for(int n=1; n<=6; n++){
  printf("%d", a[n]);
}
  return 0;
}

練習問題2.1-3

以下の探索問題(searching problem)を考えよう
入力: 長さnの数列A=とある値v
出力: v=A[i]となる添字i, またはvがAの中に存在しない時は特別なNIL
順次探索(linear search)の疑似コードを書け。
順次探索はvを探しながら列を順に走査するアルゴリズムである。

i = Nil
for j = 1 to A.Length
    if v == A[j]
        i = j
        break  
return i

練習問題2.1-4

２つのn要素配列AとBに蓄えられた2つのnビットの2進数の和を求める問題を考える。この２つの整数の和は2進数として、(n+1)要素配列Cに蓄える。この問題を形式的に記述し、2つの整数の和を求める疑似コードで示せ。

carry=0
for i=1 to A.Length
    c[i]=(A[i]+B[i]+carry)%2
    carry=(A[i]+B[i]+carry)/2
    c[i]=carry
return c

INSERTION SORTをC言語でやってみた

InsertionSort.c

#include <stdio.h>
#include <math.h>

int main(void)
{
  int i, j, key, a[7];
  a[1] = 5;
  a[2] = 2;
  a[3] = 4;
  a[4] = 6;
  a[5] = 1;
  a[6] = 3;

  for(j=2; j<7; j++){
    key = a[j];
    i = j-1;
    while (i>0 && a[i]>key){
      a[i+1]=a[i];
      i=i-1;
    a[i+1]=key;
    }
}
for(int n=1; n<=6; n++){
  printf("%d", a[n]);
}
  return 0;
}

楽しい。

練習問題2.2 バブルソートの正当性

バブルソートは人気があるが、非効率なソーティングアリゴリズムである。バブルソートは隣接要素が逆順担っていれば、それらの位置を交換する操作を繰り返すことでソートを実現する。

疑似コード

for i = 1 to A.length - 1
  for j = A.length downto i + 1
    if A[j] < A[j - 1]
      A[j]とA[j - 1]を交換する

1. A'をBubbleSort(A)の出力とする．
bubbleSortの正当性を証明するには，BubbleSortが停止し，停止時に
A'[1] <= A'[2] <= ・・・A'[n]
が成立することを証明しなければならない．
BubbleSortが実際にソートをすることを証明するには他に何を証明する必要があるか？

正当性を証明するためには，ループ不変式を用い， ３つの性質を示せばよい ・初期条件 ・ループ内条件 ・終了条件

第2~第4行のfor文に対するループ不変式を正確に記述し，
このループ不変式が成立することを証明せよ．
ただし，本章で示したループ不変式の証明の構造に従って証明すること．

ループ不変式 第2~4行のfor文の各繰り返しが開始される時には，部分配列A[j..n]には， 開始時点でA[j]に格納されている要素が，ソート済み部分配列A[j..n]の中で最小の要素が格納されている状態
・初期条件 部分配列A[j..n]は要素A[n]から構成され，これは，実際にA[n]に格納されていた要素． さらに，この部分配列は，ソート済みの為，最初の繰り返しの直前においてはループ不変式は真である．

・ループ内条件 for文本体では、A[j]とA[j-1]を比較し，A[j]がA[j-1]より小さい値の場合， 値の入れ替えを行う． 部分行列A[j..n]は，元々A[j..n]に格納されていた要素から構成されているが， 既にソートされている． for文の次の繰り返しのためにjの値から1を減算すると，ループ不変式が維持される．

・終了条件 for文の条件であるi===jになった場合，停止する． for文本体では，jの値を1だけ減算させるため，停止時にはi=jが成立する． 部分配列A[j..n]には，開始時点でのA[j..n]に格納されていた要素が格納されているが， ループ内条件により，これらの要素は既にソートされている． また，ループ内条件により，A[j]に格納されている値は，配列A[j..n]に格納されていた値の最小値が格納されている． よって，配列はソート済みであると結論でき，このアルゴリズムは正当である．

2で証明したループ不変式の停止条件を用いて，不等式(2.3)の証明に繋がる．
第１〜第4行のfor文に対するループ不変式を記述せよ．
ただし，本章で示したループ不変式の証明の構造に従って証明すること

ループ不変式 第1〜4行のfor文の繰り返しが開始される時には， 部分配列A[1..i-1]に格納されている要素が，全体の配列A[1..i-1]にソートされた要素が格納されている状態である．
・初期条件 i=1の時，A[1..i-1]は空であるので，ループ不変式を満たす．

・ループ内条件 2~4行のループの停止条件は，省略． 1〜4行のループは、ループの度にiの値を1加算して進むので，ループ不変式を満たす。

・終了条件 i=nの場合，終了する． ループは，iの値に1加算して進み，停止時i=nを満たす。 全体の配列A[1..n]には，ソートされた要素が格納されている．

挿入ソートの実行時間と比較せよ．

もっとも小さいデータを一番上の要素まで動かすのに : N-1 回
2番目のデータを上から2番目の要素まで動かすのに : N-2 回
3番目のデータを上から3番目の要素まで動かすのに :  N-3 回
    ：
    ：
(N-1) + (N-2) + (N-3) + … + 2 + 1 = 
Σi=1^n (n-1) = N(N-1)/2
n^2である．

BUBBLE SORTをC言語でやってみた

BubbleSort.c

#include <stdio.h>

#define NUM_ITEMS 7

void bubbleSort(int numbers[], int array_size);

void printArray(int numbers[], int array_size);


int main()
{
  int numbers[NUM_ITEMS] = {6,5,3,1,7,2,4};

  printf("Start:\n");
  printArray(numbers, NUM_ITEMS);
  printf("\n");

  //perform bubble sort on array
  bubbleSort(numbers, NUM_ITEMS);

  printf("Done:\n");
  printArray(numbers, NUM_ITEMS);
  printf("\n");

  return 0;
}


void bubbleSort(int numbers[], int array_size)
{
  int i, j, temp;

  for (i = 0; i < (array_size - 1) ; i++) {
    for (j = (array_size - 1); j > i; j--) {
      printf("compare: %d and %d\n", numbers[j], numbers[j-1]);
      if (numbers[j-1] > numbers[j]) {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;

        printf("\tswap: ");
        printArray(numbers, array_size);
        printf("\n");
      }
    }
    printArray(numbers, array_size);
    printf("\n");
  }
}

void printArray(int numbers[], int array_size)
{
    int x;
    for (x = 0; x < array_size; x++) {
        printf("%d ", numbers[x]);
    }
}

楽しい×2

まとめ

• ループ不変式,証明は難しいです。。
• 気が向いたら続きをやろうと思います。