Book-CSUnplugged

ทงั้ หมดน้ีเกย่ี วกบั อะไร? สมมุตวิ sาคณุ ไดมq โี อกาสออกแบบสาธารณปู โภคอยsางหน่ึง เชsน ระบบไฟฟ›า, ระบบแก¹ส, หรอื ระบบน้ำประปา เพ่ือสsงไปยงั ชุมชนทเี่ กดิ ขึ้นมาใหมs การท่เี ราจะเชื่อมตsอสงิ่ เหลsานน้ี ้ันเราจำเป€นทีจ่ ะตอq งมเี ครือขsายของสายไฟ กับทsอ แลqวบqานทุกหลงั น้นั จะตอq งเชือ่ มตsอกบั เครือขsายน้ที ีไ่ หนสกั แหงs หนง่ึ , แตsเสqนทางท่รี ะบบนี้ผsานไปถงึ บาq น นน้ั ไมไs ดเq ป€นเรอ่ื งทต่ี อq งกงั วลมากนัก, เสqนทางจะยาวแคsไหนน้นั ไมsสำคญั แตsสำคัญท่ีวsาจะมีเสqนทางที่ไปสsูบqาน ทุกหลังอยsางแนนs อนก็พอ งานออกแบบเครือขาs ยทม่ี ีความยาวรวมนqอยท่สี ดุ เรยี กวาs ปญ' หา ต\"นไมแ\" บบทอดขา\" มน\"อยทีส่ ดุ ตqนไมqแบบทอดขqามนqอยที่สุด ไมsไดqแคsใชqสำหรับ เครือขsายแก¹ส และ เครือขsายไฟฟ›าเทsานั้น มันยังสามารถ นำมาใชqแกqป'ญหาเครือขsายคอมพิวเตอร,/ เครือขsายโทรศพั ท/, ทsอสsงน้ำมัน, และเสqนทางการบินไดอq กี ดqวย ถึง อยsางไรก็ตาม การที่จะเลอื กเสqนทางที่ดีที่สุดเพื่อนักเดินทางแลqว เรานั้นตqองพิจารณาจากความสะดวกสบาย ของการเดินทางดqวย เชsนเดียวกับราคาของทริปนั้น คงไมsมีลูกคqาคนไหนที่อยากจะใชqเวลาเปน€ ชั่วโมงอยูsบน เครื่องบินที่ใชqเวลานานเพื่อไปประเทศใหมsเพียงแคsมันถูกกวsาหรอก อัลกอริทึมเมืองที่เต็มไปดqวยโคลนนั้น อาจจะไมsคsอยเป€นประโยชน/สำหรับเครือขsายพวกนี้สักเทsาไหรsเนื่องจากมันไดqลดความยาวของถนน หรือ เสนq ทางบนิ ลงกวาs เดมิ (note) ตqนไมqแบบทอดขqามนqอยที่สดุ นั้นยังเป€นสsวนหนึ่งของการแกปq 'ญหาเชิงกราฟอีกดวq ย เชsน ป'ญหาการเดนิ ทาง ของเซลล/แมน ซึ่งในแตลs ะการทดลองนนั้ จะหาเสนq ทางผาs นจุดทง้ั หมดทม่ี ีขนาดสั้นท่สี ดุ ในเครือขาs ยน้นั ๆ ยงั มีอลั กอริทึมทมี่ ีประสทิ ธิภาพมากท่สี ุดสำหรบั ใชqในการแกปq 'ญหาตqนไมqแบบทอดขาq มนqอยที่สุด วิธีพื้นฐานท่ี ใหqคำตอบที่ดที ี่สุด นั่นคือเริ่มจะที่ไมsมีการเช่ือมตsออะไรเลย และคsอยๆเพิ่มการเชื่อมตsอสsวนตาs งๆที่ยังไมไs ดq เช่อื มตอs ละไปท่ที ลี ะสวs น วิธีน้เี รยี กวsา Kruskal’s algorithm ตั้งหลังจาก J.B Kruskal เป€นคนตพี ิมพใ/ นป‹ ค.ศ. 1956 สำหรับป'ญหาตsางๆของกราฟ รวมทั้ง ปญ' หาการเดินทางของเซลล/แมน นักวิทยาศาสตร/คอมพิวเตอร/ ก็ยังไมs สามารถทจ่ี ะหาวธิ ีที่เรว็ พอทจ่ี ะหาคำตอบทดี่ ที ส่ี ุดไดq หนาq 101

วธิ ีทำและคำใบ^ รูปแบบและสyวนขยาย (หนา^ 85) จะมถี นนหรือการเชือ่ มตอs ท่ีตอq งใชqเทsาไหรsถqามบี qานจำนวน n หลังในเมือง? กลายเป€นวsาคำตอบท่ีดีท่ีสุดก็คือ n-1 การเชือ่ มตอs เทาs นนั้ แคsนนั้ ก็เพียงพอแลวq สำหรับบาq น n หลงั การทเ่ี ราจะเพ่ิมกเ็ ชื่อมตsอไปเพม่ิ นั้นเป€นสงิ่ ที เกนิ ความจำเป€นและจะกลายเป€นเสนq ทางท่ไี มสs ำคญั ระหวsางบาq นแตsละหลังอกี ดวq ย หนqา 102

กิจกรรมท่ี 10 เกมแลกสม^ - เร^าทตr งิ้ และ การติดตาย ในเครอื ขาy ย บทสรุป เมื่อเราตอq งการทจี่ ะใชทq รัพยากรอนั เดยี วกัน (เชsน รถตqองการใชถq นน หรอื ขอq ความสงs ผาs นอินเตอรเ/ น็ต) ในแตs ละที่นั้นอาจจะมี “การตดิ ตายเกดิ ขึ้น” การรsวมมือกนั ทำงานน้ัน จะเป€นหนทางในการลีกเลีย่ งปญ' หานี้ หลักสูตรทเ่ี ก่ียวข^อง ü คณติ ศาสตร/: พฒั นา ตรรกะ และ การใหqเหตผุ ล ทักษะ ü การรsวมมือกันแกปq ญ' หา ü การใหqเหตผุ ล อายุ 1. 9 ป‹ข้ึนไป อปุ กรณr นักเรยี นแตลs ะคนจะตอq งมี ü สqมหรือลกู เทนนิส สองลูกและจะตอq งมกี ารทำเครื่องหมายเป€นตวั อักษรที่เหมอื นกันไวq ü แทก¹ ช่อื หรอื สติกเกอรท/ ี่สามารถแสดงตัวอกั ษรของตัวเองได,q หรือตราชนดิ ใดกไ็ ด หนาq 103

เกมแลกส^ม บทนำ นเี่ ป€นเกมที่ตqองใชกq ารรsวมมือกนั เพ่ือแกqปญ' หา เป›าหมายอยทsู ใี่ นตอนสุดทqายทุกคนตqองถือสqมท่ีมีตัวอักษรของ ตัวเองอยsู 1. นั่งเปน€ วงกลมกลุsมหน่งึ ไมsนอq ยกวาs 5 คน 2. นักเรียนจะถูกทำเครือ่ งหมายโดยตัวอักษร (ใชq แท็คชอ่ื หรอื สตกิ เกอร)/ หรือใชสq ีก็ไดq ถาq ตวั อักษรใด ใชqไปแลวq นักเรียนแตsละคนจะมีสมq 2 ลูกที่มีตัวอกั ษรของพวกเขาตดิ อยูs แตsจะมเี พียง 1 คนที่มีสqม เพียงลูกเดียว เพือ่ ใหqแนsใจวsาจะมีนักเรียนจะมมี อื หนึ่งวsางเสมอ 3. สsงสqมกระจายแบบสุมs ไปยังนกั เรยี นทุกคนในกลมsุ เปน€ วงกลม แตลs ะคนตqองมสี มq สองลูก ยกเวqนหน่งึ คน ทม่ี ีลกู เดยี ว( นักเรยี นทุกคนควรทจี่ ะไมไs ดสq qมของตวั เอง หรอื สีเดมิ ) 4. นักเรียนจะสsงสqมไปรอบๆจนกวsานักเรียนทุกคนจะไดqรับสqมหนึ่งอันท่ีมีเครือ่ งหมายของตวั เอง โดย นักเรียนตอq งทำตามกฎสองขอq I) มอื หนง่ึ ขาq งถือสมq ไดมq ากสดุ แคsหนงึ่ ชิ้น II) จะสงs สมq ไดตq อนคนดqานขqางมีมือที่วsางเทาs น้ัน (นักเรียนสามารถสงs สqมลกู ไหนก็ไดqใหqแกsเพื่อน คนขาq งๆ) นกั เรยี นจะคqนพบไดqวsาพวกเขาอาจอยsูในสถานะโลภกเ็ ปน€ ไดq โดยรีบถือผลไมqของตนเองเอาไวqทันทีที่ ไดมq า ซงึ่ การทำแบบน้จี ะทำใหกq ลมsุ ไมสs ามารถบรรลเุ ปา› หมายไปไดq นั่นหมายความวsา แมวq าs จะมีคนท่ี ไดรq บั สqมของของตนเอง แตsท้งั กลุมs ทำภารกจิ ไมสs ำเรจ็ ก็ไมถs ือวsาคนน้ันชนะ แตทs ุกคนตqองไดqรับสqมที่ ถูกตqองของตนเองเสยี กsอน จงึ จะชนะไดq การอภปิ รายเพ่มิ เตมิ กลยุทธ/ท่นี กั เรียนสามารถใชใq นการแกqป'ญหานีไ้ ดq? ท่ไี หนบาq งท่นี ักเรยี นจะไดqพบกบั การติดตาย? เชนs รถติด, ผqเู ลนs ท่จี ะไปถึงเบสในกฬี าเบสบอล, การพยายามใหq คนหลายคนผาs นประตูไดqในครัง้ เดียว หนาq 104

กิจกรรมเพม่ิ เตมิ นง่ั เปน€ วงกลมทีเ่ ล็กลง หรอื ใหญsขึ้น • ตัง้ กฎกตกิ าใหมสs ำหรบั นักเรยี น • เลsนกจิ กรรมโดยไมsมีการพดู คยุ กัน • ลองกำหนดรปู แบบใหมๆs ในการนงั่ เชsน น่งั เป€นแถว หรือ ใหqมเี พอ่ื นน่งั ขqางๆมากกวาs 2 คน ดังตวั อยsางในรปู หนาq 105

