ホーム » 2021 » 4月

月別アーカイブ: 4月 2021

2021年4月
 123
45678910
11121314151617
18192021222324
252627282930  

最新の投稿(電子情報)

アーカイブ

カテゴリー

コンピュータとN進数

3年の情報制御基礎の授業の一回目。この授業では、情報系以外の学生も受講することから、基礎的な共通的な話題を中心に説明を行う。参考:2020年度の講義資料

情報制御基礎のシラバス

情報制御基礎では、ここに上げたシラバスに沿って授業を行う。

基本的に、センサーから読み取ったデータを使って動く制御系システムを作る場合の基礎知識ということで、アナログ量・デジタル量の話から、移動平均やデータ差分といった数値処理や、そこで求まった値を制御に用いるための基礎的な話を行う。

コンピュータと組み込み系

最近では、コンピュータといっても様々な所で使われている。

  1. 科学技術計算用の大型コンピュータ(最近なら富岳が有名)や
  2. インターネットの処理を行うサーバ群
    (必要に応じてサービスとして提供されるものはクラウドコンピューティングと呼ぶ)、
  3. デスクトップパソコン、
  4. タブレットPCやスマートフォンのような端末、
  5. 電化製品の中に収まるようなワンチップコンピュータなどがある。

(1) サーバ:ブレードサーバ

(5) ワンチップコンピュータ:PIC

身近で使われている情報制御という点では、(5)のような小型のコンピュータも多く、こういったものは組み込み型コンピュータとも呼ばれる。しかし、こういったコンピュータは、小さく機能も限られているので、

  • 組み込み系では、扱える数値が整数で 8bit や 16bit といった精度しかなかったり、
  • 実数を伴う複雑な計算をするには、処理時間がかかったりする

ため、注意が必要である。

この情報制御基礎の授業では、組み込み系のコンピュータでも数値を正しく扱うための知識や、こういった小さいコンピュータで制御を行うことを踏まえた知識を中心に説明を行う。

2進数と10進数

コンピュータの中では、電圧が高い/低いといった状態で0と1の2通りの状態を表し、その 0/1 を組み合わせて、大きな数字を表す(2進数)。

練習として、2進数を10進数で表したり、10進数を2進数に直してみよう。

N進数を10進数に変換

N進数で “abcde” があったとする。(2進数で”10101)2“とか、10進数で”12345)10“とか)

この値は、以下のような式で表せる。

(例1)

(例2)

10進数をN進数に変換

N進数のは、前式を変形すると、以下のような式で表せることから、

値をNで割った余りを求めると、N進数の最下位桁eを取り出せる。

このため、10進数で与えられた35を2進数に変換するのであれば、35を2で次々と割った余りを、下の桁から書きならべれば2進数100011)2が得られる。

実数の場合

途中に小数点を含むN進数のab.cde)Nであれば、以下の値を意味する。

ここで、小数点以下だけを取り出した、0.cde)Nを考えると、

の値に、Nをかけると、次のように変形できる。

この式を見ると、小数部にNをかけると、整数部分に小数点以下1桁目が取り出せる

このため、10進数で与えられた、0.625を2進数に変換するのであれば、0.625に次々と2をかけて、その整数部を上の桁から書きならべれば、2進数0.101)2が得られる。

ただし、10進数で0.1という値で、上記の計算を行うと、延々と繰り返しが発生する。つまり、無限小数になるので注意せよ。

2の補数と負の数

コンピュータの中で引き算を行う場合には、2の補数がよく使われる。2の補数とは、2進数の0と1を入替えた結果(1の補数)に、1を加えた数である。

元の数に2の補数を加えると(2進数が8bitの数であれば)、どのような数でも1,0000,0000という値になる。この先頭の9bit目が必ずはみ出し、この値を覚えないのであれば、元の数+2の補数=0とみなすことができる。このことから、2の補数= (-元の数) であり、負の数を扱うのに都合が良い。

練習問題

(1) 自分の誕生日で、整数部を誕生日の日、小数点以下を誕生日の月とした値について、2進数に変換せよ。(例えば、2月7日の場合は、”7.02″という小数点を含む10進数とする。)

変換の際には、上の説明の中にあるような計算手順を示すこと。また、その2進数を10進数に直し、元の値と同じか確認すること。(ただし、結果の2進数が無限小数になる場合最大7桁まで求めれば良い。同じ値か確認する際には無限少数の場合は近い値になるか確認すること)

(2) 自分の誕生日の日と、自分の学籍番号の下2桁の値を加えた値について、8bitの2進数で表わせ。(2月7日生まれの出席番号13番なら7+13=21)

その後、8bitの2進数として、2の補数を求めよ。また、元の数と2の補数を加えた値についても検証すること。

レポートの提出先は、こちらのリンクを参照(この中にレポート書式のひな型を置いてあります)

複素数クラスによる演習

複素数クラスの例

隠蔽化と基本的なオブジェクト指向の練習課題として、前回の授業では、直交座標系による複素数クラスを示した。今回の授業では、演習を行うとともに直交座標系を極座標系にクラス内部を変更したことにより、隠蔽化の効果について考えてもらい、第1回レポートとする。

直交座標系

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

