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

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

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

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

Dividing Problems into Triviality (การแบ่งปัญหาจนเหลือแต่เรื่องง่าย)

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

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

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

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

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

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

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

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

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

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

รูป 1.1 สรุปภาพรวมของการคำนวณในมุมมองเชิงการแก้ปัญหา โดยแสดงให้เห็นการหาทางของฮันเซลกับเกรเทลเป็นตัวอย่างของมุมมองที่ว่าการคำนวณจัดการกับการแทนค่าเป็นลำดับขั้นตอน ในปัญหาการลุกจากเตียงเราก็พบการแทนค่าเช่นกัน เช่น ตำแหน่ง (บนเตียง, นอกเตียง) และนาฬิกาปลุกที่แทนค่าเวลา การแทนค่าสามารถมีได้หลายรูปแบบ ซึ่งจะกล่าวถึงในรายละเอียดเพิ่มเติมใน บทที่ 3 .

Table 1.1

Computation Representation (การแทนค่าทางการคำนวณ)			Problem Representation (การแทนค่าของปัญหา)
Object (วัตถุ)	Represents (แทนค่า)		Concept (แนวคิด)	Represents (แทนค่า)
ก้อนกรวดหนึ่งก้อน	ตำแหน่งในป่า บ้าน		ตำแหน่งในป่า บ้าน	อันตราย ความปลอดภัย
ก้อนกรวดทั้งหมด	เส้นทางออกจากป่า		เส้นทางออกจากป่า	คำตอบของปัญหา

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

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

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

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

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

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

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

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

แต่โชคไม่ดีสำหรับฮันเซลกับเกรเทล วิธีเศษขนมปังใช้ไม่ได้ผลดังที่คาดไว้:

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

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

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

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

When Problems Reappear (เมื่อปัญหาปรากฏขึ้นซ้ำ)

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

เรามาดูอัลกอริทึมที่ฮันเซลกับเกรเทลใช้เพื่อหาทางกลับบ้านกัน วิธีการที่แน่นอนนั้นไม่ได้อธิบายอย่างละเอียดในเทพนิยายดั้งเดิม สิ่งที่เรารู้มีเพียง:

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

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

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

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

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

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

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

Do You Speak "Algorithmish"? (คุณพูดภาษาอัลกอริทึมได้ไหม)

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

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

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

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

A Wish List (รายการสิ่งที่พึงประสงค์)

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

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

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

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

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

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

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

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