What is computation? คำถามนี้เป็นหัวใจของวิทยาการคอมพิวเตอร์ บทนี้ให้คำตอบอย่างคร่าว ๆ และเชื่อมแนวคิดเรื่อง computation (การคำนวณ) กับแนวคิดที่เกี่ยวข้อง โดยเฉพาะผมจะอธิบายความสัมพันธ์ระหว่าง computation กับการแก้ปัญหาและ algorithm (อัลกอริทึม) เพื่อจุดประสงค์นี้ ผมจะอธิบายสองมิติที่เสริมกันของ computation: มันทำอะไร และมันคืออะไร

มุมมองแรก computation solves problems เน้นว่าปัญหาใด ๆ สามารถแก้ได้ด้วย computation เมื่อมันถูกแทนค่าอย่างเหมาะสมและถูกแบ่งออกเป็นปัญาย่อย ๆ วิธีนี้ไม่เพียงแต่สะท้อนผลกระทบอันใหญ่หลวงของ computer science ในหลายด้านของสังคม แต่ยังอธิบายด้วยว่าทำไม computation จึงเป็นส่วนสำคัญของกิจกรรมมนุษย์หลากหลายรูปแบบ แม้ไม่จำเป็นต้องอาศัยเครื่องคอมพิวเตอร์โดยตรง

อย่างไรก็ตาม มุมมองการแก้ปัญหาไม่ได้ครอบคลุมแง่มุมสำคัญบางอย่างของ computation หากมองความแตกต่างระหว่าง computation กับการแก้ปัญหาอย่างใกล้ชิด จะเห็นมุมมองที่สองว่า computation is algorithm execution. algorithm เป็นคำอธิบายที่ชัดเจนของการทำงานเชิงคำนวณ ทำให้สามารถทำให้เป็นอัตโนมัติและวิเคราะห์ได้ มุมมองนี้มอง computation เป็นกระบวนการที่ประกอบด้วยหลายขั้นตอน ซึ่งช่วยอธิบายได้ว่ามันมีประสิทธิผลในการแก้ปัญหาอย่างไรและเพราะเหตุใด

กุญแจในการใช้ประโยชน์จาก computation คือการจัดกลุ่มปัญหาที่คล้ายกันเป็นคลาสหนึ่ง และออกแบบ algorithm ที่สามารถแก้ปัญหาแต่ละข้อในคลาสนั้น สิ่งนี้ทำให้ algorithm คล้ายกับทักษะ เช่น ทักษะการอบเค้กหรือการซ่อมรถ ที่สามารถเรียกใช้งานได้ในเวลาต่าง ๆ และนำไปใช้ซ้ำเพื่อแก้กรณีต่าง ๆ ของปัญหาชนิดเดียวกัน ทักษะยังสามารถสอนและแบ่งปันให้ผู้อื่นได้ ทำให้มีผลกระทบกว้างขึ้น ในทำนองเดียวกัน เราสามารถรัน algorithm ซ้ำ ๆ กับตัวอย่างปัญหาที่ต่างกัน และการรันแต่ละครั้งจะสร้าง computation ที่แก้ปัญหาตามที่ตั้งไว้

Dividing Problems into Triviality (การแบ่งปัญหาให้เป็นปัญหาเล็กที่แก้ได้)

เริ่มจากมุมมองแรก ให้ถือว่า computation เป็นกระบวนการที่แก้ปัญหาเฉพาะตัว ตัวอย่างที่ใช้คือเรื่องคุ้นเคยของ Hansel และ Gretel ที่ถูกพ่อแม่ทิ้งไว้ในป่า มาดูไอเดียฉลาดของ Hansel ที่ทำให้เขาและ Gretel กลับบ้านได้หลังจากถูกทิ้งไว้ เรื่องราวเกิดขึ้นในบริบทของความอดอยาก เมื่อแม่เลี้ยงของพวกเขาชวนให้พ่อพาเด็ก ๆ เข้าไปในป่าแล้วทิ้ง เพื่อที่พ่อแม่จะได้รอดพ้น Hansel ได้ยินบทสนทนาของพ่อแม่ จึงออกไปข้างนอกในคืนนั้นและเก็บกรวดเล็ก ๆ ใส่กระเป๋าหลายกำ ในวันรุ่งขึ้น ขณะเดินเข้าไปในป่า เขาทิ้งกรวดเป็นเครื่องหมายตามทาง เมื่อตอนที่พ่อแม่จากไป เด็กทั้งสองรอจนมืดและกรวดเริ่มส่องประกายในแสงจันทร์ แล้วจึงตามกรวดจนกลับถึงบ้าน

