価格.com の攻撃は SQL インジェクション

授業の雑談ネタとしてはタイムリーなので、どこかで使おう。 でも、asahi.com の記事の、 『コンピューターの基本ソフト（ＯＳ）などの欠陥を突いて侵入する通常のサイト攻撃とは違い、ソフトの不備ではなく、データベースの安全設定が不十分だった点を悪用された。』 って書いてあるけど、SQL インジェクションのどこが 『ソフトの不備でない』 のかが不思議だ。

プログラム作成の課題に取り組む。 何進数かの文字で記載されたデータを数値化する、 数値データを何進数かの文字列に変換する、というテーマで、 『何進数』は自分で任意に選ぶこととする。

課題中の説明で、#include の意味等を紹介。

とある授業にて学生さん２名程が『○○先生の授業さぼりまーす！』 と通りがけに伝えてくる。 話を聞くと、 『授業進度が速く「ゆっくり説明して！」と頼んでも進んでいく。 このまま授業を聞いても判らないので、△△先生の所で教えてもらう…』 という状況らしい。 学生の理解度を考慮しない講義も心配だけど、 自主的に先生に聞きにいくという点では、『極めて積極性がある』と思う。 ということで、連続でサボるのは困るけど 今日は『学生にサボるな！』と小言を言うのは、ひとまず不粋と思う。 『がんばって△△先生の所で勉強してね…』

進路指導委員会にて、５年の就職戦線の状況報告があった。 GW 前に１次面接といった学生が増えている様子。 一時期より１月ほど就職時期が前倒しになっているみたい。

大学編入希望者で過去問題が欲しい場合は、 大学から集めた問題を図書館にて保管しているので、閲覧して欲しい。 また、図書館に無い大学については、 教務係に依頼すれば取り寄せ をしてくれる。

学生さん相手に、サーバのセッティングのお手伝い。 ただ、途中で通常画面で、パスワードが見えるようなタイプミスをしてしまう。 最近、パスワードの変更をしていなかったし、 良い機会なので、同一パスワードを使っていた物を全面変更する。

マージソートの処理速度

再帰方程式の説明の最後として、ソート処理の速度見積りを示す。 クイックソートの説明だと、微妙な所が説明が判りにくいので、 例年通りマージソートの例にて、O( N log N ) を説明。

処理の内容より、
T(1) = Ta
T(N) = Tb + 2*T(N/2) + N*Tc
再帰と同じ代入を繰り返すと、
T(1) = Ta
T(2) = Tb + 2*T(1) + 2*Tc
T(4) = Tb + 2*T(2) + 4*Tc
:
T(2^m) = Tb*(2^m-1) + 2^m * Ta + m * 2^m * Tc
よって、O( N log N )

動的なメモリ

処理速度の見積りの次のプログラム評価指針としてのメモリの使用量の説明。 再帰呼出のプログラム例から、局所変数は 『最後に出現した変数から不要となる』特徴を持っていることを紹介し、 こういったデータの保存には Stack(Last In First Out)が使えることを示す。 例として、push,pop のコードを示し、fact(階乗)のコードを push,pop を 用いて記述する。

Stackのコードも示したため、対比的な事例ということで リングバッファのコードを示し待ち行列(First In First Out)の説明を行う。

動的なメモリの説明として、授業最後に malloc,free の例を示す。 動的に配列サイズを与えるプログラム例にて説明を行う。 詳しい説明は来週に行う必要あり。

体育祭では 4EI のクラスは、応援・デコレにて、大変ご苦労さまでした。 「４年間のクラスの集大成？」というと変かもしれませんが、 クラス全員で力を会わせ大変なイベントを乗り切ったという感想です。

応援

ダンスはなかなかの物でしたよ。 見ている所では、『団長、 かわいい！ 』の声がよく聞こえてきました。

個人的には、白組(物質)のダンスの構成が旨いのに、凄く驚きました。 全体の配置・流れとも、ダンスをよく解っていると思いました。

デコレ

今日も朝早くからの準備だったみたいで、ご苦労さまでした。
録音した音が、スピーカを通しての音が予想外であったため、少し残念でした。
そういう実験って出来ないからなぁ….

FONT COLOR blue # 4EI の皆様は、この他の大量の写真につきましては、
のページを御覧下さい。(非公開)

再帰を含む処理の処理速度の見積りの例として、 階乗の再帰の速度見積り、２分探索の再帰版の速度見積り、 ハノイの塔の処理速度の速度見積りを示す。

ハノイの塔の再帰方程式と数学的機能法

N枚の板の移動は、以下の手順で実行するため、移動回数を H(N) で表すと、 以下のような再帰方程式が示される。

• 底の1枚を残して、N-1枚を一旦別の柱に移し、
• 底の１枚を目的の柱に移動、
• 別の柱に移しておいた N-1枚を移動、

H(1) = 1               (N=1の時)
H(N) = 1 + 2 * H(N-1)  (N>1の時)

少ない枚数のハノイの塔を解くと、処理速度 H(N) では、以下の仮定が成り立つ。

H(N) = 2^N - 1

よって、数学的帰納法で証明すると、

・H(1) で、仮定が正しいのは明らか。
N = k の時、仮定が正しいならば、 N=k+1の時、
・H(k+1) = 1 + 2 * H(k)         # ルールより
= 1 + 2 * (2^k - 1)    # N=kの時の仮定を代入
= 1 + 2^(k+1) - 2
= 2^(k+1) - 1
であり、仮定は k+1 でも成り立つ。
よって数学的帰納法により、N≧1で成り立つ。

フィボナッチ数の再帰プログラムの処理速度の見積り

講義では、フィボナッチ数の処理速度の見積りは示さなかったが、 自主的な取り組みをしてみることと伝えておいた。 ここで、ヒントを示す。

• ビネの公式

フィボナッチ数の再帰処理より、成り立つ再帰方程式
T(1) = Ta
T(2) = Ta
T(N) = Tb + T(N-1) + T(N-2)
代入法による一般式の予測
T(1) = Ta , T(2) = Ta
T(3) = Tb + Ta + Ta
T(4) = Tb + (Tb + 2Ta) + Ta = 2Tb + 3Ta
T(5) = Tb + (2Tb+3Ta) + (Tb+2Ta) = 4Tb + 5Ta
以下の一般式を仮定する。
T(N) = (Ta + Tb) * fib(N) - Tb
上記一般式は、N=1,2 で仮定が成り立つのは明らか。
N≦k で仮定が成り立つとすれば、N=k+1 の時、
T(k+1) = Tb + T(k) + T(k-1)
= Tb + {(Ta + Tb) * fib(k) - Tb} + {(Ta + Tb) * fib(k-1) - Tb}
= (Ta + Tb){ fib(k) + fib(k-1) } - Tb
= (Ta + Tb) * fib(k+1) - Tb
よって、k+1 でも仮定が成り立つことが確認できた。

この一般式より、フィボナッチ数の再帰呼出し処理の速度のオーダーは、 ) となる。 ビネの公式より、 )

# くそ、授業中に記憶だけで書いた(1+sqrt(5))/2 の値が違ってた….

昨日の田植えの手伝いの後遺症にて筋肉痛。 学生には「ダイエットになったでしょ！」と突っ込まれる。
# 先日の遠足では最終的に筋肉痛が出なかっただけに….