メニュー

アルゴリズムとは:アルゴリズムの基礎知識1

アルゴリズムの基礎知識

更新日:2022年6月21日(初回投稿)
著者:東京都立大学 経済経営学部 経済経営学科 准教授 森口 聡子

アルゴリズムとは、一般的にコンピュータを使ってプログラムで問題を解決するための手順として知られています。コンピュータはビックデータを高速に処理することが可能です。しかし、その処理手順には、効率のよいプログラムを作成するためのアルゴリズムが不可欠です。アルゴリズムはプログラミングに限らず、日常で見聞きする機会も増えています。手順をフローチャートにすることで、作業の標準化ができ、間違いを特定しやすいなどの効果があります。本連載は全6回にわたり、アルゴリズムの基本から代表的なアルゴリズム、さらに世の中での使われ方について解説します。

今すぐ、技術資料をダウンロードする!(ログイン)

1. アルゴリズムとは

アルゴリズムとは、問題を解決するための計算の手順や方法のことです。別のいい方をすると、与えられたデータから、望みの情報を取り出すための操作手順です。それが、コンピュータの計算によって問題を解決することが増えたことで、アルゴリズムといえば、コンピュータに計算をさせるときの計算の手順・方法のことといったように、コンピュータのプログラムを作るときに使われる用語として捉えられるようになりました(図1

図1:アルゴリズム(イメージ)

図1:アルゴリズム(イメージ)

情報技術は、発展によって社会や人の生活への影響、活用範囲の広がりが進み、現代の高度情報化社会を築いてきました。そして近年、コンピュータはその処理能力が飛躍的に高まり、さらなる情報化に貢献しています。しかし、そのようなハードウェアの進歩だけでは、今日のような急激な高度情報化は実現し得ませんでした。それは、ハードウェアに命令を出すソフトウェア(プログラム)を作る論理的な手続き処理、アルゴリズムの進歩との相乗効果によるものです。このように、高度情報化社会に対応するため、アルゴリズムの担うべき役割はますます重大なものになってきています。

2. アルゴリズムとプログラム、身近なアルゴリズム

アルゴリズムとプログラムは、よく似た意味合いを持ちます。しかし、その概念は異なり、用語は区別されて使われています。プログラムは、コンピュータ上で実行できるように、コンピュータが理解できるプログラミング言語で書かれているのに対し、アルゴリズムはプログラムを書く前の段階で、人間が理解できるように書かれたものを指します。同じアルゴリズムでも、異なるプログラミング言語を用いれば違うプログラムになります。また、同じプログラミング言語が使われていても、プログラムする人によって違うものになります。

コンピュータが理解できる言語で書かれているものと、人間が理解できるように書かれたものの例として、ソースコードと疑似コードが挙げられます(図2)。ソースコードとは、プログラミング言語で書かれたコンピュータプログラムを表現する文字列のことをいいます。それに対して、疑似コードとは、ソースコードに近く人間にも分かりやすい書き方、すなわち、非常に高水準な架空のプログラミング言語(擬似言語)で処理の流れを記述したものです。

図2:ソースコード疑似コード(例)

図2:ソースコード疑似コード(例)

記述の仕方自体に、どこからがアルゴリズムでどこまでがプログラムだという、厳密な境目は定められていません。疑似コードは、Pascal、Fortran、C言語といった、既存の伝統的なプログラミング言語の構文と、自然言語(人間が日常的に用いる言語)に近い表現を組み合わせて記述されることが多いです。

アルゴリズムがどういうもので、どのように記述したらよいのかを、身近な具体例を通して考えてみましょう。

数がバラバラにn個並んだ「要素1、要素2、要素3、…、要素n」が与えられ、その中から最も大きい値を見つけたいとします。このとき、どんな方法が思いつくでしょうか。そして、思いついた方法、手順をどう記述すればいいでしょうか。最大値を求める方法として、単純に考えると

要素1、要素2、要素3、…、要素nを順番に見ていき、途中で「それまでに見た数の中で最も大きい数」を見つけたら、それを記憶しておく。すると、最後まで見終わったときに、「それまでに見た数の中で最も大きい数」として記憶されている要素が、求めたい最も大きい値である。

という方法が思いつくでしょう。この書き方でも、確かに手続きの記述にはなっています。しかし、分かりやすいアルゴリズムの記述とはいえません。この書き方では、もっと複雑な計算手順になった場合、とても読みにくくなってしまうのではないかと不安になるでしょう。ここで、次の書き方と比べてください。次の書き方では、それまでに見た数の中で最も大きい数をyで表すことにします(図3)。

<最大値を求めるアルゴリズム>

入力:
正の整数値nと、n個の(実数)値、要素1、要素2、要素3、…要素n

出力:
要素1、要素2、要素3、…要素nの中の最大値

手続き:

  1. ステップ1:y=要素1とする
  2. ステップ2:i=2、3、…、nに対して順に次を行う。要素i>yならばy=要素iとする
  3. ステップ3:yを出力する

図3:最大値を求めるアルゴリズム

図3:最大値を求めるアルゴリズム

入力とは、アルゴリズムに与えるデータのことで、出力とは、アルゴリズムによって作り出したい情報のことです。この書き方では、最初に入力と出力を指定し、解くべき問題をはっきりさせています。

次に、手続きが記述されています。手続きは、それぞれステップと呼ばれる、1、2、3と番号の付けられた部分に分けられています。計算手続きがステップに分解されているため、行うべき操作の順序が明確です。そして、変数yや数式による記述が導入されていることで、各ステップで行うべきことが明確になっています。この書き方は疑似コードの一つといえます。疑似コードを用いたアルゴリズムの記述は、人間同士で手続きの内容を伝え合うためのもののため、プログラミング言語の文法のように従うべき厳密なルールはありません。例えば、ステップ2で

ステップ2:for i = 2 until n do、if i > y then y = 要素i;

としたり、ステップ3で

ステップ3:return y;

とするなど、よりプログラミング言語に寄せて書くこともできます。疑似コードでどれだけプログラミング言語に寄せるか、そしてどの言語の構文を使うかは、場面やコミュニケーションをとる相手に応じて臨機応変に選ばれます。

3. 世界最古のアルゴリズム

最も古いアルゴリズムは、いつ頃考案されたのでしょうか。コンピュータが発明されてからでしょうか。実は、アルゴリズムの歴史は、コンピュータよりずっと古くからあります。記録に残る世界最古のアルゴリズムは、2つの自然数の最大公約数を求めるユークリッドの互除法であるといわれています。

ユークリッドの互除法は、高校数学で習います。単に互除法と呼ばれることもあります。高校で習ったことを少し思い出してみましょう。

<2つの自然数x、yの最大公約数を求めるユークリッドの互除法>

入力:
自然数x,y (x≥y)

出力:
x,yの最大公約数

手続き:

  1. ステップ1:xをyで割り、余りrを求める
  2. ステップ2:yをrで割り、その余りr1を求める
  3. ステップ3:rをr1で割り、その余りr2を求める
  4. ステップ4:余りが0になるまで「直前の割る数÷直前の余り」を繰り返す。余りが0になったときの割る数を最大公約数として出力する

具体的に12と20の最大公約数を求めてみましょう。
x=20、y=12とすると、

  1. ステップ1:xをyで割った余りrは8
  2. ステップ2:y=12をr=8で割った余りr1は4
  3. ステップ3:r=8をr1=4で割った余りr2は0
  4. ステップ4:余りが0になったので、このときの割る数r1=4を最大公約数として出力する

ユークリッドの互除法の仕組みは、図4のように、最大公約数を求める対象の2つの整数(20と12)を幅と高さに設定した長方形内での、斜めの直線の描画過程によっても表現できます。最大公約数は、長方形内に敷き詰めることができる一番大きな正方形の、一片の長さが対応します。斜めの直線の描画は、はじめはその長方形内を描画範囲とし、その角から内部に向け、一辺に対して45°で描画します(正方形の対角線に対応します)。描画範囲の辺の途中に当たれば、その内部へと角度を変え、描画範囲も小さい長方形とします。斜めの直線が描画範囲の角に到達した場合、描画範囲の長辺の長さを短辺の長さで余りなく割れる状態となっており、描画の終了となります。そして、最後に、最小描画範囲の短辺の長さが、最大公約数(4)となります。

図4:20と12の最大公約数を求めるユークリッドの互除法

図4:20と12の最大公約数を求めるユークリッドの互除法

 

ユークリッドの互除法は、対象の2つの数が巨大な数であっても割り算を繰り返すだけという決まった手順で効率良く最大公約数を求めることができます。

このアルゴリズムが、正確にいつ発見されたのかは定かではありません。最も古い記述が、紀元前300年代に書かれたユークリッドの著書であることから、この呼び名がつけられました。これほど古くに提案されたものが、現代でも使われ続けているということです。これは、コンピュータの発明よりもはるか昔から、アルゴリズムは存在していたという証しです。

いかがでしたか? 今回は、アルゴリズムの概念や歴史を紹介しました。次回は、アルゴリズムのクオリティについて解説します。お楽しみに!

参考文献:
杉原厚吉、データ構造とアルゴリズム、共立出版、2001年

関連記事

同じカテゴリの記事

ピックアップ記事

tags