เรื่องราวยังไม่จบเพียงเท่านี้ แต่ตอนนี้ให้ตัวอย่างชัดเจนเกี่ยวกับการแก้ปัญหาโดยใช้ computation ปัญหาที่ต้องแก้คือการอยู่รอด—ชัดเจนว่าสำคัญกว่าปัญหาเรื่องการตื่นขึ้น—และปรากฏเป็นงานของการเคลื่อนจากตำแหน่งในป่าไปยังบ้านของ Hansel และ Gretel นี่เป็นปัญหาไม่ง่ายโดยเฉพาะเพราะไม่สามารถแก้ได้ในขั้นตอนเดียว ปัญหาที่ซับซ้อนเกินกว่าจะจัดการในขั้นตอนเดียวจึงต้องถูกแบ่งเป็นปัญาย่อยที่แก้ง่ายและผลของแต่ละปัญย่อยสามารถรวมกันเพื่อให้ได้คำตอบของปัญหาหลัก

ปัญหาการหาทางออกจากป่าสามารถแบ่งได้โดยการระบุลำดับตำแหน่งกึ่งกลางที่อยู่ใกล้กันพอที่คนจะเคลื่อนไหวระหว่างกันได้ง่าย ตำแหน่งเหล่านี้สร้างเส้นทางออกจากป่ากลับไปยังบ้านของ Hansel และ Gretel และการเคลื่อนย้ายทีละตำแหน่งจากตำแหน่งหนึ่งไปยังอีกตำแหน่งหนึ่งทำได้ง่าย เมื่อรวมกันแล้วจะได้การเคลื่อนที่จากจุดเริ่มต้นในป่าไปสู่บ้าน การเคลื่อนที่ลักษณะนี้แก้ปัญหาการอยู่รอดของ Hansel และ Gretel ในเชิงระบบ การแก้ปัญหาอย่างเป็นระบบคือคุณลักษณะสำคัญอย่างหนึ่งของ computation

ตามที่ตัวอย่างแสดง computation มักประกอบด้วยหลายขั้นตอน ไม่ใช่แค่หนึ่งขั้นตอน แต่ละขั้นตอนแก้ปัญหาย่อยและเปลี่ยนสถานการณ์ของปัญหาเล็กน้อย ตัวอย่างเช่น การเคลื่อนของ Hansel และ Gretel ไปยังกรวดลูกถัดไปเป็นก้าวหนึ่งใน computation ที่เปลี่ยนตำแหน่งของพวกเขาในป่า ซึ่งสอดคล้องกับการแก้ปัญหาย่อยของการไปยังเป้าหมายถัดไปบนเส้นทางกลับบ้าน ในกรณีส่วนใหญ่แต่ละก้าวจะพา computation เข้าใกล้คำตอบมากขึ้น แต่ไม่จำเป็นว่าทุกก้าวจะเป็นเช่นนั้น เฉพาะเมื่อรวมทุกก้าวเข้าด้วยกันแล้วจึงได้คำตอบ ในเรื่องราว ตำแหน่งแต่ละตำแหน่งโดยทั่วไปจะใกล้บ้านขึ้น แต่เส้นทางอาจไม่ตรง บางกรวดอาจทำให้เกิดทางอ้อม เช่น เพื่อเลี่ยงอุปสรรคหรือข้ามแม่น้ำด้วยสะพาน แต่สิ่งนี้ไม่เปลี่ยนผลของการเคลื่อนที่โดยรวม

บทเรียนสำคัญคือคำตอบได้มาจากการแบ่งปัญหาเป็นส่วนย่อยอย่างเป็นระบบ แม้ว่าการแยกย่อยจะเป็นกลยุทธ์สำคัญในการหาคำตอบ แต่โดยลำพังมันอาจไม่เพียงพอ และคำตอบอาจขึ้นกับสิ่งเสริมเพิ่มเติม—ในกรณีของ Hansel และ Gretel คือกรวดที่ใช้เป็นเครื่องหมาย

No Computation without Representation (ไม่มี computation หากปราศจากการแทนความหมาย)

ถ้า computation ประกอบด้วยหลายขั้นตอน แต่ละขั้นตอนทำอะไรจริง ๆ และขั้นตอนทั้งหมดร่วมกันจะให้คำตอบได้อย่างไร เพื่อให้เกิดผลรวม แต่ละขั้นตอนต้องมีผลที่ขั้นตอนถัดไปสามารถสร้างต่อได้ ดังนั้นผลสะสมของทุกขั้นตอนจึงต้องนำไปสู่การแก้ปัญหา ในเรื่องราว ผลของแต่ละก้าวคือการเปลี่ยนตำแหน่งของ Hansel และ Gretel และปัญหาได้รับการแก้เมื่อพวกเขาไปถึงบ้าน โดยทั่วไปแล้ว ก้าวหนึ่งใน computation อาจส่งผลต่อสิ่งใดก็ได้ ไม่ว่าจะเป็นวัตถุทางกายภาพหรือเอนทิตีทางคณิตศาสตร์ในเชิงนามธรรม

