What's an algorithm? - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Translator: Thitirat Kongkeo Reviewer: Sakunphat Jirawuthitanant

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 จากศูนย์ เป็น 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?

ปัญหาอะไรที่คุณจะแก้ด้วยอัลกอริทึม