What's an algorithm? - David J. Malan

A te agyad is képes algoritmizálni - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Fordító: Tamas Csizmadia Lektor: Judit Szabo

What's an algorithm?

Mi az az algoritmus?

In computer science,

A számítástechnikában

an algorithm is a set of instructions

olyan utasítások sora, mely

for solving some problem, step-by-step.

lépésekben haladva problémákat old meg.

Typically, algorithms are executed by computers,

Ezeket rendszerint számítógépek hajtják végre,

but we humans have algorithms as well.

de mi emberek is rendelkezünk algoritmusokkal.

For instance, how would you go about counting

Például hogy számolnád meg

the number of people in a room?

az embereket egy szobában?

Well, if you're like me,

Nos, hozzám hasonlóan,

you probably point at each person,

valószínűleg rámutatnál mindenkire

one at a time,

and count up from 0:

szépen egyesével,

és összeadnád őket nullától:

1, 2, 3, 4 and so forth.

1, 2, 3, 4 és így tovább.

Well, that's an algorithm.

Ez már egy algoritmus!

In fact, let's try to express it

Fejezzük ki ezt

a bit more formally in pseudocode,

kissé formálisabban, pszeudokódban,

English-like syntax

that resembles a programming language.

mely emberi nyelv,

de hasonlít a programozási nyelvekhez.

Let n equal 0.

Legyen n = 0.

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

Minden egyes ember esetén legyen n = n + 1.

How to interpret this pseudocode?

Hogyan értelmezzük ezt?

Well, line 1 declares, so to speak,

Az 1. sor, hogy úgy mondjam deklarálja

a variable called n

az n nevű változót

and initializes its value to zero.

és beállítja az értékét nullára.

This just means that at the beginning of our algorithm,

Ez annyit tesz, hogy az algoritmus elején

the thing with which we're counting

a számítandó dolog értéke

has a value of zero.

nullával kezdődik.

After all, before we start counting,

Végül is a számítás előtt

we haven't counted anything yet.

nem is számoltunk meg semmit.

Calling this variable n is just a convention.

Csak megszokásból hívom n-nek ezt a változót.

I could have called it almost anything.

Gyakorlatilag bárhogy nevezhetném.

Now, line 2 demarks the start of loop,

Namost, a 2. sor egy ciklus elejét jelzi,

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

lépések sorozatát, melyek bizonyos számmal ismétlődnek.

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

Példánkban ez a lépés

is counting people in the room.

az emberek számlálása a szobában.

Beneath line 2 is line 3,

A 2. sor alatt van a 3.,

which describes exactly how we'll go about counting.

mely pontosan megmondja, hogy haladjunk tovább.

The indentation implies that it's line 3

A behúzás itt azt jelenti, hogy a harmadik sor

that will repeat.

fog ismétlődni.

So, what the pseudocode is saying

Tehát a pszeudókód azt fejezi ki,

is that after starting at zero,

hogy miután nullával kezdtünk,

for each person in the room,

minden egyes személlyel

we'll increase n by 1.

növeljük n-t egyel.

Now, is this algorithm correct?

Helyes ez az algoritmus?

Well, let's bang on it a bit.

Fussunk át rajta gyorsan!

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

Helyesen működik, ha 2 ember van a szobában?

Let's see.

Lássuk!

In line 1, we initialize n to zero.

Az 1. sorban n-t beállítjuk nullára.

For each of these two people,

Mindkét emberünk esetén

we then increment n by 1.

aztán növeljük n-t egyel.

So, in the first trip through the loop,

Tehát a ciklusunk első körében

we update n from zero to 1,

felülírjuk n-t nulláról egyre,

on the second trip through that same loop,

majd ezen ciklus második körében

we update n from 1 to 2.

felülírjuk n értékét 1-ről 2-re.

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

Az algoritmusnak vége, n értéke pedig 2,

which indeed matches the number of people in the room.

ami megegyezik a szobában lévők számával.

So far, so good.

Eddig jók vagyunk.

How about a corner case, though?

Mi a helyzet a különleges esetekkel?

Suppose that there are zero people in the room,

Tegyük fel, hogy 0 ember van a szobában,

besides me, who's doing the counting.

leszámítva engem, aki a számolást végzi.

In line 1, we again initialize n to zero.

Az 1. sorban ismét nullára állítjuk n-t.

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

Ebben az esetben azonban a 3. sor le sem fut,

since there isn't a person in the room,

mivel nincs senki az egész szobában,

and so, n remains zero,

így hát n értéke 0 marad,

which indeed matches the number of people in the room.

ami ismét egyezik a szobában lévők számával.

Pretty simple, right?