เพื่อแก้ปัญหาจำเป็นที่ computation จะต้องจัดการกับ representation (การแทนความหมาย) ของบางสิ่งที่มีความหมายในโลกจริง ตำแหน่งของ Hansel และ Gretel แสดงหนึ่งในสองสถานะที่เป็นไปได้: ตำแหน่งต่าง ๆ ในป่าแสดงสถานะปัญหาคืออันตรายหรือการสูญเสีย ขณะที่บ้านของพวกเขาแสดงสถานะคำตอบคือความปลอดภัยและการรอดชีวิต นี่คือเหตุผลที่ computation ที่พา Hansel และ Gretel กลับบ้านจึงแก้ปัญหา—มันย้ายพวกเขาจากอันตรายไปสู่ความปลอดภัย ในทางตรงกันข้าม computation ที่พาไปจากที่หนึ่งในป่าไปยังอีกที่หนึ่งโดยไม่มีความหมายจะไม่บรรลุเป้าหมายนั้น

ตัวอย่างนี้มีระดับของการแทนความหมายอีกชั้นหนึ่ง เนื่องจาก computation ที่กำหนดด้วยการเคลื่อนระหว่างตำแหน่งดำเนินโดย Hansel และ Gretel ตำแหน่งจึงต้องเป็นที่รู้จักสำหรับพวกเขา ซึ่งเป็นเหตุผลที่ Hansel ทิ้งกรวดไว้ตามทาง กรวดเป็นตัวแทนของตำแหน่งในรูปแบบที่ทำให้ "คอมพิวเตอร์" — ในที่นี้หมายถึง Hansel และ Gretel — สามารถปฏิบัติขั้นตอนของ computation ได้จริง มักมีหลายชั้นของการแทนความหมาย ในกรณีนี้มีชั้นหนึ่งที่กำหนดปัญหา (ตำแหน่ง) และอีกชั้นหนึ่งที่ทำให้การคำนวณเป็นไปได้ (กรวด) นอกจากนี้ กรวดทั้งหมดรวมกันยังเป็นอีกระดับของการแทนความหมาย เพราะพวกมันแทนเส้นทางออกจากป่ากลับบ้าน สรุปการแทนความหมายเหล่านี้มีอยู่ใน table 1.1.

Figure 1.1 การคำนวณเป็นกระบวนการเพื่อแก้ปัญหาเฉพาะ โดยทั่วไป computation ประกอบด้วยหลายขั้นตอน เริ่มจากการมี representation ของปัญหา แต่ละก้าวจะแปลง representation นั้นจนกว่าจะได้คำตอบ Hansel และ Gretel แก้ปัญหาการรอดชีวิตผ่านกระบวนการเปลี่ยนตำแหน่งทีละก้าวและทีละกรวดจากภายในป่าไปยังบ้านของพวกเขา

Figure 1.1 สรุปมุมมองการแก้ปัญหาโดย computation; มันแสดงการหาทางของ Hansel และ Gretel เป็นตัวอย่างของมุมมองที่ว่า computation จัดการ representation เป็นลำดับขั้น ในปัญหาเรื่องการตื่นนอนก็พบการแทนความหมายเช่น ตำแหน่ง (อยู่ในเตียง/ออกจากเตียง) และนาฬิกาปลุกที่แทนเวลา Representation สามารถมีรูปแบบต่าง ๆ มากมาย และจะถูกอธิบายรายละเอียดเพิ่มเติมใน chapter 3

Table 1.1

Computation Representation			Problem Representation
Object	Represents		Concept	Represents
One pebble	Location in forest / Home		Location in forest / Home	Danger / Safety
All pebbles	Path out of forest		Path out of forest	Problem Solution

Beyond Problem Solving (เกินกว่าการแก้ปัญหา)

การมอง computation เป็นกระบวนการแก้ปัญหาบอกวัตถุประสงค์ของ computation แต่ไม่อธิบายว่า computation แท้จริงแล้วคืออะไร นอกจากนี้ มุมมองการแก้ปัญหายังมีข้อจำกัด เพราะไม่ใช่การแก้ปัญหาโดยทุกวิธีจะเป็น computation

ตามที่แสดงใน figure 1.2 มีทั้ง computation และการแก้ปัญหา แม้ว่าทั้งสองมักจะทับซ้อนกัน แต่บาง computation ก็ไม่ได้แก้ปัญหา และบางการแก้ปัญหาก็ไม่ได้ทำผ่าน computation หนังสือเล่มนี้เน้นที่จุดตัดของ computation และการแก้ปัญหา เพื่อความชัดเจน ผมพิจารณาตัวอย่างกรณีอื่น ๆ ที่อยู่ในสองชุดที่เหลือ