// 直交座標系の複素数クラス
class Complex {
private:
   double re ; // 実部
   double im ; // 虚部
public:
   void print() {
      printf( "%lf + j%lf¥n" , re , im ) ;
   }
   Complex( double r , double i ) // 実部虚部のコンストラクタ
     : re( r ) , im( i ) {}
   Complex()                      // デフォルトコンストラクタ
     : re( 0.0 ) , im( 0.0 ) {} 
   void add( Complex z ) {
      // 加算は、直交座標系だと極めてシンプル
      re = re + z.re ;
      im = im + z.im ;
   }
   void mul( Complex z ) {
      // 乗算は、直交座標系だと、ちょっと煩雑
      double r = re * z.re - im * z.im ;
      double i = re * z.im + im * z.re ;
      re = r ;
      im = i ;
   }
   double get_re() {
      return re ;
   }
   double get_im() {
      return im ;
   }
   double get_abs() { // 絶対値
      return sqrt( re*re + im*im ) ;
   }
   double get_arg() { // 偏角
      return atan2( im , re ) ;
   }
} ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね
int main() {
   // 複素数を作る
   Complex a( 1.0 , 2.0 ) ;
   Complex b( 2.0 , 3.0 ) ;

   // 複素数の計算
   a.print() ;
   a.add( b ) ;
   a.print() ;
   a.mul( b ) ;
   a.print() ;

   return 0 ;
}

極座標系

上記の直交座標系の Complex クラスは、加減算の関数は単純だけど、乗除算の関数を書く時には面倒になってくる。この場合、極座標系でプログラムを書いたほうが判りやすいかもしれない。

// 局座標系の複素数クラス
class Complex {
private:
   double r ;  // 絶対値 r
   double th ; // 偏角   θ
public:
   void print() {
      printf( "%lf ∠ %lf¥n" , r , th / 3.14159265 * 180.0 ) ;
   }
   Complex()
     : r( 0.0 ) , th( 0.0 ) {}

   // 表面的には、同じ使い方ができるように
   //  直交座標系でのコンストラクタ
   Complex( double x , double y ) {
      r  = sqrt( x*x + y*y ) ;
      th = atan2( y , x ) ;    // 象限を考慮したatan()
   }
   // 極座標系だと、わかりやすい処理
   void mul( Complex z ) {
      // 極座標系での乗算は
      r = r * z.r ;    // 絶対値の積
      th = th + z.th ; // 偏角の和
   } 
   // 反対に、加算は面倒な処理になってしまう。
   void add( Complex z ) {
      ; // 自分で考えて
   }
   // 
   double get_abs() {
      return r ;
   }
   double get_arg() {
      return th ;
   }
   double get_re() {
      return r * cos( th ) ;
   }
   double get_im() {
      return r * sin( th ) ;
   }
} ; // ←しつこく繰り返すけど、セミコロン忘れないでね(^_^;

このように、プログラムを開発していると、当初は直交座標系でプログラムを記述していたが、途中で極座標系の方がプログラムが書きやすいという局面となるかもしれない。しかし、オブジェクト指向による隠蔽化を正しく行っていれば、利用者に影響なく「データ構造」や「その手続き(メソッド)」を書換えることも可能となる。

このように、プログラムをさらに良いものとなるべく書換えることは、オブジェクト指向ではリファクタリングと呼ぶ。
正しくクラスを作っていれば、クラス利用者への影響が最小にしながらリファクタリングが可能となる。

const 指定 (経験者向け解説)

C++ では、間違って値を書き換えるような処理を書けないようにするための、const 指定の機能がある。

void bar( char* s ) {       // void bar( const char* s ) {...}
   printf( "%s\n" , s ) ;   //  で宣言すべき。
}

void foo( const int x ) {
   //     ~~~~~~~~~~~
   x++ ; // 定数を書き換えることはできない。
   printf( "%d\n" , x ) ;
}
int main() {
   const double pi = 3.141592 ;
   // C言語で #define PI 3.141592 と同等

   bar( "This is a pen" ) ; // Warning: string constant to 'char*' の警告
   int a = 123 ;
   foo( a ) ;

   return 0 ;
}

前述の、getter メソッドの例では要素を参照するだけで、オブジェクトの中身が変化しない。逆に言えば、getter のメソッド内にはオブジェクトに副作用のある処理を書いてはいけない。こういった用途に、オブジェクトを変化させないメソッド宣言がある。先の、get_re() は、

class ... {
   :
   inline double get_re() const {
               //         ~~~~~
      re = 0 ; // 文法エラー
      return re ;
   }
} ;

クラスオブジェクトを引数にする場合

前述の add() メソッドでは、”void add( Complex z ) { … }” にて宣言をしていた。しかし、引数となる変数 z の実体が巨大な場合、この書き方では値渡しになるため、データの複製の処理時間が問題となる場合がある。この場合は、(書き方1)のように、z の参照渡しにすることで、データ複製の時間を軽減する。また、この例では、引数 z の中身を間違って add() の中で変化させる処理を書いてしまうかもしれない。そこで、この事例では(書き方2)のように const 指定もすべきである。

// (書き方1)
class Complex {
   :
   void add( Complex& z ) {
      re += z.re ;
      im += z.im ;
   }
} ;
// (書き方2)
class Complex {
   :
   void add( const Complex& z )
   {  //     ~~~~~~~~~~~~~~~~
      re += z.re ;
      im += z.im ;
   }
} ;

レポート1(複素数の加減乗除)

