What's an algorithm? - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Μετάφραση: Maria K. Επιμέλεια: Lucas Kaimaras

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.

Έστω ότι το ν ισούται με 0.

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

Για κάθε άνθρωπο στο δωμάτιο, θέστε ν = ν + 1.

How to interpret this pseudocode?

Πώς ερμηνεύεται αυτός ο ψευδοκώδικας;

Well, line 1 declares, so to speak,

Η γραμμή 1 υποδηλώνει, ας το πούμε έτσι,

a variable called n

μια μεταβλητή που ονομάζεται ν και έχει αρχική τιμή 0.

and initializes its value to zero.

This just means that at the beginning of our algorithm,

Αυτό σημαίνει με λίγα λόγια ότι στην αρχή του αλγορίθμου μας,

the thing with which we're counting

αυτό για το οποίο μετράμε έχει τιμή 0.

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.

Η ονομασία της μεταβλητής ν είναι απλά μια σύμβαση.

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,

which describes exactly how we'll go about counting.

Κάτω από τη γραμμή 2 είναι η γραμμή 3 που περιγράφει πώς θα μετρήσουμε.

The indentation implies that it's line 3

Η εσοχή υποδηλώνει ότι η γραμμή 3 θα επαναληφθεί.

that will repeat.

So, what the pseudocode is saying

Οπότε, στην ουσία ο ψευδοκώδικας λέει ότι αφότου αρχίσουμε από το 0,

is that after starting at zero,

for each person in the room,

για κάθε άνθρωπο στο δωμάτιο, θα αυξάνουμε το ν κατά ένα.

we'll increase n by 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?

Λειτουργεί αν υπάρχουν δύο άνθρωποι στο δωμάτιο;

Let's see.

Ας δούμε.

In line 1, we initialize n to zero.

Στη γραμμή 1, θέτουμε αρχικά το ν στο 0.

For each of these two people,

Για κάθε άνθρωπο αυξάνουμε το ν κατά ένα.

we then increment n by 1.

So, in the first trip through the loop,

Οπότε, στην πρώτη φάση της ακολουθίας, ανανεώνουμε το ν από 0 σε 1,

we update n from zero to 1,

on the second trip through that same loop,

στη δεύτερη φάση ανανεώνουμε το ν από 1 σε 2.

we update n from 1 to 2.

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

Έτσι, μέχρι το τέλος του αλγορίθμου,

το ν είναι 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, ρυθμίζουμε το ν στο 0.

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,

Οπότε, το ν παραμένει 0,

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 και ούτω καθεξής;

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.

Έστω ότι το ν ισούται με 0.

For each pair of people in room,

Για κάθε ζευγάρι ανθρώπων στο δωμάτιο, θέτουμε ν = ν + 2.

set 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?

Πιάνει αν υπάρχουν δύο άνθρωποι στο δωμάτιο;

In line 1, we initialize n to zero.

Στη γραμμή 1, θέτουμε αρχικά το ν ως 0.

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

Για αυτό το ένα ζευγάρι ανθρώπων, αυξάνουμε το ν κατά δύο.

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

Έτσι, με το τέλος του αλγορίθμου, το ν ισούται με 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, θέτουμε αρχικά το ν σε 0.

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,

Οπότε, το ν παραμένει 0,

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.

Στη γραμμή 1, θέτουμε αρχικά το ν σε 0.

For a pair of those people,

Για ένα ζευγάρι ανθρώπων αυξάνουμε το ν κατά δύο.

we then increment n by 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,

Έτσι, με το τέλος αυτού του αλγορίθμου, το ν παραμένει 2, που είναι λάθος.

n is still 2, which isn't correct.

Indeed this algorithm is said to be buggy

Αυτός ο αλγόριθμος είναι προβληματικός, επειδή έχει ένα λάθος.

because it has a mistake.

Let's redress with some new pseudocode.

Ας το επανορθώσουμε με έναν νέο ψευδοκώδικα.

Let n equal zero.

Έστω ότι το ν ισούται με 0.

For each pair of people in room,

Για κάθε ζευγάρι ανθρώπων στο δωμάτιο, θέτουμε ν = ν + 2.

set n = n + 2.

If 1 person remains unpaired,

Αν ένας άνθρωπος μείνει χωρίς «ταίρι», θέτουμε ν = ν + 1.

set 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

Οπότε τώρα, είτε είναι ένας ή τρεις,

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,

Θα μπορούσαμε να μετρήσουμε ανά τρία ή τέσσερα ή ανά πέντε και δέκα,

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?

Τι πρόβλημα θα λύνατε εσείς με έναν αλγόριθμο;