สำหรับกรณีแรก ลองนึกถึง computation ที่เป็นการตามกรวดจากที่หนึ่งไปอีกที่หนึ่งภายในป่า ขั้นตอนของกระบวนการนี้โดยพื้นฐานแล้วเหมือนกับในเรื่องเดิม แต่การเปลี่ยนตำแหน่งที่เกิดขึ้นอาจไม่แก้ปัญหาการอยู่รอดของ Hansel และ Gretel ได้ ในตัวอย่างที่รุนแรงกว่า ลองจินตนาการว่ากรวดจัดเรียงเป็นวงจร ซึ่งหมายความว่า computation ที่เกิดขึ้นไม่ได้บรรลุอะไร เพราะตำแหน่งเริ่มต้นและตำแหน่งสุดท้ายเหมือนกัน โดยสรุป computation ไม่มีผลสะสม

กระบวนการที่ดูเหมือนไม่มีความหมายยังถือว่าเป็น computation ได้ แต่อาจไม่ถูกมองว่าเป็นการแก้ปัญหา กรณีนี้ไม่สำคัญมากนักเพราะเราสามารถผูกความหมายขึ้นกับ representation ที่ computation ทำงานอยู่ได้เสมอ ดังนั้นอาจกล่าวได้ว่า computation ทุกตัวสามารถถูกมองว่าเป็นการแก้ปัญหา ขึ้นอยู่กับความหมายที่ผูกไว้กับ representation ตัวอย่างเช่น การเดินเป็นวงในป่าอาจไม่มีประโยชน์สำหรับ Hansel และ Gretel แต่สำหรับนักวิ่งมันอาจเป็นการแก้ปัญหาการออกกำลังกาย ดังนั้นว่าการ computation ใดจะแก้ปัญหาหรือไม่นั้นขึ้นกับมุมมองหรือ utility ของการ computation ในทุกกรณี การให้สถานะว่าการ computation นั้นเป็นการแก้ปัญหาหรือไม่ ไม่ได้เปลี่ยนแก่นแท้ของ computation

สถานการณ์ต่างกันชัดเจนสำหรับการแก้ปัญหาแบบไม่ใช่ computation ซึ่งให้เกณฑ์เพิ่มเติมสำหรับการนิยาม computation ใน figure 1.2 มีการกล่าวถึงสองเกณฑ์ซึ่งทั้งคู่เกี่ยวข้องกันอย่างใกล้ชิด ประการแรก หากปัญหาได้รับการแก้แบบฉาบฉวยโดยไม่มีวิธีการที่กำหนด มันไม่ถือเป็น computation อีกนัยหนึ่ง computation ต้องเป็นระบบ เราพบตัวอย่างหลายกรณีของการแก้ปัญหาแบบไม่ใช่ computation ในเรื่องนี้ หนึ่งตัวอย่างคือเมื่อ Hansel และ Gretelถูกจับโดยแม่มดที่พยายามทำให้ Hansel อ้วนขึ้นเพื่อจะกินเขา แม่มดประเมินน้ำหนักของ Hansel โดยการจับนิ้ว Hansel จึงเอาเบาะเล็ก ๆ (bone) มาแทนนิ้ว Hansel นี่ไม่ใช่ผลของ computation เชิงระบบ แต่มันแก้ปัญหาได้—มันผ่อนผันการถูกกินของ Hansel

Figure 1.2 การแยกระหว่างการแก้ปัญหากับ computation การ computation ที่ผลลัพธ์ไม่มีความหมายในโลกจริงจะไม่แก้ปัญหาใด ๆ การแก้ปัญหาแบบฉาบฉวยที่ไม่สามารถทำซ้ำได้ไม่ถือเป็น computation.

ตัวอย่างอื่นของการแก้ปัญหาแบบไม่ใช่ computation เกิดขึ้นทันทีหลังจาก Hansel และ Gretel กลับบ้าน พ่อแม่วางแผนจะพาพวกเขาเข้าไปในป่าอีกในวันถัดไป แต่ครั้งนี้แม่เลี้ยงล็อกประตูในคืนก่อนเพื่อป้องกันไม่ให้ Hansel เก็บกรวด ปัญหาคือตอนนี้ Hansel เข้าถึงกรวดที่ช่วยให้เขากลับบ้านได้ในครั้งแรกไม่ได้ ทางออกของเขาคือหาทางเลือกโดยใช้เศษขนมปัง ข้อสำคัญที่นี่คือวิธีที่ Hansel คิดวิธีนี้—เขามีไอเดีย ความคิดสร้างสรรค์ การแก้ปัญหาที่มาจากการมีไอเดียแบบ "eureka" นั้นโดยทั่วไปเป็นเรื่องยากมาก หากไม่ใช่เป็นไปไม่ได้ที่ได้มาด้วยกระบวนการเชิงระบบผ่าน computation เพราะต้องการการให้เหตุผลในระดับละเอียดเกี่ยวกับวัตถุและคุณสมบัติของมัน

