「講義録」カテゴリーアーカイブ

2025年6月
日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

オブジェクト指向(2018) / ガイダンス

2018年4月13日

専攻科2年のオブジェクト指向プログラミングの授業の1回目。最初に授業全般の概要を説明した後、オブジェクト指向の歴史とC言語の構造体の説明。

オブジェクト指向プログラミングの歴史

最初のプログラム言語のFortran(科学技術計算向け)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct …}の考えができた。その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で記述する方法ができて、処理の構造化・データの構造化ができる。これが「構造化プログラミング(structured programming)」 の始まりとなる。
この後、様々なプログラム言語が開発され、C言語などもできてきた。一方で、シミュレーションのプログラム開発(例simula)では、シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。これがオブジェクト指向の始まりとなる。

この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから普及が拡大する。

C言語にこのオブジェクト指向を取り入れて、C++が開発される。さらに、この文法をベースとした、 Javaなどが開発される。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。

構造体の導入

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) ) ;
}

情報構造論ガイダンス

2018年4月12日

情報構造論のガイダンス

プログラム作成でのポイント

この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。

プログラムの速度
プログラムのわかり易さ
メモリの使用量

プログラムを作る場合、この３要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

プログラム例

例えば、配列の中から、目的データを探すプログラムの場合、最もスタンダードなプログラムは以下の方法であろう。

// ((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-2))
// 2分探索法　O(log N)
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[ key ] に保存
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られる予算から、メモリやCPUが決まり、その会社の人員やら経験やらで、プログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

動作時間の予測

ここで、プログラムの実行時間を細かく分析してみる。例えば、前節のcase-1単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ${T_A,T_B,T_C,T_D}$ とする。

この検索処理全体の時間 ${T(N)}$ を考えると、平均時間とすれば、以下のように表せるだろう。

$T(N)=T_A+T_B+T_B\times\frac{N}{2}+T_C+T_C\times\frac{N-1}{2}+T_D\times\frac{N}{2}$

$T(N)=T_A+T_B+\frac{T_C}{2}+\frac{N}{2}\times(T_B+T_C+T_D)$

$T(N)=T_{\alpha}+N\times{T_{\beta}}$

ここで例題

この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか？

感のいい学生であれば、直感的に 50μ秒と答えるだろうが、では、T_β,T_α は何秒だったのだろうか？上記のT(N)=T_α+N ✕ T_β に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、データ処理では N が小さな値の場合はあまり考えない。N が巨大な値であれば、T_αは、1000T_βに比べれば微々たる値という点である。よって

$\red{T(N)\simeq{N\times{T_{\beta}}}}$

で考えれば良い。これであれば、T(1000)=5μ秒=T_β×1000 よって、T_β=5n秒となる。この結果、T(10000)=T_β×10000=50μ秒となる。

pow(2,i)の速度

2018年3月7日

例年、2進数演算の課題を出すと、2ⁱ の処理を、pow(2,i) で書く学生さんがいる。

しかしながら、pow() は、double 型なので遅い。これは、2進数の特徴を踏まえれば、1 << i で書けば良い。
試しに、実際の処理速度を測ってみた。

#include <stdio.h>
#include <math.h>

long long int mask( ) {
  long long int m ;
  for( int j = 0 ; j < 10000000 ; j++ ) {
    m = 0 ;
    for( int i = 0 ; i < 60 ; i++ ) {
      m += pow( 2 , i ) ;
      // m |= (1 << i) ;
    }
  }
  return m ;
}

int main() {
  long long int x = mask() ;
  return 0 ;
}

m |= (1 << i) ; ---------  1.296 [sec]
m += pow( 2 , i ) ; ----- 44.956 [sec]
                          40倍の遅さ

型による処理速度の実験

2018年3月7日

授業のネタとするために、型によって計算時間がどう変化するか実験。レガシーなコンピュータを使ってきた人間には、float とか double とか出てきたら、「Z80な時代の頭」では数倍遅いのを期待したけど、FPU を搭載して当たり前のこの時代、そんなに差は出ない。

