ホーム » 2015 (ページ 11)
年別アーカイブ: 2015
Debian 8.0/Jessie のインストール
Debian 8.0 / Jessie が stable となって配布が始まったので、 まずは影響の少ないサーバに入れてみる。 自宅や自室のサーバは、すでに Jessie に切り替え済みだけど、 久々だと、なかなか手間取る。
# aptitude remove `dpkg -l | awk '{print $2}' | egrep -e ^kde-` # aptitude remove `dpkg -l | awk '{print $2}' | egrep -e ^gnome-`
あたりを実行して、依存の原因となりそうなパッケージはひとまず 減らしてから、
# aptitude update ; aptitude full-upgrade
ただし、処理中に libxml-libxml-perl が更新前の削除でエラーが発生し 手間取ってしまった。パッケージの依存情報の微妙なエラーがあるようだ。 この次に学科のメインサーバの更新となるが、 その際には、一番最初に削除してからにしよう。
再起動させたら失敗
更新は上手くいったが、翌朝再起動をかけたら起動しない。 Debian/Jessie/netinst のCDを作り、リカバリーモードで起動させる。
起動時には、ブートローダーで linux-image-2.16 なんかを探しているので、 古いブートローダーを使おうとしている。どうも、grub2のインストールで失敗していた様子。 以下のコマンドで、インストールを確認し再起動。
# aptitude install grub2 # grub-install /dev/sda # update-grub
更新の最終段階は、夜中に家からの作業だったけど、reboot は翌朝にして正解だった…(x_x;
2015年4月26日(第420回)
体育祭準備のため、収録でお送りしました。
- まるよし Train Pops ~ 国語と遊ぼう! 第100便 「寄せ書き」
- 体育祭の思い出
- 体育祭の撮影について
- お花見について
担当:田中(2B・MC)、植村(2E・MIX)、山田(2B)、川﨑(2EI)、西(教員)
再帰関数の処理と再帰方程式
前回の授業で、処理速度のオーダ記法について解説し、 実際例と処理速度の問題について解説する。 後半は、再帰呼び出しの処理速度見積もりのための再帰方程式を示す。
特殊な処理時間の見積もり
前回授業の最後に検討しておくようにと伝えた、 の処理時間のオーダについて、Nが巨大となった時の、最大項を見つければ良いことから、
が、N→∞において 発散するのか収束するのかを求める方法にて説明する。
また、2つのアルゴリズムがNの増加で処理時間が変化する時の事例として、 「データ件数が10件で、最大選択ソートが10msec、クイックソートが20msec出会った場合、 データ100件では、どちらが速いか?、この結果から、 データ件数がいくつ以上であれば、どちらの方法が良いか?」 といった問題について説明する。
最大選択ソートであれば、 より、
であるとする。 一方、クイックソートは、
より、
であるとする。
より、
。
より、
。
これより、データ100件の場合には、 となる。 また、
となりクイックソートの方が速い。
さらに、 となるNを求めれば、N件以上は クイックソートが速い…といった件数を求められる。
再帰関数と再帰方程式
再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。
// 階乗 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 といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、
で表せる。 これを代入によって解けば、
で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。
最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。
ハノイの塔
ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、
ということが予想される。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、
ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、
枚では、
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
C言語の構造体からオブジェクト指向に
前回の構造体の説明から、ポインタ渡しの説明を行った後、同様のプログラムをC++で書き換えることで、classやメソッドなどの説明を行う。
構造体でオブジェクト指向もどき
例えば、名前と電話番号の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ実装者で分けて 仕事ができることを説明。
struct Person { char name[10] ; int phone ; } ; void readPerson( struct Person* p ) { // ポインタの参照で表記 scanf("%s%d" , (*p).name , &(*p).phone ) ; } void printPerson( struct Person* p ) { // アロー演算子で表記 printf( "%s %d¥n" , p->name , p->phone ) ; } void main() { struct Person table[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { readPerson( &table[i] ) ; printPerson( &table[i] ) ; } }
このプログラムの書き方では、mainの中を読むだけもで、 データ入力とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、readPerson()や、printPerson()という関数の中身についても、 入力・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。
C++のクラスで表現
上記のプログラムをそのままC++に書き直すと以下のようになる。
class Person { private: // クラス外からアクセスできない部分 char name[10] ; // メンバーの宣言 int phone ; public: // クラス外から使える部分 void read() { // メソッドの宣言 // pのように対象のオブジェクトを明記する必要はない。 scanf( "%s%d" , name , &phone ) ; } void print() { printf( "%s %d¥n" , name , phone ) ; } } ; void main() { Person table[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { table[i].read() ; // メソッドの呼び出し table[i].print() ; // オブジェクト.メソッド() } // 文法エラーの例 printf( "%d¥n" , table[0].phone ) ; // phoneはprivateなので参照できない。 }
用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
コンストラクタとデストラクタ
プログラムを記述する場合、そのデータ構造を使うにあたり、 初期値が代入を忘れその値を参照すると、予想外の動きの原因となってしまうことが多い。
そこでオブジェクト指向では、データ構造の初期化手続き(同様に処理が終わった後の事後手続き)を 明確に記載するための初期化のコンストラクタ(と事後処理はデストラクタ)の文法がある。
class Person { private: char name[10] ; int phone ; public: Person( char s[] , int tel ) { // コンストラクタ strcpy( name , s ) ; phone = tel ; } void print() { printf( "%s %d¥n" , name , phone ) ; } } ; void main() { // オブジェクト宣言とコンストラクタでの初期化 Person saitoh( "tsaitoh" , 272925 ) ; saitoh.print() ; }
コンストラクタを宣言する場合には、返り値無しのクラス名を関数名として記述する。 デストラクタを宣言する場合には、先頭に「~」をつけたクラス名で無引数で記述する。 簡単な例として、文字列をヒープ領域に保存する処理を示す。
// デストラクタが便利な例 class String { private: char* str ; public: // コンストラクタ String( char*s ) { // ヒープメモリ上に文字列を確保 str = (char*)malloc( strlen( s ) + 1 ) ; strcpy( str , s ) ; } // デストラクタ ~String() { free( str ) ; // freeしないとメモリーリークになる。 } void print() { printf( "%s" , str ) ; } } ; void main() { String s( "abcdefg" ) ; s.print() ; } // mainを抜ける段階でsは不要となる。 // ここで自動的にデストラクタ呼び出し~String()をしてくれる。
関数の値渡しと、整数型の数値の範囲
丁度、講義の前に別授業の課題に取り組んでいる学生を見ていたら、 次週に説明を行おうと思っていたN進数、小数点を含む2進数であった。 丁度、「計算機構成論」の補数、「数値計算」の小数点を含む2進数の講義で、 いつもになく、内容と説明時期が重複している…(^_^;
関数の値渡し
関数との引数の値渡しについて解説。 C言語では基本の値渡しメカニズムしかない。 引数で副作用(side effect)を返したい場合は、その代用としてポインタ渡しを利用する。 また、配列が引数の場合、値渡しのためのコピーを最小限とするため、 配列先頭アドレスによるポインタ渡しで行われることを説明する。
// 値渡し void foo( int x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 foo( a ) ; // 124 } // ポインタ渡し void foo( int* px ) { (*px)++ ; printf( "%d¥n" , *px ) ; } void main() { int a = 123 ; foo( &a ) ; // 124 foo( &a ) ; // 125 } // 参照渡し(C++の新しい文法で紹介のみ) void foo( int &x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 foo( a ) ; // 125 } // 配列でのポインタ渡し void foo( int x[] ) { x[0]++ ; printf( "%d¥n" , x[0] ) ; } void main() { int a[1] = { 123 } ; foo( a ) ; // 124 foo( a ) ; // 125 }
整数型の数値範囲
整数型などの数値範囲について説明を行うために、2の補数表現を復習したあと、 数値の範囲について説明する。
type | range | unsigned | signed --------------+-----------+----------+--------------- char | 8bit | 0..255 | -128..127 short int | 16bit | 0..65535 | -32768..32767 int | 32bit | 0..2^32-1| -2^31..2^31-1 long int | ?32bit? | | long long int | gcc 64bit | 0..2^64-1| -2^63..2^63-1
数値範囲の大まかな計算のための2つの方法として、 や、 10進数での桁数の概算のために、
より、
といった計算を行う方法について説明。
次週は、16bitコンピュータで int が簡単に桁あふれする問題や、 2038年問題や2004年問題などを解説する予定。
2015年4月19日(第419回)
- まるよし Train Pops ~ 国語と遊ぼう! 第99便 「最後の授業」 後編
- 海外に旅立ってしまう先生が最後の授業で黒板に何とかいたか?というテーマで大喜利をしました。
- 新学期の授業について
- 新入生歓迎会について
担当:田嶋(3C・MIX)、山田(2B・MC)、稲葉(2EI)、西(教員)
授業アンケートの結果
授業アンケートが、年度末に演習室が使えなかったことから、 時期遅れではあるけれど、結果がでてきた。
プログラミング応用は、昨年度の81.7からは、若干落ちて76.3ポイント。 Q4の板書について、「やや悪い」の評価が多いのと、 Q15の理解把握について、「良い」の評価が少なめなのが、効いているか…。 板書については、文字を大きくとか、記載場所の流れを改めて意識してみよう。
情報構造論は、79.8ポイント。あとちょっとで、80点(学生さんなら優)だったのにぃ。 昨年度は、80.9ポイントなので、連続ポイントダウン。 Q4板書のポイントが、これまた低めなので、改めて意識した書き方の必要があるかな。
講義録記事にヒント表示を導入
講義録をBLOGの形で、ページに掲載するのを、この10年ほど続けているけど、 準備が不十分な場合には、授業で過去の記事をプロジェクタで表示しながら説明… という場合もある。
しかし、過去の記事で丁寧に書いてありすぎると、問題の答えまでモロに記事に 書いておくと、記事を読んでいる学生さんが、何も考えないまま…に なってしまう場合が多い。そこで、BLOGのJavaScriptに、 クリック表示/非表示を切り替えられるようなものを埋め込んおくようにした。
// BLOGパーツのJavaScriptに以下を追加 function hint_switch( hs_this ) { // 指定ブロック内の末尾ブロックをinline表示/none非表示をスイッチ if ( hs_this.lastElementChild.style.display == "none" ) { hs_this.lastElementChild.style.display = "inline" ; } else { hs_this.lastElementChild.style.display = "none" ; } }
そして、一時的に非表示にしたい部分には、以下のHTMLを埋め込む。
<div onclick="hint_switch(this)"> <p> // 常に表示しておく部分(ここをクリック) </p> <div style="display: none"> // 一時的に、非表示にしておきたい部分 </div> </div>