เมื่อพระจันทร์ขึ้น พวกเขาออกเดิน แต่ไม่พบเศษขนมปังเลย เพราะนกนับพันที่บินไปมาในป่าและทุ่งได้เก็บมันไปหมดแล้ว.

เนื่องจากเศษขนมปังหายไป Hansel และ Gretel จึงหาเส้นทางกลับบ้านไม่ได้ และเรื่องราวดำเนินต่อไป

อย่างไรก็ตาม ลองสมมติว่า Hansel และ Gretel สามารถหาทางกลับบ้านได้อีกครั้ง และพ่อแม่พยายามจะทิ้งพวกเขาอีกครั้ง Hansel และ Gretel คงต้องคิดหาวิธีใหม่ในการทำเครื่องหมายทางกลับบ้าน พวกเขาอาจหาสิ่งอื่นมาทิ้งตามทาง หรืออาจลองทำเครื่องหมายที่ต้นไม้หรือพุ่มไม้ ไม่ว่าจะเป็นวิธีใด วิธีแก้นั้นมาจากการคิดและมีไอเดียสร้างสรรค์ ไม่ใช่จากการประยุกต์วิธีการเชิงระบบ นี่ชี้ให้เห็นอีกเกณฑ์หนึ่งของ computation คือความสามารถในการทำซ้ำและแก้ปัญหาซ้ำ ๆ ได้หลายกรณี วิธีการแก้ปัญหาเส้นทางโดยตามกรวดแตกต่างตรงที่สามารถนำไปใช้ซ้ำได้กับการวางกรวดในตำแหน่งต่าง ๆ กัน

สรุปแล้ว แม้มุมมองการแก้ปัญจะแสดงว่า computation เป็นกระบวนการที่เป็นระบบและแบ่งแยกได้ แต่มันยังไม่เพียงพอที่จะให้ภาพที่ครอบคลุมและชัดเจนของ computation การมอง computation เป็นการแก้ปัญหาแสดงให้เห็นวิธีการนำ computation ไปใช้ในสถานการณ์ต่าง ๆ และแสดงความสำคัญของมัน แต่ก็ละเลยคุณลักษณะสำคัญอื่น ๆ ที่อธิบายว่าทำไม computation จึงทำงานได้และทำไมมันถูกนำไปใช้ได้อย่างกว้างขวาง

When Problems Reappear (เมื่อปัญหาเกิดซ้ำ)

Hansel และ Gretel เผชิญกับปัญหาการหาทางกลับบ้านถึงสองครั้ง ยกเว้นปัญหาเชิงปฏิบัติจากการขาดกรวด ครั้งที่สองสามารถแก้ได้เช่นเดียวกับครั้งแรก โดยการตามชุดของเครื่องหมาย ซึ่งไม่ใช่เรื่องน่าแปลกใจ เพราะ Hansel และ Gretel เพียงใช้วิธีทั่วไปในการหาทาง วิธีการเช่นนี้เรียกว่า algorithm.

มาดู algorithm ที่ Hansel และ Gretel ใช้หาเส้นทางกลับบ้านกัน วิธีการที่แน่นอนไม่ได้อธิบายอย่างละเอียดในนิทานต้นฉบับ สิ่งที่บอกเรามีเพียงดังนี้:

และเมื่อพระจันทร์เต็มดวงขึ้น Hansel ถือมือน้องสาวตัวน้อยของเขา แล้วตามกรวดที่ส่องประกายเหมือนเหรียญเงินใหม่ ๆ และชี้ทางให้พวกเขา

อัลกอริทึมง่าย ๆ ที่สอดคล้องกับคำอธิบายนี้ เช่น อาจอยู่ในรูปแบบดังต่อไปนี้:

ค้นหากรวดที่ส่องประกายซึ่งยังไม่เคยถูกเยี่ยมชม แล้วมุ่งหน้าไปยังกรวดนั้น ทำซ้ำกระบวนการนี้จนกว่าจะถึงบ้านของพ่อแม่

คุณสมบัติสำคัญอย่างหนึ่งของอัลกอริทึมคือมันสามารถใช้งานซ้ำได้โดยคนเดิมหรือคนอื่นเพื่อแก้ปัญหาเดียวกันหรือปัญหาที่เกี่ยวข้องกัน อัลกอริทึมที่สร้าง computation ที่มีผลทางกายภาพมีประโยชน์แม้มันจะแก้เพียงปัญหาเฉพาะตัวหนึ่ง เช่น สูตรทำเค้กจะให้เค้กแบบเดียวกันซ้ำ ๆ เนื่องจากผลลัพธ์ของอัลกอริทึมบางอย่างเป็นสิ่งชั่วคราว—เค้กถูกกิน—การทำซ้ำผลลัพธ์เดิมจึงมีประโยชน์ เช่นเดียวกันกับการตื่นนอนและแต่งตัว ผลของอัลกอริทึมต้องถูกทำซ้ำทุกวัน แม้อาจเปลี่ยนเสื้อผ้าหรือเวลาในวันหยุดก็ตาม ข้อนี้ใช้กับ Hansel และ Gretel ด้วย แม้พวกเขาจะถูกพามาที่เดิมในป่า การกลับบ้านก็ต้องถูกคำนวณใหม่โดยการรันอัลกอริทึมซ้ำเพื่อแก้ปัญหาเดิม