授業中に示した、直交座標系・極座標系の複素数のプログラムをベースに、記載されていない減算・除算のプログラムを作成し、レポートを作成する。 レポートには、下記のものを記載すること。

  • プログラムリスト
  • プログラムへの説明
  • 動作確認の結果
  • プログラムより理解できること。
  • 実際にプログラムを書いてみて分かった問題点など…

再帰呼び出しと再帰方程式

前回までの授業では、for ループの処理時間の分析や見積もりについて説明をしてきた。
次のテーマとして、再帰呼び出しを含む処理の処理時間の分析について説明する。

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=Ta で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(Tb)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 T(N)=Tb=T(N-1)で表せる。

} 再帰方程式

このような、式の定義自体を再帰を使って表した式は再帰方程式と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式  が得られる。

T(1)=Ta
T(2)=Tb+T(1)=Tb+Ta
T(3)=Tb+T(2)=2×Tb+Ta
:
T(N)=Tb+T(N-1)=Tb + (N-2)×Tb+Ta

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で表現し、処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか?それを踏まえ、処理時間はどのように表現できるであろうか?

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに2つに分割して解いている。

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間Ts(N)は次の再帰方程式で表せる。

   ← Tβ + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

ということで、このプログラムの処理時間は、 で表せる。


次に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。

ハノイの塔


ハノイの塔は、3本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
 … ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

 … ③より
 … ①を代入

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

  • 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
  • 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
  • 再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ。
int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

再帰を使ったソートアルゴリズム

データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。

この中で、高速なソートアルゴリズムは、クイックソート(最速のアルゴリズム)とマージソート(オーダでは同程度だが若干効率が悪い)であるが、ここでは、再帰方程式で処理時間をイメージしやすい、マージソートにて説明を行う。

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが となる。






よって、処理時間のオーダは  となる。

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

  1. データ件数 = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓などが必要。

オブジェクト指向の基本プログラム

C++のクラスで表現

前回の講義での、構造体のポインタ渡しをC++の基本的なクラスで記述した場合のプログラムを再掲する。

#include <stdio.h>
#include <string.h>

// この部分はクラス設計者が書く
class Person {
private: // クラス外からアクセスできない部分
   // データ構造を記述
   char name[10] ; // メンバーの宣言
   int  age ;
public: // クラス外から使える部分
   // データに対する処理を記述
   void set( char s[] , int a ) { // メソッドの宣言
      // pのように対象のオブジェクトを明記する必要はない。
      strcpy( name , s ) ;
      age = a ;
   }
   void print() {
      printf( "%s %d¥n" , name , age ) ;
   }
} ; // ← 注意ここのセミコロンを書き忘れないこと。

// この部分はクラス利用者が書く
int main() {
   Person saitoh ;
   saitoh.set( "saitoh" , 55 ) ;
   saitoh.print() ;

   // 文法エラーの例
   printf( "%d¥n" , saitoh.age ) ; // phoneはprivateなので参照できない。
   return 0 ;
}

この様にC++のプログラムに書き換えたが、内部の処理は元のC言語と同じであり、オブジェクトへの関数呼び出し saitoh.set(…) などが呼び出されても、set() は、オブジェクトのポインタを引数して持つ関数として、機械語が生成されるだけである。

用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのデータに対し具体的な値や記憶域が割り当てられたものオブジェクト(object)と呼ぶ。

C++では隠蔽化をさらに明確にするために、private:public: を指定できる。private: は、そのメソッドの中でしか使うことができない要素や関数であり、public: は、メソッド以外からでも参照したり呼出したりできる。オブジェクト指向でプログラムを書くとき、データ構造や関数の処理方法は、クラス内部の設計者しか触れないようにしておけば、その内部を改良することができる。しかし、クラスの利用者が勝手に内部データを触っていると、内部設計者が改良するとそのプログラムは動かないものになってしまう。

隠蔽化を的確に行うことで、クラスの利用者はクラスの内部構造を触ることができなくなる。一方でクラス設計者はクラスの外部への挙動が変化しないようにクラス内部を修正することに心がければ、クラス利用者への影響がないままクラスの内部を改良できる。このように利用者への影響を最小に、常にプログラムを修正することリファクタリングと呼ぶ。

クラス限定子

前述のプログラムでは、class 宣言の中に関数内部の処理を記述していた。しかし関数の記述が長い場合は、書ききれないこういう場合はクラス限定子を使って、メソッドの具体的な処理をクラス宣言の外に記載する。

class Person {
private:
   char name[10] ;
   int  age ;
public:
   // メソッドのプロトタイプ宣言
   void set( char s[] , int a) ;
   void print() ;
} ;

// メソッドの実体をクラス宣言の外に記載する。
void Person::set( char s[] , int a ) {  // Person::set() 
   strcpy( name , s ) ;
   age = a ;
}
void Person::print() {                  // Person::print()
   printf( "%s %d¥n" , name , age ) ;
}

inline 関数と開いたサブルーチン

オブジェクト指向では、きわめて簡単な処理な関数を使うことも多い。
例えば、上記のプログラム例で、クラス利用者に年齢を読み出すことは許しても書き込みをさせたくない場合、以下のような、関数を定義する。(getterメソッド)

# 逆に、値の代入専用のメソッドは、setterメソッドと呼ぶ

class Person {
private:
   char name[10] ;
   int  age ;
public:
   // メソッドのプロトタイプ宣言
   inline int get_age() { return age ; } // getter
   inline void set_age( int a ) { age = a ; } // setter
} ;

