What's an algorithm? - David J. Malan

Não bộ có thể xử lý các thuật toán - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Translator: Thanh Nguyen Cong Reviewer: An Nguyen Hoang

What's an algorithm?

Thuật toán là gì?

In computer science,

Trong khoa học máy tính, thuật toán là tập hợp

an algorithm is a set of instructions

for solving some problem, step-by-step.

các chỉ dẫn để giải toán từng bước.

Typically, algorithms are executed by computers,

Các thuật toán thường được máy tính xử lí,

but we humans have algorithms as well.

nhưng con người chúng ta cũng có thể dùng chúng.

For instance, how would you go about counting

Ví dụ, làm sao đếm số người

the number of people in a room?

có mặt ở trong phòng ?

Well, if you're like me,

Nếu là tôi,

you probably point at each person,

tôi sẽ chỉ vào từng người một

one at a time,

and count up from 0:

đếm : 1, 2, 3, 4 và cứ thế.

1, 2, 3, 4 and so forth.

Well, that's an algorithm.

Đó là một thuật toán.

In fact, let's try to express it

Chính quy hơn hãy thử diễn đạt bằng phương trình,

a bit more formally in pseudocode,

English-like syntax

that resembles a programming language.

dạng cú pháp giống Tiếng Anh nhưng là ngôn ngữ lập trình.

Let n equal 0.

Lấy n = 0.

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

Với mỗi người trong phòng, lập n = n+1.

How to interpret this pseudocode?

Điều đó nghĩa là gì ?

Well, line 1 declares, so to speak,

hàng 1 biểu thị

a variable called n

biến số n

and initializes its value to zero.

được gán giá trị ban đầu bằng 0.

This just means that at the beginning of our algorithm,

Nghĩa là chúng ta

the thing with which we're counting

bắt đầu thuật toán

has a value of zero.

bằng cách đếm từ 0.

After all, before we start counting,

Sau đó,

we haven't counted anything yet.

chưa đếm gì vội.

Calling this variable n is just a convention.

Quy ước gọi biến số này là n

I could have called it almost anything.

Tôi có thể gọi nó bằng bất cứ tên gì.

Now, line 2 demarks the start of loop,

Giờ hàng 2 là điểm bắt đầu của bảng mạch,

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

là một chuỗi các bước lặp lại.

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

Trong ví dụ này, các bước là

is counting people in the room.

đếm những người trong phòng.

Beneath line 2 is line 3,

Dưới hàng 2 là hàng 3,

which describes exactly how we'll go about counting.

mô tả chính xác cách đếm.

The indentation implies that it's line 3

Những nét cắt biểu thị rằng hàng thứ 3

that will repeat.

sẽ được lặp lại.

So, what the pseudocode is saying

Ngôn ngữ code nói rằng

is that after starting at zero,

sau khi bắt đầu bằng 0,

for each person in the room,

với mỗi người trong phòng

we'll increase n by 1.

chúng ta sẽ cộng thêm 1 vào n.

Now, is this algorithm correct?

Thuật toán này đã đúng chưa?

Well, let's bang on it a bit.

Hãy thử lại xem.

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

Liệu có áp dụng được trong trường hợp có 2 người trong phòng ?

Let's see.

In line 1, we initialize n to zero.

Để xem. Ở hàng 1, biến n khởi điểm = 0

For each of these two people,

Với mỗi người trong phòng

we then increment n by 1.

ta lại cộng 1 vào n.

So, in the first trip through the loop,

Vậy ở vòng đầu

we update n from zero to 1,

ta đã nâng giá trị của n từ 0 lên 1,

on the second trip through that same loop,

ở vòng hai,

we update n from 1 to 2.

từ 1 lên 2.

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

Khi thuật toán kết thúc, n=2,

which indeed matches the number of people in the room.

đúng bằng số người trong phòng.

So far, so good.

Đến đây vẫn rất suôn sẻ.

How about a corner case, though?

Còn trường hợp này thì sao ?

Suppose that there are zero people in the room,

Giả sử không có ai trong phòng,

besides me, who's doing the counting.

ngoài tôi, người đang đếm ra.

In line 1, we again initialize n to zero.

Ở hàng 1, một lần nữa giá trị ban đầu của n = 0.

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

Lần này, không thể áp dụng hàng 3

since there isn't a person in the room,

vì không còn ai trong phòng

and so, n remains zero,

thành ra, n giữ nguyên bằng 0,

which indeed matches the number of people in the room.

