What's an algorithm? - David J. Malan

Creierul poate rezolva algoritmi - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Traducător: Denise RQ Corector: Ariana Bleau Lugo

What's an algorithm?

Ce este un algoritm?

In computer science,

În informatică,

an algorithm is a set of instructions

un algoritm e un set de instrucţiuni

for solving some problem, step-by-step.

pentru a rezolva o problemă pas cu pas.

De obicei, algoritmii sunt executați de computere,

Typically, algorithms are executed by computers,

but we humans have algorithms as well.

dar şi noi îi folosim.

For instance, how would you go about counting

De exemplu, cum număraţi

the number of people in a room?

oamenii dintr-o cameră?

Well, if you're like me,

Dacă faci ca mine,

you probably point at each person,

arăți cu degetul fiecare persoană pe rând

one at a time,

and count up from 0:

şi numeri de la 0:

1, 2, 3, 4 and so forth.

1, 2, 3, 4 etc.

Well, that's an algorithm.

Ei bine, ăsta-i un algoritm.

In fact, let's try to express it

Hai să-l exprimăm într-un peseudocod,

a bit more formally in pseudocode,

English-like syntax

that resembles a programming language.

o sintaxă asemănătoare cu limbajul de programare.

Let n equal 0.

Îi atribuim lui N valoarea 0.

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

Pentru fiecare persoană din cameră, stabilim N = N+1.

How to interpret this pseudocode?

Cum interpretăm pseudocodul?

Well, line 1 declares, so to speak,

Linia 1 declară o variabilă numită N

a variable called n

and initializes its value to zero.

şi iniţializează valoarea sa la zero.

This just means that at the beginning of our algorithm,

Asta înseamnă că la începutul algoritmului,

the thing with which we're counting

lucrul pe care-l numărăm

has a value of zero.

are valoarea zero.

La urma urmei, înainte să începem să numărăm,

After all, before we start counting,

we haven't counted anything yet.

nu am numărat încă nimic.

Calling this variable n is just a convention.

Numele N dat variabilei e doar o convenţie.

I could have called it almost anything.

Aş fi putut-o numi oricum.

Now, line 2 demarks the start of loop,

Linia 2 indică începutul unei iterări,

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

o secvenţă de paşi care se repetă de un număr de ori.

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

În exemplul nostru, secvența constă

is counting people in the room.

în a număra oamenii din cameră.

Beneath line 2 is line 3,

Sub linia 2 este linia 3,

which describes exactly how we'll go about counting.

care descrie exact cum vom număra.

The indentation implies that it's line 3

Indentarea marchează că linia 3 se va repeta.

that will repeat.

So, what the pseudocode is saying

Pseudocodul ne spune că după ce începem cu zero,

is that after starting at zero,

for each person in the room,

pentru fiecare persoană din cameră,

we'll increase n by 1.

vom incrementa valoarea lui N cu 1.

Now, is this algorithm correct?

Este acest algorim corect?

Well, let's bang on it a bit.

Să vedem.

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

Funcţionează dacă sunt 2 oameni în cameră?

Let's see.

Să vedem.

In line 1, we initialize n to zero.

În linia 1 îi dăm lui N valoarea zero.

For each of these two people,

Pentru fiecare dintre cei doi oameni,

we then increment n by 1.

îl incrementăm pe N cu 1.

So, in the first trip through the loop,

Deci la prima trecere prin buclă,

we update n from zero to 1,

îl actualizăm pe N de la zero la 1,

on the second trip through that same loop,

la a 2-a trecere prin bucla de iterare

we update n from 1 to 2.

îl actualizăm pe N de la 1 la 2.

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

Deci la sfârşitul algoritmului, N este 2,

ceea ce corespunde cu numărul de oameni din cameră.

which indeed matches the number of people in the room.

So far, so good.

Până aici e bine.

How about a corner case, though?

Dar ce facem în cazul limită?

Suppose that there are zero people in the room,

Presupunem că există zero oameni în cameră,

besides me, who's doing the counting.

pe mine nu mă număr.

In line 1, we again initialize n to zero.

În linia 1 iniţializăm pe N la 0.

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

Deci linia 3 nu se execută

deoarece nu există nicio persoană în cameră

since there isn't a person in the room,

and so, n remains zero,

şi astfel N rămâne zero,

which indeed matches the number of people in the room.

care se potriveşte cu numărul de oameni din cameră.