ここで inline とは、開いた関数(開いたサブルーチン)を作る指定子である。通常、機械語を生成するとき中身を参照するだけの機械語と、get_age() を呼出したときに関数呼び出しを行う機械語が作られる(閉じたサブルーチン)が、age を参照するだけのために関数呼び出しの機械語はムダが多い。inline を指定すると、入り口出口のある関数は生成されず、get_age() の処理にふさわしい age を参照するだけの機械語が生成される。

# 質問:C言語で開いたサブルーチンを使うためにはどういった機能があるか?

コンストラクタとデストラクタ

プログラムを記述する際、データの初期化忘れや終了処理忘れで、プログラムの誤動作の原因になることが多い。

このための機能がコンストラクタ(構築子)とデストラクタ(破壊子)という。

コンストラクタは、返り値を記載しない関数でクラス名(仮引数…)の形式で宣言し、オブジェクトの宣言時に初期化を行う処理として呼び出される。デストラクタは、~クラス名() の形式で宣言し、オブジェクトが不要となる際に、自動的に呼び出し処理が埋め込まれる。

class Person {
private:
   // データ構造を記述
   char name[10] ;
   int  age ;
public:
   Person() { // (A) 引数なしのコンストラクタ
      name[0] = '
class Person {
private:
   // データ構造を記述
   char name[10] ;
   int  age ;
public:
   Person() { // (A) 引数なしのコンストラクタ
      name[0] = '\0' ;
      age = 0 ;
   }
   Person( char s[] , int a ) { // (B) 引数ありのコンストラクタ
      strcpy( name , s ) ;
      age = a ;
   }
   ~Person() { // デストラクタ
      print() ;
   }
   void print() {
      printf( "'%s' = %d¥n" , name , age ) ;
   }
} ;

int main() {
   Person saitoh( "saitoh" , 55 ) ; // オブジェクトsaitohを"saitoh"と55で初期化
   Person tomoko ;  // 引数なしのコンストラクタで初期化される。
   return 0 ;
   // main を抜ける時にオブジェクトsaitohは不要になるので、
   // デストラクタが自動的に呼び出され、'saitoh' = 55 が表示。
   // 同様に tomoko のデストラクタでは、'' = 0 を表示。
}
' ; age = 0 ; } Person( char s[] , int a ) { // (B) 引数ありのコンストラクタ strcpy( name , s ) ; age = a ; } ~Person() { // デストラクタ print() ; } void print() { printf( "'%s' = %d¥n" , name , age ) ; } } ; int main() { Person saitoh( "saitoh" , 55 ) ; // オブジェクトsaitohを"saitoh"と55で初期化 Person tomoko ; // 引数なしのコンストラクタで初期化される。 return 0 ; // main を抜ける時にオブジェクトsaitohは不要になるので、 // デストラクタが自動的に呼び出され、'saitoh' = 55 が表示。 // 同様に tomoko のデストラクタでは、'' = 0 を表示。 }

このクラスの中には、(A)引数無しのコンストラクタと、(B)引数ありのコンストラクタが出てくる。C++では、同じ名前の関数でも引数の数や型に応じて呼出す関数を適切に選んでくれる。(関数のオーバーロード)

デストラクタは、データが不要となった時に自動的に呼び出してくれる関数で、一般的にはC言語でのファイルの fopen() , fclose() のようなものを使う処理で、コンストラクタで fopen() , デストラクタで fclose() を呼出すように使うことが多いだろう。同じように、コンストラクタで malloc() を呼出し、デストラクタで free() を呼出すというのが定番の使い方だろう。

複素数クラスの例

隠蔽化と基本的なオブジェクト指向の練習課題として、複素数クラスをあげる。ここでは、複素数の加算・乗算を例に説明をするので、減算・除算などの処理を記述することで、クラスの扱いに慣れてもらう。

直交座標系の複素数クラス

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

// 直交座標系の複素数クラス
class Complex {
private:
   double re ; // 実部
   double im ; // 虚部
public:
   void print() {
      printf( "%lf + j%lf¥n" , re , im ) ;
   }
   Complex( double r , double i )  // コンストラクタで要素の
     : re( r ) , im( i ) {         //  初期化はこのように書いてもいい
   }                               // re = r ; im = i ; の意味
   Complex()      // デフォルトコンストラクタ
     : re( 0.0 ) , im( 0.0 ) {
   }

   void add( Complex z ) {
      // 加算は、直交座標系だと極めてシンプル
      re = re + z.re ;
      im = im + z.im ;
   }
   void mul( Complex z ) {
      // 乗算は、直交座標系だと、ちょっと煩雑
      double r = re * z.re - im * z.im ;
      double i = re * z.im + im * z.re ;
      re = r ;
      im = i ;
   }
   double get_re() {
      return re ;
   }
   double get_im() {
      return im ;
   }
   double get_abs() { // 絶対値
      return sqrt( re*re + im*im ) ;
   }
   double get_arg() { // 偏角
      return atan2( im , re ) ;
   }
} ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね
int main() {
   // 複素数を作る
   Complex a( 1.0 , 2.0 ) ;
   Complex b( 2.0 , 3.0 ) ;

   // 複素数の計算
   a.print() ;
   a.add( b ) ;
   a.print() ;
   a.mul( b ) ;
   a.print() ;

   return 0 ;
}

練習課題

  • 上記の直交座標系の複素数のクラスのプログラムを入力し、動作を確認せよ。
  • このプログラムに減算や除算の処理を追加せよ。

この練習課題は、次週に予定している「曲座標系の複素数クラス」に変更となった場合のプログラムを加え、第1回のレポート課題となります。

創造工学演習・PHPとDB(予備実験)

インターネットを活用したプログラムを作成する場合、データを保存管理するためのデータベースと、データベースのデータを処理するためのプログラム言語が必要となってくる。今回の予備実験では、そのためにリレーショナルデータベースと、Webの動的なプログラム言語である PHP について説明する。

リレーショナル・データベース

データベースは、データを保存し、矛盾が発生しない様に管理してくれるシステムであり、インターネットで活用されている。

データを確実に保存し、矛盾なく扱うためには、本来複雑なプログラムが必要となる。この中で、データを表形式のテーブルを組み合わせて管理するシステムはリレーショナルデータベースと呼ばれる。リレーショナルデータベースでは、データの問い合わせなどの処理が簡単にできるように、SQL と呼ばれる言語を使って処理を行う。

大量のデータをインターネットの中で利用するためには、ネットワークを経由してデータの問い合わせが求められ、有名なデータベースシステムには、Oracle, MySQL などがある。今回の実験では、ネットワーク機能は持たないが簡単な手続きで使うことができる SQLite を使って説明する。

また、今回の予備実験では時間も限られることから、複数の表を組み合わせた SQL の処理については割愛する。

SQLの基本

リレーショナルデータベースでは、データの基本は表形式データであり、1つの表に相当するデータはテーブルと呼ぶ。

以下の様な名前・住所・年齢のデータがあったとすると、1人前のデータをレコードと呼び、name, addr, age といった属性はカラムと呼ぶ。

name addr age
t-saitoh 越前市 55 ←レコード
sakamoto 福井市 50
murata 福井市 35
↑カラム

データの型には、文字列型(char型,varchar型,text型)や、数値型(integer型,decimal型,real型)などがあり、create table 文にてカラムの型を定義する。

create table テーブルを作る

データベースの表を使う最初には、create table 文を実行する。C言語での struct 文をイメージすると解り易いかもしれないが、データはデータベースの中に永続的に保存されるので、システムを動かす最初に一度実行するだけで良い。

上記のような名前・住所・年齢のデータ構造であれば、次の様な create table 文を使う。

create table テーブル名 (
    カラム名1  型1 ,
    カラム名2  型2 
    ) ;
-- 例 --
create table PERSON (        -- テーブル名:PERSON
    name  varchar( 20 ) ,    -- 名前
    addr  varchar( 20 ) ,    -- 住所
    age   integer ,          -- 年齢
    primary key( name )      -- name はデータ検索のキーであり重複は許されない
    ) ;

これと同じ様な処理をC言語で書くのであれば、以下の様な構造体宣言と同じであろう。

struct PERSON {
    char name[ 20 ] ;    // 名前
    char addr[ 20 ] ;    // 住所
    int  age ;           // 年齢
} ;

drop table テーブルを消す

データベースは永続的に保存されるので、テーブル全体のデータが不要であれば、drop table 命令で、テーブル全体を消す。

drop table テーブル名 ;
-- 例 --
drop table PERSON ;

insert into レコードを追加

データベースに1レコードを保存するには、insert文を用いる。

insert into テーブル名 ( カラム名... ) values( 値... ) ;
-- 例 --
insert into PERSON ( name ,       addr ,    age )
            values ( 't-saitoh' , '越前市' , 55  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'sakamoto' , '福井市' , 50  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'murata' ,   '福井市' , 35  ) ;

delete レコードを消す

データベースのレコードを消すには、delete 文を用いる。条件を満たす複数のデータをまとめて消すことができる。

delete from テーブル名 where 条件 ;
-- 例 --
-- 40歳未満のデータを全て消す。 murata,福井市,35 が消える。
delete from PERSON
       where age < 40 ;

update レコードを更新

データベースのレコードを修正するには、update 文を用いる。条件を満たす複数のデータをまとめて修正することもできる。

update テーブル名 set カラム = 値 where 条件 ;
-- 例 --
-- 住所が越前市のレコードの年齢を 0 にする。
update PERSON set age = 0
       where addr == '越前市' ;

select データを探す

データベースの内容を参照するための命令が select 文。where を記載することで、特定の条件のデータだけを選択したり、特定のカラムだけを抽出することができる。

select カラム名 from テーブル名 where 条件 ;
-- 例 --
-- PERSON の全データを出力
select * from PERSON ;

-- PERSON の住所が福井市だけを選別し、名前と住所を抽出
select name,addr from PERSON
       where addr = '福井市' ;

-- PERSON の年齢の最高値を出力 (集約関数)
select max(age) from PERSON
       where addr = '福井市' ;

-- PERSON の年齢条件を満たす人数を数える (集約関数)
select count(name) from PERSON
       where age >= 50 ;

動的なプログラム言語とPHP

本来、Webサーバが作られた頃は、論文や研究用のデータを公開する物であったが、扱うデータが増えるにつれ、特定の論文や研究データの一覧を表示したり探したりという処理が求められた。こういった処理のためにWebページのアクセスを受けた時に処理を実行する CGI という機能があったが、これを発展させてできたプログラム言語が PHP である。

PHPでは、ページを表示するための HTML の中に <?php?> のといった開始タグ・終了タグの中に、ブラウザから送られてきたデータに合わせて、処理を行うPHPの命令を記述し、データを(一般的にはHTML形式で)表示することができる。基本文法は C 言語に似ているが、様々なデータを扱うために変数にはどのような型でも保存できるようになっている。

ブラウザからデータを送るためのform文

ブラウザで入力欄を作ったり選択肢を表示し、その結果を送るための HTML は、入力フォーム(form)と呼ぶ。

<form method="get" action="処理ページ" >

  <input type="text" name="変数名" />

  <input type="radio" name="変数名" value="値" />
  <input type="checkbox" name="変数名" value="値" />

  <textarea cols="横文字数" rows="行数"></textarea>

  <select name="変数名">
    <option value="値1">表示1</option>
    <option value="値2">表示2</option>
  </select>
  <input type="submit" value="実行ボタンに表示する内容" />
</form>

formでは、入力する項目に変数名の名前を付け、action=”” で示したページにデータを送る。

PHPのプログラムの基本

PHPのプログラムは、外見は一般的に HTML ファイルであり、途中で <?php のタグからは、?> までの範囲が、PHP で処理が行われる。PHP のプログラムで print が実行されると、その場所に print 内容が書かれているような HTML ファイルが生成され、ブラウザで表示される。

PHP の中で変数は、$ で始まり、型宣言は基本的に不要である。

文字データを連結する場合は、”.” 演算子を使う。ダブルクオテーション”…”で囲まれた文字列の中の $名前 の部分は、変数名として扱われ、変数名の内容に置き換えられる。

HTMLのform文の action 属性で示された php であれば、PHPの中で送られてきた値を $_GET[‘変数名’] (method=”get”の場合)、 $_POST[‘変数名’] (method=”post”の場合)、または $_REQUEST[‘変数名’] (method=”get” or “post”) で参照できる。

((( sample.php )))
<html>
   <head>
      <title>sample.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <form action="sample.php" method="POST">
         <input name="A" type="text" />     <!-- 変数 $A -->
         +
         <input name="B" type="text" />     <!-- 変数 $B -->
         =
         <?php 
            ini_set( 'error_reporting' , E_WARNING ) ;
            if ( $_REQUEST[ "A" ] != "" && $_REQUEST[ "B" ] != "" ) {
               print $_REQUEST[ "A" ] + $_REQUEST[ "B" ] ;
            } else {
               print "<INPUT TYPE=submit>" ;
            }
         ?>
      </form>
   </body>
</html>

PHPでデータベースを扱う

SQLのデータベースを、プログラム言語の中で扱う場合は、その記述も色々である。PHPでは以下の様にSQLを扱う。

((( survey-init.php )))
<html>
   <head>
      <title>survey_init.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <?php
         // デバッグ用にエラー警告を表示する
         ini_set( 'error_reporting' , E_WARNING ) ;
         // データベースに接続する
         $data_dir = "../public_data" ;
         $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;
         // データベースを初期化する
         $init_sql = "drop table if exists Survey ;"
                   . "create table Survey ("
                   . "  uid  varchar( 20 ) ,"
                   . "  item varchar( 10 )"
                   . ") ;"
                   . "insert into Survey ( uid , item ) values ( 't-saitoh' , '猫'        ) ;"
                   . "insert into Survey ( uid , item ) values ( 'tomoko' ,   'ケーキ'     ) ;"
                   . "insert into Survey ( uid , item ) values ( 'mitsuki' ,  'ボードゲーム' ) ;"
                   ;
         if ( $dbh->exec( $init_sql ) < 0 ) {
            print "Error: $init_sql" ;
         }
         // データベースの表形式を読み出し、表形式で出力する。
         print "<table border='1'>\n" ;
         print "<tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;
         $select_sql = "select uid,item from Survey ;" ;
         foreach( $dbh->query( $select_sql ) as list( $uid , $item ) ) {
            print "<tr><td>$uid</td><td>$item</td></tr>\n" ;
         }
         print "<table>\n" ;

         // データベースの単一データを取り出す
         $count_sql = "select count(item) from Survey where item = 'ケーキ' ;" ;
         print $dbh->query( $count_sql )->fetchColumn() ;
      ?>
   </body>
</html>

PHPの主要なSQL関数(PDO)

$dbh = new PDO(…) ; データベースに接続するハンドラを取得。
$dbh->exec( “create…” ) ; データベースでSQLを実行。
$dbh->query( “select…” ) ; データベースに問い合わせ。「1レコードに対応した配列」が全データだけ繰り返す、2次元配列を返す。
$dbh->query( “…” )->fetchColumn() 結果が1つだけの問い合わせ。集約関数の結果を参照する場合に用いる。

練習問題(1)

  • 上記の survey-init.php の select 文の部分を編集し、色々なデータ検索を試してみよ。

入力フォームのデータをデータベースに書き込む

((( survey-vote.php )))
<?php
    // エラー警告を表示                                                                                                     
    ini_set( 'error_reporting' , E_WARNING ) ;

    // form から送られてきた変数を保存                                                                                      
    $uid  = $_REQUEST[ "uid" ] ;
    $item = $_REQUEST[ "item" ] ;

    // データベースに接続する                                                                                               
    $data_dir = "../public_data" ;
    $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;

    // データベースに項目を追加する                                                                                         
    if ( $uid != "" && $item != "" ) {
        $insert_sql = sprintf( "insert into Survey( uid , item ) values ( %s , %s ) ;" ,
                               $dbh->quote( $uid ) , $dbh->quote( $item ) ) ;
        $dbh->exec( $insert_sql ) ;

        // reload処理で追記しないためページを強制的に再表示させる                                                           
        header( "Location: survey-vote.php" ) ;
    }
?>
<html>
  <head>
    <title>survey_vote.php</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  </head>
  <body>
    <form method="get" action="survey-vote.php">
       名前:   <input type="text" name="uid" />
       好きな物:<input type="text" name="item" />
       <input type="submit" value="投票" />
    </form>
    <?php
      // データベースの表形式を読み出し、表形式で出力する。                                                                   
      print "<table border='1'>\n" ;
      print "  <tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;

      $select_sql = "select uid,item from Survey ;" ;
      foreach( $dbh->query( $select_sql ) as list( $t_uid , $t_item ) ) {
          print "  <tr><td>$t_uid</td><td>$t_item</td></tr>\n" ;
      }
      print "</table>\n" ;
    ?>
  </body>
</html>

練習問題(2)

  • 上記の survey-vote.php のプログラムを編集し色々な入力方法・出力方法を試してみよ。
    • 例えば、入力の item 選択に select や ラジオボタン フォームを使う。
    • 例えば、出力結果で、item の投票結果を、棒グラフで出力する。

新入生の昼食風景

{CAPTION}
今年の新入生は、天気の良い日はこんな感じでピクニック昼食が多い。コロナで教室の密を避けてるのかな。

DCON2021で福井高専チーム優勝

4/17(土) に開催された 第2回全国高等専門学校 ディープラーニングコンテスト2021 にて、福井高専のプログラミング研究会チームの D-ON にて優勝しました。

「全国高等専門学校ディープラーニングコンテスト(DCON)」は高専生が日頃培った<ものづくりの技術>と人工知能(AI)分野の重要技術<ディープラーニング>を活用した作品を制作し、生み出される<事業性>を企業評価額で競うコンテストです。

D-ON

D-ON / トンネルや橋の点検のために行われる打音検査を低コストで実現するためのシステム。「打音検査が必要なトンネルや橋は日本で約80万以上あるが、熟練の点検員が検査を行う必要があるため、コストが掛かっている」という課題の解決を目指しシステムが作られました。
プログラミング研究会(4EI 前川, 小川, 指導:村田) (写真はDCON2021 HPより引用)

DCON2021 Twitter のページより引用

値渡しとポインタ渡し

C言語をあまりやっていない学科の人向けのC言語の基礎として、関数との値渡し, ポインタ渡しについて説明する。ただし、参照渡しについては電子情報の授業でも細かく扱っていない内容なので電子情報系学生も要注意。

オブジェクト指向のプログラムでは、構造体のポインタ渡し(というよりは参照渡し)を多用するが、その基本となる関数との値の受け渡しの理解のため、以下に値渡し・ポインタ渡し・参照渡しについて説明する。

ポインタと引数

値渡し

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
   return 0 ;
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
   return 0 ;
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
int main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
   return 0 ;
}

ポインタ渡し

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
int main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
   return 0 ;   // さらに125と増える
}

ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを極力使わないようにするために、参照渡しを利用する。ただし、ポインタ渡しも参照渡しも、機械語レベルでは同じ処理にすぎない。