FPUという言葉さえ、最近は死語かな…

しかたがないので、macOS , Raspberry-Pi , Arduino 遅さの時代を逆行しながら実験。

// test.cxx
#ifndef TYPE
#define TYPE int
#endif
#include <stdio.h>

TYPE foo( TYPE i ) {
    TYPE ans = 0 ;
    for( int j = 0 ; j < 30000 ; j++ ) {
        ans += i * i ;
    }
    return ans ;
}

int main() {
    TYPE y = 0 ;
    for( TYPE i = 0 ; i < 100000 ; i++ ) {
        y = foo( i ) ;
    }
    return 0 ;
}

iMac で実験

iMac で実験。デスクトップ 64 bit マシンだし、そんなに差は出ないのは予想どおり。

bash-3.2$ uname -a
Darwin imac2 17.4.0 Darwin Kernel Version 17.4.0: ... root:xnu-4570.41.2~1/RELEASE_X86_64 x86_64

bash-3.2$ g++ -O0 -DTYPE=int test.cxx
bash-3.2$ time ./a.out
user    0m6.857s
bash-3.2$ g++ -O0 -DTYPE="long long int" test.cxx
bash-3.2$ time ./a.out
user    0m6.831s
bash-3.2$ g++ -O0 -DTYPE=float test.cxx
bash-3.2$ time ./a.out
user    0m8.528s
bash-3.2$ g++ -O0 -DTYPE=double test.cxx
bash-3.2$ time ./a.out
user    0m8.615s

Raspberry-Pi3 で実験

組み込み系の FPU などが貧弱なマシンを想定し、Raspberry-Pi 3 で同じことをやってみた。
64bit整数 long long int が想定外に遅いな。

raspberry-pi:~$ uname -a
Linux raspberry-pi 4.14.22-v7+ #1096 SMP ...2018 armv7l GNU/Linux

raspberry-pi:~$ gcc -O0 -DTYPE=int test.cxx
raspberry-pi:~$ time ./a.out
user    0m37.588s
raspberry-pi:~$ gcc -O0 -DTYPE="long long int" test.cxx
raspberry-pi:~$ time ./a.out
user    1m18.535s
raspberry-pi:~$ gcc -O0 -DTYPE=float test.cxx
raspberry-pi:~$ time ./a.out
user    0m52.206s
raspberry-pi:~$ gcc -O0 -DTYPE=double test.cxx
raspberry-pi:~$ time ./a.out
user    0m50.287s

Arduino で実験

同じことを Arduino でやってみた。main のループは 1/10000 の回数にして、10000倍の時間を掲載…
ようやく「Z80 な頭」が期待している実験結果となったかな。

int       6880[sec] 16bit int
long      6320[sec] 32bit int 
float    92080[sec] 32bit float
double   92080[sec] Arduino Uno では、double = 32bit で float と同じ

2段階認証のレポートにて

2018年2月5日

情報ネットワーク基礎で、セキュリティの話の中で2段階認証の説明を行ったので、レポートにて自分のアカウントの2段階認証の設定を行い、その経過をレポートにまとめるという課題をだした。TwitterやGoogleや自分のゲームアカウントの2段階認証でレポートを出してくれている。

ただし、レポートでは個人情報の扱いには注意すること…という条件をだしたけど、wordで提出されたレポートで、画像ファイルをみると、キャプチャ画像の上に図を貼って隠している状態のレポートが多い。これじゃ、上の図をずらせば個人情報丸見え…なレポートの人が若干見受けられた。以下の図がその状態を真似たもの。

楽天を偽装したフィッシングメール

2018年1月31日

楽天を偽装したメール…完成度高いな…

職場のメールアドレスに楽天カードからの「カード利用のお知らせ」が、迷惑メールフォルダ内に落ちてる。でも、職場のメアドで楽天さんのカードは作っていない。かといって、いつも送られてくるメールとほぼおなじ雰囲気。カード会社のメールが迷惑メールフォルダの落ちる段階で、怪しいけどな。

