algorithm a

アルゴリズムA 第1回

アルゴリズムとは

「アルゴリズム」とは「問題を解くための手順」であり、これをプログラミング言語であらわしたものが「プログラム」です。


   アルゴリズム ＋ データ構造 ＝ プログラム

「プログラムを書く」ための３段階

問題を分析して、何をするプログラムを書くのかを决める。（プログラムの仕様を決定する）
どんなアルゴリズムとデータ構造を使用すればよいかを選択する。
プログラミング言語で実際にプログラムを書く。

データの分量、実行するコンピュータのリソース(CPU速度、メモリ量などの資源)を考えて、複数のアルゴリズムから適切なものを選択する必要があります。


(例)時間と空間のトレードオフ
    「遅いけど、メモリをあまり使わないアルゴリズム」
    「速いけど、メモリをたくさん使うアルゴリズム」

計算量

「コンピュータの性能を評価する」ためには、「ベンチマーク」という「評価の基準となるプログラム」を動作させたときの「実行時間」を比べるのが一般的です。

しかし、この方法は「アルゴリズムを評価する」ためには不適切です。アルゴリズムを実現するプログラムの書き方や、プログラムを動作させるコンピュータのCPUやメモリの性能や特性によって大きく影響を受けてしまうからです。


アルゴリズムの性能を評価する尺度 → 計算量(complexity)

「計算量」とは、「仮想的なコンピュータ上でアルゴリズムを実行したときに必要な○○を『入力データの大きさn』を使って表したもの」です。

○○には、次の２種類があります。単に計算量と言った場合は、「実行時間」を指します。

実行時間 ... 時間計算量 (time complexity)
メモリ領域の大きさ ... 領域計算量 (space complexity)

計算量についても次の２種類があります。単に「計算量」といった場合は、普通は「最大計算量」を指します。

最大計算量 (worst-case complexity) ... 最悪の入力データを想定したときの計算量
平均計算量 (expected complexity) ... 全ての入力データに対する計算量の平均を取ったもの

計算量の表記

入力データの大きさをnとしたときに、実行時間がxに比例してかかるアルゴリズムを「$O(x)$ のアルゴリズム」と表現し、「オーダー $x$ のアルゴリズム」と読みます。 $x$ は $n$ の関数です。

(例)

$n$ に比例する場合 ... $O(n)$ のアルゴリズム
$n^2$ に比例する場合 ... $O(n^2)$ のアルゴリズム
$2^n$ に比例する場合 ... $O(2^n)$ のアルゴリズム

線形探索法による探索の計算量

Entry.java (キーとデータの組を表す)

EntryTable.java (Entryを要素とする表)

線形探索法 LinearSearch.java

RunLinearSearch.java

以下の実行例の中の行の先頭にある '%'は「プロンプト」を表すものとします。

RunLinearSearch.javaの実行例

% javac Entry.java EntryTable.java LinearSearch.java RunLinearSearch.java 
% java RunLinearSearch  
10   ←入力
value=ten
15   ←入力
Not found
17   ←入力
value=seventeen
^C  ← Controlキーを押しながらCキーを押すと終了

ステーテメント	実行回数	計算量
(1)	1	$O(1)$
(2)	(平均)$\frac{n}{2}$	$O(n)$
(3)	(平均)$\frac{n}{2}$	$O(n)$
(4)	1	$O(1)$
(5)	(平均)$\frac{n}{2}$	$O(n)$
(6)	1	$O(1)$

計算量の加算: $O(f(n)) ＋ O(g(n)) ~\longrightarrow~ O(\max(f(n),g(n)))$
$\max(f(n), g(n))$ は、増加率で決ります。

小さい ←←←←←←←←←←←増加率→→→→→→→→→→→大きい
1    log n    n log n    n²    n³    ...    n^k    2ⁿ    n!

計算量の乗算: $O(f(n)) \cdot O(g(n)) ~\longrightarrow~ O(f(n)・g(n))$

上記の線形探索の計算量は $O(n)$ です。計算量は入力データの大きさnに比例し、たとえば、入力データの大きさが100倍になると、計算量も100倍のオーダーで大きくなります。

アルゴリズムA 演習

課題1a

提出ファイル	LSearch.java
コメント欄:	なし
提出先:	「宿題提出Web:アルゴリズムA：課題1」 http://ynitta.com/class/algoA/local/handin/up.php?id=kadai1a

RunLinearSearch.java を動作させて下さい。

Entry.java, EntryTable.java, LinearSearch.java, RunLinearSearch.java が必要となります。

次の仕様を満たすLSearch.javaを作成して下さい。

データは標準入力から読むこと。LinearSearch.javaはそのまま利用すること。

入力形式


N
K₁ D₁
K₂ D₂
...
K_N D_N
M
Q₁
...
Q_M

最初の行には、データの個数を表す整数 N が含まれている。ただし1≦N ≦100である。

２行目以降はデータを表す行がN行続く。これらの各行は、「キー」を表す1個の整数 K_i と、「データ」を表す1個の文字列 D_i が空白文字1個で区切られたものである。

その次の行には、質問の個数を表す整数 M が含まれている。ただし 1≦M ≦10 である。その行以降にM 行続き、これらの各行は「探索すべきキー」をあらわす整数Q_j (1≦j≦M ) を含む。

出力形式

それぞれの質問 Q_jに対して、1行の答を標準出力に出力しなさい。

もし質問 Q_jと一致するキーを持つデータ K_aが存在したら、そのキーに対応するデータ D_aを答えなさい。複数のデータが同じキーを持つことはないと仮定して構わない。

質問に一致するキーを持つデータが存在しない場合は、"Not found"と出力すること。

LSearch.javaをキーボードからデータを与えて動作させて下さい。

LSearch.javaの実行例1

% javac LSearch.java 
% java LSearch 
5            ←入力(データの個数)
2 apple      ←入力
8 peach      ←入力
6 melon      ←入力
9 orange     ←入力
7 lemon      ←入力
3            ←入力(質問の個数)
6            ←入力 (探索するキー)
melon            ←出力
4            ←入力 (探索するキー)
Not found            ←出力
9            ←入力 (探索するキー)
orange            ←出力

LSearch.javaを次のデータhttp://ynitta.com/class/algoA/numstr01.txt に対して動作させて下さい。
LSearch.javaの実行例2
% javac LSearch.java % java LSearch < numstr01.txt bridge Not found wan
作成したプログラム LSearch.javaが正しく動作することを確認したら、 LSearch.javaを「宿題提出Web:アルゴリズムA：課題1」 http://ynitta.com/class/algoA/local/handin/up.php?id=kadai1a から提出して下さい。

提出した後は、正しく提出されていることを http://ynitta.com/class/algoA/local/handin/list.php?id=kadai1a で必ず確認しておいて下さい。

LSearch.javaの骨子

課題提出の〆切は次回の講義の開始時刻です。