参照渡し

// ポインタ渡しのプログラム
void foo( int& x ) {  // xは参照
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後 main::a は 124 に増えている。
   foo( a ) ;  // 124
   return 0 ;  // さらに125と増える。
}

構造体のポインタ渡し

ここまでの説明を踏まえ、構造体を使ったプログラムでは、構造体のポインタ渡しが一般的である。以下に、名前と年齢のデータを扱うプログラムを示す。

// 構造体のポインタ渡しのプログラム
struct Person {
   int name[ 20 ] ;
   int age ;
} ;
// 構造体にデータを代入するための関数
void set_Person( struct Person* p , char nm[] , int ag ) {
   // ポインタ参照で書くと以下の通り
   strcpy( (*p).name , nm ) ;
   (*p).age = ag ;
   // アロー演算子を使うとシンプルに書ける。
   // strcpy( p->name , nm ) ;
   // p->age = ag ;
}

// 構造体のデータを表示するための関数
void print_Person( struct Person* p ) {
   printf( "%s %d¥n" , p->name , p->age ) ;
}

// 関数名さえ処理の意図がつたわる名前を使えば、
// 値をセットして、表示する...ぐらいは一目瞭然。
// 構造体の中身を知らなくても、関数の中身を知らなくても、
// やりたいことは伝わる。...隠蔽化
int main() {
   struct Person tsaitoh ;
   // tsaitohに set して、
   set_Person( &tsaitoh , "t-saitoh" , 55 ) ;
   // tsaitohを print する。
   print_Person( &tsaitoh ) ;
   return 0 ;
}