細かく見ていくと「Edyのチャージ」金額が、10,276円。 EdyやSuicaはよく使っているけど、3,000円 or 5,000円単位でチャージしているし、276円の端数なんやねん。
リンクにマウスを「移動」させURLを確認すると、「楽天e-NAVIにログイン」は正しそうなURL。しかし、「Gmailアドレスをご登録の会員様へ」あたりから怪しそうな短縮URLがぞろぞろ。カードというよりは、Gmail アカウント狙いっぽい。

仕方がないので最終段階の確認。メールヘッダ表示をしてみたら、案の定。

Received: from [84-40-95-70.net1.bg]  // .bg = ブルガリア
    (helo=mail.rakuten-card.co.jp)
    by 84-40-95-70.net1.bg with esmtpa...

しっかしまあ、よくできたフィッシングメールだわ。

2段階認証の設定とセキュリティ

2018年1月17日

2段階認証

前回授業の暗号化の説明でも解説したように、パスワードはブルートフォース攻撃をうければ、いつかはパスワードが破られる危険性がある。こういった対策で最も重要な方法が、2段階認証(多要素認証)である。

この方式では、通常のパスワード入力の後に、以下の様な方式でワンタイムパスワードを入力することでログインが可能となる。

携帯電話にテキストメッセージ(SMS)でワンタイムパスワードを送る。
音声を用いると、電話がかかってくると機械音声でワンタイムパスワードを読み上げてくれる。
認証システムアプリは、時間で変化するワンタイムパスワードが表示される。
バックアップコード(非常時用のパスワード)

以下の資料では、Google と Twitter で2段階認証を設定するための例を示す。

情報ネットワーク基礎後半のレポート課題

各自が利用しているインターネットサービスの中から1つを選び、2段階認証の設定を行うこと。
もし、インターネットサービスを一切利用していない人は、暫定で入会し課題終了後解約すればいい。

設定の資料として、Google, Twitter の例を上記に示す。他にも、Facebook , Amazon , Microsoft ID などがあるので、自分にとってセキュリティ上重要なサービスについて設定を行うこと。もし、2段階認証で問題がある場合は、このレポート課題終了後、2段階認証の設定を外せばよい。

レポートでは、2段階認証の設定中の画面、ログイン時の2段階認証が行われている画面、受信したワンタイムパスワードの例などを画面のキャプチャなどで取得し、その手順の流れを解説し、考察として2段階認証の利点と欠点について記載すること。

ただし、キャプチャ画面をレポートに貼り付ける際は、自分の個人情報が記載されないように注意をすること。

既に全てのサービスで2段階認証の設定を終えている人は、いくつかのサービスで2段階認証を用いてログインする手順を説明せよ。

学校の Office365 にて、2段階認証を使いたいと思うかもしれないけど、慣れない学生さんがログインできなくなる可能性があり、一部の教職員しか使えない。

セキュリティ

インターネットをクラッカーからの攻撃をうけないように守る場合、以下の3点の対策が重要となる。

インターネットの経路での対策
サーバ側での対策
パソコン側での対策

バッファオーバーフロー

クラッカーがサーバを攻撃する場合、サーバ上のプログラムの脆弱性を利用する。
サーバプログラムの脆弱性で最も典型的な攻撃方法は、「バッファオーバーフロー」がある。

void foo() {              // foo 実行時のstackの内容
    char str[ 10 ] ;      //   str                  fooからの戻り番地
    scanf( "%s" , str ) ; //   [ | | | | | | | | | ][ret_label]
}                         //  入力時に、abcdefghijklmn\r と入力したら
                          //  [a|b|c|d|e|f|g|h|i|j][k|l|m|n|\n]
void main() {             //                          戻り番地が破壊される
    foo() ;               //  入力時に、abcdefghij][ウィルス番地][ウィルスプログラム]
ret_label:                //  といったデータを与えると、foo() の処理が終わると
    return 0 ;            //  ウィルスのプログラムを実行してしまう
}

こういったプログラムは危険なので、こういうミスが見つかったらプログラムの更新が重要。