ทัง้ หมดนเ้ี กย่ี วขอ^ งกับอะไร? ในระบบเครือขsายนั้นมีป'ญหามากมายเกี่ยวกับการกำหนดเสqนทางและการติดตาย เชsน ในระบบโทรศัพท/ ระบบถนน หรือระบบคอมพิวเตอร/ เหลsาวิศวกรจึงทุsมเทอยsางมากในการแกqป'ญหาเหลsานี้ ดังนั้นจึงตqอง ออกแบบเครือขาs ยใหดq ี เพอื่ แกไq ขปญ' หาเหลsานี้ไดงq าs ยข้ึน การกำหนดเสนq ทาง,ความแออัดและการติดตายสามารถทำใหqเกดิ ปญ' หาในหลาย ๆ เครือขsาย ลองคิดถึงตอน ชั่วโมงเรsงดsวนในนครนิวยอร/กดูสิ ในตอนที่การจราจรติดขัด ไมsมีรถคันไหนขยับไดqเลย หรือตอนที่พวก คอมพิวเตอร/เกิดการขดั ขอq ง เพราะป'ญหาที่เกิดจากการติดตายของเครือขsายการสื่อสาร ดังนั้นการออกแบบ เครือขsาย เพื่อใหqการกำหนดเสqนทางทำไดqงsายและมีประสิทธิภาพจะชsวยลดป'ญหาเรื่องความแออัดซง่ึ เป€น ป'ญหาทย่ี ากลำบาก ทว่ี ศิ วกรตอq งเผชิญ ในบางครั้ง มันกม็ มี ากกวsาหนึ่งคนทีต่ อq งการขqอมูลในเวลาเดยี วกัน แลวq ถqาเราเกิดจะแกqไขขอq มูลบางสsวน เชsน ยอดเงินคงเหลือของบัญชีธนาคาร ในระหวsางนั้น ขqอมูลก็ควรจะถูกล็อคไวq ไมsใหqคนอื่นเขqามาแกqไขไดq ไมsเชsนนั้น ขqอมูลอาจถูกบันทึกอยsางไมsถูกตqอง อยsางไรก็ตาม หากการล็อคนี้ถูกแทรกแซงโดยการล็อคของ ขqอมูลอืน่ การติดตายกอ็ าจเกิดขน้ึ ไดอq กี เชsนกัน หนึ่งในการพัฒนาที่นsาตื่นเตนq ที่สุดในการออกแบบคอมพิวเตอร/คือการถือกำเนิดของระบบประมวลผลแบบ ขนานซึง่ มีหลายรqอยหรอื หลายพันเคร่ืองคอมพวิ เตอรท/ ท่ี ำงานประสานกันในเครือขาs ย เพอ่ื สรqางคอมพวิ เตอรท/ ่ี มปี ระสทิ ธภิ าพเพียงเครอ่ื งเดียว โดยปญ' หามากมาย เชนs เกมแลกสqม ตอq งเลsนบนเครือขาs ยเหลsานี้อยsางตอs เนอื่ ง (แตsเร็วกวsามาก) เพอ่ื ใหคq อมพิวเตอร/แบบขนานเหลาs น้สี ามารถทำงานไดq หนqา 106

กิจกรรมที่ 11 แผyนจารกึ หนิ - ระเบยี บการสอื่ สารภายในเครอื ขาy ย สรปุ คอมพิวเตอร/สื่อสารกันโดยการสงs ขqอความผsานทางอินเทอรเ/ น็ต อยsางไรก็ตาม ในบางครั้ง อินเทอรเ/ นตก็ไมs เสถียรมากพอ ทำใหqขอq ความเหลาs นน้ั สญู หายไดq มันจงึ เกิดการเพ่มิ ขอq มูลบางอยsางลงในขอq ความ เพ่อื ใหแq นใs จ วาs ขqอความนน้ั ถกู สงs ออกไปแลqว และขอq มลู นัน้ เอง สราq งเกณฑว/ ธิ ีในการติดตอs สอ่ื สารกนั ระหวsางคอมพวิ เตอร/ หลกั สูตรทเี่ กีย่ วข^อง ü คณติ ศาสตร/ : การพัฒนาตรรกะและเหตผุ ล ü ภาษาองั กฤษ : การส่อื สาร และการฟง' ภาษาองั กฤษ ทักษะ ü การรsวมมือกันแกqปญ' หา ü ตรรกะและเหตุผล อายุ ü 9 ป‹ข้นึ ไป อปุ กรณr นักเรยี นแตลs ะคนจะตqองมี : üกระดาษเปลsา หลายๆแผนs คนสsงขqอความแตsละคนจะตqองมี : üชุดของการด/ ขอq ความ คณุ ครูจะตqองมี : ü นาºกิ าจับเวลา หนาq 107