giá trị đúng bằng số người trong phòng.

Pretty simple, right?

Đơn giản nhỉ!

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

Nhưng đếm từng người một thì có vẻ không hiệu quả cho lắm!

Surely, we can do better!

Chắc chắn có thể làm tốt hơn!

Why not count two people at a time?

Sao không thử đếm hai người 1 lúc?

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

Thay vì đếm 1,2,3,4,5,6,7,8 , v.v

why not count

hãy thử 2,4,6,8, v.v

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

It even sounds faster, and it surely is.

Có vẻ nhanh hơn và chắc chắn là thế rồi!

Let's express this optimization in pseudocode.

Thử thể hiện bước cải tiến này bằng ngôn ngữ lập trình nhé!

Let n equal zero.

Coi n = 0.

For each pair of people in room,

Mỗi cặp trong phòng

set n = n + 2.

có giá trị n = n+2

Pretty simple change, right?

Thay đổi này cũng đơn giản mà !

Rather than count people one at a time,

Thay vì đếm từng người một

we instead count them two at a time.

ta đếm hai người một.

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

Thuật toán nhờ thế nhanh gấp đôi.

But is it correct?

Nhưng nó có chính xác không? Để xem.

Let's see.

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

Nếu có 2 người trong phòng,

In line 1, we initialize n to zero.

ở hàng 1, n có giá trị ban đầu bằng 0.

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

Có 1 cặp trong phòng nên cộng thêm 2 vào n.

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

Cuối cùng, khi thuật toán kết thúc, n = 2,

which indeed matches the number of people in the room.

trùng với số người trong phòng.

Suppose next that there are zero people in the room.

Giả sử không có ai trong phòng.

In line 1, we initialize n to zero.

Ở hàng 1, giá trị ban đầu n = 0.

As before, line 3 doesn't execute at all

Cũng như lần trước, không áp dụng được

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

cho hàng 3 vì không có cặp nào trong phòng

and so, n remains zero,

n giữ nguyên bằng 0

which indeed matches the number of people in the room.

đúng bằng số người trong phòng.

But what if there are 3 people in the room?

Nhưng nếu có 3 người trong phòng

How does this algorithm fair?

thuật toán này sẽ thực hiện thế nào?

Let's see.

Để xem!

In line 1, we initialize n to zero.

Ở hàng 1, giá trị đầu của n bằng 0.

For a pair of those people,

cứ hai người một

we then increment n by 2,

ta cộng thêm 2 vào n

but then what?

rồi sao nữa?

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

Không có đủ một cặp nữa trong phòng

so line 2 no longer applies.

nên hàng 2 không áp dụng được.

And so, by this algorithm's end,

kết thúc thuật toán,

n is still 2, which isn't correct.

n = 2, và kết quả này không đúng.

Indeed this algorithm is said to be buggy

Thuật toán này

because it has a mistake.

mắc một sai lầm.

Let's redress with some new pseudocode.

Hãy xem lại một lần nữa!

Let n equal zero.

Coi n = 0.

For each pair of people in room,

Với mỗi đôi trong phòng,

set n = n + 2.

lập n = n+2.

If 1 person remains unpaired,

Nếu 1 người lẻ ra,

set n = n + 1.

lập n = n+1.

To solve this particular problem,

Để giải quyết vấn đề này,

we've introduced in line 4 a condition,

chúng ta đưa một điều kiện vào hàng 4

otherwise known as a branch,

gọi là một nhánh,

that only executes if there is one person

chỉ áp dụng nếu có một người lẻ ra

we could not pair with another.

So now, whether there's 1 or 3

Giờ thì, nếu có 1 hay 3

or any odd number of people in the room,

hay bất kì số người lẻ nào trong phòng,

this algorithm will now count them.

thuật toán này vẫn hoạt động được.

Can we do even better?

Ta có thể làm tốt hơn không?

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

Ờ thì, ta có thể đếm 3, 4, 5 hay 10 người một lúc,

but beyond that it's going to get

nhưng quá nữa thì sẽ

a little bit difficult to point.

hơi khó đếm.

At the end of the day,

Cuối cùng,

whether executed by computers or humans,

dù là vận hành bởi máy móc hay con người,

algorithms are just a set of instructions

thuật toán cũng là tập hợp những chỉ dẫn

with which to solve problems.

để giải các bài toán.

These were just three.

Đây chỉ mới có ba bài toán thôi,

What problem would you solve with an algorithm?

bạn sẽ dùng thuật toán để giải những bài nào ?