สถานการณ์เปลี่ยนไปสำหรับอัลกอริทึมที่ให้ผลลัพธ์เป็นนามธรรม เช่น ตัวเลข ในกรณีเช่นนี้อาจจดผลลัพธ์ลงและค้นดูในครั้งต่อไปแทนการรันอัลกอริทึมอีกครั้ง เพื่อให้อัลกอริทึมมีประโยชน์ในบริบทนี้ มันต้องสามารถแก้ปัญหาคลาสหนึ่งของปัญหาได้ ซึ่งหมายความว่าต้องสามารถนำวิธีไปประยุกต์ใช้กับปัญหาหลาย ๆ แบบที่เกี่ยวข้องกันได้

ในเรื่องราว วิธีนี้กว้างพอที่จะแก้ปัญหาการหาทางได้หลายแบบ เพราะตำแหน่งกรวดจริง ๆ แล้วไม่สำคัญว่าตั้งที่ใด ไม่ว่าในป่าพ่อแม่จะพาเด็กไปที่ไหน อัลกอริทึมนี้ก็จะใช้ได้ในทุกกรณี และดังนั้นจะก่อให้เกิด computation ที่แก้ปัญหาการอยู่รอดของ Hansel และ Gretel พลังและผลกระทบมากมายของอัลกอริทึมมาจากความจริงที่ว่า one algorithm ให้กำเนิด many computations

แนวคิดของอัลกอริทึมเป็นหนึ่งในแนวคิดสำคัญที่สุดใน computer science เพราะมันเป็นพื้นฐานของการศึกษาที่เป็นระบบเกี่ยวกับ computation ดังนั้นแง่มุมต่าง ๆ ของอัลกอริทึมจะถูกพูดถึงในเล่มนี้อย่างกว้างขวาง

Do You Speak “Algorithmish”? (คุณพูด "Algorithmish" ไหม?)

อัลกอริทึมคือคำอธิบายเกี่ยวกับวิธีการปฏิบัติ computation และด้วยเหตุนี้จึงต้องถูกนิยามในภาษาอย่างใดอย่างหนึ่ง ในเรื่องราว อัลกอริทึมถูกกล่าวถึงเพียงเล็กน้อย Hansel แน่นอนมีอัลกอริทึมในหัวและอาจบอก Gretel ด้วย แต่ไม่ได้ถูกเขียนไว้ในนิทาน อย่างไรก็ตาม ข้อเท็จจริงที่ว่าอัลกอริทึมสามารถเขียนได้เป็นคุณสมบัติสำคัญ เพราะมันทำให้การแบ่งปันอัลกอริทึมเป็นไปได้อย่างเชื่อถือได้ และทำให้หลายคนสามารถใช้มันเพื่อแก้ปัญหาได้ ความสามารถในการแสดงอัลกอริทึมในภาษาที่คนเข้าใจได้สนับสนุนการแพร่หลายของ computation เพราะแทนที่จะให้คนคนเดียวผลิต computation จำนวนมาก มันทำให้หลายคนผลิต computation ได้มากขึ้น หากภาษาที่ใช้แสดงอัลกอริทึมสามารถเข้าใจได้โดยเครื่องคอมพิวเตอร์ การแพร่หลายของ computation แทบจะไม่มีขอบเขต ขึ้นกับทรัพยากรที่ต้องใช้ในการสร้างและดูแลเครื่องคอมพิวเตอร์

การที่อัลกอริทึมการตื่นนอนต้องมีคำอธิบายในภาษาไหม? อาจจะไม่จำเป็น เพราะผ่านการทำซ้ำเราทุกคนซึมซับขั้นตอนจนปฏิบัติได้โดยไม่ต้องมีคำอธิบาย อย่างไรก็ตาม สำหรับบางส่วนของอัลกอริทึมนี้มีคำอธิบาย เช่น ชุดภาพลำดับ ตัวอย่างเช่น การผูกเนคไทหรือการสานผมที่ซับซ้อน หากเป็นครั้งแรกและไม่มีใครสอนให้ดู คุณสามารถเรียนทักษะจากคำอธิบายประเภทนั้นได้

