情報構造論・ガイダンス
最初の授業ということで、シラバスなどのガイダンスに交えて、 「プログラムを作る時、何を考慮して書くべきか」という質問をしてみた。 こちらとしては、プログラムでのアルゴリズム評価の観点ということで、 「処理速度」、「使用メモリ量」、「アルゴリズムの複雑さ」という答えを 期待していたんだけれど、プログラムの見易さについての返答ばかり。 「処理速度」という答えがでるまでに随分と時間がかかってしまった。
速度・メモリ・複雑さの3つは、それぞれ速度優先のアルゴリズムは、メモリを大量消費したり、 プログラムが複雑になるなど、一方を優先すれば他方に悪影響のでる トレードオフの関係にあることを解説。 単純検索・2分探索法・全データメモリーマップなどの方法を例に挙げて説明を行う。 プログラム開発では、トレードオフの関係にあるからこそ、 その状況に応じたアルゴリズムを選択(デザイン)できるためにも、 速度・メモリ・複雑さを客観的に評価できる必要性がある。
速度の評価
まず手始めに、N件のデータを配列の中から探す処理で説明。
int data[ N ] ; int key = ??? ; for( int i = 0 ; i < N ; i++ ) { if ( data[ i ] == key ) break ; }
このプログラムの実行時間を考えると、最悪のケースでは、式の実行回数は、 i=0 | 1回、i < N | N+1回、i++,if(==) | N回となる。 よって、処理時間は、以下の式で示される。
このプログラムで、1000件で1msecの時間を要した場合、 10000件であれば、何秒かかるか?という問題があった場合、2変数1式であり 通常では処理時間を求めることができない。しかし、 処理速度の見積もりでは、大抵データ件数Nは巨大な場合がほとんどであり、 も、1回の初期化の時間であり、きわめて小さい値が一般的であり、無視できる。 よって、
から、10000件では、10msecという予想時間を求めることができる。
次に、もう少し複雑な例ということで、データの並び替えで最大選択法の プログラムを示し、処理時間を議論する。
int data[ N ] ; int i , j , m , t ; for( i = 0 ; i < N-1 ; i++ ) { m = i ; for( j = i+1 ; j < N ; j++ ) if ( data[ m ] < data[ j ] ) m = j ; t = data[ m ] ; data[ m ] = data[ i ] ; data[ i ] = t ; }
内部のjのループの実行回数は、(N-1-i) 回であり、 これを外側iのループで回すため、以下のような式で示される。
プログラミング応用・ガイダンス
プログラミング応用の最初ということで、授業の方針やシラバスを示しながら、 テストや評価方法などを解説。後半は、プログラミングの基礎を改めて説明。
制御構文:C言語の復習ということで制御構文について示す。 最初に文の定義として、式や制御構文、複文、空文などを説明し、 複数の文から大きな文が作られることを話す。 理解確認のために、例年通りforループの処理順序を書かせながら、 if(式)文 else 文、while(式)文、do 文 while(式) ; 、for(式;式;式) 文、break、continueなどを説明する。 breakなどで goto 文はほぼ不要となっている話の雑談として、 構造化プログラミングについて話し、処理の構造化・データの構造化を解説。 用語として、インデント、ネスティング(入れ子)など。
来週は、switch(…) case などの説明から。