ホーム » 2018 (ページ 13)

年別アーカイブ: 2018

2025年5月
日	月	火	水	木	金	土
	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	31

制御構文について

2018年4月19日

プログラムの基本は、処理の順序を正しく理解していること。

まずは理解度確認

では、過去の電子情報3年プログラム応用のテスト問題から、以下のプログラムの実行順序を答えて下さい。

制御構文とフローチャート

構文の入れ子

繰り返し処理とオーダ記法

2018年4月19日

先週に、単純繰り返し処理の時間分析をやったので、次のステップに。

2分探索法の処理時間

データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。

// 2分探索法　O(log N)
int a[ 1000 ] ;
int size ;      // データ数 N
int L = 0 ;     // L=下限のデータの場所
int R = size ;  // R=上限のデータ+1の場所
while( L != R ) {
   int M = (L + R) / 2 ;  // 計算は整数型で行われることに注意
   if ( a[M] == key )     // 見つかった
      break ;
   else if ( a[M] < key ) // |L         |M.         |R
      L = M + 1 ;         // |----------|-+---------|
   else                   // |L---------|M|
      R = M ;             //              |M+1------|R
}

上記のようなプログラムの場合、処理に要する時T(N)は、

${T(N)}=T_{\alpha}+T_{\beta}\times{M}$ 　# Mは繰り返し回数

処理は、対象となるデータ件数が繰り返し毎に半分となり、対象データ件数が1件になれば処理が終わる。このことから、

$\frac{N}{2^{M}}=1$

となることから、 ${M}=\log{N}$ の関係が成り立つ。よって、 ${T(N)}$ は、以下のように表せる。

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

単純なソート(最大選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

int a[ 1000 ] ;
int size ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は…

$T(N)=T_{\alpha}+\sum_{i=0}^{N-1}{T_{loop-j}(i)}$

$T(N)=T_{\alpha}+\sum_{i=0}^{N-1}(T_{\beta}+T_{\gamma}\times{i})$

$T(N)=T_{\alpha}+N{\times}T_{\beta}+T_{\gamma}\times\frac{N(N-1)}{2}$

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

となる。

オーダー記法

ここまでのアルゴリズムをまとめると、処理時間に大きく影響する部分は、赤字の部分であり、特にその項の係数 ${T_{\beta},T_{\gamma}}$ は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 ${N,\log{N},N^2$ の部分の方が重要である。

単純サーチ	${T(N)}=T_{\alpha}+T_{\beta}\times{N}$
２分探索法	${T(N)}=T_{\alpha}+T_{\beta}\times\log{N}$
最大選択法	${T(N)}=T_{\alpha}+T_{\beta}\times{N}+T_{\gamma}\times{N^2}$

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ	${O(N)}$	オーダーNのアルゴリズム
2分探索法	${O(\log{N})}$	オーダー log N のアルゴリズム
最大選択法	${O(N^2)}$	オーダー N² のアルゴリズム

練習問題

コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか？
${T(N)}=T_A$ の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？また、このようなアルゴリズムの例を答えよ。
${T(N)}=T_A+T_B\times\sqrt{N}+T_C\times\log{N}$ の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？

緊急連絡システムとメール分析システム

2018年4月17日

私が管理している丹南地区緊急連絡システムで、利用者の方から『「受信確認」作業をしているのに、記録されていない…』との相談を受ける。

メール分析システム

上記の現象は、昨年度に行った迷惑メールの分析システム対策が原因であった。

緊急連絡システムでは、ユーザに送った文面の末尾に URL を添付し、その URL をユーザにアクセスしてもらうことで、受信確認を行っている。

一方、連絡システムで、ユーザがメールアドレスを変更したり、ユーザ登録にミスがあると、相手に届かないメールが発生する。最近のメールシステムでは、プロバイダが迷惑メールの分析をすることがあり、この分析処理の中でメール内のURLを、分析システムがアクセスしていると思われる。

コレ以外にも、チャット表示形式のメールアプリでは、届いたメールの概要を確認するために、文中のURLをアクセスするものもある。このような処理が行われると、ユーザがメールを読んでいないのに、受信確認の URL をアクセスされ、受信確認が済んだことになってしまう。

最初、この現象を把握し状況を確認したら、このような分析システムの多くは逆引きできないIPアドレスからアクセスしていることが判明した。そこで、逆引きできないIPアドレスからの受信確認は、アクセス履歴を保存しないように改良を行っていた。

さらなる対策

しかし、今回相談を受け確認を行った所、逆引きできないIPアドレスの中に、通常のユーザからのアクセスも含まれていることが分かった。

そこで、今回以下のような改良を行った。

逆引きできないアドレスからのアクセスの場合には、以下のような送信フォームを表示し、ユーザが「確認」ボタンを押すことで受信確認の記録を行うようにした。

この方法は、ユーザが受信確認のために2回ボタンを押す必要があるが、止む終えないかな。

macOSのOneDriveでキーチェーンのパスワード

2018年4月16日

OneDrive アプリの更新がかかったら、「キーチェーンが一致しない」というエラーで OneDrive が起動しなくなった。

対応法法を調べると、キーチェーンのリセットとか書いてあるので色々と調べたけど、いい方法がない。グダグダ考えてもアプリの一時的な問題かと思い、macOS を再起動かけたら、普通に起動してくれた。

はぁ…

高専ライブ：2018年4月15日（第570回）

2018年4月15日

収録放送でお送りしました。

オリエンテーション合宿の話
乗り物の話
サイエンス共和国　第２７回「テラヘルツの話」
ディズニーランドの話

担当：田中（２Ｃ，ＭＣ）、山野（２ＥＩ，ＭＩＸ）、西島（４ＥＩ）、中島（４Ｃ），西（教員）

オブジェクト指向(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}$ とする。