ファイアウォール

サーバで動かしているプログラムにバッファオーバーフローのような不備が残っていて、全世界のどこからでもこういった不備があるプログラムに簡単に接続できたとしたら、極めて危険である。

サーバで動くプログラムは、接続するためのポート番号が決まっているので、相手のコンピュータのIPアドレスが分かったら攻撃を仕掛けてくるかもしれない。

FireWall は、これらの接続をできなくするための方法で、例えば学内のWebサーバへの攻撃を防ぎたいのなら、ルータで「宛先ポート番号が80のパケットは廃棄」といった設定をすればよい。また、危険な攻撃を加えてくるコンピュータのIPアドレスがわかっている場合は、「送信元IPアドレスXX.XX.XX.XXのパケットは廃棄」という設定をすればよい。こういった、ポート番号やIPアドレスを見てパケットを遮断するルータは、FireWall(防火壁)と呼ばれる。

よくある設定であれば、ポート番号23(telnet)、137,139(Windows ファイル共有)を禁止など(ブラックリスト型)、基本は全面禁止だけどポート番号22(ssh)は許可(ホワイトリスト型)など。

mallocとfreelist

2018年1月16日

C言語では、動的メモリ領域をどのように管理していくのか解説する。

動的メモリ領域とフリーリスト

動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。

この借りるタイミングと返却するタイミングが、「Last In First Out」最後に確保したメモリを最初に開放してくれるのであれば、スタックを使えばいいが malloc や free のタイミングは、LIFO の順番のようにはならない。

この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。

mallocが一定サイズの場合

free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。

malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。

任意サイズのメモリ確保の場合

malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。

丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。

使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、malloc()ができなくなる。

そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。

ヒープメモリの断片化

ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。

この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。

ガベージコレクタと演習(ハッシュ法)

2018年1月16日

ハッシュ法について演習ができていなかったので、前半座学(ガベージコレクタ)と後半演習(ハッシュ法)

ガベージコレクタ

前回、malloc などで使用を終えたデータを free で開放する際に発生する問題について説明し、その問題の解決法として参照カウンタ法を説明した。しかし、参照カウンタ法は循環リストなどが含まれる場合、free で開放できない状態が発生する場合があることを説明した。

このため、malloc で確保したデータ領域を、free で開放する処理は、複雑なデータ構造の場合かなり処理の記述が大変になる。

そこで最近のプログラム言語では、ガベージコレクタがある。この方法では、プログラムが malloc で確保した動的データ領域は、データが不要となっても開放処理 free は行わない。

しかし、このままでは、不要となったデータ領域がメモリに溢れ、メモリ不足が発生してしまう。そこで、一定量のメモリを使い切ったら、不要なメモリ(ゴミ=ガベージ)を回収(コレクタ)する。

マーク&スイープ法

ガベージコレクタの方法には、色々あるが、マーク&スイープ法では、

処理を一旦停止し、
動的メモリの領域すべてに「未使用マーク」をつける。
実際に使用している変数や、その変数が指している領域には「使用中マーク」をつける。
マーク処理が終わったら「未使用マーク」の付いているデータは誰も使っていないので回収する。

他にも、コピー法といった方法もあるが説明は割愛する。

上で述べた様に、ガベージコレクタはプログラムを一旦停止し、全動的メモリ領域を検査するという手間のかかる作業を行うため、通常は「一時的にプログラムが止まる」ことからリアルタイムに処理を行うような場合には、極めて不都合が多い。

このため、最近では参照カウンタ法の技術なども取り入れ、局所変数は参照カウンタ法の技法を中心に回収し、大域変数はガベージコレクタの技法で回収する。

CやC++言語では、ガベージコレクタは基本的には利用できず、ガベージコレクタが取り入れられた言語としては、Java が有名。Java では、ガベージコレクタが実装されているため、通常のプログラミングでは、free や delete といった処理は不要である。しかし、処理速度や突発的な一時停止を避ける場合には、適切なタイミングで変数に null を代入するといった処理を明記するなどのテクニックが重要となる。