Egyszerű, igaz?

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

Ám egyesével számolni az embereket nem túl hatékony, igaz?

Surely, we can do better!

Biztosan megy ez jobban is!

Why not count two people at a time?

Miért nem számoljuk őket kettesével?

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

Miért számolunk így: 1, 2, 3, 4, 5, 6, 7, 8, és így tovább

why not count

ahelyett, hogy

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

2, 4, 6, 8, és így tovább?

It even sounds faster, and it surely is.

Már eleve rövidebben hangzik, és tényleg az.

Let's express this optimization in pseudocode.

Fejezzük ki ezt az optimalizálást pszeudokódban!

Let n equal zero.

Legyen n értéke nulla.

For each pair of people in room,

Minden szobában lévő pár esetén

set n = n + 2.

legyen n = n + 2.

Pretty simple change, right?

Nem túl nagy változtatás, igaz?

Rather than count people one at a time,

Ahelyett, hogy egyesével számolnánk őket,

we instead count them two at a time.

két embert számolunk meg egy időben.

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

Ez az algoritmus kétszer olyan gyors, mint az előző.

But is it correct?

De vajon helyes-e?

Let's see.

Lássuk!

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

Helyesen működik, ha 2 ember van a szobában?

In line 1, we initialize n to zero.

Az 1. sorban n értékét nullára állítjuk.

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

Van egyetlen párunk, így növeljük n értékét kettővel.

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

Ezzel az algoritmus a végéhez is ért, és n értéke 2,

which indeed matches the number of people in the room.

amely megegyezik a szobában lévő emberek számával.

Suppose next that there are zero people in the room.

Most legyen 0 ember a szobában.

In line 1, we initialize n to zero.

Az első sorban beállítjuk n értékét nullára.

As before, line 3 doesn't execute at all

S mint korábban, a 3. sor most sem fut le,

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

mivel hogy nincs egyeltenegy pár sem a szobában,

and so, n remains zero,

ezért n értéke nulla marad,

which indeed matches the number of people in the room.

mely ismét megegyezik a szobában lévő emberek számával.

But what if there are 3 people in the room?

Ám mi történik, ha három ember van a szobában?

How does this algorithm fair?

Hogy muzsikál az algoritmusunk?

Let's see.

Lássuk!

In line 1, we initialize n to zero.

Az első sorban beállítjuk n-t nullára.

For a pair of those people,

Az egy pár ember kapcsán

we then increment n by 2,

növeljük n értékét 2-vel,

but then what?

ám ezután?

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

Nincs annyi ember, hogy kitegyen egy párt,

so line 2 no longer applies.

ezért a 2. sor már nem fut le.

And so, by this algorithm's end,

Ezzel az algoritmus a végéhez ért,

n is still 2, which isn't correct.

n még mindig 2, ami helytelen.

Indeed this algorithm is said to be buggy

Ezt az algoritmust hibásnak tekintjük,

mert tartalmaz egy tévedést.

because it has a mistake.

Let's redress with some new pseudocode.

Szabjuk át kicsit újabb pszeudokóddal!

Let n equal zero.

Legyen n értéke nulla.

For each pair of people in room,

Minden pár esetén a szobában,

set n = n + 2.

legyen n = n + 2.

If 1 person remains unpaired,

Ha egy ember pár nélkül marad,

set n = n + 1.

legyen n = n + 1.

To solve this particular problem,

Hogy megoldjuk ezt a problémát,

we've introduced in line 4 a condition,

a 4. sorban bevezettünk egy feltételt,

otherwise known as a branch,

másnéven elágazást,

that only executes if there is one person

mely akkor fut csak le, ha marad egy ember,

we could not pair with another.

aki nem talál párt magának.

So now, whether there's 1 or 3

Tehát akár 1, vagy 3,

or any odd number of people in the room,

vagy más páratlan számú ember van a szobában,

this algorithm will now count them.

ez az algoritmus meg tudja számolni őket.

Can we do even better?

Ezt is felülmúlhatjuk?

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

Ami azt illeti, számolhatunk egyszerre 3, 4, 5, vagy 10 embert,

but beyond that it's going to get

ám ezen túl már kicsit macerás

a little bit difficult to point.

lenne rájuk mutogatni.

At the end of the day,

Végezetül pedig,

whether executed by computers or humans,

akár számítógép, vagy ember hajtja végre,

algorithms are just a set of instructions

az algoritmus csupán utasítások sora,

with which to solve problems.

mellyel problémákat oldunk meg.

These were just three.

Ez csupán három volt.

What problem would you solve with an algorithm?

Te milyen problémát oldanál meg egy algoritmussal?