コロナ対策で、4年向けの情報構造論も始められないので、自習用資料。

制御構文の理解

基本として、C言語の制御構文の意味をフローチャートで表すと以下のようになる。

条件分岐if

繰り返しwhile, for, do-while

繰り返し命令の中では、break文でループを抜ける、continue文で次の繰り返し先頭に飛ぶ。フローチャートで表すと、上記の図中の赤、青の部分。

条件分岐switch

条件分岐のswitch文は、以下のようなフローチャートで示すことができる。
ただしcase の後には定数式しか書けない。 一般的には、分岐処理のAAA;BBB;CCC;の後ろには、break を書くのが一般的。繰り返し処理の中にswitch文があった場合、break命令では、switch文を抜けるだけで、ループを抜け出す訳ではない。

もし、breakを書き忘れると、以下のようなフローチャートになるので要注意。

このフローチャートを見てわかるように、breakが無いと、X=Bの時、処理BBB,CCCが実行することになる。

文の定義

C言語では、文とは(大雑把に言うと)以下の定義である。複文の所が要注意。

for()の後には1つの文が書ける。単純な計算式であれば、式；で1つの文なので、{,} は本来不要。forの中で複数の処理を書きたい時は、{ 文 文 … } のように複文で1つの文の塊をつくる。

((( C言語の文 )))

// 式 : 計算式が ; で終わっているもの
式 ;

// if文
if ( 式 ) 文
else      文   // else以下略あり

// while文   
while( 式 ) 文
// for文
for( 式 ; 式 ; 式 ) 文
// do-while文
do 文 while( 式 ) ;   // セミコロンまででdo-while文

// 複文
{ 文 文... }   // 複数の文を1つの文として扱う
// 空文
;             // for(;;); これも文法としては正しい

例題

上記の制御構文の意味を踏まえた上で、過去のテスト問題より具体例で説明。

以下のプログラムの動作順序を(A)〜(M)の記号で答えよ。
答えは20ステップ目までで良い。

前述の文の定義を踏まえ、前述の問題の中では、以下の様な命令の塊(ブロック)が存在する。

ここで、水色部分(c)の if 文の break は{,} は不要なのか？という質問をする人が多いけど、if(式) { 文 } と書いても、if(式) 文 でも、文の部分に複文を使うか使わないかの違いにすぎない。

これを踏まえて、フローチャートを書くと以下の通り。

よって、この問題の回答は、以下のようになる。

A(i=0)→	B(i==0)→D(j=0)→	E(j==0)→G→H→　　 F→
		E(j==1)→G→H→I(break)→
	J(j=0)→	K(j==0)→M→L→
		K(j==1)→	C(i=1)→
	B(i==1)→D(j=0)→	E(j==0)→G→H→　　 F→
		E(j==1)→G→H→I(break)→
	J(j=0)→	K(j==0)→M→L→
		K(j==1)→M→L→
		K(j==2)→	C(i=2)→
	B(i==2)

第2回レポート課題

(1) 以下の rep1-1〜rep1-4 の中から1つを選び、処理順序の結果を答えよ。rep-1-(出席番号%4+1)を答えること。(例:出席番号10番の人はrep1-3)

rep-1-1

rep-1-2

rep-1-3

rep-1-4

(2) 以下の foo(n) , bar(n) の関数で、プログラムの(a)〜(i)の計算式の1命令の実行に10[nsec]とする。(それ以外の実行時間は無視して良い)

引数が n=2 , n=4 の場合、各関数foo(n),bar(n)の返り値 cnt の値、foo(n),bar(n) の実行にかかる時間を答えよ。ただし、答えた理由がわかるような情報をつけること。

例えば、命令に実行回数を数えるためのチェックマークの数がわかる資料でも良い。

nの値	foo(n)		bar(n)
	cnt	処理時間	cnt	処理時間
n=2
n=4

(3) n=1024 の時、foo(n),bar(n)はどんな値になると思いますか？

どのように考えて計算すればいいか、考え方を提案してください。

レポート課題は、上記(1),(2),(3)を簡単に(A4×1〜2ページ)まとめ、この共有フォルダに提出して下さい。提出するファイル名は、出席番号-名前-レポート名.拡張子としてください。提出締め切りは、(2020/04/24までとする)

• 講義補足資料
• 反応がないと判らないので、アンケートに回答をお願いします。

基本的なガイダンス

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

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

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

• あなたが良いプログラムを作るために何を考えて作りますか？ ※1
  • ここまでの段階で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が決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

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

第1回課題

• 最初の※1で、あなたが考えた「良いプログラムを作るために考えること」を３つあげてください。
• あなたが考えた３つは、それぞれ、「速度、わかりやすさ、メモリの使用量」のどれに関係すると思いますか？(複数に関連する場合もあります)
• 仮想メモリ、スワッピング、プログラミング・パラダイムの用語の中から１つを選び、意味を調べて簡単にまとめてください。

この3つの内容を簡単に(A4×1ページ)まとめ、この共有フォルダに提出して下さい。提出するファイル名は、出席番号-名前-レポート名.拡張子 (例 01-愛上男-第1回課題.pdf) としてください。提出締め切りは、(2020/04/17までとする)

(2020/04/10,13:40) 当初のフォルダが書き込み禁止状態だったので、提出場所を変更、書き込み許可を与えたので改めて提出をお願いします。