What's an algorithm? - David J. Malan

Мозъкът ви може да решава алгоритми - Дейвид Д. Малан

Translator: Andrea McDonough Reviewer: Jessica Ruby

Translator: Anton Hikov Reviewer: Yavor Ivanov

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:

и ще броите от 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,

Ами, ред 1 декларира, така да се каже,

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,

Сега, ред 2 обозначава началото на цикъл,

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,

Под ред 2 е ред 3,

which describes exactly how we'll go about counting.

който описва точно как ще проведем броенето.

The indentation implies that it's line 3

Абзацът предполага, че ред 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.

В ред 1, ние инициализираме 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.

В ред 1, отново инициализираме n с нула.

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

Този път, обаче, ред 3 не се изпълнява въобще,

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.

В ред 1, ние инициализираме 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.

В ред 1, ние инициализираме n с нула.

As before, line 3 doesn't execute at all

Както преди, ред 3 не се изпълнява въобще,

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.

В ред 1, ние инициализираме 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.

така ред 2 вече не се прилага.

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,

Ако 1 човек остане сам, без двойка,

set n = n + 1.

задайте n = n + 1.

To solve this particular problem,

За решаването на този проблем,

we've introduced in line 4 a condition,

ние въведохме в ред 4 условие,

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,

Ами, можем да броим по 3-ки или 4-ки или дори 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?

Какви проблеми бихте решили с алгоритъм?