What's an algorithm? - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

翻訳: Kohgaku Eguchi 校正: Tomoyuki Suzuki

What's an algorithm?

アルゴリズムとは何でしょう

In computer science,

コンピューターサイエンスでは 問題を一歩ずつ解くための

an algorithm is a set of instructions

for solving some problem, step-by-step.

一連の指示のことを言います

Typically, algorithms are executed by computers,

通常 アルゴリズムは コンピューターで実行されますが

but we humans have algorithms as well.

人間もアルゴリズムを使います

For instance, how would you go about counting

例えばあなたはどうやって

the number of people in a room?

部屋にいる人の数を数えるでしょう

Well, if you're like me,

私と同じだとしたら

you probably point at each person,

おろらく 一度に １人ずつ指さして

one at a time,

and count up from 0:

０からはじめて

1, 2, 3, 4 and so forth.

１、２、３、４・・・と数えるでしょう

Well, that's an algorithm.

これがアルゴリズムです

In fact, let's try to express it

それでは実際に

a bit more formally in pseudocode,

少し形式的ですが 擬似コードという

English-like syntax

that resembles a programming language.

プログラム言語に似た

英語のような構文で表現してみましょう

Let n equal 0.

まず N = ０とします

For each person in room, set n = n + 1.

部屋にいる人を １人ずつ数える時 N = N + １と表します

How to interpret this pseudocode?

この擬似コードを解釈してみましょう

Well, line 1 declares, so to speak,

まず１行目で

a variable called n

いわゆる変数 N を宣言し

and initializes its value to zero.

その値を０に初期化します

This just means that at the beginning of our algorithm,

これはアルゴリズムの始まりでは

the thing with which we're counting

数えている対象の値が

has a value of zero.

０であることを意味します

After all, before we start counting,

つまり 数え始める前は

we haven't counted anything yet.

私たちはまだ何も数えていません

Calling this variable n is just a convention.

変数をNにしたのは ただの慣例で

I could have called it almost anything.

Nでなくても ほとんど何でも使えます

Now, line 2 demarks the start of loop,

さて ２行目はループの開始点です

a sequence of steps that will repeat some number of times.

一連のステップを何度か繰り返します

So, in our example, the step we're taking

この場合 ループするステップは

is counting people in the room.

部屋にいる人を数えるところです

Beneath line 2 is line 3,

続く３行目では

which describes exactly how we'll go about counting.

どう数えるかを正確に記述します

The indentation implies that it's line 3

字下げは３行目の作業を

that will repeat.

繰り返すという意味です

So, what the pseudocode is saying

つまりこの擬似コードは

is that after starting at zero,

０から始まって

for each person in the room,

部屋にいるそれぞれの人に対して

we'll increase n by 1.

Nを１つずつ増やしていきます

Now, is this algorithm correct?

さて このアルゴリズムは正しいでしょうか

Well, let's bang on it a bit.

ちょっと試してみましょう

Does it work if there are 2 people in the room?

もし部屋に２人いる場合はどうでしょう

Let's see.

見てみましょう

In line 1, we initialize n to zero.

１行目でNを０に初期化します

For each of these two people,

２人それぞれに対して

we then increment n by 1.

Nを１つずつ増やします

So, in the first trip through the loop,

ですので ループの１周目では

we update n from zero to 1,

Nは０から１になり

on the second trip through that same loop,

ループの２周目で

we update n from 1 to 2.

Nは１から２に更新されます

And so, by this algorithm's end, n is 2,

そして アルゴリズムが終わるとNは２で

which indeed matches the number of people in the room.

たしかに 部屋にいる人の数に 一致しています

So far, so good.

ここまでは順調ですね

How about a corner case, though?

特殊なケースではどうでしょうか

Suppose that there are zero people in the room,

部屋に１人もいない場合

besides me, who's doing the counting.

― 数えている私を別としてですが ―

In line 1, we again initialize n to zero.

１行目でまたNを０に初期化し

This time, though, line 3 doesn't execute at all

今回は３行目は まったく実行されません

since there isn't a person in the room,

誰も部屋にいませんからね

and so, n remains zero,

ですので Nは０のままで

which indeed matches the number of people in the room.

実際に 部屋にいる人の数に一致しますね

Pretty simple, right?

簡単でしょう？