Pretty simple, right?

Simplu, nu?

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

Dar numărarea oamenilor pe rând este ineficientă.

Surely, we can do better!

Se poate mai bine!

Why not count two people at a time?

De ce să nu numărăm doi dintr-odată?

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

În loc să numărăm 1, 2, 3, 4, 5, 6, 7, 8 ş.a.m.d.,

why not count

numărăm 2, 4, 6, 8 etc.

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

It even sounds faster, and it surely is.

Pare mai rapid și chiar este.

Let's express this optimization in pseudocode.

Să exprimăm această optimizare în pseudocod.

Let n equal zero.

Îi atribuim lui N valoarea 0.

For each pair of people in room,

Pentru fiecare pereche din cameră,

set n = n + 2.

îl facem pe N = N+2.

Pretty simple change, right?

Simplu, nu?

Rather than count people one at a time,

În loc să numărăm oamenii unul câte unul,

we instead count them two at a time.

numărăm doi o dată.

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

Acest algoritm e de două ori mai rapid decât primul.

But is it correct?

Dar este corect?

Let's see.

Să vedem.

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

Funcționează dacă sunt 2 oameni în cameră?

In line 1, we initialize n to zero.

În linia 2, îl iniţializăm pe N la 0.

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

Pentru acea pereche de oameni, îl incrementăm pe N cu 2.

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

Şi astfel, la sfârşitul algoritmului, N este 2,

which indeed matches the number of people in the room.

care-i într-adevăr egal cu numărul de oameni din cameră.

Suppose next that there are zero people in the room.

Presupunem acum că sunt zero oameni în cameră.

In line 1, we initialize n to zero.

În linia 1, iniţializăm pe N la 0.

As before, line 3 doesn't execute at all

Ca înainte, linia 3 nu se execută

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

deoarece nu există nicio pereche de oameni în cameră,

and so, n remains zero,

şi astfel, N rămâne 0,

which indeed matches the number of people in the room.

care se potriveşte cu realitatea din cameră.

But what if there are 3 people in the room?

Dar dacă sunt 3 oameni în cameră?

How does this algorithm fair?

Cât e de corect algoritmul?

Let's see.

Să vedem.

In line 1, we initialize n to zero.

În linia 1, iniţializăm pe N la 0.

For a pair of those people,

Pentru o pereche de oameni,

we then increment n by 2,

creştem pe N cu 2, dar apoi?

but then what?

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

Nu există altă pereche de oameni în cameră.

so line 2 no longer applies.

deci linia 2 nu se mai aplică.

And so, by this algorithm's end,

La sfârşitul acestui algoritm,

n is still 2, which isn't correct.

N este tot 2, deși nu-i corect.

Indeed this algorithm is said to be buggy

Se spune că algoritmul are un „bug”

pentru că are o greşeală.

because it has a mistake.

Let's redress with some new pseudocode.

Să-l corectămm cu un pseudocod nou.

Let n equal zero.

Îl facem pe N egal 0.

For each pair of people in room,

Pentru fiecare pereche de oameni din cameră,

set n = n + 2.

stabilim N = N+2.

If 1 person remains unpaired,

Dacă o persoană rămâne fără pereche,

set n = n + 1.

stabilim N = N+1.

To solve this particular problem,

Pentru a corecta această eroare

we've introduced in line 4 a condition,

am introdus în linia 4 o condiţie, numită ramură,

otherwise known as a branch,

that only executes if there is one person

care execută doar dacă există

we could not pair with another.

o persoană fără pereche.

So now, whether there's 1 or 3

Acum, chiar dacă există 1 sau 3

or any odd number of people in the room,

sau oricare alt număr în cameră,

this algorithm will now count them.

acest algoritm îi va număra.

Can we do even better?

Putem oare și mai bine?

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

Am putea număra din 3 în 3, 4, 5 sau 10,

but beyond that it's going to get

dar dincolo de asta

a little bit difficult to point.

e dificil de numărat cu degetul.

At the end of the day,

whether executed by computers or humans,

În final, fie că-s executați de computer fie de om,

algorithms are just a set of instructions

algoritmii sunt doar un set de instrucțiuni

with which to solve problems.

cu care se rezolvă probleme.

These were just three.

Acestea sunt doar 3.

What problem would you solve with an algorithm?

Ce problemă aţi rezolva voi cu un algoritm?