このプログラムでは、main() の部分だけを見ると、tsaitoh という Person というデータがあり、set_Person() で値をセットして、print_Person() で値を出力するという雰囲気は伝わる。

この main() であれば、Person の name が文字配列とか age が int 型といった情報は知らなくても使える。(データ構造の隠蔽化)

また、set_Person() や print_Person() もどんな関数を使って表示しているのかも知らなくてもいい。(手続きの隠蔽化)

これにより、Person というデータ構造やそれを扱う処理の中身を設計する人と、Person というデータを使う人でプログラム開発の分業ができる。さらに、プログラムで不具合があったときは、Personの内部が悪いのか、使い方が悪いのかの原因の切り分けも明確になる。

オブジェクト指向プログラミングに書き換え

// 構造体のポインタ渡しのプログラム
class Person {
private:
   int name[ 20 ] ;
   int age ;
public:
   void set( char nm[] , int ag ) {
      strcpy( name , nm ) ;
      age = ag ;
   }
   void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;  // ← この行の「;」に要注意

int main() {
   Person tsaitoh ;
   // tsaitohに set して、
   tsaitoh.set( "t-saitoh" , 55 ) ;
   // tsaitohを print する。
   tsaitoh.print() ;
   return 0 ;
}

繰り返し処理と処理時間の見積もり

単純サーチの処理時間

ここで、プログラムの実行時間を細かく分析してみる。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その1つ1つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を とする。

この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。

ここで例題

この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか?

感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、Tβ,Tα は何秒だったのだろうか? 上記のT(N)=Tα+NTβ に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、データ処理では N が小さな値の場合はあまり考えない。N が巨大な値であれば、Tαは、1000Tβに比べれば微々たる値という点である。よって

で考えれば良い。これであれば、T(1000)=5μ秒=Tβ×1000 よって、Tβ=5n秒となる。この結果、T(10000)=Tβ×10000=50μ秒 となる。

2分探索法と処理時間

次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。

// ((case-2))
// 2分探索法
int L=0 , R=size ; // プログラムは複雑になった 
while( L != R ) {
   int M = (L + R) / 2 ;
   if ( a[M] == key )
      break ;
   else if ( a[M] < key )
      L = M + 1 ;
   else
      R = M ;
}

このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。