But counting people one a time is pretty inefficient, too, no?

しかし １人ずつ数えるのは とても非効率的ですよね？

Surely, we can do better!

もちろん 改善できます！

Why not count two people at a time?

一度に２人ずつ数えたらどうでしょう

Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth,

１、２、３、４、５、６、７、８ と数える代わりに

why not count

数え方を

2, 4, 6, 8, and so on?

２、４、６、８・・・にしてみましょう

It even sounds faster, and it surely is.

速くなりそうですが 実際に速くなります

Let's express this optimization in pseudocode.

ではこの最適化を 擬似コードで表現してみましょう

Let n equal zero.

Nを０にします

For each pair of people in room,

部屋にいるそれぞれのペアに対して

set n = n + 2.

N = N + ２とします

Pretty simple change, right?

とても簡単な変更ですね

Rather than count people one at a time,

１人ずつ数えていくのではなく

we instead count them two at a time.

２人ずつ数えていきます

This algorithm's thus twice as fast as the last.

このアルゴリズムなら 前よりも２倍速くなります

But is it correct?

でもこれでいいでしょうか？

Let's see.

確認しましょう

Does it work if there are 2 people in the room?

部屋に２人いる場合はどうでしょう

In line 1, we initialize n to zero.

１行目でNをゼロに初期化します

For that one pair of people, we then increment n by 2.

ペアが１組いるごとにNを２増やします

And so, by this algorithm's end, n is 2,

そしてアルゴリズムが終わると Nは２で

which indeed matches the number of people in the room.

実際に 部屋にいる人の数に一致します

Suppose next that there are zero people in the room.

次に部屋に人がいない場合を考えましょう

In line 1, we initialize n to zero.

１行目でNを０に初期化します

As before, line 3 doesn't execute at all

３行目はまったく実行されません

since there aren't any pairs of people in the room,

部屋には１組も人がいませんからね

and so, n remains zero,

ですから Nは０のままで

which indeed matches the number of people in the room.

部屋にいる人の数に一致します

But what if there are 3 people in the room?

でも 部屋に３人いたらどうでしょう？

How does this algorithm fair?

アルゴリズムは正しく動くでしょうか

Let's see.

見てみましょう

In line 1, we initialize n to zero.

１行目でNを０に初期化します

For a pair of those people,

１組ごとに

we then increment n by 2,

Nを２ずつ増やします

but then what?

それから？

There isn't another full pair of people in the room,

部屋にはもう他にペアはいませんから

so line 2 no longer applies.

２行目はこれ以上適用されません

And so, by this algorithm's end,

ですから アルゴリズムは終わり

n is still 2, which isn't correct.

Nは２のままで これは間違いです

Indeed this algorithm is said to be buggy

このアルゴリズムには バグがあるといわれます

because it has a mistake.

間違いがあるからです

Let's redress with some new pseudocode.

新しい擬似コードで修正しましょう

Let n equal zero.

Nを０にします

For each pair of people in room,

部屋にいるペアごとに

set n = n + 2.

N = N + ２とします

If 1 person remains unpaired,

もしペアになってない人が１人いたら

set n = n + 1.

N = N + １とします

To solve this particular problem,

この問題を解決するために

we've introduced in line 4 a condition,

４行目に条件を導入しました

otherwise known as a branch,

これは分岐ともいわれます

that only executes if there is one person

ペアとなる人がいない １人だけの場合に実行されます

we could not pair with another.

So now, whether there's 1 or 3

これで 部屋にいる人の数が １人や３人や

or any odd number of people in the room,

どんな奇数であっても

this algorithm will now count them.

このアルゴリズムは数えることができます

Can we do even better?

もっと上手くできるでしょうか

Well, we could count in 3's or 4's or even 5's and 10's,

３、４、５や10人ずつでも 数えることもできますが

but beyond that it's going to get

それ以上になると

a little bit difficult to point.

指すのが少し難しくなりますね

At the end of the day,

要するに

whether executed by computers or humans,

実行するのがコンピュータでも人間でも

algorithms are just a set of instructions

アルゴリズムとは問題を解くための

with which to solve problems.

一連の指示にすぎません

These were just three.

アルゴリズムを３つだけ紹介しました

What problem would you solve with an algorithm?

あなたはアルゴリズムで どんな問題を解決したいですか？