繰り返し処理と処理時間の見積もり
単純サーチの処理時間
ここで、プログラムの実行時間を細かく分析してみる。
// ((case-1))
// 単純サーチ O(N)
#include <stdio.h>
int main() {
int a[ 10 ] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int N = 10 ; // 実際のデータ数(Nとする)
int key = 21 ; // 探すデータ
for( int i = 0 ; i < N ; i++ )
if ( a[i] == key )
break ;
return 0 ;
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
// Your code here!
int a[] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int N = a.length ;
int key = 21 ;
for( int i = 0 ; i < N ; i++ )
if( a[i] == key )
break ;
}
}
例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ,
,
,
とする。
この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。
ここで例題
この単純サーチのプログラムを動かしてみたら、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分探索法の処理時間を考える。データはあらかじめ昇順に並べておくことで、一度の比較で対象件数を減らすことで高速に探すことができる。
下記プログラムを読む場合の注意点：
- Lは、探索範囲の一番左端のデータのある場所。
- Rは、探索範囲の一番右端のデータのある場所 + 1
// ((case-2))
// 2分探索法 O(log N)
#include <stdio.h>
int main() {
int a[] = {
9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
} ;
int L = 0 ; // L : 左端のデータの場所
int R = 10 ; // R : 右端のデータの場所+1
while( L != R ) {
int M = (L + R) / 2 ;
if ( a[M] == key )
break ;
else if ( a[M] < key )
L = M + 1 ;
else
R = M ;
}
return 0 ;
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
} ;
int L = 0 ; // L : 左端のデータの場所
int R = a.length ; // R : 右端のデータの場所+1
int key = 73 ;
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分探索は、繰り返し処理であるから、処理時間は、
… (Mはループ回数)
ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式 ()で係数が出てくるが、これはTβに含めて考えればいい。
単純なソート(選択法)の処理時間
次に、並べ替え処理の処理時間について考える。
単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。
// ((case-3))
// 選択法 O(N^2)
#include <stdio.h>
int main() {
int a[] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int size = 10 ;
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 ;
}
return 0 ;
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
} ;
int size = a.length ;
for( int i = 0 ; i < size - 1 ; i++ ) {
int tmp ;
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の時
…(参考 数列の和の公式)
となる。
オーダー記法
ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、
の部分の方が重要である。
| 単純サーチ | |
| ２分探索法 | |
| 最大選択法 |
そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を取り除いた式で表現する。これをオーダー記法と言う。
| 単純サーチ | オーダー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になってしまう。
- 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
インターネットとWebの仕組み
前回の講義では、最初のガイダンスとしてOSの仕組みについて説明をおこなった。
2回目の授業では、インターネットのWebページを作るために使われているHTMLやCSSやプログラム言語について解説を行う。
Webページの生成とプログラム言語
理解確認
- こちらの小テストに回答してください。
構造体からクラスの導入
構造体の参照渡し
構造体のデータを関数で受け渡しをする場合は、参照渡しを利用する。
struct Person {
char name[ 20 ] ;
int age ;
} ;
void print( struct Person* this ) {
printf( "%s %d¥n" , this->name , this->age ) ;
}
void main() {
struct Person saitoh ;
strcpy( saitoh.name , "t-saitoh" ) ;
saitoh.age = 50 ;
print( &saitoh ) ; // ポインタによる参照渡し
}
このようなプログラムの書き方をすると、「データ saitoh に、print() せよ…」 といった処理を記述したようになる。 これを発展して、データ saitoh に、print という命令をするイメージにも見える。
この考え方を、そのままプログラムに反映させ、Personというデータは、 名前と年齢、データを表示するprintは…といったように、 データ構造と、そのデータ構造への処理をペアで記述すると分かりやすい。
オブジェクト指向の導入
構造体でオブジェクト指向もどき
例えば、名前と年齢の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ利用者で分けて 仕事ができることを説明。
// この部分はデータ構造の設計者が書く
// データ構造を記述
struct Person {
char name[10] ;
int age ;
} ;
// データに対する処理を記述
void setPerson( struct Person* this , char s[] , int a ) {
// ポインタの参照で表記
strcpy( (*this).name , s ) ;
(*this).age = a ;
}
void printPerson( struct Person* this ) {
// アロー演算子で表記 "(*this).name" は "this->name" で書ける
printf( "%s %d¥n" ,
this->name , this->age ) ;
}
// この部分は、データ利用者が書く
int main() {
// Personの中身を知らなくてもいいから配列を定義(データ隠蔽)
struct Person saitoh ;
setPerson( &saitoh , "saitoh" , 55 ) ;
struct Person table[ 10 ] ; // 初期化は記述を省略
for( int i = 0 ; i < 10 ; i++ ) {
// 出力する...という雰囲気で書ける(手続き隠蔽)
printPerson( &table[i] ) ;
}
return 0 ;
}
このプログラムの書き方では、mainの中を読むだけもで、 データ初期化とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、setPerson()や、printPerson()という関数の中身についても、 初期化・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。
C++のクラスで表現
上記のプログラムをそのままC++に書き直すと以下のようになる。
#include <stdio.h>
#include <string.h>
// この部分はクラス設計者が書く
class Person {
private: // クラス外からアクセスできない部分
// データ構造を記述
char name[10] ; // メンバーの宣言
int age ;
public: // クラス外から使える部分
// データに対する処理を記述
void set( char s[] , int a ) { // メソッドの宣言
// pのように対象のオブジェクトを明記する必要はない。
strcpy( name , s ) ; // メソッドは隠れた引数としてオブジェクトへのポインタ this がある。
age = a ; // このため strcpy( this->name , s ) ; , this->age = a ; などと書いてもいい。
}
void print() {
printf( "%s %d¥n" , name , age ) ;
}
} ; // ← 注意ここのセミコロンを書き忘れないこと。
// この部分はクラス利用者が書く
int main() {
Person saitoh ;
saitoh.set( "saitoh" , 55 ) ;
saitoh.print() ;
// 文法エラーの例
printf( "%d¥n" , saitoh.age ) ; // age は private なので参照できない。
return 0 ;
}
用語の解説：C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
この様にC++のプログラムに書き換えたが、内部の処理は元のC言語と同じであり、オブジェクトへの関数呼び出し saitoh.set(…) などが呼び出されても、set() は、オブジェクトのポインタを引数して持つ関数として、機械語が生成されるだけである。
用語の解説：C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのデータに対し具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
C++では隠蔽化をさらに明確にするために、private: や public: といったアクセス制限を指定できる。private: は、そのメソッドの中でしか使うことができない要素や関数であり、public: は、メソッド以外からでも参照したり呼出したりできる。オブジェクト指向でプログラムを書くとき、データ構造や関数の処理方法は、クラス内部の設計者しか触れないようにしておけば、その内部を改良することができる。しかし、クラスの利用者が勝手に内部データを触っていると、内部設計者が改良するとそのプログラムは動かないものになってしまう。
隠蔽化を的確に行うことで、クラスの利用者はクラスの内部構造を触ることができなくなる。一方でクラス設計者はクラスの外部への挙動が変化しないようにクラス内部を修正することに心がければ、クラス利用者への影響がないままクラスの内部を改良できる。このように利用者への影響を最小に、常にプログラムを修正することをリファクタリングと呼ぶ。
クラス限定子
前述のプログラムでは、class 宣言の中に関数内部の処理を記述していた。しかし関数の記述が長い場合は、書ききれないこういう場合はクラス限定子を使って、メソッドの具体的な処理をクラス宣言の外に記載する。
class Person {
private:
char name[10] ;
int age ;
public:
// メソッドのプロトタイプ宣言
void set( char s[] , int a) ;
void print() ;
} ;
// メソッドの実体をクラス宣言の外に記載する。
void Person::set( char s[] , int a ) { // Person::set()
strcpy( name , s ) ;
age = a ;
}
void Person::print() { // Person::print()
printf( "%s %d¥n" , name , age ) ;
}
inline 関数と開いたサブルーチン
オブジェクト指向では、きわめて簡単な処理な関数を使うことも多い。
例えば、上記のプログラム例で、クラス利用者に年齢を読み出すことは許しても書き込みをさせたくない場合、以下のような、inline 関数を定義する。(getterメソッド)
# 逆に、値の代入専用のメソッドは、setterメソッドと呼ぶclass Person { private: char name[10] ; int age ; public: // メソッドのプロトタイプ宣言 inline int get_age() { return age ; } // getter inline void set_age( int a ) { age = a ; } // setter } ;ここで inline とは、開いた関数(開いたサブルーチン)を作る指定子である。通常、機械語を生成するとき中身を参照するだけの機械語と、get_age() を呼出したときに関数呼び出しを行う機械語が作られる(閉じたサブルーチン)が、age を参照するだけのために関数呼び出しの機械語はムダが多い。inline を指定すると、入り口出口のある関数は生成されず、get_age() の処理にふさわしい age を参照するだけの機械語が生成される。
# 質問：C言語で開いたサブルーチンを使うためにはどういった機能があるか？
コンストラクタとデストラクタ
プログラムを記述する際、データの初期化忘れや終了処理忘れで、プログラムの誤動作の原因になることが多い。
このための機能がコンストラクタ(構築子)とデストラクタ(破壊子)という。
コンストラクタは、返り値を記載しない関数でクラス名(仮引数…)の形式で宣言し、オブジェクトの宣言時に初期化を行う処理として呼び出される。デストラクタは、~クラス名() の形式で宣言し、オブジェクトが不要となる際に、自動的に呼び出し処理が埋め込まれる。
class Person {
private:
// データ構造を記述
char name[10] ;
int age ;
public:
Person() { // (A) 引数なしのコンストラクタ
name[0] = 'class Person {
private:
// データ構造を記述
char name[10] ;
int age ;
public:
Person() { // (A) 引数なしのコンストラクタ
name[0] = '\0' ;
age = 0 ;
}
Person( char s[] , int a ) { // (B) 引数ありのコンストラクタ
strcpy( name , s ) ;
age = a ;
}
~Person() { // デストラクタ
print() ;
}
void print() {
printf( "'%s' = %d¥n" , name , age ) ;
}
} ;
int main() {
Person saitoh( "saitoh" , 55 ) ; // オブジェクトsaitohを"saitoh"と55で初期化
Person tomoko ; // 引数なしのコンストラクタで初期化される。
return 0 ;
// main を抜ける時にオブジェクトsaitohは不要になるので、
// デストラクタが自動的に呼び出され、'saitoh' = 55 が表示。
// 同様に tomoko のデストラクタでは、'' = 0 を表示。
}
' ;
age = 0 ;
}
Person( char s[] , int a ) { // (B) 引数ありのコンストラクタ
strcpy( name , s ) ;
age = a ;
}
~Person() { // デストラクタ
print() ;
}
void print() {
printf( "'%s' = %d¥n" , name , age ) ;
}
} ;
int main() {
Person saitoh( "saitoh" , 55 ) ; // オブジェクトsaitohを"saitoh"と55で初期化
Person tomoko ; // 引数なしのコンストラクタで初期化される。
return 0 ;
// main を抜ける時にオブジェクトsaitohは不要になるので、
// デストラクタが自動的に呼び出され、'saitoh' = 55 が表示。
// 同様に tomoko のデストラクタでは、'' = 0 を表示。
}
このクラスの中には、(A)引数無しのコンストラクタと、(B)引数ありのコンストラクタが出てくる。C++では、同じ名前の関数でも引数の数や型に応じて呼出す関数を適切に選んでくれる。(関数のオーバーロード)
デストラクタは、データが不要となった時に自動的に呼び出してくれる関数で、一般的にはC言語でのファイルの fopen() , fclose() のようなものを使う処理で、コンストラクタで fopen() , デストラクタで fclose() を呼出すように使うことが多いだろう。同じように、コンストラクタで malloc() を呼出し、デストラクタで free() を呼出すというのが定番の使い方だろう。
nitfcei ディスク移行
実験用にさくらインターネットのサーバを借りて運用しているけど、経年劣化にともなう危険性拡大の緩和ということで、ディスクを移行しろとな。
クラウドのコンソールで、サーバを止めて、マニュアルに従って移行ボタンをポチっとな。
情報構造論ガイダンス2025
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。
プログラムを評価する3つのポイント
まずは以下を読む前に、質問。
- あなたが”良い”プログラムを作るために何を考えて作りますか？ ※1
- ここまでの段階で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 main() {
int a[ SIZE ] = {
52 , 14 , 82 , 62 , 15
} ; // 配列
int size = 5 ; // 実際のデータ数(Nとする)
int key = 62 ; // 探すデータ
for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル
if ( a[i] == key ) {
printf( "Find %d¥n" , key ) ;
break ;
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
52 , 14 , 82 , 62 , 15
} ;
int key = 62 ;
for( int i = 0 ; i < a.length ; i++ ) {
if ( a[i] == key ) {
System.out.println( "Find " + key ) ;
break ;
}
}
}
}
// import java.util.Arrays; // こういった正当なJavaのプログラムでは、
// public class Main { // データ件数が大きくなった時の挙動がわからない
// public static void main( String[] args ) {
// Integer a[] = {
// 52 , 14 , 82 , 62 , 15 // Integer型 int 型は何が違うの？
// } ;
// if ( Arrays.asList( a ).contains( 62 ) ) {
// System.out.println("配列内に値が存在しています。");
// }
// }
// }
しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)
// ((case-2))
// 2分探索法 O(log N)
// 速いけど、プログラムは分かりにくく(複雑に)なった
int main() {
int a[] = {
14 , 15 , 52 , 62 , 82 // データはあらかじめ昇順に並べておく
} ;
int L=0 , R= 5 ;
while( L != R ) {
int M = (L + R) / 2 ;
if ( a[M] == key )
break ;
else if ( a[M] < key )
L = M + 1 ;
else
R = M ;
}
}
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int a[] = {
14 , 15 , 52 , 62 , 82 // データはあらかじめ昇順に並べておく
} ;
int key = 62 ;
int L = 0 ;
int R = a.length ;
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が決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。
皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ？ゲームがバグですぐに変な動きしたらキレるでしょ！(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!
情報メディア工学・ガイダンス/2025
情報メディア工学では、前期では情報を扱うためのOSの仕組みなどを、実践を交えながら演習を中心に行う。後期は５年の人工知能の授業につながる内容として、情報の中のデータをどう処理するのかを議論する。
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週をかけて演習を中心にしながら、今まで習ってきたことを総括する。
理解確認
オブジェクト指向プログラミング・ガイダンス2025
専攻科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言語なら{ 文 … }の複文で 記述する方法ができてきた。(処理の構造化)
! 構造化文法がないFORTRAN
integer i
do 999 i = 0 , 9
write( 6 , '(I2)' ) i
999 continue
end
---------------------------------------------------
// ブロックの考えがない時代の雰囲気を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と増える。 }
大きなプログラムを作る場合、副作用のあるプログラムの書き方は、間違ったプログラムの原因となりやすい。そこで関数の呼び出しを中心としてプログラムを書くものとして、関数型プログラミングがある。
2024年度 情報構造論 講義録
- 繰り返し処理と処理時間の見積もり
- 値渡しと参照渡しとポインター
- ポインタと文字列処理
- 情報構造論のレポート課題
- 配列に要素を追加
- Javaのオブジェクト指向入門
- Javaでリスト構造
- スタックと待ち行列
- 前期期末前の課題レポート
- 集合とリスト処理
- ランダムアクセス・シーケンシャルアクセスから双方向リスト
- 双方向リストとdeque
- 2分探索木
- 2分探索木への追加とAVLと2分ヒープ
- 2分木の応用(意思決定木と演算子)
- 2分木による構文木
- 木構造の探索・深さ優先探索・幅優先探索
- データベースとB木
- ハッシュ法
- メモリ管理・スタック領域とヒープ領域
- ガベージコレクタとヒープ管理
- 関数ポインタとラムダ式
- レポート課題(後期期末) ハッシュ法
- Javaでラムダ式の呼び出し
セキュリティ対策
セキュリティ
バッファオーバーフロー
クラッカーがサーバを攻撃する場合、サーバ上のプログラムの脆弱性を利用する。
サーバプログラムの脆弱性を利用する最も典型的な攻撃方法には、バッファオーバーフローがある。
こういった問題が含まれるアプリケーションは危険であり、こういった脆弱性が見つかったらプログラムの更新が重要である。
広く利用されているソフトウェアでも日々脆弱性が見つかる。(JVNなどのサイトでは脆弱性情報を収集・公開してくれている)
マルウェア
ウィルスとは、パソコン利用者の上で動く、感染能力のある悪意のあるプログラム。機械語で書かれたものや、オフィスソフトのマクロ機能で動くものもある。パソコン内の情報を利用して、ウィルス付きメールを自動的に送ることが多い。(メールソフトを使うなど、人の操作が必要なもの)
ウィルスは元々、愉快犯によるものが一般的であったが、感染したパソコンのファイルを暗号化し、暗号化を復元するために、ネットバンキングへのお金の振り込みを要求(身代金=ransom)するようなランサムウェアが増えている。
ウォームとは、脆弱性のあるネットワークプログラムに、バッファオーバーフローを引き起こすようなデータを送りつけて、ウィルスを送りつけたり、そのコンピュータを踏み台にしてネットワークを利用した攻撃をさらに行うもの。(ネットワークを介して悪意のあるプログラムを起動させるもの)
通常、インターネットからの攻撃を防ぐために、各組織ではFireWall(後述)を設置している。一方、FireWallの内側では、防御されていることから内部のコンピュータからの攻撃に甘く、無防備であることが多い。そこで、FireWall の内側のコンピュータに、メールなどの添付ファイルでマルウェアを送付・感染させることで、FireWall内で被害が拡大することもある。
このような、FireWall 内部での感染・被害拡大を狙ったマルウェアは、トロイの木馬型と呼ばれる。
ネットワークを介した攻撃では、攻撃対象のコンピュータを乱数で得られたIPアドレスや、そのアドレスを1つづつ増やしながら攻撃を行うことが多い。こういった攻撃は絨毯攻撃と呼ぶ。
ボットとはロボットを略した単語で、ウォームの中で「外部からの命令で動くもの」を指すことが多い。マルウェアのボットの中には感染しても表面上は何もせず、クラッカーの動かすインターネットの掲示板などを監視し、そこに書かれた命令を見て spam 送信や、DoS攻撃を行うものがある。
DoS攻撃(Denial of Service attack) – サーバなどに大量のデータを送りつけたりすることで、サーバがその処理に手間取り、他の利用者のサービスに悪影響を引き起こさせる攻撃。ボットからのDoS攻撃は、インターネットの様々なIPアドレスから攻撃を受けるためFireWallで防ぐことも困難である。分散DoS攻撃(Distributed DoS 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 以外からのアプリをインストールできないため、マルウェアのインストールがほぼ不可能なためである。ただし、欧州連合（EU）では 、EU域内のデジタル市場の公正性を確保し競争力を高めるためのデジタル市場法(DMA)によりに、App Store 以外からのソフトウェアダウンロードが可能。
一方、Google 社の Android は、アプリの審査が甘く、Google Play アプリ以外からのソフトのインストールも可能であり、ウィルス対策ソフトが必要である。
理解度確認
- Formsによる理解度確認テスト
- 標的型攻撃メールがウィルス対策ソフトでは防ぐことが難しい理由を述べよ。
- ファイアウォールでは、どういった処理を行うのか説明せよ。