    …両辺のlogをとる

2分探索は、繰り返し処理であるから、処理時間は、

ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式で係数が出てくるが、これはTβに含めて考えればいい。

単純なソート(選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。

int a[ 1000 ] = { 対象となるデータ } ;
int size = N ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は…

… i=0の時
… i=1の時
:
         … i=N-1の時

        …(参考 数列の和の公式)

となる。

オーダー記法

ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
2分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ オーダーNのアルゴリズム
2分探索法 オーダー log N のアルゴリズム
最大選択法 オーダー N2 のアルゴリズム

練習問題

  1. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか?
  2. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
    データ10000件なら何[sec]かかるか?
    (ヒント: 底変換の公式)
  3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このようなアルゴリズムの例を答えよ。
  4. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?
    (ヒント: ロピタルの定理)
  • 2と4の解説
  • 1は、N→∞において、N2<<2Nなので、O(2N) 。厳密に回答するなら、練習問題4と同様の説明を行う。
  • 3は、O(1)。誤答の例:O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)

再帰呼び出しの予習

次の講義の基礎を確認という意味で、再帰呼出しと簡単な処理の例を説明する。

最初に定番の階乗(fact)

次に、フィボナッチ数列の場合

次の講義への導入問題

ここで示す導入問題をすべて答えるには、若干の予習が必要です。まずはどういう考え方をすれば解けるかな…を考えてみてください。

