プログラミング技法とデータ構造

アルゴリズムとプログラミング

以下の記述は，テキスト「定本Cプログラマのためのアルゴリズムとデータ構造」(近藤嘉雪著)の内容に基づき，本授業の内容と合うように一部要点を抜粋・翻案したものである．

アルゴリズムとプログラムは次のような関係にある．

• アルゴリズム : 処理手続きを記述したもの
• プログラム : アルゴリズムをプログラミング言語で表現したもの

プログラミング(プログラムを書く)ということは次の行動を含む．

1. 問題を分析してプログラムすべき内容を決める．(仕様の決定)
2. それに適したアルゴリズムとデータ構造を選択する．
3. 実際にプログラムを書く．

これまでの「C言語入門」「情報処理演習」「制御プログラミング」などで行ってきたプログラムはこのうち3.のみを中心に作業した．プログラミングの入門書で学べることも3.が中心である．3.は，C言語の文法を学び，指示どおりに作業内容をプログラムとして書き下すことができる能力であり，本科目の受講者にはこの能力がすでに備わっていることを期待している．すなわちC言語をマスターした段階である．

C言語をマスターした次の段階は，1.と2.について学ぶことである．しかし，1.についてはプログラム対象の問題次第で個々に事情が異なり，すべてに対応できる魔法の定石はない．プログラムを数多く書く経験を積むことが必要となる．

2.に関しては，これまでに一般に利用可能な様々なアルゴリズムやデータ構造が提案されてきており，これらを学ぶことで実際にプログラミングする際の直接的な「武器」を手にすることができる．また，この「武器」の種類を頭に入れておくことで，1.を効率よく検討することもできる．

この講義では2.を中心に習得するものとする．

「プログラム」=「アルゴリズム+データ構造」

もうひとつ，プログラムする際にはアルゴリズムだけではなくデータ構造を必要とする．コンピュータはCPUとメモリによって構成されている．そのコンピュータのプログラムでは検討しなければならないトレードオフとして次の問題にいつも悩まされる．

• アルゴリズムA+データ構造A: 速いが，記憶容量が大きくないとだめ
• アルゴリズムB+データ構造B: 記憶容量が少なくてよいが，遅い

目的に応じてどちらかを選択することになる．様々なアルゴリズムについてその長所・短所をしっておくことで，ある問題に対してどのアルゴリズムが適切か判断できるようにすることが大切である．

アルゴリズムの性能(計算量と記憶容量)

最終的なプログラムの性能は，それを稼働させる本番の実機上で実際に処理速度を測定することで得られる．しかし「アルゴリズム」の性能は様々なコンピュータで動かされる状況が想定され，実際に測定すればいいというものではない．どれかの大きなコンピュータでは高速でも，別の小さなコンピュータでは遅くなるかもしれない．

アルゴリズムの性能を示す指標は，「計算量」である．

• 時間計算量: アルゴリズムの実行時間にどれくらいかかるか．
• 空間計算量:　アルゴリズムの実行にどれくらいメモリが必要か．

あるアルゴリズムは，入力するデータによっては処理時間などが異なってくる．最悪のデータに対する「最大計算量」や，すべてのデータに対する(あるいは統計的に計算して)「平均計算量」を算出して，アルゴリズムの性能を比較することとなる．

時間計算量の単位は，残念ながら実際のコンピュータで測定した秒などの時間単位では表現できない．メモリ量やCPUの早さなどアルゴリズム以外の要素の影響が大きすぎるため，一般的に時間が計測で着ないからである．そこで，「入力データの数nに対して実行時間はnの2乗に比例する」などの大雑把な表現しかできない．これをO(n²)(オーダn2と呼ぶ)と表現する．アルゴリズムの時間計算量はこのオーダで比較することとなる．

アルゴリズムの比較例

素数を求めるアルゴリズムを比較してみよう．まず素数の定義どおりに求める方法である．

素数の定義は，「1とその数自身以外に正の約数がない、1 より大きな自然数のこと」である．すなわち1以外では割り切れない正の整数のことをいう．

これから，定義どおりに100000までの素数を求めるプログラムである．

#include <stdio.h>
#define MAX 1000000

int main(void)
{
  int i, j;
  for(i=2;i < MAX;i++){      //2からMAXまで順番に調べる(i)
    for(j=i-1; j > 1; j--){  //1より大きくてiより小さい数jを調べる
      if(i%j==0){          //iがjで割りきれるかどうか
        break;             //割りきれたらiについての調査はおしまい
      }
    }
    if(j==1){              //jが1，つまりjが1になるまで調べた，つまりiを割りきれるjがなかった
      printf("%d\n", i);   //ならば，このiは素数である．
    }
  }  
  return 0;
}

もう一つは，素数を求めるアルゴリズムとして有名な「エラトステネスのふるい」である．あらかじめ最大の数100000までの表(table)を用意しておき，表にはフラグとして「0」を入れておく．フラグが0の数は素数として扱う．

そして数2,3,4,5,....,1000000まで順に調べる．数2は，table[2]にフラグが立っていないので，素数である．逆に考えれば2の倍数は(必ず2で割りきれるため)素数ではない．そこで，2の倍数にあたる部分の表のフラグに1を立てる．続いて数3は，table[3]にフラグが立っていないのでやはり素数である．同じように3の倍数にもフラグを立てる．次に4は，先ほどtable[4]が2の倍数としてフラグが立てられているため素数ではない．だから4はスキップし，次の5を調べる．

以下同様に処理をつづけ，最大数まで調べれば終了となる．

#include <stdio.h>
#define MAX 1000000

int main(void)
{
  int i, j;
  int table[MAX];

  for(i=2 ; i < MAX ; i++){  //初期化
    table[i] = 0;          //フラグを全部下ろす
  }
  for(i=2 ; i < MAX ; i++){
    if(table[i]==0){       //フラグがなければ
      printf("%d\n", i);   //ならば，このiは素数である．
      for(j=2 ; i*j < MAX ; j++){ //倍数を除外，なにかの倍数にフラグを立てる
        table[i*j] = 1;
      }
    }
  }

  return 0;
}

プログラムの実行方法

WindowsPCで利用できるフリーのC言語開発環境としては窓の杜などで紹介されている

• 学習用C言語開発環境

などが利用できる．

(参考)Ubuntuを使った場合

Ubuntuを使ったプログラムの実行方法は，「アクセサリ」→「端末」を起動して，次のようにコンパイルし実行することができる

% cc ファイル名.c　-o 実行ファイル名
% ./実行ファイル名

問題

両方のプログラムの，時間計算量と空間計算量を比較してみよ．