ความสามารถในการแสดงอัลกอริทึมในภาษาอีกด้านหนึ่งมีผลสำคัญอีกประการ มันทำให้การวิเคราะห์เชิงระบบและการจัดการเชิงรูปแบบกับอัลกอริทึมเป็นไปได้ ซึ่งเป็นหัวข้อของทฤษฎี computer science และงานวิจัยด้านภาษาโปรแกรม

อัลกอริทึมต้องสามารถแสดงเป็นภาษาที่คอมพิวเตอร์เข้าใจเพื่อให้สามารถรันได้ นอกจากนี้ คำอธิบายต้องเป็นแบบ finite กล่าวคือมีขอบเขตและไม่ยาวเกินไป สุดท้ายแต่ละขั้นตอนต้องเป็น effective ซึ่งหมายความว่าผู้ปฏิบัติต้องเข้าใจและสามารถทำแต่ละขั้นตอนได้ อัลกอริทึมของ Hansel และ Gretel ชัดเจนว่าเป็น finite เพราะประกอบด้วยคำสั่งไม่กี่ข้อ และแต่ละขั้นตอนก็เป็นไปได้ที่จะปฏิบัติได้ อย่างน้อยเมื่อสมมติว่ากรวดถูกวางในระยะที่มองเห็นถึงกัน อาจมีข้อสงสัยเกี่ยวกับเงื่อนไขที่บอกให้หากรวดที่ยังไม่เคยเยี่ยมชมนั้นเสมอ เพราะอาจยากที่จะจำกรวดที่เคยพบทั้งหมด อย่างไรก็ดี เงื่อนไขนี้สามารถทำให้เป็นจริงได้ง่ายโดยการหยิบกรวดแต่ละก้อนขึ้นมาทันทีหลังจากเยี่ยมชม แต่ในกรณีนั้นจะเป็นอัลกอริทึมที่ต่างออกไป โดยบังเอิญ อัลกอริทึมที่เปลี่ยนเล็กน้อยนั้นจะทำให้ Hansel และ Gretel กลับบ้านได้ง่ายในวันที่สอง เพราะ Hansel จะถือกรวดทั้งหมดไว้ การเปลี่ยนแปลงเล็กน้อยของอัลกอริทึมจะทำให้เรื่องราวตามที่ Brothers Grimm เล่าเป็นไปไม่ได้ (น่าเสียดายที่เราจะสูญเสียนิทานคลาสสิกชิ้นนี้)

A Wish List (รายการคุณสมบัติที่พึงประสงค์)

นอกเหนือจากคุณลักษณะนิยามพื้นฐาน ยังมีคุณสมบัติที่พึงประสงค์สำหรับอัลกอริทึมหลายประการ ตัวอย่างเช่น อัลกอริทึมควรสร้าง computation ที่ terminates และให้ correct results เสมอ เนื่องจาก Hansel วางกรวดจำนวนจำกัดที่ทำเครื่องหมายเส้นทางไปยังบ้านของพ่อแม่ การรันอัลกอริทึมที่อธิบายนี้จะสิ้นสุดเพราะมันเยี่ยมชมกรวดแต่ละก้อนไม่เกินหนึ่งครั้ง อย่างไรก็ตาม แปลกใจที่มันอาจไม่ให้ผลลัพธ์ที่ถูกต้องในทุกกรณีเพราะกระบวนการอาจติดขัดได้

Figure 1.3 เส้นทางที่แสดงตัวอย่างทางตันที่เป็นไปได้ในอัลกอริทึม ซ้าย: การเยี่ยมกรวดในลำดับกลับกันนำไปสู่บ้านของ Hansel และ Gretel ขวา: เนื่องจากกรวด B, C และ D อยู่ในระยะมองเห็นต่อกัน Hansel และ Gretel อาจเลือกไปจาก D ไป B แล้วไป C แต่ในจุดนั้นพวกเขาจะติดเพราะไม่มีกรวดที่ยังไม่เคยเยี่ยมชมปรากฏจาก C โดยเฉพาะพวกเขาไม่สามารถไปถึง A ซึ่งเป็นกรวดถัดไปบนเส้นทางกลับบ้าน

ดังที่กล่าวไว้ อัลกอริทึมไม่ได้ระบุว่าต้องไปหากรวดใดโดยเฉพาะ หากพ่อแม่พา Hansel และ Gretel ไม่เป็นเส้นตรง แต่เดินเป็นทางซิกแซกเข้าไปในป่า อาจเกิดกรณีที่จากกรวดหนึ่งสามารถเห็นกรวดอื่น ๆ หลายก้อน Hansel และ Gretel ควรไปกรวดใดในสถานการณ์เช่นนี้? อัลกอริทึมไม่ได้บอก ภายใต้สมมติฐานว่ากรวดทั้งหมดถูกวางในระยะที่มองเห็นกันได้ เราอาจเจอสถานการณ์ดังต่อไปนี้ ซึ่งแสดงใน figure 1.3