  • fact(N)の処理時間を、のような式で表現し、処理時間をオーダ記法で答えよ。
  • 以下のプログラムの実行結果を答えよ。また、関数sum()の処理時間を対象となるデータ件数N=RLを用いてのような式で表現せよ。
int a[] = { 1 , 5 , 8 , 9 , 2 , 3 , 4 , 7 } ;
int sum( int a[] , int L , int R ) {
   if ( R-L == 1 ) {
      return a[L] ;
   } else {
      int M = (L + R) / 2 ;
      return sum( a , L , M ) + sum( a , M , R ) ;
   }
}
int main() {
   printf( "%d¥n" , sum( a , 0 , 8 ) ) ;
   return 0 ;
}

情報構造論2021ガイダンス

基本的なガイダンス

情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。ただし、今後の休講などの影響で評価方法は随時変更を行う。

プログラムを評価する3つのポイント

まずは以下を読む前に、質問。

  • あなたが良いプログラムを作るために何を考えて作りますか? ※1
    • ここまでの段階で3つの要点を考えメモしておいてください。
    • ガイダンス最初のレポートに使います。

具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。

  • プログラムの速度
  • プログラムのわかり易さ
  • メモリの使用量

プログラムを作る場合、この3要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

メモリの使用量の影響

メモリを大量に使用すると、どういった影響がでるのか? OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)

しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)

ソフトウェアとアルゴリズムとプログラム

用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か?

  • アルゴリズム – 計算手順の考え方。
  • プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
  • ソフトウェア – プログラムと、その処理に必要なデータ。(日本語を変換するプログラムは、日本語の辞書データが無いと動かない)
  • パラダイム – プログラムをどう表現すると分かりやすいか?

トレードオフ関係をプログラムで確認

例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)

// ((case-2))
// 2分探索法
int L=0 , R=size ; // プログラムは複雑になった 
while( L != R ) {
   int M = (L + R) / 2 ;
   if ( a[M] == key )
      break ;
   else if ( a[M] < key )
      L = M + 1 ;
   else
      R = M ;
}

でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)

// ((case-3))
// 添字がデータ O(1)
// 探すデータが電話番号 272925 のような 6 桁ならば
int a[ 1000000 ] ;
a[ 272925 ] = 272925 ;
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られた予算からメモリやCPUが決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ?ゲームがバグですぐに変な動きしたらキレるでしょ!発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!