マージソートの処理時間+動的メモリ(malloc/free)
再帰方程式による処理速度の見積りとして、 IMG n /cgi-bin/mimetex.cgi?O(N\log{N}) となる、マージソートを説明する。 処理の内容より再帰方程式をたて、代入法で一般式の予想を行う。
後半は、動的メモリの使い方ということで、 C言語の配列サイズに定数しか使えないことによる、 「想定外のデータ投入」と「余裕をみた際の配列の無駄」を説明する。 この対策として、malloc の使い方、free の使い方を紹介する。
N進数と10進,8進,16進,小数点を含む2進数,double型の範囲と誤差
浮動小数点の説明のために、N進数と10進変換より小数点を含む2進数を説明する。 その後、浮動小数点の扱いの考え方を説明し、扱えるデータの範囲を解説する。 最後に浮動小数点の誤差として、丸め誤差、桁落ちまで説明。
桁落ちの話しで、誤差の有効数字を例にとって説明するが、 「誤差の計算ってどうすれば？」と聞かれる。
プログラムと桁落ち、情報落ちの話しは次回に…
3年で抜けていそうなネタ
昨日実験のレポート提出でも、正しい電気の回路図の書き方 FN 例えば、抵抗のクネクネを大量に書く学生さんやら、GND 記号などの「正式な」書き方を知らない。 /FN や、桁落ちや有効数字などの知識が乏しい学生が多い。 数学的な座学をしている時には、わざわざ時間をとって説明すると、 講義時間がもったいないけど、『常識』としてきちんと話しをしていないとやばいかも。
数値の型と扱える値の範囲
変数の型と扱える数値の範囲の説明として、 char,short int,int,long int の整数型、 float, double の実数型 を説明し、整数 演算子 整数の計算は、整数で行われることによるトラブル事例を紹介。
N bit の整数の扱える範囲
IMG n /cgi-bin/mimetex.cgi?0\sim{2^{N}-1} を説明。
2の補数表現
コンピュータの中では、負の数の扱いには、2の補数が使われ、 最上位ビットを符号ビットに使う。 2の補数とは、2進数 IMG n /cgi-bin/mimetex.cgi?x のbit反転に1を加える方法。 bit反転を IMG n /cgi-bin/mimetex.cgi?\overline{x} としたら、 IMG n /cgi-bin/mimetex.cgi?x+\overline{x}=1111,1111 (8bit)の場合。 IMG n /cgi-bin/mimetex.cgi?x+\overline{x}+1=1,0000,0000 となるが、先頭の1は覚えられないので、 IMG n /cgi-bin/mimetex.cgi?x+\overline{x}+1\simeq{0} よって、2の補数 IMG n /cgi-bin/mimetex.cgi?\overline{x}+1 は IMG n /cgi-bin/mimetex.cgi?-x を表現するのに都合がいい。
よって N bit の2の補数表現で扱える数値の範囲は、 IMG n /cgi-bin/mimetex.cgi?-2^{N-1}\sim(2^{N-1}-1) となる。
数値の範囲のトラブル事例として、2000年問題の32bit版ということで、 2037年問題(正確には2038年)を紹介する。
類似ネタ
- 2038年問題(旧unix系で時間を1970年から IMG n /cgi-bin/mimetex.cgi?(2^{31}-1) 秒までしか時間を扱えない問題)
- 2036年問題(NTPが1900年から IMG n /cgi-bin/mimetex.cgi?(2^{32}-1) 秒までしか時間を扱えない問題)
- 20XX年問題特集
- 2004年銀行系トラブル事例(2038年問題・中間地点)
5EI実験:Webアプリケーションとセキュリティ
5年の実験「Webアプリケーションとセキュリティ」の説明で、 うちの卒研学生さんが2人もいることだし、現実のセキュリティのネタまで「深く」解説する。 Phishing の説明の後、自宅に届いている生の SPAM メールを実際に 見せながら、CGIのリンクに埋め込んだメールアドレスから、 「活きたメールアドレス取得」の手口などを説明する。 HTML メールの危険性なども交えて説明する。
Antinny解析レポート
Winny や Share をベースとして広がるウィルス Antinny の解析レポート。 GW 期間あけに感染拡大が懸念されるので、色々と啓蒙活動が高まっているらしい。 んで、Antinny の詳しい解説である。 でも、このウィルスの動き自身は、そんなに難解ではない。 テクニックで重要なのは「如何に間違ってクリックさせるか…」という技だから…
この間違ってクリックという点では、 それ Unicode で… にて紹介されているテクの方が、参考になる。
といっても、Winny,Share なんて動かすヤツが悪いんだけど…
大域変数・局所変数
大域変数と局所変数について、スコープ・寿命をキーワードに 説明し、混乱目的の趣味の悪いコーディング例を元に、説明を行う。 次に、大域変数共有で正しく動かなくなる二重ループのプログラム例を示し、 大域変数の問題点を説明する。
後半は、途中で健康診断が入ったので、 簡単に説明できる変数名のルール([a-zA-Z_][a-zA-z0-9_]*) などを示す。
# そういえば、__で始まる変数名は処理系利用で、使用を避けるべき…の説明が必要だった…
foo , 「ほげ」って何？
プログラムを書いていて、定番の質問「foo って何？」を休憩時間に質問される。
詳しくは メタ構文変数… を参照
# さすが Wikipedia …
LINK http://kmaebashi.com/programmer/hoge.html ほげを考えるページ
個人的には、「久米宏・ぴったしカンカン」が紀元と思っているが、 この説は Web 上に少ないのであった…