What's an algorithm? - David J. Malan

Твой мозг может использовать алгоритмы — Дэвид Мелен

Translator: Andrea McDonough Reviewer: Jessica Ruby

Переводчик: Jane Goryanaya Редактор: Aygul Zagidullina

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.

1,2,3,4 и так далее.

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 равняется 0.

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

Для каждого человека в комнате установим N=N+1.

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.

Я мог бы назвать её как хочу.

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 на 1.

Now, is this algorithm correct?

Правильно ли работает этот алгоритм?

Well, let's bang on it a bit.

Ну что же, проверим.

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

Работает ли алгоритм, когда в комнате 2 человека?

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 на 1.

So, in the first trip through the loop,

При первом обходе цикла

we update n from zero to 1,

значение N увеличивается с 0 до 1.

on the second trip through that same loop,

При втором обходе

we update n from 1 to 2.

N увеличивается с 1 до 2.

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

В конце алгоритма N равняется 2,

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 значение 1.

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,

Вместо 1,2,3,4,5,6,7,8 и так далее,

why not count

почему бы не считать

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

2,4,6,8 и так далее?

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+2.

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?

Работает ли он, если в комнате 2 человека?

In line 1, we initialize n to zero.

В первой строчке, присваиваем N значение ноль.

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

Для двух людей увеличиваем N до 2.

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

В конце алгоритма N равняется 2,

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?

Но что делать, если в комнате 3 человека?

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 до 2.

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 до сих пор равняется 2, что неверно.

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+2.

If 1 person remains unpaired,

Если остаётся один человек,

set n = n + 1.

тогда N=N+1.

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

Вот сейчас, даже если в комнате 1 или 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,

Мы можем считать по 2, 3 или даже по 5 или по 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?

А какие задачи ты бы решил с помощью алгоритма?