จินตนาการถึงลำดับกรวด A, B, C และ D ที่ Hansel วางไว้ระหว่างทางเข้าไปในป่า สมมติว่า A สามารถมองเห็นจาก B ได้ และ B สามารถมองเห็นจาก C ได้ แต่ A ไกลเกินกว่าจะมองเห็นจาก C (สิ่งนี้แสดงในภาพด้วยวงกลมของระยะมองเห็นรอบ ๆ กรวด B และ C) ยิ่งไปกว่านั้น สมมติว่า D อยู่ภายในระยะมองเห็นทั้งจาก B และ C ซึ่งหมายความว่าเมื่อ Hansel และ Gretel มาถึง D พวกเขาจะเห็นกรวดสองก้อน B และ C และต้องตัดสินใจ หากพวกเขาเลือกไปยัง C พวกเขาจะพบ B ต่อไปและสุดท้ายคือ A ทุกอย่างจะเรียบร้อย (ดูส่วนซ้ายของ figure 1.3) อย่างไรก็ตาม หากพวกเขาเลือก B แทน C — ซึ่งเป็นไปได้ตามอัลกอริทึม เพราะ B เป็นกรวดที่มองเห็นได้และยังไม่เคยถูกเยี่ยมชม — พวกเขาอาจตกอยู่ในปัญหาเพราะหากพวกเขาเลือก C ต่อไป (ซึ่งอีกครั้งเป็นกรวดที่เห็นได้และยังไม่เคยถูกเยี่ยมชม) พวกเขาจะติดอยู่ที่ C เหตุผลคือกรวดเดียวที่พวกเขาเห็นจาก C คือ B และ D ซึ่งทั้งคู่ถูกเยี่ยมชมแล้วและดังนั้นจึงไม่สามารถเลือกได้ตามอัลกอริทึม (ดูส่วนขวาของ figure 1.3)

แน่นอนว่าเราสามารถแก้ไขอัลกอริทึมด้วยการเพิ่มคำสั่งให้ backtrack ในกรณีแบบนี้และเลือกทางเลือกอื่นได้ แต่จุดประสงค์ของตัวอย่างนี้คือการแสดงให้เห็นกรณีที่อัลกอริทึมที่กำหนดไว้ไม่ให้ผลลัพธ์ที่ถูกต้อง มันยังแสดงให้เห็นว่าพฤติกรรมของอัลกอริทึมไม่ง่ายที่จะทำนายเสมอไป ซึ่งทำให้การออกแบบอัลกอริทึมเป็นงานที่ท้าทายและน่าสนใจ

หากเราตัดเงื่อนไขในอัลกอริทึมที่บอกให้หากรวดที่ยังไม่ถูกเยี่ยมชมเท่านั้น การ computation อาจเลื่อนเข้าสู่การเคลื่อนที่ไป-กลับไม่สิ้นสุดระหว่างกรวดสองก้อนได้ง่าย บางคนอาจค้านว่า Hansel และ Gretel จะไม่ทำสิ่งโง่ ๆ เช่นนั้นและจะรู้จักรูปแบบการทำซ้ำเช่นนี้ อาจเป็นจริง แต่ในกรณีนั้นพวกเขาไม่ได้ปฏิบัติตามอัลกอริทึมอย่างเคร่งครัดและแท้จริงแล้วกำลังหลีกเลี่ยงกรวดที่เคยถูกเยี่ยมชมไปแล้ว

ในขณะที่กรณีของการไป-กลับไม่สิ้นสุดระหว่างกรวดสองก้อนอาจสังเกตได้ง่าย ปัญหาโดยทั่วไปอาจยากกว่ามาก ลองนึกภาพเส้นทางที่พ่อแม่เดินเข้าไปในป่าแล้วตัดกันหลายครั้ง การวางกรวดที่ได้จะมีหลายวงแต่ละวงที่ Hansel และ Gretel อาจติดอยู่ได้; มีเพียงการจำกรวดที่เคยเยี่ยมชมเท่านั้นที่ทำให้แน่ใจว่าจะหลีกเลี่ยงวงเหล่านั้นได้ Chapter 11 พิจารณาปัญหาของการสิ้นสุด (termination) อย่างละเอียดมากขึ้น

คำถามเกี่ยวกับความถูกต้องและการสิ้นสุดอาจดูไม่สำคัญสำหรับอัลกอริทึมการตื่นนอน แต่ผู้คนก็เคยใส่ถุงเท้าที่ไม่คู่กันหรือทำผิดกฎการติดกระดุมเสื้อ และหากคุณยังยืนยันกดปุ่ม snooze ซ้ำ ๆ อัลกอริทึมการตื่นนอนก็คงไม่สิ้นสุดด้วยเช่นกัน