アルゴリズムA 第1回


アルゴリズムとは

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

   アルゴリズム + データ構造 = プログラム

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

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

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

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

計算量

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

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

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

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

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

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

計算量の表記

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

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

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

Entry.java (キーとデータの組を表す)
/*
 * キーとデータの組
 */
public class Entry {
    private int key;		//比較の対象となるキー
    private Object data;	// それ以外の情報
    public Entry(int key,Object data) {	// コンストラクタ
	this.key = key;
	this.data = data;
    }
    public int getKey() { return key; }	// キーを返す
    public Object getData() { return data; } // データを返す
    public String toString(){ return key + ":" + (String)data; } // 文字列に
    static String toString(Entry[] a) { // Entryの配列全体を文字列に
	StringBuffer sb = new StringBuffer();
	sb.append("{");
	for (int i=0; i<a.length; i++) sb.append(a[i] + " ");
	sb.append("}");
	return sb.toString();
    }
}
EntryTable.java (Entryを要素とする表)
public class EntryTable {
    protected int nEntry;	// 表に登録されているエントリの個数
    protected Entry[] table;	// 表を配列として表現する
    public EntryTable() { this(100); }
    public EntryTable(int n) {
	table = new Entry[n];   // 表の初期化
	nEntry = 0;		// エントリの個数は最初は0
    }
    public void set(int idx,Entry entry) { // idx番目にエントリを登録する
	if (idx < 0 || idx >= table.length)
	    throw new IllegalArgumentException("場所が不正です");
	table[idx] = entry;
    }
    public Entry get(int idx) { // idx番目のエントリを返す
	if (idx < 0 || idx >= table.length)
	    throw new IllegalArgumentException("場所が不正です");
	return table[idx];
    }
    public void add(int key, Object data) { // エントリを後ろに追加する
	if (nEntry >= table.length) // 表の大きさを越えた場合
	    throw new IllegalArgumentException("データの個数が多過ぎます");
	set(nEntry++, new Entry(key,data));
    }
    public int getNumber() { return nEntry; } // エントリの個数を返す
    public int getSize() { return table.length; } // 表の大きさを返す
}
線形探索法 LinearSearch.java
授業で配布するプリントを参照して下さい。
RunLinearSearch.java
import java.util.*;
public class RunLinearSearch {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in); // キーボードから読み取る
	LinearSearch table = new LinearSearch(); // テーブルを生成する
	table.add(1,"one");
	table.add(10,"ten");
	table.add(2,"two");
	table.add(11,"eleven");
	table.add(17,"seventeen");
	table.add(3,"three");
	// ...     本来はここで沢山のデータをaddする。
	while (true) {
	    int key = sc.nextInt(); // キーを読み込んで
	    String x = (String)table.search(key); // 探索する
	    if (x != null) {	// 見つかった場合
		System.out.println("value=" + x);
	    } else {		// 見つからなかった場合
		System.out.println("Not found");
	    }
	}
    }
}

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

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)1O(1)
(2)(平均)n/2O(n)
(3)(平均)n/2o(n)
(4)1O(1)
(5)(平均)n/2o(n)
(6)1o(1)
計算量の加算
  O(f(n))O(g(n))O(max(f(n),g(n)))
max(f(n),g(n)) は、増加率で決ります。
小さい ←←←←←←←←←←←増加率→→→→→→→→→→→大きい
1    log n    n log n    n2    n3    ...    nk    2n    n!
計算量の乗算
  O(f(n))O(g(n))O(f(n)・g(n))

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



アルゴリズムA 演習


課題1a

  1. RunLinearSearch.java を動作させて下さい。
  2. Entry.java, EntryTable.java, LinearSearch.java, RunLinearSearch.java が必要となります。

  3. 次の仕様を満たすLSearch.javaを作成して下さい。
  4. データは標準入力から読むこと。LinearSearch.javaはそのまま利用すること。

    入力形式

    N
    K1 D1
    K2 D2
    ...
    KN DN
    M
    Q1
    ...
    QM
    

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

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

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

    出力形式

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

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

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

  5. LSearch.javaをキーボードからデータを与えて動作させて下さい。
  6. 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            ←出力
    
  7. LSearch.javaを次のデータhttp://nw.tsuda.ac.jp/class/algoA/numstr01.txt に対して動作させて下さい。

    LSearch.javaの実行例2
    % javac LSearch.java 
    % java LSearch < numstr01.txt 
    bridge
    Not found
    wan
    
  8. 作成したプログラム LSearch.javaが正しく動作することを確認したら、 LSearch.javaを「宿題提出Web:アルゴリズムA:課題1」 http://nw.tsuda.ac.jp/class/algoA/local/handin/up.php?id=kadai1a から提出して下さい。
  9. コメント欄には何も書かなくて構いません。

  10. 提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai1a で必ず確認しておいて下さい。
LSearch.javaの骨子
授業で配布するプリントを参照して下さい。

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