アルゴリズムの基礎1

概要

大学時代に受けた"データ構造とアルゴリズム"という講義を元に執筆しようと思う。誤字脱字や間違いなどあれば指摘いただければありがたい。

用語の定義

直近で使う用語の定義をする。

問題とは

問題とは、入力と(入力を処理して望まれる)出力のペアである。入力となるパラメータは有限長とする。各パラメータに対して問題例が一つ定まる。

例1: GCD (最大公約数)
入力: 2つの非負整数 $x, y$
出力: $gcd(x, y)$

問題例: $(x, y) = (5, 12)$

例2: 最小値
入力: 非負整数 $n$ および $n$ 個の非負整数 $a_1, a_2, \cdots, a_n$
出力: $a_1, a_2, \cdots, a_n$ の最小値

問題例: $(n, a_1, a_2, \cdots, a_n) = (3, 4, 6, 1)$

アルゴリズムとは

アルゴリズムとは、有限ステップで停止することが保証(証明)され、任意の問題例に対して常に正しい答えを出力していることが保証(証明)されている計算手続きである。
※前者だけをアルゴリズムの要件とし、後者をアルゴリズムの正当性と呼ぶこともあるが、ここでは両方を満たす時とする。

例1: GCD
最大公約数の問題を解くアルゴリズムとして、世界最古のアルゴリズムと呼ばれているユークリッドの互除法がある。

問題例: $(x, y) = (5, 12)$ に対する動作
12 を 5 で割った余りは 2
5 を 2 で割った余りは 1
2 を 1 で割った余りは 0
余りが 0 になったら終了でその前の余り 1 が 5 と 12 の最大公約数となる。

PHP でのコードは下記のようになる。

function gcd($x, $y){
    return $y === 0 ? $x : gcd($y, $x % $y);
}

例2: 最小値
与えられた数値の中から最小値を求めるというよくある問題。
色々と解き方があるが、一例として下記のように解ける。

function min(array $elements){
    $last_element = array_pop($elements);
    if (empty($elements)) {
        return $last_element;
    }

    $min_tmp = min($elements);
    return $min_tmp < $last_element ? $min_tmp : $last_element;
}

それらがアルゴリズムであることの証明は次回する。