情報構造論ガイダンス

前年度のプログラミング応用の次のステップとしての情報構造論として、 どういった内容を行うのかガイダンスを行う。

最初に、使用する教科書のタイトルにもある、アルゴリズムという言葉の説明として、 アルゴリズムとは、計算の方法の考え方、 そのアルゴリズムをどう表現するのかがパラダイム、 そのパラダイムに沿って実際に書いたものがプログラム。

いいプログラムとは？

次に、ある程度プログラム記述を学んできたところだし「あなたはどうプログラムを書くといいと思うか？」 を次々と聞いてみた。 学生さんから帰ってくる言葉は、 「わかりやすい、行数が短い、関数が使われている、変数名が解りやすい、バグが少ない…」 といった物がほとんど。 中には、「プログラムが再利用しやすい」といったオツな答えもあったけど、 どれも大きくまとめれば「わかりやすい」という観点。

途中で、「処理速度が速い」という答えもあったけど、「メモリの使用量が少ない」という 観点がなかなか出てこない。

処理速度という観点では、3秒ルールなどの雑談を交えながら計算時間について説明。 また、メモリの使用量という観点では、限られた主記憶を有効に使わないと、 プログラムが動かなかったり、仮想記憶などを使うことになり、頻繁なスワップ処理で 処理速度の低下につながることを説明する。

これらの「プログラムの分かりやすさ」、「処理速度」、「メモリの使用量」は、一般的に、 どれかを優先すれば、ほかの観点が悪化してしまうトレードオフの関係にあることを説明。

処理時間を式で表現

まず、プログラムの処理時間を分析するために、簡単なプログラムがどんな式で表現できるかを示す。

// 配列(順序はデタラメ)の中の特定データを探す処理。
int data[ N ] ;
   for( i = 0 ; i < N ; i++ ) {
      if ( data[ i ] == key )
         break ;
}

このようなループ処理であれば、ループ回数の平均を考えて式にすると、

で表現できることを説明。

// 最大選択法の並び替え
int data[ N ] ;

for( i = 0 ; i < N-1 ; i++ ) {
   int m = i ;
   for( j = i+1 ; j < N ; j++ ) {
      if ( data[m] > data[j] )
         m = j ;
   }
   tmp = data[ m ] ;
   data[ m ] = data[ i ] ;
   data[ i ] = tmp ;
}

このような処理であれば、ループ回数をΣなどを用いて表しながら、以下のような式で示されることを説明。