アルゴリズムとはなんぞや

アルゴリズムってやつについて書いてみます．
wikipediaさんによると...

アルゴリズム（英: algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。
アルゴリズム - Wikipedia

なんだかわかるようなわからないような解説ですね．wikipedia先生っていつもそう．

アルゴリズムの"定義"はカッチリと数学的にできるんですが，カッチリやろうと思うと計算モデルがどうだとか計算可能性がどうだとかなんだか難しい話になるっぽいのでここではやりません．

ここではアルゴリズムという概念について簡単に説明していこうと思います．

細かい部分で厳密性を欠いた表現をするかもしれませんが，ここでは難しい議論はしたくないのでできるだけスルーしてもらえると助かります．

僕が誰かに「アルゴリズムとは？」と聞かれたらきっと

「問題を解くための計算手順」

と答えると思います．

抽象的すぎてピンとこないかもしれませんね．
現実の問題では，料理のレシピなんかもアルゴリズムと言えるでしょう．
上の回答にあてはめると，

「問題（料理）を解く（作る）ための計算（調理）手順」

といった具合です．
アルゴリズムってのは実は，
料理を作るための調理手順のことなんです！(違
cookpadさんなんかはアルゴリズムの宝庫ってことですね．

ですが，ここではあくまで
情報科学の意味でのアルゴリズムについてお話をしていきます．
つまりは「料理がしたい！」だとか「彼女が欲しい！」だとかの
コンピュータさんじゃあどうしようもない問題は考えません．

すると，
「じゃあ“問題”ってなんやねん！」
「"解く"ってなんやねん！」
「"計算"ってなんやねん！」
って話になってきます．

ここでは，"問題"というのは
「入力に対して出力(解)があり，数学的に記述できるもの．」
としましょう．

問題を“解く”とは，
「問題の入力が与えられたとき，有限時間内に正しく問題の出力(解)を導くこと．」
としましょう．

"計算"とは，
「コンピュータによって処理ができるもの．」
としましょう．(これはちょっと間違いかも...)

まだ抽象的すぎてよくわかりませんね．
では例を挙げながら考えていきましょう．
※ 本記事の問題の入力での変数はすべて整数値であるとします．

問題1(BMI計算問題)
入力 : Aさんの体重 $w$ [kg], 身長 $h$ [m]
出力 : AさんのBMI

BMIの計算式は皆さんご存知の通り(?)
BMI = (体重[kg]) ÷ (身長[m])^2
でしたね！
よって以下のアルゴリズム1-1は
正しくBMIを計算してることがわかります．

アルゴリズム1-1 :
$h' ← h*h;\\ BMI ← w/h';\\ {\bf output}\, BMI;$

また，途中の変数を使わずに
アルゴリズム1-2のようにも書けます．

アルゴリズム1-2 :
${\bf output}\, w/(h*h);$

正しいアルゴリズムは一通りとは限りません．
違う理論をもとに設計をしたり計算の順番を入れ替えたり，
いくらでも違うものは存在し得ます．

アルゴリズムが正しいのは大前提として，
「アルゴリズムの性能」だとか「わかりやすさ」
なんてものも重要になってきます．(ここでは書きませんが...)

次のような Yes/No を問う問題も考えられます．
問題2 (偶奇判定問題)
入力 : $x$
出力 : $x$ が偶数ならYes, 奇数ならNo

アルゴリズム2 :
${\bf if}\ (x\ {\bf mod}\ 2 = 0)\ {\bf then}\\ \quad {\bf output}\ “Yes”;\\ {\bf else}\\ \quad {\bf output}\ “No”;\\$

アルゴリズム中で if だの else だの書いてますね．
これは条件分岐が必要なときに登場します．
意味は...そのまんまです(投げやり)

さて，次のようなものはどうでしょう？
問題(?) :
入力 : Aさん
出力 : Aさんは太っているか否か

これは問題とは言えないですね．
数学的に記述できていないので，コンピュータさんが困ります．
コンピュータさんは定性的な説明や判断基準では何もできません．
常に数学的・定量的な記述が必要になります．

問題3 :
入力 : Aさんの体重 w [kg]，身長 h [m]
出力 : AさんのBMIが25以上か否か

これなら良さそうです．

アルゴリズム3 :
${\bf if} (w/(h*h) ≥ 25) {\bf then}\\ \quad {\bf output}\ “Yes”;\\ {\bf else}\\ \quad {\bf output}\ “No";\\$

問題1のように「これの値を計算して出力してくれ」っていう問題を計算問題と呼び，問題2,3のように「これはYesですか？Noですか？どっちですか？」っていう問題を判定問題と呼びます．そのまんまですね．問題は大きく上の2つに分類できます．

あれ，数学的な記述がされた問題ならば
どんな問題でもアルゴリズムが書けるのでは！？！？
アルゴリズムさん最強wwwwwコンピュータバンザイ！！！

と思われた方もいらっしゃるかもしれませんが，実は，
アルゴリズムが書けない(正確には，計算が不可能な)問題が存在します．

計算できないとは，なんのこっちゃ．
具体的にどんな問題があるのかってのは次回以降で書こうと思います．

まとめ :
アルゴリズムとは...

数学的に記述された問題を，コンピュータさんに，
有限時間内で正しく解いてもらうための計算手順のこと．