แผนy จารกึ ข^อความ (Tablets of Stone) บทนำ ในแบบทดสอบน้ี นักเรยี นตqองพจิ ารณาวาs วิธีสื่อสารทแ่ี ตกตsางกนั ตsางใหผq ลสมั ฤทธิอ์ ยาs งไร นกั เรียนจะ เรยี นรqหู ลักปฏบิ ัตขิ องการสือ่ สารจากกฎและขั้นตอนทมี่ ีอยูs ภายใตqการสวมบทบาท นกั เรยี นจะไดq ทดสอบความเปน€ ไปไดขq องหลกั ปฏบิ ัติในสภาพแวดลอq มทีไ่ มแs นsนอนคลาq ยกับทเี่ กดิ ในแพ็คสวทิ ช/ใน อนิ เตอรเ/ นต็ โดยเฉพาะอยาs งยง่ิ ท่ี TCP/IP. การเตรียมการ (30 นาที) 1. เร่มิ ดวq ยการรวบรวมบตั รคำสงั่ โดยกsอนอน่ื ตอq งเตรียมพมิ พบ/ ัตรคำสงั่ (ตามแบบขาq งลsาง) และตัดแตลs ะ คำสง่ั มาเตรยี มไวq 2. ตอs ไปจึงเลอื กขอq ความท่จี ะใหนq กั เรยี นสงs ออกไป โดยขอq ความน้นั ตqองไมใs ชปs ระโยคภาษาองั กฤษ หรอื อักษรหรอื ตวั เลขใดทมี่ รี ูปแบบโครงสรqางเปน€ คำทเี่ ขาq ใจไดq “1LHC255HD((RLLS” คอื ขอq ความที่ ใชไq ดq หรอื อาจเปน€ เลขหมายโทรศพั ท/ 3. พิมพแ/ ผsนจารกึ ขqอมลู (Tablet) ออกมาหลายๆแผsน แตลs ะแผsนจารกึ ขอq มลู นีจ้ ะมเี นื้อท่พี อแคsตัวอักษร หรือตวั เลข 6 หลกั เพ่อื ทจ่ี ะไดqไมสs ามารถเขียนขอq ความทงั้ หมดลงในแผนs เดียวไดq ผูqนำการทดสอบ เตรียมแผsนจารึกขอq มลู ใหqนกั เรยี นคนละประมาณ 30 แผsนขน้ึ อยกsู ับระยะเวลาการเลนs เกมส/นี้ หมายเหตุ : บัตรคำสั่งมี 3 ประเภทดวq ยกัน คือ ลาs ชqา ไมsนำสsง และ นำสงs การปรบั สดั สsวนของบตั ร แสดงใหเq ห็นถงึ คุณภาพของผqูสงs สาร ยิง่ มีจำนวนบัตรนำสงs มากเทาs ใด หมายถึง ขqอความยิง่ มีความ นาs เชอ่ื ถอื มากเทาs นน้ั ยง่ิ มีจำนวนบตั รชqา หรอื บัตรไมนs ำสsงมากเทาs ใด ความนsาเชอื่ ถอื ในเครือขsายลด นอq ยลงเทาs นน้ั บตั รคำสงั่ เหลsานี้ อยบsู นแนวคิดคลาq ยคลึงกบั เครือขsายคอมพวิ เตอร// ชsองทางสอ่ื สาร วธิ ีเลyนเกมสr 1. จบั คsูนักเรยี น ขอq สำคญั คือ แยกใหqอยหsู sางกนั โดยไมคs วรมองเหน็ กันหรอื สอ่ื สารกนั ไดq แยกหอq งไดจq ะ เป€นการดแี ตsใหqนกั เรียนหนั หลงั ใหกq นั ก็นsาจะพอ 2. บอกขqอความใหนq ักเรียนฝา¸ ยหนงึ่ คนละขอq ความเพ่อื ใหqสงs ใหคq ขูs องตน 3. สับบตั รคำสง่ั และทำการเลอื กผสqู งs สาร โดยผูนq ำการทดสอบอาจเป€นผสูq sงสารเองกไ็ ดq หรือ ถqาจำนวน นกั เรยี นทั้งหมดเป€นเลขค่ีกใ็ หนq กั เรยี นคนทีเ่ หลือเปน€ ผสqู sงสารกไ็ ดq อาจตอq งมผี สqู งs สารมากกวาs หนงึ่ คน หากเป€นหqองเรยี นใหญs 4. นักเรยี นทไี่ ดรq ับขอq ความตอq งเขยี นลงบนแผนs จารึกขอq มลู (Tablet) ของตนและสงs ใหกq บั ผสูq งs สาร อยsาง นอq ย ควรมีชื่อคูขs องตนอยูsบนแผนs จารกึ ทใี่ หqไปนั้นดqวย หนาq 108

5. ผสqู งs สารตqองหยิบบัตรคำสง่ั ใบบนสดุ หงายข้ึน อsานขอq ความในบัตรนัน้ และปฏบิ ตั ติ าม 6. ทำซำ้ ขั้นตอนท่ี 4 และ 5 กบั แผsนจารึกขqอมูลทุกอนั ประมาณ 5 นาที หลงั เกิดความวนุs วsาย นักเรยี นจะตระหนกั วาs การระบุช่ือเพยี งอยsางเดยี วไมsดพี อสำหรบั หลัก ปฏบิ ัติ ขอใหหq ยดุ การเลsนและดำเนนิ การอภิปรายรsวมกนั วาs ประเด็นป'ญหาคอื อะไร ใชลs ำดับทีเ่ รยี งขอq ความ หรอื ไมs บางทอี าจเป€นการดที ่จี ะเติมตัวเลขประจำแผsนจารกึ ขอq มูลลงไปในชอs งขqอความทกี่ ำหนดใหมq ีอยูs 6 ชsอง ซึง่ กห็ มายความวsาพน้ื ทีใ่ สsขอq ความลดนqอยลงไป การกระทำเชsนนมี้s คี วามหมายตsอจำนวนของแผนs จารกึ ขqอมูล อยsางไร ในเวลาตsอมา นกั เรยี นอาจจะพบปญ' หาอน่ื กข็ อใหนq ำมาอภปิ รายกนั ป'ญหาท่ีอาจเกดิ ขึน้ คอื แผsนจารกึ ขอq มลู หายไปโดยทไี่ มรs วqู sาถูกสงs ถงึ มือผูqรบั หรือไมs ไมรs วqู าs ควรสงs แผนs จารึกขqอมลู ไปใหมรs ไึ มs ผนqู ำการทดสอบอาจบอก นักเรียนวาs ใหสq งs ขqอความตอบรบั ออกไปและรอการตอบรับกอs นจะสงs แผsนจารกึ ขqอมลู ออกไปใหมอs กี ครง้ั ซ่ึงก็ หมายความวsานกั เรียนผรqู อรบั แผนs จารกึ ขqอมลู จะตอq งมแี ผนs จารกึ ขอq มูลเปลาs เพมิ่ อีกเพือ่ ใหใq ชสq sงขอq มลู ตอบรบั และนักเรียนทง้ั คูกs ต็ qองชวs ยกันกำหนดและตกลงขqอความตอบรบั ทีมีความยาวไมเs กนิ 6 ตัวอักษร กอs นจะเรมิ่ เลนs เกมส/ ผqนู ำการทดสอบตqองมนี ักเรยี นผเqู ลsนเกมสอ/ ยsางนqอย 2 คนแตแs นะนำใหqมีจำนวนผเqู ลsนเกมสม/ ากเทาs ที่จะมีไดq ถาq เป€นหอq งเรยี นใหญs ขอใหกq ำหนดผสูq sงสารไวq 2-3 คน พรอq มเปด„ หวั ขอq อภิปรายวาs ผสูq sงสารหลายคนมีผล อยsางไรและผสูq sงสารคนเดยี วมผี ลอยาs งไร หนqา 109

ถึง: ถงึ : จาก: จาก: ถงึ : ถงึ : จาก: จาก: ถงึ : ถึง: จาก: จาก: ถงึ : ถงึ : จาก: จาก: หนาq 110

แผนy จารึก (Tablets of Stone) ณ เมืองโบราณแหงs หนง่ึ มีผปqู กครองชุมชนคนสำคญั อยหูs ลายคน ผูqปกครองเหลsาน้ไี ดqตกลงบรหิ ารเมอื งและ ตดั สินใจในเรอ่ื งสำคัญรsวมกนั ผqปู กครองเหลาs นีต้ sางอาศยั อยทsู บ่ี าq นของตนทต่ี งั้ อยsทู ่ัวเมอื ง บรรดาผปูq กครองชุมชนเหลาs นลี้ qวนตqองการสือ่ สารหรอื สงs -รบั ขอq มูลไปทัว่ เมอื ง ฐานนั ดรของผปqู กครองชมุ ชนถูก ระบุโดยเลขทีบ่ าq นและแตลs ะคนกส็ ามารถเรยี กใชผq สqู sงสารทงั้ หลายทท่ี ำหนqาท่สี งs สารไดq วิธเี ดยี วทจ่ี ะสงs สารไดคq ือเขยี นลงบนแผนs ศิลาจารึกสเี่ หลี่ยมใหญsซง่ึ ผสูq sงสารตอq งแบกไปสงs ยังที่หมาย แผนs ศลิ า จารกึ นมี้ ีขนาดเทาs กนั และสามารถบรรจขุ อq ความไดเq พียง 6 หลัก ขอq ความแตsละหลกั อาจเป€นอกั ษรตวั หนงึ่ หรอื ตวั เลขตัวหนงึ่ ก็ไดq จึงตอq งเขยี นสารทงั้ หมดลงบนหนิ หลายกอq นแตsดqวยความใหญแs ละหนกั จงึ สงs ไดเq พยี งคราวละ กqอนเทาs นัน้ ผสูq งs สารก็เปน€ ทไ่ี มนs sาไวqวางใจวาs จะสsงสารไดถq กู ตqองเพราะขลี้ มื และข้เี กยี จ พวกเขามกั จะแวะพกั เปน€ เวลานาน ๆ ระหวาs งช่วั โมงทำงานและแมqกระทงั่ พยายามหลบหนอี อกนอกเมืองไป ผปqู กครองตอq งการหาวิธที ่จี ะทำใหกq ารสอ่ื สารเปน€ ไปอยsางมปี ระสิทธิภาพ พวกเขาจึงตอq งการพัฒนากฎระเบียบ ขั้นตอนขน้ึ มาเพือ่ ทกุ คนจะไดqปฏิบตั ิตาม ดวq ยกฎระเบยี บขัน้ ตอนท่ีพัฒนาข้ึนใหมนs ้ีพวกเขาจะทราบไดวq าs สารไดq ถงึ มือผรูq บั หรอื ไมแs ละขอq ความน้นั ถูกตqองหรือไมs เหลาs ผปqู กครองชมุ ชนตกลงกันวsา ควรระบุทหี่ มายไวบq นหนิ แตs ละกอq น ในกลมsุ ทดสอบท้งั หมดน้ี ผรqู วs มทดสอบตอq งคิดคนq หา กฎระเบียบขน้ั ตอนการปฏบิ ตั กิ ารเพ่ือใหเq หลาs ผปูq กครอง ชุมชนไดqใชqเพอ่ื การสอื่ สาร… หนาq 111

ทงั้ หมดนเี้ กย่ี วกับอะไร ? ในอนิ เตอรเ/ นต็ ขอq ความจะถูกแยกออกเป€นชดุ ขqอมลู เพอ่ื การสงs ตอs อยาs งไรกต็ าม ชอs งทางการสงs ชุด ขอq มลู เหลาs นี้ มักเกดิ ความไมsนาs ไววq างใจ บางคร้งั ชดุ ขอq มลู อาจจะถกู ทำใหเq สียหาย ขาดหายไป หรือ เรยี งลำดับผดิ ในแผsนศิลาจารกึ แผนs หินจารึกแตลs ะกอq นคือชดุ ขqอมลู และส่งิ ทบี่ รรจอุ ยูกs ็คือใจความบางสsวนของสาร ชุดขqอมลู ประกอบดqวย ทง้ั หวั ขqอและใจความ ขนาดของหวั ขอq และใจความสงs ผลตsอปรมิ าณใจความที่ จะนำสงs ดังนัน้ จงึ ตqองจัดใหสq มดลุ เพราะชุดขอq มลู มขี นาดคงท่ี นักเรียนจะพบวาs พวกเขาจะตอq งแลกเปลยี่ นขqอมูลบางสsวนกนั ไวqลวs งหนqากอs นเลsนเกมส/ เชsน ตวั เลข ประจำชดุ ขอq มูล และจำนวนชุดขqอมลู ทง้ั หมด หรอื ชุดขqอมูลนั้นเป€นชดุ ขอq มูลตอบรบั หรอื ไมs เพราะ ขqอมลู เหลาs นี้จะกินพื้นทีใ่ นแผนs จารกึ หรอื อกี นัยหนง่ึ จะตqองใชชq ดุ ขqอมูลมากข้ึน หลักปฏบิ ัตทิ างอนิ เตอร/เนต็ เชนs TCP และ UDP ทำใหปq จ' จัยเหลาs น้ีเกดิ ความสมดุลเพอ่ื ใหเq กิด ประสทิ ธิภาพและความนาs เชอ่ื ถือในการส่ือสาร แบบทดสอบนป้ี ระยุกตม/ าจากแบบทดสอบของโครงการ “Computing Science Inside” (csi.dcs.gla.ac.uk) หนqา 112

บทท่ี 3 สง่ั คอมพวิ เตอรrให^ทำงาน – การแสดงกระบวนการทำงาน (procedure)

การบอกคอมพวิ เตอรใr หส^ ง่ิ ใดสงิ่ หนง่ึ ในทุกๆวินาที คอมพิวเตอร/ทำตามคำสั่งหลายลqานคำสั่ง การจะบอกใหqคอมพิเตอร/ทำอะไรสักอยsางนั้น เรา จะตqองปอ› นคำสงั่ ใหqแกมs นั อยsางถกู ตqอง......แตsมนั ไมงs sายอยsางน้นั นsะส!ิ เมื่อเราไดรq ับคำส่ังจำนวนหน่ึงมา เรามักใชqความรูqสกึ และความคุqนเคยในการตีความวsาคำสั่งเหลsาน้ัน ตqองทำ อะไรบาq ง หากใครคนหนึง่ บอกเรา “ผาs นประตนู ่นั ไป” นน่ั ไมsไดหq มายความวsาใหqเราพงั ประตเู ขqาไป แตเs พียงใหq เราเดินผsานประตูเขqาไปและหากประตูป„ดอยูsก็ใหqเป„ดออกกsอนที่จะเดินเขqาไป แตsคอมพิวเตอร/นั้นแตกตsาง ออกไป หากเราสงั่ ส่ิงเหลsานก้ี บั หุนs ยนตห/ รือคอมพิวเตอร/ เราจะตอq งระวงั อยsางมากเพือ่ หลีกเล่ียงอันตรายและ ความเสียหายที่จะเกิดขึ้นจากการตีความคำสั่งผิดพลาด เชsนความพยายามที่จะเดินผsานประตูเขqาไปขณะที่ ประตยู งั ปด„ อยsู สงิ่ เหลาs นีท้ ำตามคำสั่งโดยท่ไี มมs คี วามสามารถในการตีความเป€นของตนเอง 2 กิจกรรมตsอไปน้ี จะใหqไอเดียในการสอ่ื สารกบั หนุs ยนต/โดยใชq ชดุ คำส่งั ทีต่ ายตวั กจิ กรรมแรกจะสอนเราเก่ยี วกับ “หุsนยนต/” สิง่ ท่คี อมพิวเตอร/สามารถรับรqูและทำงานรsวมไดqนัน้ คือ คำ, ตัวเลข และตัวอกั ษร หsนุ ยนตเ/ หลsานี้เราจะเรยี กวาs เครอื่ งจักรอตั โนมตั ิที่มีจำนวนสถานะแนนs อน กจิ กรรมที่ 2 จะอธบิ ายวsาเราจะสามารถส่ือสารกับคอมพิวเตอร/ไดอq ยsางไร โปรแกรมเมอรท/ ี่ดีจะตอq งรqูวsาจะสื่อ ใหqหุsนยนต/ทำตามไดอq ยsางไรผาs นชดุ คำสั่งทีต่ ายตัวท่ีสามารถตีความไดqโดยไมsมีความกำกวม เราเรียกชดุ คำส่ัง เหลาs น้ีวาs โปรแกรม ซง่ึ มหี ลายหลายโปรแกรมทแ่ี ตกตsางกนั ไปซึ่งโปรแกรมเมอร/สามารถเลอื กและหยิบมาใชqใน การสราq งโปรแกรมไดq แตsในที่น้เี ราจะใชqภาษาทีง่ าs ยตอs ความเขqาใจซึ่งใชqโดยไมsตอq งมีคอมพิวเตอรไ/ ดq หนqา 114

กิจกรรมท่ี 12 ลyาสมบตั ิ - เครอ่ื งจกั รอัตโนมัตทิ ่มี ีจำนวนสถานะแนนy อน สรปุ โปรแกรมคอมพิวเตอร/มักจะประมวลผลจากชุดตัวอักขระ ตัวอักษรหรือคำ ในแตsละขqอมูล นักวิทยาศาสตร/ดqานคอมพิวเตอร/มักจะใชqเครื่องจักรอัตโนมัติที่มีจำนวนสถานะแนsนอน (FSA) ซ่ึง เครื่องจักรดังกลsาวจะทำตามชุดคำสั่งซึ่งเป€นคำหรืออักขระ ที่ไดqสั่งไปหากคำสั่งเหลsานั้นถูกตqองและ สามารถรับรqูไดq จากนี้เราจะมาทำอะไรทคี่ ลาq ยกับ FSA — แผนท่ีขุมทรัพย/! หลกั สูตรทเ่ี ก่ียวขอ^ ง ü คณิตศาสตร:/ การพฒั นาตรรกะและการใหqเหตุผล—โดยใชqคำและตวั อกั ษรในการอธิบายและ ตอs ยอดแบบแผน ü สังคมศึกษา ü ภาษาอังกฤษ ทักษะ ü การอsานแผนท่ีเบื้องตนq ü การตรวจจับแบบแผน ü ตรรกะ ü การทำตามคำสง่ั อายุ ü 9 ปข‹ น้ี ไป อุปกรณr คณุ ต^องการ: üหนงึ่ ชุดการ/ดคำส่งั (ชุกคำสงั่ จะตอq งถูกซอs นจากคนทพี่ ยายามจะหยบิ แผนท่)ี ü สำเนาของการด/ เกาะ (หนqา 123) ตดั ตามรอยเสqนประและนำกาวมาประกบตดิ ระหวsางชอ่ื เกาะกบั ชดุ คำสั่ง โดยชื่อเกาะจะติดอยsดู าq นหนqาและชดุ คำสง่ั จะติดอยดูs าq นหลัง นักเรียนแตลy ะคนตอ^ งการ: üชที กิจกรรม: หาทางไปสsูขุมสมบัติ (หนาq 122) üปากกาหรอื ดนิ สอ หนาq 115

กิจกรรมเพม่ิ เตมิ สำหรับนักเรยี นแตyละคนตอ^ งการ: üชที กิจกรรม: เกาะมหาสมบตั ิ (หนqา 128) üชีทกิจกรรม: เกมเหรียญลกึ ลบั (หนqา 129) หนาq 116

เกาะมหาสมบตั ิ บทนำ เป›าหมายของคุณคือการตามหาเกาะมหาสมบัติ เพอื่ นๆชาวโจรสลดั ลอs งเรือตามทางระหวาs งเกาะสำหรบั เหลาs นักเดนิ ทาง แตsละเกาะจะมที างเขqาทคี่ ณุ สามารถเลอื กไดqทงั้ หมด 2 ทางคอื A และ B คุณจำเป€น จะตอq งหาทางที่ดที ส่ี ุดที่จะไปสเูs กาะมหาสมบัติ เริ่มตqนจากการเลอื กวsาจะไปเสนq ทางทางใดทางหนึ่ง (A หรอื B) ท่แี ตsละเกาะที่คณุ ไปถึง คนในแตsละเกาะนั้นๆจะเปน€ คนบอกคณุ ตsอวsาทางทคี่ ณุ เลือกน้ันจะพา คุณไปยงั ทใ่ี ดตsอ ซง่ึ เราฝา¸ ยโจรสลดั เองน้นั ไมsมแี ผนท่ี จงใชแq ผนทีเ่ พอื่ วางแผนและเลอื กเรือทจ่ี ะลงแลsน ตัวอยyาง (บันทึก: แผนทน่ี ้ีแตกตsางจากแผนท่ีในกจิ กรรม) วาดเกาะทัง้ 3 ลงบนกระดานดังน:้ี ทำสำเนาของไพsทงั้ 3 ใน 2 หนาq ถัดไป จากนั้นใหqนกั เรียนถอื ไพsไวq โดย 1 คน ถือเพียง 1 ใบ เทาs น้นั บนั ทกึ : ทางท่แี สดงในไพsทง้ั 3 ใบน้นั แตกตาs งจากทางจรงิ ในกจิ กรรม เลอื กใหไq ปในทาง A นกั เรียนมsุงหนาq ไปสเsู กาะ Shipwreck Bay ซงึ่ บอกใหqใชทq าง A ดงั เดมิ คณุ จะตqองเดนิ ทาง กลบั ไปยงั Pirate’s Island เขียนผังการเดินทางลงในแผนที่ จากนั้นเราเลอื กใชทq าง B เขียนลงในแผนที่ ทางน้ี หนqา 117

จะเป€นหนทางไปสูs Dead Man’s Island ซ่งึ เป€นทางท่คี ณุ จะตดิ อยใูg นน้นั ! แผนทข่ี องคณุ ควรจะเปนz ดงั น:้ี หนาq 118

ไพสy ำหรับกจิ กรรมตวั อยyาง หนาq 119

ไพสy ำหรับกจิ กรรมตวั อยyาง หนาq 120

กจิ กรรม ใหqนักเรียน 7 คน เป€นเกาะ ซึ่งจะตqองถือไพsของแตsละเกาะที่ซsอนคำสั่งไวqดqานหลัง สsุม ตำแหนsงของแตsละคนใหยq ืนกระจายอยูsรอบบรเิ วณสนามหรือหqอง นักเรียนทีเ่ หลือจะไดรq บั แผนที่ ที่วsางเปลsาและจะตqองสำรวจทางอยsางระแวดระวังจาก Pirate’s Island ไปยัง Treasure Island (ควรสsงนักเรยี นออกไปทีละคนเพ่ือไมใs หนq ักเรยี นคนอ่ืนไดรq ทqู างกอs น) ทางลัด: สำรวจมากกวsา 1 ทางเดิน แผนทท่ี ส่ี มบูรณเr ปzนดังแสดง: คำถามทตี่ ามมา ทางไหนท่ีไวทสี่ ุด? ทางไหนท่ีชาq ท่สี ุด? ทางบางทางอาจเดินทางเป€นวงวน จงแสดงตัวอยาs ง (เชsน BBBABAB และ BBBABBABAB ทางท้ัง 2 ไปถงึ Treasure Island) หนาq 121

ชีทกจิ กรรม : หาทางสขsู ุมทรัพย/บนเกาะมหาสมบัติ หนาq 122

ต^นแบบ: ไพyเกาะ (1/4) หนาq 123

ต^นแบบ: ไพyเกาะ (2/4) หนาq 124

ต^นแบบ: ไพyเกาะ (3/4) หนาq 125

ต^นแบบ: ไพyเกาะ (4/4) หนาq 126

ออโตมาตา^ สถานะจำกดั อีกวธิ หี นง่ึ ในการวาดรูปแผนทนี่ ้ันเป€นเชนs น:ี้ หมูsเกาะตาs งๆ จะแทนดqวยวงกลมทีม่ ตี ัวเลขอยูs และเกาะสุดทqายจะแทนดวq ยวงกลมสองวง เสqนทางไหนที่เรา จะสามารถใชใq นการเดนิ ทางไปยงั เกาะสดุ ทาq ยไดq?(เปน€ การดที ่ีจะสำรวจส่งิ เหลาs น้ีโดยการพจิ ารณาตวั อยsางเชsน เสqนทาง “A” สามารถนำไปถึงเกาะสุดทqายไดqหรือไมs แลqวกรณี “AA”, “ABA” หรือ “AABA” ลsะ? รูปแบบ ทั่วไปของแตsละกรณเี ปน€ ยงั ไงบาq ง?) วิธีทำ: แผนที่ /ขqอ (a) จะไปยงั เกาะสดุ ทqาย (เลข 2) ไดกq ต็ อs เม่ือจำนวนของ A นั้นเปน€ เลขขี่ (เชsน AB, BABAA, AAABABA ฯลฯ) แผนที่/ขqอ (b) จะไปยังเกาะสุดทqาย (เลข 1) ก็ตsอเมื่อเลือก A กับ B สลับกันไปเรื่อยๆ (เชsน AB, ABAB, ABABAB ฯลฯ) แผนท่ี/ขqอ ( c) จะไปยงั เกาะสดุ ทาq ย (เลข 2) ก็ตsอเมอ่ื มี B อยsางนqอยหนงึ่ ตวั (ตัวอยาs งท่ีไมsสามารถไปเกาะ สดุ ทาq ยไดqคอื A, AA, AAA, AAAAA ฯลฯ) หนาq 127

แบบฝšกหดั กิจกรรม : เกาะสมบตั ิ คุณสามารถซsอนสมบัติของคุณไดดq ีแคไs หน? คุณสามารถทำใหqหาสมบัติไดqยากแคsไหน? ถึงเวลาท่ีคณุ จะสรqาง แผนทีเ่ องแลวq ! 1. ภาพดงั กลsาวนี้จะเปน€ แนวคิดท่ซี ับซอq นมากขึ้นในการแสดงแผนท่ี ซง่ึ ในภาพนี้จะเปน€ แผนท่ีอนั เดียวกันกับ แบบฝŸกหัดครัง้ กsอน นักวิทยาศาสตร/คอมพิวเตอร/ใชวq ิธีการนี้ซึ่งงาs ยและรวดเร็วในการออกแบบเสqนทาง สำหรบั รปู แบบของพวกเขา วาดแผนพ้ืนฐานของคณุ เองแบบตัวอยาs งดqานบนเพอ่ื ใหqคณุ เห็นเสqนทางทเี่ รอื โจรสลดั ของคุณจะสามารถ ใชqในการเดนิ ทางไดq หลังจากนั้นใหqคุณสราq งแผนทีเ่ ปลsาๆ กับการด/ เกาะของคณุ เอง ลำดับเสนq ทางที่มี ประสิทธิภาพทด่ี ที ส่ี ุดในการเดินทางไปยงั เกาะสมบตั ขิ องคุณคอื เสqนไหน? 2. เพ่ือนๆ ของคุณทำตามแผนทข่ี องคุณไดqดีแคsไหน? ลองนำลำดบั ตัวอยsางของ A และ B ใหกq บั พวกเขาแลqว ดวู sาเขาสามารถไปยังเกาะท่ีถูกตqองไดqหรอื ไมs คณุ สามารถนำไอเดยี น้ี (ออโตมาตqาสถานะจำกัด)ไปสรqางเกมหรอื โจทยป/ ญ' หาตาs งๆ ไดqมากมาย 3. นค้ี ือวธิ ีสรqางประโยคโดยการเลือกเสนq ทางแบบสมsุ ผsานผนทแ่ี ละสังเกตคำที่พบเหน็ ระหวาs งทาง คุณลองใชไq อเดียเดียวกันเพอ่ื สรqางเน้ือเรอื่ งขึน้ มา บางทคี ุณอาจจะสามารถแตsงเรื่องตลกกเ็ ป€นได!q หนาq 128

แบบฝšกหดั กิจกรรม : เหรยี ญลึกลบั เพือ่ นๆของคณุ ไดqดาวนโ/ หลดเกมมาจากอินเตอรเ/ น็ตโดยทีเ่ กมน้จี ะมหี sุนยนต/คอยโยนเหรียญและผูqเลsน จะตอq งเดาวาs ผลลพั ธ/จะออกมาเปน€ หัวหรือกqอย มนั นอาจจะดเู หมือนเปน€ เกมท่งี sายเพราะโอกาสชนะก็ คอื 50-50 แตsนั้นกเ็ ปน€ แคสs ิ่งท่ีผqูเลsนคิดเทาs นั้น! หลังจากทเ่ี ลนs ไปหลายรอบแลวq ผqเู ลนs ก็เริ่มจะสงั เกตไดq วsามันมีรูปแบบบางอยsางในการโยนเหรียญ พวกเขาก็เลยตัดสินใจที่สำรวจเกมโดยการจดผลลัพธ/ ทั้งหมดออกมาซ่งึ ไดqออกมาตามน้ี (h = หัว, t = กอq ย) hhthhthhhtthhhhtthttthhhhhthhhttthhhttthhhhhhtth ttttthtthttthhhtthhhthhhhhhhhhtthhhtttthhhhhttttt tt คุณสามารถหารปู แบบทีท่ ายไดqหรือไมs มี 'แผนท่ี' ซง่ึ จะอธิบายถึงลำดับของการโยนเหรียญ ดวู าs คณุ สามารถคดิ ออกไดหq รอื ไมs (คำแนะนำ: มีเพียง 4 เกาะ) หนqา 129

ทง้ั หมดนเ้ี กยี่ วกับอะไร? ออโตมาตqาสถานะจำกัดใชqในวิทยาการคอมพิวเตอร/เพือ่ ชsวยใหqคอมพิวเตอร/ประมวลผลลำดับตามตัวอักษร หรือตามเหตกุ ารณ/ ตวั อยsางงsายๆ คือเมอื่ คณุ หมุนหมายเลขโทรศัพท/และคณุ ไดqรับขอq ความวาs \"กด 1 สำหรับขqอมลู นี้ ... กด 2 เพ่ือ ดวู าs ... กด 3 เพอ่ื พดู คยุ กบั ผดqู ำเนนิ การ\" การกดป¸ุมของคณุ คือขอq มลู สำหรับออโตมาตาq สถานะจำกัดทอ่ี ยsูอกี ฝง¢' ของการสือ่ สาร บทสนทนาอาจคอs นขqางงsายหรือซบั ซอq นมาก บางครัง้ คณุ อาจจะตดิ อยูsในลปู ทไ่ี มมs สี ิ้นสุด หาก เกดิ กรณนี ้ีนั้นแปลวsาอาจจะเกิดขqอผดิ พลาดในการออกแบบระบบและอาจเป€นเร่อื งท่ีนsาผดิ หวงั สำหรับผโูq ทร! อีกตวั อยาs งหนง่ึ คอื เม่ือคุณไดรq ับเงินสดจากเครือ่ งเอทีเอ็ม โปรแกรมในคอมพวิ เตอร/ของเคร่ืองชsวยใหqคุณผsาน ลำดบั ของเหตุการณ/ ภายในโปรแกรมทุกลำดบั ท่ีเปน€ ไปไดqจะถูกเกบ็ ไวใq นออโตมาตqาสถานะจำกัด ทกุ คีย/ที่คุณ กดจะนำหsุนไปยงั สถานะอ่นื บางสถานะจะมคี ำแนะนำสำหรับคอมพวิ เตอรเ/ ชsน แจกจsายเงินสด\"100 เหรียญ \" \"หรือ \"พิมพใ/ บแจqงยอด\" หรือ \"นำบัตรเงนิ สดออก บางโปรแกรมจัดการกับประโยคภาษาอังกฤษโดยใชqแผนที่เชsนเดียวกับที่หนqา 124 พวกเขาสามารถสรqาง ประโยคดqวยตวั เองและประมวลผลประโยคที่ผูใq ชพq ิมพ/มาไดq ในป‹ 1960 นกั วิทยาศาสตรด/ qานคอมพวิ เตอร/เขยี น โปรแกรมชอื่ ดงั วsา \"Eliza\" (มาจาก Eliza Dolittle) ท่ีมีการสนทนากับผูคq น โปรแกรมน้ีจะปลอมตัวเป€นนักจิต อายุรเวทและจะมาพรqอมกับคำถามเชsน \"บอกฉันเกี่ยวกบั ครอบครวั ของคุณ\" และ \"ทำตsอไป\" แมqวsาจะไมไs ดq \"เขqาใจ\" อะไรก็ตาม แตsก็นsาเชื่อถือเป€นอยsางมากสำหรับโปรแกรม - บางคนคิดวsาพวกเขากำลังคุยกับนกั จติ อายรุ เวชคนหนงึ่ จริงๆ ถึงแมqคอมพิวเตอร/จะไมsคsอยเขqาใจภาษามนษุ ย/ แตsก็สามารถใชqภาษาเทียมไดอq ยsางงาs ยดาย ภาษาประดษิ ฐ/ท่ี สำคญั อยาs งหน่งึ คือภาษาเขียนโปรแกรม คอมพวิ เตอร/ใชอq อโตมาตqาสถานะจำกัดในการอsานในโปรแกรมและ แปลลงในรปู แบบของคอมพวิ เตอรข/ ้ันพ้นื ฐานซึ่งจะสามารถ \"ดำเนินการ\" ไดโq ดยตรงจากคอมพวิ เตอร/ หนqา 130

วธิ ที ำและคำใบ^ เกมเหรยี ญลึกลับ (หน^า 129) เกมเหรียญลกึ ลบั ใชแq ผนทตี่ sอไปน้ีในการโยนเหรยี ญ: ถqาคณุ ทำตามน้ันคุณจะเห็นวาs การโยนเหรียญครั้งแรกของทงั้ สองมผี ลเหมือนกัน หนาq 131

กิจกรรมที่ 13 ลำดบั การเดนิ ขบวน – ภาษาโปรแกรมมิง่ สรปุ คอมพิวเตอรม/ กั ถกู ตั้งโปรแกรมโดยใชq \"ภาษา\" ซ่ึงเปน€ คำศัพทท/ ่ีจำกดั และเปน€ คำส่งั ทส่ี ามารถปฏิบตั ติ ามไดq สิ่ง ที่นsาผิดหวังมากที่สุดประการหนึ่งเกี่ยวกับการเขียนโปรแกรมคือคอมพิวเตอรม/ ักปฏิบัติตามตลอดแมqวsาจะ กsอใหเq กดิ ผลลัพธ/ทไี่ มดs กี ต็ าม กจิ กรรมนีท้ ำใหนq กั เรียนมปี ระสบการณด/ าq นการเขียนโปรแกรมน้ี การเชื่อมโยงหลกั สูตร ü ภาษาอังกฤษ: การฟง' ระหวsางบคุ คล ความสามารถ ü การใหคq ำแนะนำและทำตามคำแนะนำ อายุ ü 7 ปข‹ ึ้นไป วสั ดุ คณุ จะต^องการ: ü การ/ดทมี่ ีรูปภาพเชsนรปู ภาพทีแ่ สดงในหนqา นกั เรียนแตyละคนจะต^องมี: ü ดินสอกระดาษและไมqบรรทัด หนาq 132

หนาq 133

ลำดบั การเดนิ ขบวน คำนำ พดู คุยวsาจะดหี รือไมถs qาคนอ่ืนทำตามคำแนะนำ ตัวอยsางเชsนจะเกิดอะไรขึ้นถqาคุณช้ีไปที่ประตูที่ป„ดและพูดวsา \"เดนิ ผsานประตนู ้นั \"? คอมพวิ เตอร/ทำงานโดยปฏิบัติตามรายการคำสง่ั ถงึ แมqวาs จะไมsสมเหตุสมผลกต็ าม! ตวั อยาy งการสาธิต ดวู าs นักเรียนสามารถวาดภาพจากคำสงั่ เหลาs นไ้ี ดหq รือไมs 1. วาดจดุ ตรงกลางหนqากระดาษของคุณ 2. เร่ิมตนq ทม่ี มุ บนซqายสุดของกระดาษ ใชqไมบq รรทัดวาดเปน€ เสนq ตรงผาs นจุดที่วาดไวqตรงกลาง ไปจนถึงมมุ ลาs ง ขวามอื 3. เรม่ิ ตนq ทมี่ มุ ลาs งซqายสดุ ของกระดาษ ใชไq มบq รรทดั วาดเปน€ เสqนตรงผาs นจุดทีว่ าดไวqตรงกลาง ไปจนถึงมมุ บน ขวามอื 4. เขยี นชื่อของคุณในรปู สามเหลี่ยมตรงกลางดาq นซาq ยมอื ของกระดาษ ผลลพั ธค/ วรมีลักษณะดงั น้ี: หนาq 134

กิจกรรม เลอื กนกั เรียนมา 1 คนและใหรq ปู ภาพกบั นกั เรียนคนน้ัน (เชนs แสดงในหนาq 130) ใหqนักเรยี นท่ถี ูกเลือกอธิบาย ภาพกบั นักเรยี นคนอืน่ ๆ โดยใหนq ักเรยี นคนอน่ื ทำตามเพ่อื ทีจ่ ะใหวq าดภาพเดยี วกนั นักเรยี นสามารถถามคำถาม เพือ่ ชีแ้ จงคำอธิบายไดq จุดประสงค/คอื เพื่อดวู าs นักเรียนสามารถทำไดqอยsางรวดเรว็ และถกู ตอq งหรือไมs ใหqลองทำกิจกรรมนี้อีกคร้งั โดยที่คร้งั นี้ไมใs หนq ักเรียนคนอื่นๆ ถามคำถามนักเรยี นท่อี ธิบายรปู ภาพ แนะนำใหqใชq รปู งsายๆ เนอื งจากวsานักเรียนน้ันหลงงาs ยมาก ทีนี้ลองใหqนักเรยี นที่อธิบายภาพนั้นไปยืนอยูsดqานหลังหนqาจอบางอยsาง เพื่อที่จะไมsใหqสือ่ สารกับนักเรียนคน อื่นๆ นอกจากการอธบิ ายภาพ ช้ีใหเq ห็นวาs รูปแบบการสื่อสารนเี้ ปน€ แบบทีผ่ เqู ขียนโปรแกรมคอมพิวเตอร/พบมากท่สี ดุ เม่ือเขียนโปรแกรม พวก เขาใหqคำส่ังกับคอมพวิ เตอร/และจะไมsสามารถเห็นผลลัพธไ/ ดทq นั ที ใหqนักเรยี นวาดรปู และเขียนคำอธบิ ายของตนเอง ทดลองทำกจิ กรรมโดยเป€นคหูs รือทง้ั ชัน้ เรยี น รปู แบบ • เขียนคำสงั่ ในการสรqางกระดาษปาเป›า • เขียนคำสงั่ เก่ยี วกับวธิ เี ดินทางไปยงั สถานทต่ี sางๆ รอบโรงเรยี นโดยใชคq ำแนะนำเชsน \"ไปขqางหนาq x เมตร\" \"เลยี้ วซqาย\" (90 องศา) หรอื \"เลยี้ วขวา\" (90 องศา) ฯลฯ นักเรยี นควรทดสอบและปรับแตsงคำสงั่ จนกวsาจะมีผลตามทต่ี qองการ • เกมตาบอด ปด„ บังนักเรียนและใหนq ักเรียนคนอ่นื นำพวกเขาไปรอบ ๆ หqอง หนาq 135

ทัง้ หมดนเี้ กยี่ วกบั อะไร? คอมพิวเตอร/ดำเนนิ การตามคำสัง่ ทเี่ รยี กวsาโปรแกรมซึง่ เขยี นขึ้นเพอ่ื ดำเนินงานเฉพาะ โปรแกรมจะเขียนเป€น ภาษาทไ่ี ดqรับการออกแบบมาเปน€ พเิ ศษโดยมีชุดคำสงั่ ทีจ่ ำกดั เพอื่ บอกคอมพวิ เตอรว/ าs จะทำอยาs งไรและทำอะไร ไดบq qาง บางภาษาเหมาะสำหรบั วตั ถุประสงคบ/ างอยsางมากกวsาภาษาอ่ืน ไมsวsาพวกเขาใชqภาษาใดโปรแกรมเมอร/ตqองเชี่ยวชาญในการระบุวsาตqองการใหqคอมพิวเตอร/ทำอะไร คอมพิวเตอร/จะทำตามคำสงั่ ตลอด ถึงแมqวsาจะเปน€ คำส่ังท่ีไรqสาระก็ตาม เป€นสิ่งสำคัญที่โปรแกรมถูกเขียนออกมาดี ขqอผิดพลาดเล็กๆ อาจทำใหqเกิดป'ญหาไดqมาก ลองนึกภาพผลที่ ตามมาของขqอผดิ พลาดในโปรแกรมของคอมพวิ เตอร/ในการเป„ดตัวกระสวยอวกาศ โรงไฟฟ›านิวเคลียร/ หรือ สัญญาณในรถไฟ ขqอผิดพลาดทั่วไปเรียกวsา “bug” เพื่อเป€นเกียรติ (มกี ารกลsาว) ของมอดที่เมื่อถูกนำออก (\"debugged\") จากการถsายทอดไฟฟ›าในเครื่องคำนวณอเิ ลก็ ทรอนกิ ส/ตqนป‹ ค .ศ.1940 โปรแกรมทซ่ี บั ซqอนมักจะมีขอq ผดิ พลาดมากข้ึน เร่ืองน้ีกลายเปน€ ประเด็นสำคญั คร้งั ทสี่ หรฐั ฯกำลงั ทำงานอยูsใน โครงการยทุ ธศาสตร/ปอ› งกัน (\"สตารว/ อร/ส\") ซง่ึ เปน€ ระบบควบคมุ โดยคอมพวิ เตอร/ซึ่งต้ังใจจะป›องกันไมsใหqเกิด การโจมตดี qวยอาวุธนิวเคลียร/ นักวทิ ยาศาสตรค/ อมพิวเตอรบ/ างรายอqางวsาไมsสามารถทำงานไดqเน่ืองจากความ ซับซqอนและความไมsสามารถไวqใจไดqโดยธรรมชาติของซอฟต/แวร/ที่จำเป€น ซอฟต/แวร/ตqองไดqรับการทดสอบ อยาs งรอบคอบเพือ่ หาขอq ผดิ พลาดใหqมากทสี่ ุดเทาs ท่จี ะเป€นไปไดqและจะไมสs ามารถทดสอบระบบน้ีไดqเน่ืองจาก จะตอq งมกี ารยิงขปี นาวธุ ทป่ี ระเทศสหรฐั อเมรกิ าเพอื่ ใหqแนsใจวาs ไดผq ลดี! หนาq 136

บทที่ 4 ปญ• หาที่ยาก – ไมสy ามารถจดั การหรอื ควบคมุ ได^ หนาq 137

ป•ญหาทไี่ มyสามารถควบคุมหรือจัดการได^ ถาq ถามวาs มปี 'ญหาที่ยากเกินไปสำหรับคอมพิวเตอร/หรอื ไม?s คำตอบคือ ใชs เราจะเหน็ ในกิจกรรมท่ี 20 วsาการ พูดคยุ สนทนาเป€นส่ิงทค่ี อมพิวเตอรไ/ มสs ามารถทำไดq ไมใs ชsเพราะพวกเขาไมสs ามารถพดู ไดq แตเs ป€นเพราะวาs พวก เขาไมsสามารถเขาq ใจหรอื คดิ ถงึ สิง่ ทีเ่ หมาะสมท่จี ะพูดไดq แตนs ัน่ ไมsใชปs ญ' หาใหญsทีเ่ รากำลงั พดู ถงึ อยsทู ่ีน่ี – ไมsใชs วsาคอมพิวเตอร/ไมสs ามารถมกี ารสนทนาไดq แตsเราไมsทราบวsาเราทำการสนทนากันอยาs งไร เราจึงไมสs ามารถ บอกไดqวsาคอมพิวเตอร/ควรทำอยsางไร แตsในสsวนนี้เราจะดปู 'ญหาที่บอกไดงq าs ยวsาคอมพิวเตอร/จะทำอะไรโดย การเขียนโปรแกรม แตsคอมพิวเตอร/ไมsสามารถทำในสิ่งที่เราตqองการไดqเพราะใชqเวลานานเกินไป การซ้ือ คอมพวิ เตอรท/ เี่ รว็ ขึน้ ไมsชsวยมากเทาs ไหรs เพราะถึงแมqคอมพวิ เตอร/จะเร็วข้ึนอีกรอq ยเทาs ก็อาจจะยงั ตqองใชqเวลา นับลqานป‹อยูsดี นั่นคือสิ่งที่คุณเรียกวsาเป€นป'ญหาอยsางหนึ่งที่ตqองใชqเวลานานกวsาอายุการใชqงานของ คอมพวิ เตอรท/ ่เี รว็ ทสี่ ุดเทsาทจี่ ะเปน€ ไปไดใq นการแกqป'ญหา! กจิ กรรมในสsวนท่ี 2 เกี่ยวกบั อัลกอรทิ ึมแสดงใหqเหน็ วsาคุณควรหาวธิ ที ีจ่ ะทำใหโq ปรแกรมคอมพิวเตอร/ทำงานไดq มีประสทิ ธิภาพมากขึ้น ในสsวนนีเ้ ราจะพิจารณาถึงป'ญหาที่ไมsมีวธิ ีการแกqป'ญหาที่มีประสทิ ธิภาพ ป'ญหาที่ใชq เวลานับลqานคอมพิวเตอร/ในการแกqป'ญหา และเราจะพบวsาอะไรคือความลึกลับที่ยิ่งใหญsที่สุดในวิทยาการ คอมพวิ เตอร/วันนี้ นน่ั คอื ไมมs ใี ครรqวู sามีวิธแี กqไขป'ญหาเหลsานไี้ ดqอยาs งมปี ระสทิ ธิภาพมากขนึ้ อาจเป€นไดqวsาไมsมี ! ใครรูqวิธีที่ดียังหรืออาจเป€นไดqวsาไมsมีทางที่ดี เราไมsทราบ และนั่นไมsใชsทั้งหมด มีหลายป'ญหาที่แมqวsาจะดู แตกตาs งกันอยาs งสิน้ เชิงแตกs ็มคี วามเทsาเทียมกันในแงsทวี่ าs หากมีการคqนพบวธิ ีท่มี ีประสิทธิภาพในการแกqป'ญหา หนึ่งขqอก็สามารถแปลงเป€นวิธีที่มีประสิทธิภาพในการแกqป'ญหาเหลsานี้ทั้งหมด ในกิจกรรมเหลsานี้คุณจะไดq เรียนรqเู กย่ี วกับป'ญหาเหลาs นี้ สำหรบั ครู สวs นนม้ี ีอยูs 3 กิจกรรม กิจกรรมแรกจะเกยี่ วขqองกบั การระบายสแี ผนทแ่ี ละการนบั จำนวนสีท่ีตอq งการเพอื่ ทำใหq ประเทศเพื่อนบqานแตกตsางกัน กิจกรรมที่สองตqองการความสามารถในการใชqแผนที่ถนนที่เรียบงsายและ เกี่ยวขqองกับการวางรถตูไq อศกรมี ที่มุมถนนเพือ่ ใหqไมsมีใครไปไกลเกินไปที่จะไดqรับไอศกรีม กิจกรรมที่สามคือ กจิ กรรมกลางแจqงทใี่ ชqเชือกและหมดุ เพ่ือสำรวจวsาจะทำใหเq ครือขาs ยสัน้ ๆ เชื่อมตsอชดุ ของจุดใด กิจกรรมนใี้ หqความรสqู กึ ท่เี ป€นประโยชนเ/ กย่ี วกบั ความซบั ซอq นของปญ' หาวsาป'ญหาทเี่ กิดข้นึ ไดงq าs ยเพยี งใดแตsการ แกqป'ญหานั้นก็ไมsสามารถแกqไดqงsายๆ ถึงแมqวsาป'ญหาเหลsานี้จะไมsลึกซึ้ง แตsก็เป€นคำถามที่เป€นประโยชน/ซึ่ง เกิดขึ้นในกิจกรรมประจำวันเชsนการทำแผนที่ ตารางเวลาในโรงเรียน และการสรqางถนน การคำนวณอยูsบน ความคิดที่เรียกวsา \"NP-completeness\" ที่อธิบายไวqใน ‘มันเกี่ยวกับอะไร?’ สsวนทqายของแตsละกิจกรรม หนาq 138

แมวq าs กจิ กรรมเหลsานส้ี ามารถแกไq ขไดตq ามลำดับใดก็ตามสsวนตsางๆเหลาs นมี้ วี ัตถปุ ระสงคเ/ พือ่ ใหอq าs นตามลำดับท่ี ปรากฏ เม่ือถึงจุดจบแลวq คุณจะไดqรบั ความสนใจจากคำถามท่ีสำคญั ท่ีสุดในวิทยาการคอมพิวเตอร/ในปจ' จบุ นั ชือ่ ทางเทคนิคสำหรบั สวs นนค้ี ือ \"intractability\" เนือ่ งจากปญ' หาที่ยากท่จี ะแกqปญ' หาเรยี กวาs intractable คำ ท่ีมาจากภาษาละติน tractare หมายถึงการวาดหรือลากนำไปสsูการใชqงานทท่ี นั สมัยของราs งกายเป€นเรอื่ งงาs ยท่ี จะจัดการอsอนโยนหรืออsอนนqอม ปญ' หาทยี่ ากลำบากคอื การท่ีไมสs ามารถจดั การกับปญ' หานั้นไดqงsายเพราะจะ ใชqเวลานานในการหาคำตอบ ถึงแมqวsามันอาจฟง' ดูลึกลับ แตsความสามารถในการหาคำตอบกับโจทยย/ ากๆ ก็ เป€นเรื่องที่นsาสนใจเป€นอยsางมากเนื่องจากความกqาวหนqาในดqานนี้จะมีสsวนสำคัญในการวิจัยหลายๆ อยsาง ตวั อยsางเชsนรหัสลบั สsวนใหญsใชคq วามยากลำบากในการแกปq ญ' หา และผูqกระทำผดิ ท่สี ามารถแกqปญ' หาไดqอยาs งมี ประสิทธิภาพอาจมีวันถอดรหัสลับและขายไดqหรือเพียงแคทs ำธุรกรรมปลอม เราจะมองส่ิงเหลsานี้ในสsวน V- Cryptography หนาq 139

กจิ กรรมท่ี 14 ผู^ทำแผนที่ทน่ี าy สงสาร - กราฟสี สรุป ป'ญหาการเพ่ิมประสทิ ธภิ าพหลายอยsางเก่ียวขอq งกบั สถานการณ/ที่เหตุการณ/บางอยาs งไมsสามารถเกิดขึน้ ในเวลา เดียวกันหรือท่ีสมาชิกในชุดของวัตถุไมsสามารถอยsูตดิ กันไดq ตัวอยsางเชนs ทุกคนทีพ่ ยายามทำตารางเวลาเรียน หรือการประชุมจะพบป'ญหาในการสราq งความพึงพอใจใหqกบั ทุกคนที่เก่ียวขqอง หลายป'ญหาเหลาs นี้คลqายกบั ป'ญหาการระบายสขี องแผนท่ีซึง่ ตqองเลือกสีสำหรับประเทศบนแผนที่ในลกั ษณะที่ทำใหqประเทศที่มพี รมแดน ตดิ กนั มีสแี ตกตาs งกนั กิจกรรมน้เี กีย่ วกบั ป'ญหาดังกลsาว การเช่อื มโยงหลกั สตู ร ü คณติ ศาสตร:/ ตวั เลข - สำรวจตัวเลขในฐานอนื่ ๆ แทนตวั เลขในฐานสอง ü คณิตศาสตร/: พีชคณิต - ตsอรูปแบบลำดับและอธิบายกฎสำหรับรูปแบบนี้ และความสัมพันธ/ใน รปู แบบของเลขยักกำลงั สอง ความสามารถ ü การแกปq ญ' หา ü เหตผุ ลเชิงตรรกะ ü รqูขัน้ ตอนและความซับซอq นของอัลกอริธมึ ü การสอ่ื สารขอq มูลเชิงลกึ อายุ ü 7 ปข‹ ้นึ ไป วสั ดุ ü ไวทบ/ อรด/ หรอื บอรด/ ท่ีสามารถเขยี นลงไดqคลqายกัน นกั เรยี นแตsละคนจะตอq งมี: ü กระดาษเวริ ก/ ชีทหนง่ึ แผsนหรือมากกวsา ü เครือ่ งหมายระบขุ นาดเล็กทีเ่ คลื่อนท่ไี ดq (เชนs เคานเ/ ตอรห/ รอื ชิปโปÈกเกอร)/ ü ดินสอสสี ่แี ทsงท่ีแตกตาs งกัน หนาq 140

ระบายสีกราฟ (Graph Coloring) คำนำ กิจกรรมนเ้ี ปน€ การเลาs เรอ่ื งราวทีน่ ักเรยี นไดรq ับหนqาท่ีใหqชsวยผูqทำแผนทีซ่ ึ่งเป€นผูqระบายสใี หqประเทศตาs งๆ บนแผนที่ งานดงั กลsาวนไี้ มsสนวาs แตsละประเทศจะมสี อี ะไรตราบเทาs ทปี่ ระเทศที่มพี รมแดนติดกนั นนั้ เปน€ คนละสกี เ็ พียงพอ ตัวอยsางเชนs แผนทีน่ ้ีแสดงส่ีประเทศ ถqาเราระบายสีแดงใหq Northland แปลวsา Westland และ Eastland จะไมสs ามารถเปน€ สีแดงไดเq น่ืองจาก ชายแดนของพวกเขากบั Northland นั้นติดกันซ่งึ จะทำใหยq ากที่จะเห็น แตsเราสามารถระบายสเี ขยี วใหq Westland และ Eastland ไดเq น่อื งจาก ทั้งสองประเทศไมsไดqมีพรมแดนติดกัน (ถqาทั้งสองประเทศพบกันที่จุด เดียวพวกเขาจะไมsถือวsาเป€นชายแดนและดqวยเหตุนี้จึงสามารถทำสี เดียวกันไดq) นั้นแปลวsา Southland ก็สามารถเป€นสีแดงไดqและเรา ตอq งการเพียงแคsสองสีเทาs นน้ั สำหรบั แผนที่ ในเร่ืองราวของเราผทูq ำแผนทเ่ี ปน€ คนยากจนและไมsสามารถซอื้ ดินสอสมี ากมายดังน้ันเราตqองการใหqใชqสี ใหqนqอยที่สดุ เทาs ท่จี ะเป€นไปไดq การสนทนา อธบิ ายป'ญหาทีน่ ักเรยี นจะตอq งทำและแสดงกระบวนการระบายสีบนกระดานดำ แจกแผsนงานแรกใหกq บั นักเรยี น แผนทน่ี ้สี ามารถทำสไี ดอq ยาs งถกู ตอq งโดยใชเq พยี งสองสีเทาs นั้น แมวq าs การ จำกัด จำนวนสีใหqเหลือเพียงสองขqออาจเป€นเรื่องทีท่ qาทาย แตsจะคsอนขqางงsายเมื่อเทียบกับแผนที่ที่ตqองใชสq ีมากข้นึ เนอ่ื งจากมีทางเลอื กนอq ยมากเก่ียวกับสีทแ่ี ตลs ะประเทศสามารถทำไดq ใหqนกั เรยี นพยายามทำแผนทใ่ี หqมเี พียงสองสเี ทsาน้นั ในกระบวนการนพ้ี วกเขาอาจคนq พบกฎ \"มีทจ่ี ะเป€น\": เม่ือ ประเทศหนึ่งมีสอี ยูsประเทศที่มีพรมแดนตดิ ๆ กันจะตqองเป€นสีตรงขqาม กฎนี้ถูกนำมาใชqซ้ำๆ จนกวsาประเทศ ทั้งหมดจะมีสีทีถ่ ูกตqอง ถqานักเรียนสามารถคนq พบกฎน้ีไดqดqวยตัวเอง จะทำใหพq วกเขาเขqาใจถึงขั้นตอนน้ีไดดq ี ยง่ิ ข้ึน หนqา 141

เม่ือนกั เรียนทำกิจกรรมนเ้ี สรจ็ สามารถมอบแผsนงานตอs ไปใหqพวกนักเรียนลองไดq นักเรียนอาจพบวsาควรใชเq คาน/เตอรส/ ีแทนการระบายสปี ระเทศทันทเี นอื่ งจากชsวยใหพq วกเขาเปลย่ี นความคิดไดq งาs ยขึน้ สำหรับนักเรียนที่เคยทำแลqว ลองใหqพวกเขาอธิบายวsาสามารถรูqจำนวนสีที่ตqองใชqนqอยที่สุดไดqอยsางไร ตัวอยsางเชsนตqองมีอยsางนqอยสามสีสำหรับแผนทีน่ ี้เนือ่ งจากมีกลุsมสามประเทศ (ใหญsที่สุดสามแหsง) ซึ่งแตลs ะ แหงs มพี รมแดนกบั อกี สองประเทศ ถqามีนักเรยี นคนไหนทท่ี ำกจิ กรรมน้ีเรว็ ลองใหพq วกเขาลองคดิ คqนแผนทที่ ต่ี อq งใชสq ที แ่ี ตกตาs งกันหqาสี ตอนนไ้ี ดมq ี การพสิ ูจน/แลวq วsาแผนทีน่ งึ สามารถมีสไี ดqเพยี ง 4 สเี ทาs นัน้ ดงั นั้นงานน้จี ะทำใหพq วกนกั เรยี นใชเq วลาเปน€ อยsาง มาก! จากประสบการณ/ของเรานกั เรยี นจะไดqพบกับแผนทที่ พี่ วกเขาเชอ่ื วsาตqองใชสq หี qาสี แตsแนนs อนวsามนั เปน€ ไปไดqเสมอทจ่ี ะหาทางแกแq ผนทขี่ องพวกเขาใหเq หลอื เพียงสส่ี ีไดq หนqา 142

ใบงานกจิ กรรม : ระบายสแี ผนภาพ 1 ระบายสีลงบนประเทศในแผนทีน่ ้ี ดqวยสที ่นี qอยทีส่ ุดเทsาทจี่ ะเป€นไปไดq แตตs อq งแนใs จวาs ไมมs ีสองประเทศที่ติดกัน ใชqสเี ดยี วกนั หนqา 143

ใบงานกิจกรรม : ระบายสีแผนภาพ 2 ระบายสลี งบนประเทศในแผนท่ีน้ี ดqวยสีทนี่ qอยทส่ี ุดเทาs ทจ่ี ะเป€นไปไดq แตตs qองแนsใจวsาไมมs ีสองประเทศที่ติดกัน ใชสq ีเดยี วกัน หนาq 144

ใบงานกิจกรรม : ระบายสีแผนภาพ 3 ระบายสลี งบนประเทศในแผนท่ีน้ี ดqวยสีทนี่ qอยทส่ี ุดเทาs ทจ่ี ะเป€นไปไดq แตตs qองแนsใจวsาไมมs ีสองประเทศที่ติดกัน ใชสq ีเดยี วกัน หนาq 145

ใบงานกิจกรรม : ระบายสีแผนภาพ 4 ระบายสลี งบนประเทศในแผนท่ีน้ี ดqวยสีทนี่ qอยทส่ี ุดเทาs ทจ่ี ะเป€นไปไดq แตตs qองแนsใจวsาไมมs ีสองประเทศที่ติดกัน ใชสq ีเดยี วกัน หนาq 146

ความหลากหลาย และการขยายความ มีวิธีงsายๆที่ใชqในการสรqางแผนที่ที่ตqองการ เพียงแคs 2 สี ดังรปู ขวามือนี้ แผนทนี่ ี้วาดโดย การใชqการทับซqอนกันของเสqนโคqงป„ดหลาย เสqน (เสqนที่จุดเริ่มตqนชนกับจุดสิ้นสุด) คุณ สามารถวาดเสqนโคqงเหลsานี้กี่รูปก็ไดqซqอนทับ กบั รปู อืน่ ๆ และคุณกจ็ ะไดแq ผนทที่ ่ีใชqเพียง 2 สีในการระบายไดq นักเรียนสามารถทดลอง สราq งแผนทแี่ บบนไ้ี ดq เพียงแคs 4 สีก็มักจะเพยี งพอในการระบายสี แผนท่ีทถี่ กู เขยี นลงบนกระดาษ หรอื ทรงกลม (หรือก็คือ ลูกโลก) อาจแปลกใจ(ขณะที่ นักวิทยาศาสตร/ถูกจqางใหqทำ) ตqองใชqกี่สีใน การระบายแผนที่ที่ถูกเขียนลงบนรูปรsาง แปลกประหลาด อยsางเชsน ทรงหsวงยาง (Torus) หรือก็คือทรงโดนัท ในกรณีนี้ 5 สี นsาจะเพียงพอ และ 5 สีก็เพยี งพอสำหรับทุก รปู นักเรียนอาจจะอยากทดลองกับมัน มีความหลากหลายในการทำใหqสนุกสนานในการระบายสีแผนที่ ซึ่งนำไปสsูหนทางทีป่ 'จจุบันเราก็ยังไมทs ราบ อยsางเชsน ถqาเราระบายสีลงบนแผนที่บนกระดาษดqวยตัวเราเอง ดังนั้นเราจะรูqวsาเราทำมันอยsางชาญฉลาด หรือไมs 4 สีก็จะเพียงพอในการระบาย แตsถqาสมมติแทนท่ีจะระบายคนเดียว เราก็ระบายกับเพือ่ นท่ีไมsคsอยรูq เรื่องหรือคนที่เป€นปรป'กษ/กัน สมมติวsาเราระบายสีไดqอยsางชาญฉลาดใขขณะที่เพ่ือนเราระบายเพียงแคsใหq ถูกตqองตามกฏ โดยเราจะสลับกันระบายสีลงบนแผนที่ ดqวยความฉลาดของเรา เราตqองการสีกี่แทsงบนโต¹ะ เพอ่ื ทีจ่ ะเพยี งพอกบั การระบายสีของเพอื่ นที่เพียงทำตามกฏแตsไมsฉลาดนัก(หรือไมกs ็คsอยจะลqมเรา) จำนวนที่ มากที่สุดนนั้ ไมsอาจทราบไดq ในป‹ ค.ศ.1992 มนั ไดqถูกพิสูจน/วsาใชสq เี ทียนเพียง 33 แทsงกพ็ อ และในป‹ ค.ศ.2008 ก็ถูกพิสูจน/อีกวsาใชเq พียงแคs 17 สีก็เพยี งพอ แตsเราก็ยังคงไมsรูวq sาจรงิ ๆแลวq ตqองการเทsาไรกนั แนs (ผูqเชีย่ วชาญ คาดเดาวsา ใชนq qอยกวsา 10 สีก็เพียงพอ) นักเรียนอาจสนุกกับการแสดงความเหน็ กับสถานการณน/ ้ี โดยเลsนเป€น เกมสองคน พยายามท่จี ะทำใหฝq ¸ายตรงขาq มใชqสีมากท่ีสดุ ในอีกความหลากหลายของการระบายแผนท่ี รqูจกั ในนาม การระบายสอี าณาจกั ร (empire coloring) เราเริ่ม จากมีกระดาษสองแผนs ทตี่ sางกันโดยมจี ำนวนประเทศเทาs กนั แตลs ะประเทศบนแผนทห่ี น่งึ (หรอื เรยี กวาs โลก) หนqา 147

ถกู จับคูsกบั หนงึ่ ประเทศในอีกแผนที่(ซง่ึ อาจเปน€ อาณานคิ มบนดวงจันทร)/ ท่เี พิ่มเติมจากขอq กำหนดการระบาย สใี หตq sางกันระหวาs งสองประเทศทต่ี ิดกนั แลวq (สำหรบั ทง้ั สองแผนท่ี) เราใหแq ตลs ะประเทศบนโลกตอq งระบายสี เดยี วกนั กับอาณานคิ มบนดวงจันทร/ เราตqองใชสq เี ทsาไรในการแกqปญ' หานี้ คำตอบยงั คงไมsมีใครทราบ หนqา 148

ทง้ั หมดนีเ้ กยี่ วกับอะไร? การระบายสแี ผนท่ีท่ีเราไดqลองทำกันมานน้ั สsวนสำคัญของกจิ กรรมนอี้ ยูsทกี่ ารหาจำนวนสีท่ีนqอยท่ีสุด—สอง, สาม, หรอื ส—่ี ท่ีจำเปน€ ตอq งใชใq นการระบายแผนทนี่ ั้นๆ การคาดเดาวsาทกุ แผนทสี่ ามารถระบายไดดq วq ยสเี พยี ง 4 สี ถูกคิดขึ้นเมื่อป‹ ค.ศ.1852 แตsยังพิสูจน/ไมsไดqจนกระทั่งป‹ ค.ศ.1976 วิทยาศาสตร/คอมพิวเตอรเ/ ตม็ ไปดqวย ปญ' หาทไี่ มสs ามารถแกไq ดq การไดqรับรวูq sาทฤษฎี 4สีน้นั ถูกพสิ ูจนไ/ ดq 120 ป‹ หลังจากนกั วิจัยนำเสนอทฤษฎีไป ก็ เป€นกำลังใจใหqแกsนักวิจัยหลายคนท่ีกำลังวิจัยในป'ญหาอื่นๆซึ่งคำตอบของป'ญหานั้นหลีกหนีจากพวกเขาอยูs เปน€ หลายสบิ ป‹ การระบายสีแผนที่เป€นหมวดหมูsหนึ่งของ ปญ' หาที่รูเจักกันคอื “การระบายสีแผนภาพ” ในวิทยาศาสตร/คอมพิวเตอร/ แผนภาพเป€น การแสดงความสัมพันธ/แบบนามธรรม ดัง ภาพที่แสดงใหเq ห็นทางขวามอื ดงั ทก่ี ลาs วไวใq นกิจกรรมท่ี 9 Muddy City คำ วsาแผนภาพถกู ใชใq นความหมายท่ีแตกตsางกันในวิชาคณิตศาสตร/ ซ่ึงหมายความถงึ แผนภาพท่ีแสดงขqอมูลทาง ตัวเลข อยsางเชนs แผนภมู แิ ทงs แตแs ผนภาพทที่ างวิทยาศาสตร/คอมพวิ เตอร/ใชqนัน้ ไมsไดเq ก่ยี วขอq งกับสิง่ เหลาs น้ี ใน วิทยาศาสตร/คอมพิวเตอร/ แผนภาพถูกวาดดqวยรูปวงกลมหรือจุดขนาดใหญs ทางเทคนิคเรียกวsา “โนด (nodes)” เพ่อื ใชqแทนวตั ถุ และเสนq ระหวาs งโนดนน้ั บsงบอกถงึ ความสัมพนั ธ/บางอยsางระหวาs งวตั ถนุ นั้ แผนภาพ ดqานบนใชแq สดงแทนแผนท่ใี นตอนเริ่มตนq ของกจิ กรรม โนดแทนประเทศ และเสนq บงs บอกวsาสองประเทศนนั้ ใชq ชายแดนรsวมกนั ในแผนภาพกฎการระบายสที ีไ่ มsใหสq องโนดทีเ่ ชือ่ มกันใชqสเี ดียวกนั ไมsมขี อq จำกดั ในเรือ่ งจำนวน ของสที ี่แผนภาพท่ัวไปจำเปน€ ตqองมี เพราะวsาขอq บังคับทแี่ ตกตsางกนั ถูกยบุ รวมเปน€ การเชื่อมเสqนเขาq ดวq ยกัน ไมs เหมอื นกับแผนท่ี ในขณะท่ธี รรมชาตขิ องแผนท่ี 2มิติ จำกดั ความเปน€ ไปไดขq องการจัดเรียง ปญ' หาการระบายสี แผนภาพ คือการหาจำนวนสีทนี่ qอยท่สี ดุ ทีจ่ ำเป€นตอq งใชqในการแตลs ะแผนภาพน้ัน ในแผนภาพทางดqานขวา โนดแทนรายวิชาในโรงเรยี นแหsงหนึ่ง เสqนระหวsางสองวิชาแสดงวsามีนักเรียนอยsาง นอq ยหน่งึ คนทเ่ี รียนทงั้ สองวิชาน้ี และดังน้นั สองวิชาน้ันไมคs วรถกู จัดตารางเรยี นในชsวงเวลาเดยี วกัน การใชกq าร นำเสอนแบบนี้ ป'ญหาในการจดั หาตารางสอนโดยใหqใชqจำนวนชวs งเวลาทนี่ qอยท่สี ุดนั้น เทียบเทsากับปญ' หาการ ระบายสี ในขณะที่สีที่แตกตsางกันก็เหมือนกับชsวงเวลาที่แตกตsางกัน วิธีการการระบายสีแผนภาพเป€น ประโยชนอ/ ยsางย่งิ ในวงการวิทยาศาสตร/คอมพิวเตอร/ มันถกู ใชใq นปญ' หามากมายของโลกแหงs ความจริง แมqวsา บางทมี นั อาจจะไมเs คยถูกใชqในการระบายสีแผนท่ีจรงิ ๆก็ตาม—นกั ทำแผนทีผ่ ูqยากจนของเราเป€นเพียงเร่ืองท่ี หนาq 149

แตงs ขน้ึ เทsานน้ั แทqจริงแลวq หลายพันป'ญหาอื่นๆ ก็อยูs บนพื้นฐานของแผนภาพ บางอยsางก็ ถูกอธิบายไวqที่ไหนสักแหsงในหนังสือ เลsมนี้ อยsางเชsน ตqนไมqแบบทอดขqาม นอq ยท่ีสดุ (minimum spanning tree) ของกิจกรรมท่ี 9 และเซทของจุดท่อี ยูs ใกล(q dominating set) จากกจิ กรรมที่ 15 แผนภาพนั้นเป€นแนวทางทั่วไปทีใ่ ชqในการนำเสนอขqอมูล และยังสามารถใชqเพ่ือนำเสนอการจัดเรียงของ เหตุการณ/ไดq ดังเชsน แผนที่ที่ประกอบไปดqวยถนนและทางแยก, การเชื่อตsอกันระหวsางอะตอมในโมเลกุล, เสqนทางที่ขqอความจะใชqเดินทางในระบบคอมพิวเตอร/เน็ตเวิร/ค, การเชื่อตsอระหวsางอุปกรณ/แตsละชิ้นบน แผsนวงจรที่ถูกปริ้น, และความสัมพันธ/ระหวsางงานที่ตqองทำเพื่อใหqโครงการใหญsสำเร็จลุลsวง ดqวยเหตุผลนี้ ป'ญหามากมายที่ประกอบไปดqวยการใชqแผนภาพแสดงแทน เป€นสิ่งที่นsาดึงดูดสำหรับนักวิทยาศาสตร/ คอมพิวเตอร/มายาวนาน หลากหลายป'ญหานั้นยากมาก ไมsไดqยากโดยหลักการ แตsยากเพราะตqองใชqเวลานานในการแกqป'ญหา ตัวอยsางเชนs ในการพิจารณาคำตอบทม่ี ีประสิทธิภาพที่สุดสำหรับป'ญหาการระบายสีแผนภาพขนาดกลาง— เชsน การหาวิธที ีด่ ีที่สดุ ในการจดั ตารางของโรงเรยี นทมี่ นี คณุ ครู 30 คนและนกั เรยี น 800 คน—สามารถใชqเวลา หลายป‹ หรือกระทั่งหลายศตวรรษ สำหรับคอมพิวเตอร/ที่ใชqอัลกอลิทึมที่เป€นที่รูqจักเป€นอยsางดี ป'ญหาจะไมs เกี่ยวขqองกันจนกระทัง่ ผลลัพธ/ถูกคqนพบ—และน่ันก็ตqองสมมติวsาคอมพิวเตอรจ/ ะไมsพังหรือเกsาจนใชqไมไs ดqไป กsอนที่มนั จะเสร็จ ป'ญหาเหลsานี้ถูกแกqเพียงในแบบฝŸกเทsานั้น เพราะเราพอใจที่จะทำงานกบั สsวนที่เหมาะสม สsวนหนง่ึ แตกs ไ็ ดqผลลพั ธท/ ่ดี ี ถqาเราจะยนื ยันวsาสามารถการันตผี ลลพั ธ/วsาเป€นคำตอบทด่ี ีที่สดุ ปญ' หานั้นจะเป€น ปญ' หาทีไ่ มสs ามารถแกqไดอq ยาs งสมบูรณ/ ระยะเวลาที่คอมพิวเตอร/ใชqในการแกqป'ญหาการระบายสีนั้น เพิ่มขึ้นแบบทวีคูณตามขนาดของแผนภาพ พจิ ารณาท่ีปญ' หาการระบายสีแผนท่ี มนั สามารถแกปq 'ญหาไดqโดยการทดลองทกุ ความเป€นไปไดขq องการระบาย แผนท่ี เรารqวู sาตอq งการสีอยาs งมาก 4 สี ดงั นนั้ ตอq งประเมินทุกจากทกุ กลมsุ (combination) ของ 4 สีท่จี ะระบาย ถqามีประเทศทังหมด n ประเทศจะก็จะมีกลุsมทั้งหมด 4n กลุsม เลขจำนวนนี้จะเพิ่มขึ้นอยsางรวดเร็ว ในทุกๆ ประเทศท่เี พ่มิ เขาq มา จะคณู ปริมาณของกลsุมไปอกี 4 ดงั นัน้ มันจึงเพ่ิมเวลาในการหาผลลพั ธข/ น้ึ อีก 4 เทsา แมวq าs จะสรqางคอมพิวเตอร/ทส่ี ามารถแกปq 'ญหาไดq 50 ประเทศในเวลาเพียง 1 ชั่วโมง แตsเมือ่ เพิม่ เขาq ไปอีก 1 ประเทศ มันก็ตqองใชqเวลา 4 ชั่วโมง และเราเพิ่มแคs 10 ประเทศเทsานั้นก็ทำใหqคอมพิวเตอร/ใชqเวลาแกqถึงหนึ่งป‹แลqว ป'ญหาประเภทนไ้ี มไs ดหq มดไปเพยี งเพราะเราแคsสราq งคอมพิวเตอร/ใหเq ร็วข้นึ เรอื่ ยๆ หนqา 150