【初心者にやさしい】CS(コンピューターサイエンス)基礎の基礎の学習：アルゴリズム

CS(コンピューターサイエンス)基礎の基礎

現在、CS基礎の基礎を一から学んでいるので、その学習成果のアウトプットに、、、

今回は「アルゴリズム」

1. アルゴリズムとは

　アルゴリズムとは、 問題を解くための手順をモレなく図や文章に示したもの を指します。以前の記事でコンピューターは、「inputしたものを演算し、結果をoutput」するが、演算部分は「ブラックボックス」になっていて、ユーザーには見える必要がないという構造になっていると説明しました。このブラックボックスの部分が アルゴリズム です。

2. アルゴリズムを作成する際のポイント

ポイント①：アルゴリズムは「手順が明確」で「機械的」で「終わりが定まっていること」

　アルゴリズムを組む際に、「手順が不明瞭」で「複雑」で、尚且つ「終わりがどこなのか分からない」状態では、アルゴリズムだと呼ぶことはできません。

　例えば、「2つの整数の最大公約数を求める」という問題があったとします。この時、私たち自身が解くとすると、数学で習った方法を適用し、「両者を小さい数字で割り切れなくなるまで割っていき、割り切れなくなったところで、その時の数字を掛けたものが最大公約数となる」という手順で解答していくでしょう。

　しかし、これは「アルゴリズム」とは呼べない方法です。なぜなら「 人間の勘 」を利用した方法だからです。「まず最も小さい数字で両者を割れるのは2だろう」と思って2で割ってみるわけですから、「勘」で行っていることになります。他にもアルゴリズムとは呼べない点がいくつかありますが、コンピューターに「勘」はありません。 全てを機械的に行うだけなので、「手順の明確さ」というものが何よりも必要 になります。

　この「最大公約数」をアルゴリズムを組んで機械的に解答しようとした場合、「ユークリッドの互除法」が利用できます。
　↓↓↓↓↓↓↓↓↓

　これなら、「手順が明確」で、「機械的」で、「終わりが定まっている」という条件を満たしています。ちなみに、これをRubyでコーディングした場合、以下のようになります。

a = 42
b = 12

while a != b
  if a > b
    a = a - b
  else
    b = b - a
  end
end

puts "最大公約数は#{b.abs}です"

ポイント②：定番のアルゴリズムを利用する

　①で利用した「ユークリッドの互除法」はまさに、この「定番アルゴリズム」です。すでに世の中に生み出されているアルゴリズムを知って、利用できるようになっていくことは、とても有効的な手段となるはずです。
定番のアルゴリズムを理解できるような書籍やサイトを参考にすると良いでしょう。私もこれから学んでいきたいと思っています。ちなみに、私はとっつきやすい教材として以下の2つをピックアップしてアルゴリズムを学習し始めています。よろしければ参考にしてみてください。

　●Scratch(パズル感覚で子供でも学べる学習サイト)
　https://scratch.mit.edu/

　●アルゴリズム図鑑(定番のアルゴリズムを動画で視覚的に学べるアプリ)
　https://apps.apple.com/jp/app/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%9B%B3%E9%91%91/id1047532631

ポイント③：コンピューターの処理スピードアップを意識する

　同じ答えを導き出すためのアルゴリズムでも、組み方によってコンピューターの処理速度に差が生まれます。

　● チェック回数を減らす方法
　一つの手段として、「コンピューターがチェックする回数を減らして処理速度を上げる」という方法があります。例えば、「ずらーっと並べられた数字の中から特定の数字を探すための処理」を組もうとした場合、普通なら「並べられた数字を左から順番にチェックしていき、指定した数字と合致したら終了」という処理を組もうとするでしょう。一方、他のやり方もあります。それは「BinarySearch(2分割検索法)」です。
　これは、「まず並べられた数字の中で真ん中に存在する数字を指定し、探したい数字が真ん中の数字に対して右か左かどちらにあるかを特定します。その後、真ん中に対して探したい数字が存在しない側にある数字を全て無視し、ある側の数字に対して次の検索を実行します。これを繰り返すのです。」

　こうすることで、一度にチェックするべき総量が半分に減っていっているのが分かります。つまりコンピューターの処理速度も格段に上がります。

　● 法則性を見出す方法
　次は、出てくる数字の法則性に注目して、アルゴリズムを組み、処理速度を上げる方法です。例えば、「ユーザーとコンピューターでじゃんけんをして、その結果を出力する」という処理を組む時、「勝ち負けの判定」はどのように組むでしょうか。おそらく、「グー：0, チョキ：1, パー：2」のように数字を割り振り、if文を使って考えられるパターンを書き出していくという方法を思いつくでしょう。しかし、数字に着目して法則性を見出せば、かなり単純な処理で済ませることができるようになります。どうぞお考えください！！

　以上のように、「より効率的な方法な何か」という視点も大切ということが言えますね。

ポイント④：いきなりプログラムを書かないこと

　まずは、 アルゴリズムを紙に書き出すことから 始めましょう。「何を答えとして求めたいのか」、「必要な手順は何か」、「条件分岐は必要か」、「終わりは」などと一つ一つ検討して、フローチャートなどを利用しながら組み立てて初めて、実際にプログラムを書いてみることが重要です。
　私もいきなりプログラムを書いてしまい、後から考慮しなければならない追加要素があることに気づき、プログラムそのものを一から書き直す羽目になったことが何度もあります。まず落ち着いて考えることが必要なのですね。

　ちなみにフローチャートは以下のようなものです。

3. 参考文献

　この記事の内容は、「コンピュータはなぜ動くのか」という書籍を読んだ後のアウトプットとなっています。
　この書籍は、「ハードウェアからソフトウェアへ」と順序立てて学習していける構造になっており、それぞれの章では実際に手を動かしながらやってみるコーナーや、クイズなども用意されていて、良質なインプットとアウトプットをしながら学習していける内容となっていると感じました！！
　初めは表紙のデザインが学術書みたいで内容も難しく重たいのかなと思っていたのですが、いざ読み進めると、好奇心がどんどん高まっていき、「早く次を学びたい！！」という衝動を抑えられなくなるほどでした。
　ご興味があれば、チェックしてみてください！！

4. 学び

　アルゴリズムと聞いて、「難しい」という印象しか持っていなかったのですが、自分が普段プログラミングで記述しているコード一つ一つがアルゴリズムの一部だと考えると、それほど遠い存在ではないように思えるということが分かりました。「論理的思考力」を磨くという点でも、今後学びを深めていきたいと思います。