アルゴリズム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 (キーとデータの組を表す)

授業で配布するプリントを参照して下さい。
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)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の骨子

import java.util.*;

public class LSearch {
    public static void main(String[] args) {
	LinearSearch table = new LinearSearch(); // LinearSearchクラスを使う
	Scanner sc = new Scanner(System.in); // 標準入力からScannerで読み込む
	int n = sc.nextInt();	// データの個数
	// [n回繰り返し] データを読み込む。
	//    データは 整数 k      sc.nextInt()
	//    データは 文字列 d      sc.next()
        //    kとdを table にaddする
	int m = sc.nextInt();	// 質問のキーの個数
	// [m回繰り返し] キーを読み込んで探索する。
	//    キーは 整数 q       sc.nextInt()
	//    探索は table の search()メソッドを呼び出す
        //    探索結果がnullなら"Not found"、それ以外はその結果を表示する
    }
}

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