情報構造論の質問の回答
今日は、遠隔授業形式で初めての情報構造論を行った。
ペン書きを交えながらの説明はそれなりにうまくいったかな。
今日は、2重forループの処理時間の分析の説明を行ったけど、最後の説明は次回の授業への橋渡しで(To be continued…)的に終わらせたんだけど、積極的な学生さんからチャットで質問があったので、解説しちゃえ。
2重forループの処理時間の見積もり
内容は、以下のようなプログラムが、foo(100)で1msecかかったとして、foo(1000)は何秒かかる？
int foo( int n ) {
int c = 0 ;
for( int i = 0 ; i < n ; i++ )
for( int j = 0 ; j < i ; j++ )
c++ ;
return c ;
}
勘がいい人なら、2重forループだし処理時間は に比例するから、
が10倍なら処理時間は100倍なので 100msec と速攻で答えるかもしれない。でもここはもう少し複雑な見積もりの基礎を説明するのが目標ということで、もう少し厳密な説明を示す。
授業でも解説したが、このプログラムの処理時間は、以下の式で表せる。
よって、の条件で解けばいい…。
ただ、未知変数がと3つある癖に、与えられた式は１つだけ。本来なら、この方程式は解けない。
こういった処理速度を予測するといったニーズでは、通常Nの値は、ある程度大きな値。しかも、正確な時間を求めるのではなく、大まかな見積もりがしたいだけ。だとすると、 の項目は、
に比べて小さな値のはずなので、最初の方程式も以下の式で考えればいい。
そうなると、なので、
となる。
よって、となる。
授業が終わってのアンケート、初めての遠隔授業だったけど、おべんちゃらも入ってるだろうけど「わかりやすかった」との言葉をもらえました。学生さんの感想の中には「先生の操作を近くの画面で見れるので、説明も理解しやすかった。トイレにいても授業に参加できます！」との楽しい💩感想ももらえました。👍
値渡しとポインタ渡し
前回はWeb提示資料と課題でガイダンスを行ったが、今日は遠隔授業形式での初回。前回のガイダンス資料を前半ざっと流し、後半はC言語をあまりやっていない学科の人向けのC言語の基礎。ただし、参照渡しについては電子情報の授業でも細かく扱っていない内容なので電子情報系学生の人はそこだけ注意してね。
オブジェクト指向のプログラムでは、構造体のポインタ渡しを多用するが、その基本となる関数との値の受け渡しの理解のため、以下に値渡し・ポインタ渡し・参照渡しについて説明する。
ポインタと引数
値渡し
// 値渡しのプログラム
void foo( int x ) { // x は局所変数(仮引数は呼出時に
// 対応する実引数で初期化される。
x++ ;
printf( "%d¥n" , x ) ;
}
void main() {
int a = 123 ;
foo( a ) ; // 124
// 処理後も main::a は 123 のまま。
foo( a ) ; // 124
}
このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか？
// 大域変数を使う場合
int x ;
void foo() {
x++ ;
printf( "%d¥n" , x ) ;
}
void main() {
x = 123 ;
foo() ; // 124
foo() ; // 125
}
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
for( i = 0 ; i < 2 ; i++ )
printf( "A" ) ;
}
void main() {
for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と
foo() ; // 表示されない。
}
ポインタ渡し
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。
// ポインタ渡しのプログラム
void foo( int* p ) { // p はポインタ
(*p)++ ;
printf( "%d¥n" , *p ) ;
}
void main() {
int a = 123 ;
foo( &a ) ; // 124
// 処理後 main::a は 124 に増えている。
foo( &a ) ; // 124
} // さらに125と増える。
ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを使わないようにするために、参照渡しを利用する。
参照渡し
// ポインタ渡しのプログラム void foo( int& x ) { // xは参照 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( a ) ; // 124 } // さらに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 ) ;
}
// 関数名さえ処理の意図がつたわる名前を使えば、
// 値をセットして、表示する...ぐらいは一目瞭然。
// 構造体の中身を知らなくても、関数の中身を知らなくても、
// やりたいことは伝わる。...隠蔽化
void main() {
struct Person tsaitoh ;
// tsaitohに set して、
set_Person( &tsaitoh , "t-saitoh" , 55 ) ;
// tsaitohを print する。
print_Person( &tsaitoh ) ;
}
Teams 説明会のトラヒック
nitfukui の名前取得
このコロナ騒動の中、Office365のID+PWは、本科-新1年生に配布できていない状態。公式の情報を伝えるのにも一苦労。その中で今回、校長のことばを伝えるために、YouTube を試験的に取り入れた。メディア研究室のチャネルを使うとかいう話もあったけど、新たに Gmail の nitfukui のアカウントをとったりしながら、開設となった。
こういったSNSなどで使う名前は、原則早い者勝ちが基本ルール。ただあまりにも広く知れ渡っているものは、あとで取り返すことができる。サイバースクワッティング
実際、Twitter の某アカウントは、福井高専のOBが取得していて、アイコンも校章で、投稿内容は学校のイメージダウンするような内容だったりする。
このため、サイバースクワッティング対策としては、早い者勝ちで取るしかない。
https://facebook.com/fukui.kosen とか、https://twitter.com/FukuiKousen などは、以前に私が取得し、非公式だけどそれなりに活用中。ただ、法人化になってからは、福井高専は、National Institute of Technology, fukui college なので、短縮名だと “nitfukui” だし、Twitter のアカウントで、 @nitfukui を取得しておきたい。
ちなみに、slack の nit-fukui.slack.com, nitfukui.slack.com は、私が取得してある。(つかってねーけど)
fukuikousen-bot の更新周期を短く
福井高専のホームページの最新情報を、つぶやく bot ( https://twitter.com/FukuiKousen )を動かしているけど、この連日、コロナウィルスのため重要な公式情報の流れる機会が増えている。
通常は、5時,9時,11時,15時,19時 としていたが、当面頻度を高めておこう。8時から22時まで2時間刻みとしておく。
オブジェクト指向/2020/ガイダンス
専攻科2年のオブジェクト指向プログラミングの授業の1回目。コロナ対策でこのページを見て簡単な初回課題を提示。
シラバスは、ここに示すように、最近のプログラミングの基本となっているオブジェクト指向について、その機能についてC++言語を用いて説明し、後半では対象(オブジェクト)をモデル化して設計するための考え方(UML)について説明する。
評価は、3つの課題と最終テストを各25%づつで評価を行う。ただし、今回の感染予防の休み期間のレポート課題を別途含める。
オブジェクト指向プログラミングの歴史
最初のプログラム言語のFortran(科学技術計算向け)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct …}の考えができた。(データの構造化)
// C言語の構造体
struct Person { // 1人分のデータ構造をPersonとする
char name[ 20 ] ; // 名前
int b_year, b_month, b_day ; // 誕生日
} ;
一方、初期のFortranでは、プログラムの処理順序は、繰り返し処理も if 文と goto 文で記載し、処理がわかりにくかった。その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で 記述する方法ができてきた。(処理の構造化)
// ブロックの考えがない時代の雰囲気をC言語で表すと
int i = 0 ;
LOOP: if ( i >= 10 ) goto EXIT ;
if ( i % 2 != 0 ) goto NEXT ;
printf( "%d " , i ) ;
NEXT: i++ ;
goto LOOP ;
EXIT:
// C 言語で書けば
int i ;
for( i = 0 ; i < 10 ; i++ ) {
if ( i % 2 == 0 ) {
printf( "%d¥n" , i ) ;
}
}
このデータの構造化・処理の構造化により、プログラムの分かりやすさは向上し、このデータと処理をブロック化した書き方は「構造化プログラミング(Structured Programming)」 と呼ばれる。
この後、様々なプログラム言語が開発され、C言語などもできてきた。 一方で、シミュレーションのプログラム開発(例simula)では、 シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、 データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。 これがオブジェクト指向プログラミング(Object Oriented Programming)の始まりとなる。略記するときは OOP などと書くことが多い。
この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから、この考え方は多くのプログラム言語へと取り入れられていく。
C言語にこのオブジェクト指向を取り入れ、C++が開発される。さらに、この文法をベースとした、 Javaなどが開発されている。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。
構造体の導入
C++でのオブジェクト指向は、C言語の構造体の表記がベースになっているので、まずは構造体の説明。詳細な配布資料を以下に示す。
// 構造体の宣言
struct Person { // Personが構造体につけた名前
char name[ 20 ] ; // 要素1
int phone ; // 要素2
} ; // 構造体定義とデータ構造宣言を
// 別に書く時は「;」の書き忘れに注意
// 構造体変数の宣言
struct Person saitoh ;
struct Person data[ 10 ] ;
// 実際にデータを参照 構造体変数.要素名
strcpy( saitoh.name , "t-saitoh" ) ;
saitoh.phone = 272925 ;
for( int i = 0 ; i < 10 ; i++ ) {
scanf( "%d%s" , data[ i ].name , &(data[ i ].phone) ) ;
}
感染予防による休講期間中の課題
以下の3つについてレポートにまとめ、ここに示すURLのファイル共有に提出せよ。Office365の接続がうまくいかない場合は、メールにてレポートを提出でも良い。
- 今まで、プログラムを作成する際に、わかりやすいプログラムを作成するために、自分自身がどのような考え方をとっていたか(工夫していたか)、考え方を10行程度に考えをまとめること。
- オブジェクト指向の歴史に関連する以下のワードの中から、2つを選んでインターネットをつかって調べ、自分なりの言葉でまとめ、簡単に説明せよ。
- Fortran90, ALGOL, Smalltalk80, 入れ子とインデント, Dijkstraのgoto文有害論, プログラミングパラダイム
- 以下に、C言語の構造体を使った基本的なプログラムを示す。このプログラムでは、国語,算数,理科の3科目と名前の5人分のデータより、各人の平均点を計算している。このプログラムを動かし、以下の機能を追加せよ。レポートには プログラムリストと動作結果の分かる結果を付けること。
- 国語の最低点の人を探し、名前を表示する処理。
- 算数の平均点を求める処理。
#include <stdio.h>
struct Student {
char name[ 20 ] ;
int kokugo ;
int sansu ;
int rika ;
} ;
struct Student table[5] = {
// name , kokugo , sansu , rika
{ "Aoyama" , 56 , 95 , 83 } ,
{ "Kondoh" , 78 , 80 , 64 } ,
{ "Saitoh" , 42 , 78 , 88 } ,
{ "Sakamoto" , 85 , 90 , 36 } ,
{ "Yamagoshi",100 , 72 , 65 } ,
} ;
int main() {
int i = 0 ;
for( i = 0 ; i < 5 ; i++ ) {
double sum = table[i].kokugo + table[i].sansu + table[i].rika ;
printf( "%-10.10s %3d %3d %3d %6.2lf\n" ,
table[i].name , table[i].kokugo , table[i].sansu , table[i].rika ,
sum / 3.0 ) ;
}
return 0 ;
}
制御構文の理解
コロナ対策で、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までとする)
2020年度情報構造論ガイダンス
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、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) 当初のフォルダが書き込み禁止状態だったので、提出場所を変更、書き込み許可を与えたので改めて提出をお願いします。
入学式のネット配信も中止
入学式のネット配信の中止
新型コロナ対策で、入学式も大人数を集めての実施もできず、クラス毎に教室に別れ、保護者の方もクラス毎に分かれて実施の予定でした。来ていただいた保護者の方にも少しでも入学式を楽しんでもらおうと、校長の訓示、学生の呼名を各部屋間をネット中継すべく、有志の先生に協力してもらい準備してました。
しかし、福井県も患者数も増え、週末の外出自粛、公立校も再開延期で、本校も入学式・ホームルームなども延期となりました。
ネットの準備はひとまず無駄になったけど、TeamsやStreamの使い方の勉強になりました。
ネット配信の案
入学式のネット配信は、新入学生の撮影などの問題もあることから、各教室、保護者控室に限定した配信で、以下のような予定でした。
しかし、入学式を短時間で終わらせたい事情も考慮しました。
最終的には、配信は以下のような構成となりました。
