繰り返し処理と処理時間の見積もり
単純サーチの処理時間
ここで、プログラムの実行時間を細かく分析してみる。
// ((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 ;
例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その1つ1つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ,
,
,
とする。
この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。
ここで例題
この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか?
感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、Tβ,Tα は何秒だったのだろうか? 上記のT(N)=Tα+N ✕ Tβ に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。
ここで一番のポイントは、データ処理では N が小さな値の場合(データ件数が少ない状態)はあまり考えない。N が巨大な値であれば、Tαは、1000Tβに比べれば微々たる値という点である。よって
で考えれば良い。これであれば、T(1000)=5μ秒=Tβ×1000 よって、Tβ=5n秒となる。この結果、T(10000)=Tβ×10000=50μ秒 となる。
2分探索法と処理時間
次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。
// ((case-2)) // 2分探索法 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 ; }
このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、
件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。
…両辺のlogをとる
2分探索は、繰り返し処理であるから、処理時間は、
ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式で係数が出てくるが、これはTβに含めて考えればいい。
単純なソート(選択法)の処理時間
次に、並べ替え処理の処理時間について考える。
単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。
int a[ 1000 ] = { 対象となるデータ } ; int size = N ; 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)は…
… i=0の時
… i=1の時
:
… i=N-1の時
…(参考 数列の和の公式)
となる。
オーダー記法
ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、
の部分の方が重要である。
単純サーチ | |
2分探索法 | |
最大選択法 |
そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。
単純サーチ | オーダーNのアルゴリズム | |
2分探索法 | オーダー log N のアルゴリズム | |
最大選択法 | オーダー N2 のアルゴリズム |
練習問題
- ある処理のデータ数Nに対する処理時間が、
であった場合、オーダー記法で書くとどうなるか?
- コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか?
(ヒント: 底変換の公式) の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このような処理時間となるアルゴリズムの例を答えよ。
の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?
(ヒント: ロピタルの定理)
- 2と4の解説
- 1は、N→∞において、N2 ≪ 2Nなので、O(2N) 。厳密に回答するなら、練習問題4と同様の証明が必要。
- 3は、O(1)。
- 誤答の例:O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。
- 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
再帰呼び出しの予習
次の講義の基礎を確認という意味で、再帰呼出しと簡単な処理の例を説明する。
最初に定番の階乗(fact)
次に、フィボナッチ数列の場合
次の講義への導入問題
ここで示す導入問題をすべて答えるには、若干の予習が必要です。まずはどういう考え方をすれば解けるかな…を考えてみてください。
- fact(N)の処理時間を、Tfact(N) = … のような式で表現し、処理時間をオーダ記法で答えよ。
- 以下のプログラムの実行結果を答えよ。また、関数sum()の処理時間を対象となるデータ件数N=R–Lを用いて Tsum(N) = …のような式で表現せよ。
int a[] = { 1 , 5 , 8 , 9 , 2 , 3 , 4 , 7 } ; // 分割統治法による合計の例 int sum( int a[] , int L , int R ) { if ( R-L == 1 ) { return a[L] ; } else { int M = (L + R) / 2 ; return sum( a , L , M ) + sum( a , M , R ) ; } } int main() { printf( "%d¥n" , sum( a , 0 , 8 ) ) ; return 0 ; }
⾼専プロコン連携シンポジウム 2023 ならびに応募説明会
高専プロコン実行委員会より、下記のようなシンポジウム開催の案内が届いています。
今年度の⾼専プロコンは福井高専主管で行われますし、関連の学生の方々の参加をお待ちしています。
今年度の高専プロコンは,課題部⾨では「オンラインで⽣み出す新しい楽しみ」をテーマとして応募を募っております。そして、⾼専⽣に現場のニーズや動向を学習する機会を提供することを⽬的としたシンポジウム を本年度も開催いたします。
昨年度実施したシンポジウムは⼤変好評を頂き,各⾼専から多くの参加がありました。現場のニーズや動向を知る機会を提供できたことは応募作品のコンセプトにも良い影響を与えたと思われます。本年度も,多⾓的な視点からシンポジウムを開催する予定となっておりますので,奮ってご参加ください。また、合わせて応募説明会の実施も予定しておりますので、ご検討頂きますようお願い致します。
シンポジウム(2023-04-14-高専プロコン連携シンポジウム2023ご案内2)
- 概要
YouTube 配信により,講師から企業,高専生,プロコンの関係についての情報を提供頂きます。プロコンに興味を持っている教職員及び学生はもちろん,一般の学生にも興味の持てる内容となっております。 - 講演者・講演タイトルおよび日程
- 5 月 12 日(金) 16:30〜17:00
- 「高専・プロコンでの経験が生きる今 〜CAC での働き方〜」
株式会社シーエーシーR&D 本部 高橋 滉一 氏, R&D 本部 吉野 瑠 氏, 人事部 鈴木 李実 氏
※ 講演に引き続き、応募説明会[*]を実施します。
- 「高専・プロコンでの経験が生きる今 〜CAC での働き方〜」
- 5 月 19 日(金) 16:30〜17:00
- 「アメリカのクラウドサービス ServiceNow の最新動向の現場より」
Blueship 株式会社 代表取締役 慶松 大海 氏
- 「アメリカのクラウドサービス ServiceNow の最新動向の現場より」
- 5 月 19 日(金) 17:00〜17:30
- 「さくらインターネットが高専を応援する理由」
さくらインターネット株式会社 執行役員 高橋 隆行 氏
- 「さくらインターネットが高専を応援する理由」
- 5 月 12 日(金) 16:30〜17:00
- 応募説明会[*]
- 5 月 12 日(金) 17:00〜18:00(予定)
- 課題部門および自由部門の募集内容について
- 競技部門の競技ルール等について
- 5 月 12 日(金) 17:00〜18:00(予定)
YouTube配信の URL などは こちらの procon.gr.jp のページにて公開されています。
参加希望の方は、こちらの Forms にて参加希望の連絡をお願いします。
オブジェクト指向プログラミング・ガイダンス2023
専攻科2年のオブジェクト指向プログラミングの授業の1回目。
最近のプログラミングの基本となっているオブジェクト指向について、その機能についてC++言語を用いて説明し、後半では対象(オブジェクト)をモデル化して設計するための考え方(UML)について説明する。
評価は、3つの課題と最終テストを各25%づつで評価を行う。
オブジェクト指向プログラミングの歴史
最初のプログラム言語のFortran(科学技術計算向け言語)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け言語)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct {…}の考えができた。(データの構造化)
// C言語の構造体 struct Person { // 1人分のデータ構造をPersonとする char name[ 20 ] ; // 名前 int b_year, b_month, b_day ; // 誕生日 } ;
一方、初期のFortranでは、プログラムの処理順序は、繰り返し処理も if 文と goto 文で記載し、処理がわかりにくかった。その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で 記述する方法ができてきた。(処理の構造化)
// ブロックの考えがない時代の雰囲気をC言語で表すと int i = 0 ; LOOP: if ( i >= 10 ) goto EXIT ; if ( i % 2 != 0 ) goto NEXT ; printf( "%d " , i ) ; NEXT: i++ ; goto LOOP ; // 処理の範囲を字下げ(インデント)で強調 EXIT: --------------------------------------------------- // C 言語で書けば int i ; for( i = 0 ; i < 10 ; i++ ) { if ( i % 2 == 0 ) { printf( "%d¥n" , i ) ; } } --------------------------------------------------- ! 構造化文法のFORTRANで書くと integer i do i = 0 , 9 if ( mod( i , 2 ) == 0 ) then print * , i end if end do
このデータの構造化・処理の構造化により、プログラムの分かりやすさは向上し、このデータと処理をブロック化した書き方は「構造化プログラミング(Structured Programming)」 と呼ばれる。
雑談
ここで紹介した、最古の高級言語 Fortran や COBOL は、今でも使われている。Fortran は、スーパーコンピュータなどで行われる数値シミュレーションでは、広く利用されている。また COBOL は、銀行などのシステムでもまだ使われている。しかしながら、新システムへの移行で COBOL を使えるプログラマーが定年を迎え減っていることから、移行トラブルが発生している。特に、CASEツール(UMLなどの図をベースにしたデータからプログラムを自動生成するツール)によって得られた COBOL のコードが移行を妨げる原因となることもある。
この後、様々なプログラム言語が開発され、C言語などもできてきた。 一方で、シミュレーションのプログラム開発(例simula)では、 シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、 データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。 これがオブジェクト指向プログラミング(Object Oriented Programming)の始まりとなる。略記するときは OOP などと書くことが多い。
この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから、この考え方は多くのプログラム言語へと取り入れられていく。
C言語にこのオブジェクト指向を取り入れ、C++が開発される。さらに、この文法をベースとした、 Javaなどが開発されている。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。
この授業の中ではオブジェクト指向プログラミングにおける、隠蔽化, 派生と継承, 仮想関数 などの概念を説明する。
構造体の導入
専攻科の授業では、電子情報以外の学科系の学生さんもいるので、まずは C 言語での構造体の説明を行う。
C++でのオブジェクト指向は、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) ) ; }
構造体に慣れていない人のための課題
- 以下に、C言語の構造体を使った基本的なプログラムを示す。このプログラムでは、国語,算数,理科の3科目と名前の5人分のデータより、各人の平均点を計算している。このプログラムを動かし、以下の機能を追加せよ。レポートには プログラムリストと動作結果の分かる結果を付けること。
- 国語の最低点の人を探し、名前を表示する処理。
- 算数の平均点を求める処理。
#include <stdio.h> struct Student { char name[ 20 ] ; int kokugo ; int sansu ; int rika ; } ; struct Student table[5] = { // name , kokugo , sansu , rika { "Aoyama" , 56 , 95 , 83 } , { "Kondoh" , 78 , 80 , 64 } , { "Saitoh" , 42 , 78 , 88 } , { "Sakamoto" , 85 , 90 , 36 } , { "Yamagosi" ,100 , 72 , 65 } , } ; int main() { int i = 0 ; for( i = 0 ; i < 5 ; i++ ) { double sum = table[i].kokugo + table[i].sansu + table[i].rika ; printf( "%-10.10s %3d %3d %3d %6.2lf\n" , table[i].name , table[i].kokugo , table[i].sansu , table[i].rika , sum / 3.0 ) ; } return 0 ; }
値渡し,ポインタ渡し,参照渡し
C言語をあまりやっていない学科の人向けのC言語の基礎として、関数との値渡し, ポインタ渡しについて説明する。ただし、参照渡しについては電子情報の授業でも細かく扱っていない内容なので電子情報系学生も要注意。
オブジェクト指向のプログラムでは、構造体のポインタ渡し(というよりは参照渡し)を多用するが、その基本となる関数との値の受け渡しの理解のため、以下に値渡し・ポインタ渡し・参照渡しについて説明する。
ポインタと引数
値渡し(Call by value)
// 値渡しのプログラム void foo( int x ) { // x は局所変数(仮引数は呼出時に // 対応する実引数で初期化される。 x++ ; printf( "%d¥n" , x ) ; } int main() { int a = 123 ; foo( a ) ; // 124 // 処理後も main::a は 123 のまま。 foo( a ) ; // 124 return 0 ; }
このプログラムでは、aの値は変化せずに、124,124 が表示される。ここで、関数 foo() を呼び出しても、関数に「値」が渡されるだけで、foo() を呼び出す際の実引数 a の値は変化しない。こういった関数に値だけを渡すメカニズムは「値渡し」と呼ぶ。
値渡しだけが使われれば、関数の処理後に変数に影響が残らない。こういった処理の影響が残らないことは一般的に「副作用がない」という。
大域変数を使ったプログラム
でも、プログラムによっては、124,125 と変化して欲しい場合もある。どのように記述すべきだろうか?
// 大域変数を使う場合 int x ; void foo() { x++ ; printf( "%d¥n" , x ) ; } int main() { x = 123 ; foo() ; // 124 foo() ; // 125 return 0 ; }
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。大域変数はどこでも使える変数であり、副作用が発生して間違ったプログラムを作る原因になりやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例 int i ; void foo() { for( i = 0 ; i < 2 ; i++ ) printf( "A" ) ; } int main() { for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と foo() ; // 表示されない。 return 0 ; }
ポインタ渡し(Call by pointer)
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。(副作用の及ぶ範囲を限定する) こういった、値の受け渡し方法は「ポインタ渡し」と呼ぶ。
// ポインタ渡しのプログラム void foo( int* p ) { // p はポインタ (*p)++ ; printf( "%d¥n" , *p ) ; } int main() { int a = 123 ; foo( &a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( &a ) ; // 124 return 0 ; // さらに125と増える }
ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。
参照渡し(Call by reference)
C++では、ポインタ渡しを極力使わないようにするために、参照渡しを利用する。ただし、ポインタ渡しも参照渡しも、機械語レベルでは同じ処理にすぎない。
// ポインタ渡しのプログラム void foo( int& x ) { // xは参照 x++ ; printf( "%d¥n" , x ) ; } int main() { int a = 123 ; foo( a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( a ) ; // 124 return 0 ; // さらに125と増える。 }
大きなプログラムを作る場合、副作用のあるプログラムの書き方は、間違ったプログラムの原因となりやすい。そこで関数の呼び出しを中心としてプログラムを書くものとして、関数型プログラミングがある。
情報メディア工学・ガイダンス/2023
情報メディア工学では、前期では情報を扱うためのOSの仕組みなどを、実践を交えながら演習を中心に行う。後期は5年の人工知能の授業につながる内容として、情報の中のデータをどう処理するのかを議論する。
OSの役割と仕組み
組込み系システム
組込み系のシステムで、OSが無い場合(例えば Arduino でデバイスを制御する場合)には、ユーザプログラムはデバイスを操作するライブラリやI/Oポートを直接制御しながら、ハードウェアを制御する。ユーザプログラムは、デバイスを操作するライブラリを含むため、異なるシステムでは機械語をそのまま使うことはできない。(共通化が不十分)
組込み系システムでは、ハードウェアを操作する命令をすべてユーザプログラムが面倒を見る必要があるため、システムが複雑化するとプログラム開発が大変になってくる。また、ユーザプログラムが間違った制御方法を取れば、ハードウェアを壊すような処理を実行してしまうかもしれない。(資源保護ができない)
オペレーティングシステム経由でハード操作
コンピュータのハードウェアの違いは OS がすべて包み隠し、OSが管理する。OSは 特権モード で動作し、ハードウェアを直接制御する。ユーザプログラムはユーザモードで動作し、OSの機能を呼び出すシステムコールを経由し、デバイス毎のデバイスドライバを経由して、ハードウェアを操作する。ユーザモードのプログラムは、ハードウェアを直接操作するような命令を実行しようとすると、OSが命令を強制停止させる。(資源保護)
ユーザプログラムには、ハードウェアを直接操作する機械語が含まれていないので、ユーザプログラムの機械語を同じOSが動く他のコンピュータにコピーして動かすことができる。(資源の扱いを共通化)
(例) helloworld のプログラムがコンソールに出力
簡単な例として、helloworld.c のような簡単なコンソール出力プログラムが動いて、画面に文字が表示されるのは以下の図のようにOSを経由して文字を表示している。
古いコンピュータで、プログラムが動作するだけならば、仕組みはすごく簡単にみえる。ユーザプログラムはすべて特権モードで動くOS(狭義のOSとかカーネルと呼ぶことが多い)を経由してハードウェアを操作する。
GUI が使えるグラフィカルな OS の場合
GUI が使えるグラフィカルなOSの場合、GUI の操作を支援するプログラム(ウィンドウマネージャ)などを利用しながら、ユーザはOSを操作する。コンピュータを操作する場合は、こういうウィンドウマネージャなどがないと不便であり、カーネルとユーザ支援のウィンドウマネージャなどをまとめて広義のOSと呼ぶ場合も多い。
ユーザプログラムは、GUIを操作するためのライブラリを経由し、さらにカーネルを経由してディスプレィに結果が表示される。
ユーザモードのプログラムの実行単位プロセスでは、処理を実行するためのメモリなどは他の処理と分離されており、他のプロセスのメモリ領域などを間違ってアクセスすると「メモリエラー」といった例外などが発生し、処理が強制的に停止させられる。このように、プロセスが他に悪影響を及ぼさないように、OS はメモリを管理する。(OSの保護機能)
(例) helloworld の結果を端末ソフトで表示
以下のように、コンソールアプリの実行結果を表示するような、cmd.exe は、helloworld.exe と OS を経由しながら連動して動いている。
helloworld.exe の出力は、OS を経由しながら cmd.exe に伝わり、cmd.exe はその表示内容に応じて、テキストの文字やフォントに合わせてグラフィカルな画面に文字を表示しようとする。グラフィカルな出力は GUI のライブラリを経由しながら OS に送られ、グラフィックドライバが画面に文字を表示する。
インターネットとプログラム
次に、インターネットの仕組みを踏まえ、インターネットで使われるプログラム言語やデータについて3~4週をかけて演習を中心にしながら、今まで習ってきたことを総括する。
理解確認
情報構造論ガイダンス2023
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。
プログラムを評価する3つのポイント
まずは以下を読む前に、質問。
- あなたが”良い”プログラムを作るために何を考えて作りますか? ※1
- ここまでの段階で3つの要点を考えメモしてください。
具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。
- プログラムの速度
- プログラムのわかり易さ
- メモリの使用量
プログラムを作る場合、この3要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。
メモリの使用量の影響
メモリを大量に使用すると、どういった影響がでるのか? OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)
しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)
int 型のメモリ使用量
int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。
32bit の0/1情報の組み合わせで、232通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-231~0~231-1 の範囲を扱うことができる。231 = 2×210×210×210 ≒ 2×10003
32bit = 4byte
ソフトウェアとアルゴリズムとプログラム
用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か?
- アルゴリズム – 計算手順の考え方。
- プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
- ソフトウェア – プログラムと、その処理に必要なデータ。
(日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない) - パラダイム – プログラムをどう表現すると分かりやすいか?
トレードオフ関係をプログラムで確認
例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。
// ((case-1)) // 単純サーチ O(N) #define SIZE 1024 int a[ SIZE ] ; // 配列 int size ; // 実際のデータ数(Nとする) int key ; // 探すデータ for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル if ( a[i] == key ) break ;
しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)
// ((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[ 272925 ] = 272925 ; : // データを探したければ a[ 電話番号 ] で探せばいい printf( "%d\n" , a[ 621111 ] ) ; // 処理速度はクソ速いけど、メモリは大量消費
良いプログラムを作るとは
プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。
実際には、限られた予算からメモリやCPUが決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。
皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ?ゲームがバグですぐに変な動きしたらキレるでしょ!(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!
授業アンケート2022後期
データベース
ポイント86.3
chatGPT、計算問題もこなすのかよ
今回、4EI 情報構造論の期末試験の1問目を chat GPT に解いてもらった。
福井高専の解説ではお得意の”知ったかぶり”を発揮しちゃったけど、処理時間のオーダー問題だと、具体的な数値を交えてちゃんと計算してらぁ。しかも、オーダー記法だからあくまで概算の予想値ということを踏まえ、1024msec だけでなく 約 1 秒と答えている。
情報構造論-2022-講義録
- 情報構造論ガイダンス2022
- 繰り返し処理と処理時間の見積もり
- 再帰呼び出しの処理時間の見積もり
- 再帰呼び出しと再帰方程式
- ポインタ処理
- malloc()とfree()
- 様々なデータの覚え方のレポート課題
- リスト構造の導入
- リスト処理
- リストへの追加処理
- スタックと待ち行列
- ライブラリと分割コンパイル
- 集合とリスト処理
- ランダムアクセス・シーケンシャルアクセスから双方向リスト
- 双方向リスト
- 2分探索木
- 2分探索木の処理とデータ追加処理
- AVLと意思決定木と演算子
- 演算子と言語処理系
- 2分木による構文木とデータベースとB木
- ハッシュ法(導入)
- ハッシュ衝突対策と文字列のハッシュ関数
- 共有のあるデータの取扱い
- ガベージコレクタとスタック領域
- 動的メモリ管理 malloc() と free()
- 関数ポインタ
暗号化とセキュリティ対策
暗号化
有線LANで1本のケーブルを共有したり無線でデータをやりとりする場合、通信の盗聴が行われると危険である。
前回の授業で紹介したように、簡単な置換式暗号などでは暗号の解読ができてしまう。
暗号化アルゴリズム
1980年頃には DES(Data Encryption Standard) がアメリカでの標準的な暗号化として使われていたが、コンピュータの性能があがると共に解読される危険性が高まってきた。そこで2000年頃にはAES(Advanced Encryption Standard) が使われるようになった。どちらも共通鍵を用いてデータをブロック(固定長のデータ)単位で暗号化する共通鍵ブロック暗号方式であり、暗号の鍵の長いものは暗号解読が困難となっている。
1980年頃に開発された RSA 暗号(開発者の名前より) は、巨大な数字の素因数分解が困難なことを利用した、公開鍵暗号方式の1つである。
最近、量子コンピュータを用いた暗号解析が話題となっている。量子力学の原理を計算に応用したコンピュータで、スーパーコンピュータで1万年かかる暗号解読のような処理が200秒で終わってしまうかもしれないと言われている。
公開鍵暗号方式とは…
以前に使われていた暗号化の方式は、暗号化の鍵と復号化の鍵に同じものを用いる共通鍵方式であった。
しかし、この鍵をどうやって相手に渡すか…が問題となっていた。(鍵を相手に渡す瞬間のデータを盗聴されると危険)
このため、最近では公開鍵暗号方式が中心となっている。この方式は「暗号化するため専用の公開鍵」と、「暗号化を復号するための秘密鍵」をペアにして用いる。公開鍵は、暗号化するため専用なので、この鍵が他の人に見られても、暗号を復号することはできない。
公開鍵だけでは成り済ました別人と通信してしまう可能性[1]がある。そこで通信相手が本物かどうかを、認証局とよばれる第三者機関によって証明書で確認する。HTTPを暗号化したHTTPSでは、SSL証明書と呼ばれる。最近のブラウザでは、URLの左側の鍵マーク🔒からSSL証明書を確認することができる。
[1] DNSサーバの脆弱性を利用して、間違ったIPアドレスを教えさせる DNSポイズニング が行われると、利用者を間違ったサーバに接続させることが可能。
多要素認証
前に述べた暗号化の説明でも解説したように、パスワードはブルートフォース攻撃をうければ、いつかはパスワードが破られる危険性がある。こういった対策で最も重要な方法が、多要素認証(2段階認証)である。
この方式では、通常のパスワード入力の後に、以下の様な方式でワンタイムパスワードを入力することでログインが可能となる。
- 携帯電話にテキストメッセージ(SMS)でワンタイムパスワードを送る。
- かかってきた電話の機械音声のワンタイムパスワードを伝える。
- 時間で変化するワンタイムパスワード生成アプリの数字を入力する。
- メールで送られてきたワンタイムパスワードを含んだURLにアクセスする。
- 認証画面に表示されたQRコードのURLにアクセスする。
SMSやワンタイムパスワードアプリは、携帯電話などを常に持ち歩いていることが本人確認となっている。このような方式では、携帯電話などを失くすとシステムが使えなくなるので、バックアップコード(非常時用のパスワード)の保存や、login先とは別のメールアドレスを登録してあることが重要となる。
CAPTCHA
最近では、フリーで取得できるメールアドレスをプログラムで動くロボットで自動生成し、そのアカウントを使ってspamを送るなどの手口が問題となっている。このため、接続してきた相手が人間か判定することがある。判定には、読みづらく加工された英字を入力させたり、パズルを解かせるといった方法が使われる。
元々は、読みづらい文字はコンピュータでは画像解析しづらいことから、CAPTCHA が使われるが、最近では機械学習によって解析ができるようになってきた。
セキュリティキー
SMSやメールを使ったワンタイムパスワードによる多要素認証も、間にネットワークを挟むと多要素認証では問題となる。そこで、もっと複雑な暗号で多要素認証を行うために、セキュリティキーが使われる。
多要素認証が必要になると、パソコンにセキュリティキーを差し込むことで認証が行われる。現在では FIDO(Fast IDentity Online)や FIDO2 といった規格のものが普及している。
ハッカー
インターネットの用語でハッカー(Hacker)は、コンピュータを使って悪いことをする人という意味でよく使われている。しかし元々は「主にコンピュータや電気回路一般について常人より深く高度な技術的知識を持ち、その知識を利用して技術的な課題をクリアする人々のこと」(Wikipedia引用)という意味で使われていた。このため本来は「優秀なエンジニアへの最大級の誉め言葉」として使われており、ハッカー以上の技術者を ウィザード/wizard や グル/guru と呼称することもある。
しかしながら一部のハッカーの中で、その技術を悪用する人も出てきたことから、インターネットで悪いことをする人という意味で使われることも増えてきた。そこで、悪いことをする人は別な呼び方をしようということで、攻撃を加えるひとはクラッカーと呼ぶことが多い。最近では、正義のためのハッカー = ホワイト・ハッカー、悪いハッカー = ブラック・ハッカー という表現も使われるが、黒人差別主義につながる用語ということで、最近ではエシカル・ハッカー(高い倫理観と道徳心を兼ね備えている高い技術を持ったハッカー)という言葉を使う。
セキュリティ
バッファオーバーフロー
クラッカーがサーバを攻撃する場合、サーバ上のプログラムの脆弱性を利用する。
サーバプログラムの脆弱性を利用する最も典型的な攻撃方法には、バッファオーバーフローがある。
こういった問題が含まれるアプリケーションは危険であり、こういった脆弱性が見つかったらプログラムの更新が重要である。
マルウェア
ウィルスとは、パソコン利用者の上で動く、感染能力のある悪意のあるプログラム。機械語で書かれたものや、オフィスソフトのマクロ機能で動くものもある。パソコン内の情報を利用して、ウィルス付きメールを自動的に送ることが多い。(メールソフトを使うなど、人の操作が必要なもの)
ウィルスは元々、愉快犯によるものが一般的であったが、感染したパソコンのファイルを暗号化し、暗号化を復元するために、ネットバンキングへのお金の振り込みを要求(身代金=ransom)するようなランサムウェアが増えている。
ウォームとは、脆弱性のあるネットワークプログラムに、バッファオーバーフローを引き起こすようなデータを送りつけて、ウィルスを送りつけたり、そのコンピュータを踏み台にしてネットワークを利用した攻撃をさらに行うもの。(ネットワークを介して悪意のあるプログラムを起動させるもの)
通常、インターネットからの攻撃を防ぐために、各組織ではFireWall(後述)を設置している。一方、FireWallの内側では、防御されていることから内部のコンピュータからの攻撃に甘く、無防備であることが多い。そこで、FireWall の内側のコンピュータに、メールなどの添付ファイルでマルウェアを送付・感染させることで、FireWall内で被害が拡大することもある。
このような、FireWall 内部での感染・被害拡大を狙ったマルウェアは、トロイの木馬型と呼ばれる。
ネットワークを介した攻撃では、攻撃対象のコンピュータを乱数で得られたIPアドレスや、そのアドレスを1つづつ増やしながら攻撃を行うことが多い。こういった攻撃は絨毯攻撃と呼ぶ。
ボットとは、感染しても表面上は何もせず、クラッカーの動かすインターネットの掲示板などを監視し、そこに書かれた命令を見て spam 送信や、DoS攻撃を行うものがある。
DoS攻撃(Denial of Service attack) – サーバなどに大量のデータを送りつけたりすることで、サーバがその処理に手間取り、他の利用者のサービスに悪影響を引き起こさせる攻撃。
最近では、ウィルスやウォームの区別が難しいため、マルウェアと呼ぶ。
ファイアウォール
サーバで動かしているプログラムにバッファオーバーフローのような不備が残っていて、全世界のどこからでもこういった不備があるプログラムに簡単に接続できたとしたら、極めて危険である。
サーバで動くプログラムは、接続するためのポート番号が決まっているので、相手のコンピュータのIPアドレスが分かったら攻撃を仕掛けてくるかもしれない。
FireWall は、これらの接続をできなくするための方法で、例えば学内のWebサーバへの攻撃を防ぎたいのなら、ルータで「宛先ポート番号が80のパケットは廃棄」といった設定をすればよい。また、危険な攻撃を加えてくるコンピュータのIPアドレスがわかっている場合は、「送信元IPアドレスXX.XX.XX.XXのパケットは廃棄」という設定をすればよい。こういった、ポート番号やIPアドレスを見てパケットを遮断するルータは、FireWall(防火壁)と呼ばれる。
よくある設定であれば、ポート番号23(telnet),137,139(Windows ファイル共有),513(リモートデスクトップ)を禁止など(ブラックリスト型)、基本は全面禁止だけどポート番号22(ssh)は許可(ホワイトリスト型)など。
セキュリティ対策
- OSの更新・インストールアプリケーションの更新
バッファオーバーフローのような脆弱性が無いようにソフトウェアを更新することが重要。
Windows で、インストールされているソフトの更新では、winget が便利!!
- 不審なメールは開かない
添付ファイルにマルウェアがしかけられている可能性。リンクや画像ファイルを開くと、実際に使われているメールアドレスとして迷惑メールが増える可能性がある。 - 危険なWebサイトをアクセスしない
OSやブラウザの脆弱性から、マルウェア被害の可能性。 - パソコンで不要なサービスを動かさない
ファイル共有や、リモート接続のサーバを不用意に動かさない。 - ウィルス対策ソフトをインストール&更新
ウィルス対策ソフトは、新しく発生したマルウェアの命令などのパターンを保存しておき、同じパターンのものをマルウェアとして判定する。- マルウェアは日々新しいものが作られるため、ウィルス対策ソフトのメーカーから、常に新しいマルウェアのパターンをダウンロード&更新が重要。
- OSの脆弱性が見つかった場合、ウィルス対策ソフトのメーカーがマルウェアパターンを登録する前にマルウェアが届く場合がある。ゼロディ攻撃
- 特定の企業を攻撃する場合は、その企業専用のウィルスを作る場合もある。このためマルウェアパターンが無いため、ウィルス感染の可能性がある。標的型攻撃
- 最近では、ブラウザによるWebアクセスからの感染を防ぐために危険なURLへのアクセスを監視したり、危険なIPアドレス・ポート番号へのアクセスを監視する機能も含まれている。
- このパソコンは重要な情報が入っていないから、ウィルスに感染しても放置するのは危険。他のコンピュータを攻撃する踏み台、DoS攻撃のボット、トロイの木馬となって危険の元となる。
一般的に、Apple社のiPhone iOS では、ウィルス対策ソフトは不要である。これは、App Store でアプリを公開するためには、プログラムのソースコードを提出した上での審査があり、デバイスも、App Store 以外からのアプリをインストールできないため、マルウェアのインストールがほぼ不可能なためである。一方、Google社のAndroidは、アプリの審査が甘く、Google Play アプリ以外からのソフトのインストールも可能であり、ウィルス対策ソフトが必要である。
理解度確認
- Formsによる理解度確認テスト
- 標的型攻撃メールがウィルス対策ソフトでは防ぐことが難しい理由を述べよ。
- ファイアウォールでは、どういった処理を行うのか説明せよ。