Book-CSUnplugged

การระบายสแี ผนภาพเปน€ ตัวอยsางท่ีดีตัวอยsางหนง่ึ ที่มเี วลาในการหาคำตอบเป€นแบบทวีคูณ(exponentially) สำหรับกรณีของป'ญหาที่เล็กๆอยsางแผนที่ท่ีใชqในกิจกรรมนี้ มันงsายที่จะหาคำตอบที่เหมาะสมไดq แตsวsาหาก จำนวนของประเทศนน้ั เพมิ่ ข้ึนกวsา 10 ประเทศ ปญ' หาจะกลายเปน€ ป'ญหาที่ยากมากหากตอq งแกดq qวยมือ และ กบั หนง่ึ รqอยประเทศหรอื มากกวsา แมกq ระทัง่ คอมพวิ เตอรก/ ย็ งั ตอq งใชqเวลาหลายป‹ในการทดลองหาทางที่เป€นไป ไดใq นการระบายสีแผนท่เี พือ่ ใหqไดqคำตอบทีเ่ หมาะสม ป'ญหาในชีวิตจริงมากมายกเ็ ป€นเชsนนี้ แตสามารถแกqไดqดqวยทางใดทางหนึ่ง นักวิทยาศาสตร/คอมพิวเตอร/ใชq วิธีการที่ใหqผลลัพธท/ ่ีดแี ตยs งั ไมสs มบรู ณ/ เทคนคิ ทถี่ กู ศกึ ษามาอยาs งด(ี heuristic techniques) เขาq ใกลqกับความ พึงพอใจมาก คำนวณไดอq ยsางรวดเร็ว ใหผq ลลพั ธ/ทีใ่ กลเq พยี งพอสำหรับจดุ ประสงคจ/ รงิ โรงเรยี นสามารถยอมใหq ใชqหอq งเรียนมากขึ้นหนึ่ง จากท่ีตอq งการจริงๆถาq ตารางน้นั สมบูรณ/ และนักทำแผนท่ผี qยู ากจนก็สามารถรับภาระ ในคาs สหี นึง่ สีทีเ่ พ่มิ ข้นึ ไดqแมวq าs ไมsไดqเจาะจงวาs จำเป€น ไมsมีใครทพี่ สิ จู นว/ าs ไมมs วี ธิ ีท่มี ปี ระสิทธิภาพในการแกqป'ญหาในทำนองนโี้ ดยใชqคอมพวิ เตอร/ธรรมดา แตกs ็ไมsมีใคร พสิ จู น/วาs มเี ชนs กนั และนกั วิทยาศาสตร/คอมพวิ เตอรย/ งั กังขาวาs วิธีการทม่ี ปี ระสทิ ธิภาพจะไดqรับการคqนพบ เรา จะไดqเรียนรเqู กีย่ วกบั ปญ' หาประเภทนเี้ พิม่ เติมไดจq าก 2 กจิ กรรมตอs จากน้ี อาy นเพิ่มเตมิ Harel อภิปรายเกย่ี วกบั ทฤษฎี 4สไี วq รวมถงึ ประวัตศิ าสตร/ของมันใน Algorithmics มมุ มองเพ่ิมเติมของ ป'ญหาการระบายสแี ผนท่ีไดqถกู อภปิ รายกันใน This is MEGA-Mathematics! โดย Casey และ Fellows หนงั สอื Kubale’s 2004 Graph Colorings รวมประวตั ิของป'ญหาเอาไวดq วq ย ยงั มเี วบ็ ไซตห/ ลายเว็บไซตท/ ่ี เนือ้ หาเกยี่ วกบั เรอื่ งน้ี เฉลยและคำใบ^ หนาq 151

นี่เป€นทางเดียวที่เป€นไปไดqสำหรับแผนที่ในชีทกิจกรรมที่ 1 (แนsนอนวsาทางเลือกของสีข้ึนอยูกs ับนักเรียน แตs 2 สที ีแ่ ตกตาs ง กนั เทาs น้ันที่ตqองการ) แผนที่บนสุด ในชีทกิจกรรมท่ี 2 สามารถลงสีไดอq ยsางถูกตqอง โดย 3 สี ในขณะทแ่ี ผนทีด่ qานลsางตอq งการ 4 สี แผนทใ่ี นชที กจิ กรรม ที่ 3 เปน€ แผนที่ 3 สี อยาs งงsายดังแสดง หนqา 152

เฉลยสำหรบั ชีทกจิ กรรมท่ี 4 โดยใชq 2 สี (สี ขาวและสที แ่ี รเงา) หนาq 153

กิจกรรมท่ี 15 เมอื งนกั ทอy งเทย่ี ว - Dominating sets สรุป หลายสถานการณใ/ นชีวติ จรงิ สามารถจำลองใหqอยูsในรปู แบบของกราฟหรอื เครอื ขาs ย เมอื่ จำลองแลวq จะ เห็นวsาเราสามารถพัฒนาอัลกอรทิ ึมทเ่ี ป€นประโยชน/ในงานจรงิ ลงไปไดq ในกิจกรรมน้ี เราตอq งการทจี่ ะทำ เคร่ืองหมายสำหรบั จุดเชื่อมบางจุด ซ่ึงเชอ่ื มไปยังจดุ เชื่อมอนื่ โดยอยาs งมากแคs 1 ข้นั การเชื่อมตsอจาก จุดเชอื่ มท่ีถกู ทำเครอื่ งหมาย ปญ' หาคอื เราจะแยกจดุ เช่อื มเหลาs น้ีออกจากจุดเชอื่ มท้ังหมดไดอq ยาs งไร? ซงึ่ ปญ' หานกี้ ลบั กลายเป€นหน่งึ ในป'ญหาทยี่ ากอยsางนาs ประหลาดใจ หลักสตู รท่ีเกย่ี วขอ^ ง • คณติ ศาสตร/ – ตำแหนsงและมมุ หมุน • คณิตศาสตร/ – การใหเq หตุผล ทกั ษะ • แผนท่ี • ความสัมพนั ธ/ • การแกปq ญ' หาภาพปรศิ นา • การย้ำมsุงหาเป›าหมาย อายุ • 7 ป‹ขึ้นไป อุปกรณr นักเรยี นแตลy ะกลมyุ ตอ^ งการ: • สำเนาเสqนทางของรถตqไู อศกรมี • เคาน/เตอรห/ รอื ชปิ ทมี่ สี ีแตกตsางกนั 2 สี คุณตอ^ งการ: อุปกรณฉ/ ายภาพของเสนq ทางของรถตูไq อศกรมี บนกระดานหรือวาดขนึ้ บนกระดาน Dominating Sets บทนำ หนาq 154

ชที กิจกรรมของรถตqไู อศกรมี แสดงใหqเห็นถึงแผนภาพของเมืองนักทอs งเท่ยี ว แตsละเสนq หมายถงึ ถนนและ จุดหมายถึงมมุ ถนน เมืองนี้เป€นเมืองท่ีมีอากาศรอq นมากและในชsวงหนqารqอนจะมรี ถตqูไอศกรีมจอดขาย ไอศกรมี อยตsู ามมมุ ของถนน เราอยากจะเลอื กจดุ ท่ีควรจะวางรถตูqซงึ่ ทุกคนสามารถเขาq ถึงไดดq วq ยการเดนิ บนถนนมาจนสุดมมุ ของถนน (มันอาจจะงาs ยขึน้ หากจินตนาการวsาผคูq นอาศัยอยsู ณ บริเวณซอq นทับ แลวq พวกเขาตqองสามารถซือ้ ไอศกรมี ไดโq ดยการเดินอยาs งมากเพยี ง 1 ชอs ง) ปญ' หาคือ เราตqองการรถตqูทง้ั หมด กค่ี นั และจะจดุ ซอq นทับไหนบาq งท่สี มควรจะตดิ ตง้ั รถตูq การพจิ ารณา แบงs นกั เรียนออกเป€นกลมsุ เลก็ ๆหลายๆกลุsม มอบแผนท่เี มืองนักทอs งเที่ยวใหqแตลs ะกลsุม จากนั้นใหqพวก เขาอธิบายหลักการ แสดงใหqนักเรียนไดเq ห็นถงึ หลักการการวางแตลs ะรถตไูq อศกรีมหรอื เคานเ/ ตอรโ/ ดยทำสัญลักษณ/อีกสีหนึ่ง บนจุดเช่ือมทีเ่ ลอื ก ซึง่ ผqูคนอาศยั อยูsตามจดุ ซqอนทบั (หรอื ตามถนนท่ผี าs นพวกเขา) ตอq งสามารถเขqาถึงรถ ตเqู หลาs น้ีไดq พยายามชมนักเรียนที่วางตำแหนงs ใหสq ามารถเขาq ถึงทกุ บาq นไดq และพยายามยำ้ บอกพวกเขาวsารถตแqู ตsละ คันนัน้ มีราคาแพง เราควรจะเขาq ถงึ ทกุ บqานไดโq ดยใชqรถตนูq อq ยท่สี ุด จะเหน็ ไดqชดั วsาเงื่อนไขและขqอจำกัดที่ กลsาวผาs นมานนั้ สามารถแกqไขไดqหากมจี ำนวนรถตทqู ่ีมากพอท่จี ะวางลงบนทกุ ๆจดุ ซอq นทบั —แตปs ญ' หาที่ นsาสนใจคอื เราจะใชqรถตูนq qอยที่สุดไดนq qอยแคsไหนท่ยี ังคงสอดคลอq งกับเงื่อนไขเหลาs น้ีอยไูs ดq จำนวนรถตqูทีน่ qอยทส่ี ดุ ท่ยี ังสอดคลอq งกบั เง่ือนไขคือ 6 คัน ซึ่งคอื เฉลย ดังแสดงในรปู แตวs าs มนั ยากมากที่จะไดqรับมาซ่งึ คำตอบดังน!ี้ หลังจาก เวลาผาs นไปชsวงหนึง่ กบ็ อกพวกนกั เรียนวsาจำนวนรถตูqที่เพียงพอนั้น คอื 6 คนั และจากนนั้ ทqาใหqพวกเขาทางทีจ่ ะนำไปสsคู ำตอบน้ีไดqจริงๆ (ใหqพวกเขาวาดภาพใหqไดqดังเฉลย) ซึ่งป'ญหานี้ก็ยังคงเป€นป'ญหาที่ คsอนขqางยาก: หลายๆกลุมs จะถอดใจในที่สุด (คำตอบซึ่งใชqรถจำนวน 8 หรอื 9 คันน้นั กย็ ังถอื วาs ยากทจ่ี ะหามาไดแq ลqว) หนาq 155

แผนทข่ี องเมอื งนักทอs งเทีย่ วถกู สรqางขึ้นโดย 6 ชนิ้ สsวนแผนท่ี ซึง่ อยูsขqางใตขq องเฉลยของชีทกิจกรรม ซึ่ง แตลs ะอันจะตqองการเพยี งแคs 1 คันรถไอศกรมี เทาs น้ัน จากนั้นเชอื่ ม 6 ชิน้ สวs นเหลsานีเ้ ขqาดวq ยกนั ดวq ยถนน จำนวนมากเพอ่ื ใหqเกดิ ความยาก ส่งิ หลักๆนน้ั ไมsใชsการวางการเชือ่ มตอs ระหวาs งทกุ ๆจุดเช่ือมท่ีเป€นเฉลย (จุดโปรงs ) แตsเพยี งจุดพิเศษ (จดุ ทบึ ) แสดงวิธีคิดเหลาs นใี้ นหอq งเรียนโดยการวาดหรือโดยโปรเจคเตอร/ พยายามใหqนกั เรียนลองสรqางแผนทข่ี องพวกเขาเองโดยใชวq ิธีคิดดงั กลาs ว พวกเขาอาจจะอยากเสนอแนวคิดหรือ แผนท่ีของเขาใหqกบั เพื่อนๆหรอื พอs แมsของเขาดูและฟง' – พวกเขาจะพบวาs เขาสามารถสราq งภาพปริศนาทต่ี วั เขาเองสามารถแกไq ดอq ยาs งงาs ยดายในขณะทค่ี นอืน่ ไมสs ามารถแกปq 'ญหาของพวกเขาไดq! นเ่ี ปน€ ตวั อยาs งของ “ฟ'งกช/ นั ทางเดียว”: มนั งsายทีจ่ ะเรยี นรสูq ่งิ นจ้ี ากภาพปรศิ นาที่ยากทจี่ ะแกq – นอกจากคุณทเ่ี ปน€ คนสราq งมัน ขน้ึ มา ซง่ึ ฟง' ก/ชนั ทางเดียว เหลsาน้จี ะมหี นqาทส่ี ำคญั อยsางมากในระบบการเขาq รหัส (ดู กจิ กรรมที่ 17 และ 18) หนqา 156

ชีทกจิ กรรม: รถตู^ไอศกรีม ลงมอื มองหาวาs จะเลอื กตำแหนงs ของรถไอศกรีมอยsางไร ทจี่ ะทำใหqจดุ ซอq นทบั จดุ อ่นื ๆถูก เชื่อมตsอเขqาดqวยกบั รถตqเู หลาs นี้ หนาq 157

ชที กจิ กรรม: เฉลยป•ญหารถตู^ไอศกรมี แสดงภาพเฉลยนใี้ นหqองเรยี นเพ่อื ใหqพวกเขาไดqเห็นวาs ภาพอนั แสนยากนถี้ กู สราq งไดอq ยาs งไร หนาq 158

ความหลากหลายและสyวนขยาย มีหลากหลายสถานการณ/ซึ่งจะเจอในป'ญหาจำพวกการวางผังเมือง: การวางตำแหนsงตqู ไปรษณยี /, บอs น้ำ, สถานดี ับเพลิงและอน่ื ๆ ในชวี ิตจริง แผนภาพอาจไมsไดอq ยsบู นพนื้ ฐานทีง่ าs ย ตsอการแกไq ขแบบนี้ ถqาคณุ ตอq งแกไq ขป'ญหาเหลาs น้จี รงิ ๆในอนาคต คุณจะทำอยsางไร? วิธีแบบตรงไปตรงมา: พิจารณาทกุ ความเป€นไปไดqของการวางรถตูqจากน้ันเลือกทางท่ดี ีทีส่ ุด ออกมา กรณี 26 มุมถนนในเมอื งนักทอs งเที่ยว จะมที ั้งหมด 26 ตำแหนsงในการวางรถตqู มัน ไมใs ชเs ร่ืองยากท่จี ะตรวจสอบกรณีทีเ่ ปน€ ไปไดqทง้ั หมดจาก 26 ตำแหนsงดังกลาs ว และก็ชัดเจน ทีจ่ ะระบไุ ดqวาs ไมsมคี วามเป€นไปไดqไหนเลยที่สอดคลqองตอs เงื่อนไขที่ตqองการ พิจารณากรณีใชq รถตูqทง้ั หมด 2 คัน ซ่งึ คอื การเลือก มาทง้ั หมด 2 จุดซอq นทบั จาก 26 จุดซqอนทับ โดยในครั้ง แรกที่เลอื กเราจะมที งั้ หมด 26 จุดใหสq ามารถเลือกไดqแตsหลังจากนนั้ เราจะเหลอื เพยี ง 25 จุด ซqอนทบั ใหqเลอื กในขณะทเ่ี ลือกจุดซอq นทับที่ 2 (มนั คอs นขาq งทีจ่ ะชัดเจนที่คณุ จะไมวs างรถตูqท้ัง 2 คนไวทq จี่ ุดซqอนทบั จดุ เดยี วกัน): 26 × 25 = 650 ความเปน€ ไปไดทq ีจ่ ะพิจารณา เชsนเคยแตs ละกรณีนั้นงsายตsอการตรวจสอบถึงแมqวsาจะตqองทนกับความนsาเบื่อในการตรวจทุกความ เป€นไปไดqกต็ าม แตจs ริงๆแลqวคุณตqองการพจิ ารณาเพียงแคsครง่ึ หน่ึงของทั้งหมด (325) เพราะ มันไมsไดมq คี วามหมายหากการวางรถตqเู ปน€ ดังน:้ี ถาq คณุ เลอื กใหqรถตคqู นั ที่ 1 อยทูs ่จี ดุ ซqอนทบั A และรถตูqคันที่ 2 อยูsที่จุดซqอนทับ B หลังจากพจิ ารณากรณีดังกลsาวน้ีแลqว ไมsมีความจำเป€น จะตอq งตรวจสอบกรณที ่ี รถตqูคนั ท่ี 1 อยูsที่ B และรถตคqู นั ที่ 2 อยsทู ี่ A และจากนนั้ คณุ สามารถ ตรวจสอบกรณี การใชqรถตูq 3 คัน (2600 ความเป€นไปไดq), 4 คัน (14950 ความเป€นไปไดq), และตอs ๆไป ซ่ึงแนsนอนวsารถตqู 26 คันนัน้ เพียงพอเพราะมี 26 จุดซอq นทับและไมsมจี ดุ ซqอนทับ ไหนท่ีจะมีรถตูqมากกวsา 1 คัน อกี ทางหนง่ึ ในการพิจารณาจำนวนความเป€นไปไดqซ่ึงพิจารณา วาs จำนวนจดุ ทัง้ หมด 26 จุดซqอนทับน้ีควบคsูกับจำนวนรถตqู เนื่องจากในแตลs ะจุดซqอนทับน้ัน มีเพียง 2 ความเป€นไปไดqเทsานั้นคือ — มีรถตูqหรือไมsมีรถตูq — ดังนั้นจำนวนกรณีที่ตqอง พิจารณาทัง้ หมดคอื 226 ความเปน€ ไปไดq ซ่งึ คิดเปน€ 67,108,864 ความเป€นไปไดq การแกqป'ญหาดังกลsาวนีถ้ กู เรยี กวsา “brute-force” อลั กอรทิ ึม ซ่ึงกินเวลานานในการประมวลผล มคี วามเขqาใจผิดกนั อยsางกวqางขวางวsาคอมพวิ เตอร/นั้นทำงานไดรq วดเร็วมากและสามารถแกqป'ญหา ใดๆไดqอยsางรวดเร็วไมsวsางานที่จะตqองทำนั้นมากและหนกั เพียงใด แตsมันไมsจรงิ ระยะเวลาในการ แกqป'ญหาของ “brute-force” อัลกอริทมึ นัน้ ขึ้นอยูsกับความเร็วที่ตัวมันตรวจสอบไดqวsาในความ เป€นไปไดนq ้ันๆเปน€ คำตอบหรือไมs เพ่อื ตรวจสอบทกุ ๆจุดซqอนทบั เพอ่ื หาระยะทางระหวsางรถตูqท่ีอยูs ใกลทq ี่สดุ หากสมมตวิ าs การพจิ ารณาความเป€นไปไดq 1 กรณี นนั้ ใชเq วลาทัง้ หมด 1 วินาที เราควรใชq เวลาเทาs ไหรsในการพิจารณาทกุ ความเปน€ ไปไดq 226 กรณี ในเมืองนักทอs งเท่ยี วน้ี? (คำตอบคือ 226 หนาq 159

นั้นประมาณ 67 ลqาน; ใน 1 วันมีทัง้ หมด 86400 วินาที, ดังนั้น 226 วินาที นั้นจะใชqเวลาทัง้ หมด 777 วัน หรือประมาณ 2 ป)‹ และหากสมมติวsามนั ไมsไดqใชqเวลา 1 วินาที ในการพิจารณา 1 ความ เป€นไปไดq แตsเป€น 1000 วินาที ในการพิจารณา 1 ความเป€นไปไดqแทน แลqวเสมือน 2 ป‹ในกรณี สมมติเดิม ยอมใหqคอมพิวเตอร/แกqป'ญหาที่มี 36 จุดซqอนทับในเมือง เพราะ 236 เป€นประมาณ 1000 เทsาของ 226 แมวq sาถqาคอมพวิ เตอรจ/ ะเร็วกวsานเี้ ป€น 1 ลาq นเทsา ดงั นนั้ 1 ลqานความนsาจะเป€น สามารถถูกตรวจสอบไดใq น 1 วินาที เรากย็ ังคงตqองการเวลา 2 ป‹ เพอื่ แกปq 'ญหาทม่ี ี 46 จุดซอq นทับ ในเมือง และคุณคงทราบดี วาs นไี่ มsใชsเมืองท่ีใหญอs ะไรเลย! (คณุ คิดวาs มีท้งั หมดกจ่ี ุดเช่ือมในเมืองท่ี คุณอยใูs นป'จจุบัน? เนื่องจาก brute-force อัลกอริทึม นั้นชqามาก เรามีทางอื่นที่จะแกqป'ญหาเหลsานี้มั้ย? ซึ่งเรา สามารถใชq greedy approach ซึ่งประสปความสำเร็จอยsางมากในการแกqป'ญหา muddy city (กจิ กรรมที่ 9) เราจำเป€นจะตqองนกึ ถึงวsาจะประยุกต/วิธีเหลาs นี้ลงในปญ' หารถตูqไอศกรีมไดqอยsางไร แนวทางการทำคือการวางรถตูคq ันแรกทีจ่ ุดซqอนทับซึง่ เชื่อมถนนจำนวนมากที่สุดเขqาดวq ยกนั และ วางรถตูqคันถัดไปท่ีจุดเชื่อมถนนท่ีมากที่สดุ อันดับถัดไปและทำอยsางนี้ตsอไปเรื่อยๆ อยsางไรก็ตาม มันไมsจำเป€นจะตอq งทำใหqจำนวนรถตูนq ั้นนqอยทีส่ ุด — ในความเป€นจริง จุดเชื่อมที่มีการเชื่อมตอs มากทีส่ ุดน้นั ไมsใชsจดุ ทด่ี ที จี่ ะวางรถตqูเลย (ตรวจสอบไปดqวยกันกบั หอq งเรียน) หากมองไปทปี่ 'ญหาทีผ่ าs นมา แทนท่จี ะหากรณที ี่จำนวนรถตทูq ่นี อq ยทีส่ ดุ ท่เี ป€นไปไดq สมมตวิ sาคณุ ถูกมอบหมายกรณแี ตลs ะกรณีมาแลqวถามวsานั่น คอื กรณีทีน่ qอยท่ีสุดแลqวหรือไม?s ในบางกรณี มันเป€นป'ญหาทง่ี sาย เชนs แผนภาพนี้แสดงแผนที่อยsางงsาย ซง่ึ มีคำตอบที่คsอนขqางจะตรงไปตรงมา จนิ ตนาการวsา ถนน ทง้ั หมดเป€นดัง่ ขอบดqานของปริมาตร มันแสดงใหqเห็นวาs หากรถตqไู อศกรีมน้ันอยsูตรงดqานตรงขqาม กันบนเสนq ทแยงมมุ กรณีดงั กลาs วนน้ั เพยี งพอจะใหqคำตอบแลวq หนqา 160

ท้งั หมดน้เี กยี่ วอะไร? หนึ่งในสง่ิ ทนี่ าs สนใจในป'ญหารถไอศกรมี ก็คอื ไมมs ีใครรqวู sา มอี ัลกอรทิ มึ ท่ีสามารถหาคำตอบที่ ดีที่สุดซึ่งเร็วกวsา “brute-force” อัลกอริทึม! เวลาที่ใชqใน “brute-force” อัลกอริทึมนน้ั เติบโตแบบเอกซ/โพเนนเชียลตามจำนวนของจุดซqอนทับ เราสามารถเรียกมันวsาอัลกอริทมึ แบบเอกซ/โพเนนเชียล อัลกอริทึมแบบพหุนามเป€นหนึ่งในอัลกอริทึมที่เติบโตเป€นสัดสsวน กำลัง 2 หรือกำลัง 4 หรือกำลัง 17 หรือยกกำลงั อ่ืนๆตามจำนวนจุดซqอมทับ ซึ่งอัลกอริทมึ แบบพหุนามนั้นรวดเร็วกวsาอัลกอริทึมแบบเอกซ/โพเนนเชียลเสมอ ถึงแมqวsาเราจะเป€น อลั กอรทิ ึมแบบพหุนามแบบกำลงั 17 ก็ตาม เพราะฟ'งกช/ นั ที่เตบิ โตแบบเอกซโ/ พเนนเชียลนนั้ มีคsามากกวsาฟ'งก/ชันที่เติบโตแบบพหุนามเสมอเมื่อจำนวนตัง้ ตนq นั้นๆมากพอ (เชsน หากคณุ ลองคำนวณดูแลqวจะพบวาs เม่ือ n มคี าs มากกวาs 117 เมอื่ นั้น n17 จะมคี าs นqอยกวsา 2n) แลวq ... มันมีอัลกอริทึมแบบพหุนามสำหรับการแกqป'ญหานี้ไหมลsะ? คำตอบคือไมsมีใครรูq ถึงแมqวsา หลายๆคนจะพยายามคนq หาทางแกqอยาs งหนกั หนวs งกต็ าม และคงเปน€ จรงิ สำหรบั ปญ' หาทง่ี าs ย กวาs ทตี่ รวจสอบวาs แตsละชดุ ของตำแหนงs นั้นนqอยทสี่ ุด: อลั กอริทมึ แบบ brute-force ซึ่งทำ การตรวจสอบทุกๆความเป€นไปไดqนั้นเติบโตอยsางเอกซ/โพเนนเชียลกับจำนวนจุดซqอนทับ และอัลกอริทึมแบบพหนุ ามซ่งึ แกqปญ' หาน้ีไดqทง้ั ยังไมsถกู คqนพบและเป€นทพี่ ิสูจน/ออกมาใหเq หน็ มันทำใหqคุณนึกถึงการเลือกสีในแผนที่ (กิจกรรมที่ 13) ไหมลsะ? ก็ควรจะเป€นเชsนน้ันเพราะ ป'ญหารถตูqไอศกรีมซึ่งรูqจักกันในนาม “ชุดควบคุมนqอยสุด” เป€นหนึ่งในป'ญหาหลายพัน ป'ญหาท่ียงั ไมเs ปน€ ที่รqูอัลกอริทึมแบบพหุนามในการแกใq นทางของตรรกะ ผsานจิ๊กซอว/เหมือน การจัดเตรียมป'ญหาเลือกสีในแผนที่ การหาคำตอบที่ดีที่สุดบนแผนที่ ชsางนsาตกใจที่เรา สามารถมองปญ' หาเหลาs น้เี ปรยี บเสมือนป'ญหาเดียวกันไดq ซง่ึ หากเราพบอัลกอริทึมแบบพหุ นามซึ่งแกqป'ญหาใดป'ญหาหนึ่งไดq เราก็จะสามารถนำอัลกอริทึมที่ไดqนี้ มาประยุกต/เพื่อ แกqปญ' หาท่ีถูกจดั อยsใู นกลุมs เดียวกันไดq ปญ' หาเหลาs น้ถี ูกเรยี กวาs NP-complete โดย NP นน้ั หมายถงึ การยงั ไมsปรากฏของอลั กอริทึมแบบ พหุนามซึ่งแกปq 'ญหานั้นๆไดq ซ่งึ ศัพทเ/ ฉพาะน้ีหมายถงึ ป'ญหาทีส่ ามารถแกqไดใq นเวลาที่สมเหตุสมผล ถqาคุณมีคอมพิวเตอร/ที่สามารถลองจำนวนใดๆขนาดใหญsของคำตอบในครั้งเดียว (สำหรับคำวาs NP) คณุ อาจจะคดิ วาs นน่ั ไมsสามารถทำไดจq รงิ ในทางปฎบิ ัติ และก็จริงตามน้ัน มันเป€นไปไมsไดqท่ีจะ สราq งคอมพิวเตอร/แบบนน้ั เพราะมันจะเกิดจำนวนคำตอบเทsาไหรsก็ได!q อยsางไรกต็ ามแนวคดิ ตsางๆ ของเครื่องจักรนั้นเป€นสิ่งที่สำคัญในเชิงหลักการ เพราะวsาป'ญหาแบบ NP-complete นั้นไมs สามารถแกqไดใq นเวลาทส่ี มเหตุสมผลโดยไมมs ีคอมพิวเตอร/ดังกลาs ว หนาq 161

นอกจากนั้น ป'ญหาเหลsานี้ถูกเรียกวsา complete เพราะแมqวsาป'ญหาทั้งหลายคลqายจะ แตกตsางกนั เชsน การเลอื กสใี นแผนที่คsอนขqางทีจ่ ะแตกตาs งกบั การเลือกวางตำแหนงs ของรถตqู ไอศกรีม แตsหากสามารถแกqป'ญหาใดป'ญหาหนึ่งไดโq ดยวิธีที่มีประสิทธิภาพ วิธีนั้นสามารถ นำไปประยุกต/เพอ่ื แกปq ญ' หาทง้ั หลายทถี่ ูกจำแนกวsาคลqายกันไดqอกี ดวq ย มีปญ' หาแบบ NP-complete อยูมs ากมายหลายพนั ปญ' หา ซึ่งเหลาs นักวจิ ยั กำลังหาทางแกqมันอยsาง มีประสิทธิภาพ หลายสิบป‹ที่ไมsประสบผลสำเร็จ หากเราพบวิธีทางแกqป'ญหาเหลsานี้อยsางมี ประสิทธภิ าพแลวq ละs กเ็ รากส็ ามารถแกปq 'ญหาอนื่ ๆไดqเชนs กันทง้ั หมด ดังนั้นพวกมนั จึงถกู มองวsาไมมs ี ทางแกqท่มี ีประสทิ ธภิ าพ จึงจำเป€นจะตqองพิสูจน/วาs ปญ' หาเหลาs นีม้ อี ัลกอริทึมแบบเอกซโ/ พเนนเชียล เปน€ ทางที่ดีท่สี ดุ ในการแกqในทางทฤษฎขี องวทิ ยาการคอมพิวเตอร/และอาจจะเปน€ ในทางทกุ ศาสตร/ ของคณติ ศาสตร/อกี ดqวยในปจ' จบุ นั อาy นเพ่มิ เตมิ หนังสือของ Harel ชื่อ Algorithmics แสดงหลายๆป'ญหาแบบ NP-complete และอธิบายถึงการมีอยูsของ อลั กอริทึมแบบพหุนามที่ใชqแกqมนั หนงั สอื ช่อื Turing Omnibus ของ Dewdney ก็เชนs กัน และมาตรฐานของ วิทยาการคอมพิวเตอร/ถูกเขียนบนหนังสือชื่อ Computers and Intractability โดย Garey และ Johnson ซึ่งเสนอหลายรqอยป'ญหาแบบ NP-complete ตลอดจนหนทางการพิสูจน/วsาป'ญหาเหลsานั้นเป€น NP- complete จริง แตsอยsางไรก็ตามมันคsอนขqางจะเป€นงานที่หนักและเหมาะสมสำหรับผูqเชี่ยวชาญทางดqาน วิทยาการคอมพิวเตอร/โดยเฉพาะ หนาq 162

กจิ กรรมท่ี 16 ถนนนำ้ แข็ง - ต^นไม^ Steiner สรปุ บางครง้ั ความแตกตsางเพียงเล็กนqอยเฉพาะจุดของแตลs ะป'ญหากอs ใหเq กิดความแตกตsางอยsางมากในแงขs อง การแกปq ญ' หาเหลาs น้ัน ในกิจกรมนเี้ หมือนปญ' หา Muddy City (กจิ กรรมท่ี 9) ซ่ึงเปน€ การหาทางทส่ี ้นั ทีส่ ุดผsานการเชอ่ื มเตอs นน้ั ๆ แตsจดุ แตกตาs งก็คอื เราอนญุ าตทจี่ ะสรqางจุดใหมๆs ขึ้นมาบนการเชอ่ื มตอs เดมิ ถqาหากมนั สามารถลดระยะทางลงไดq ผลลัพท/ที่ออกมาคือมนั กลายเป€นปญ' หาท่ยี ากกวาs เดมิ ข้ึนมากและ มนั ไมsไดqมคี วามสมั พันธก/ บั ปญ' หา Muddy City เดิมเลย แตกs ลับสามารถมองใหqอยูใs นรปู แบบเดยี วกบั ป'ญหา the cartographer’s puzzle ในกจิ กรรมที่ 13 หรอื ป'ญหา Tourist Town ในกจิ กรรมท่ี 14 หลักสูตรท่ีเก่ยี วขอ^ ง ü คณติ ศาสตร/ – ตำแหนsงและมมุ หมุน ü คณติ ศาสตร/ – การใหqเหตุผล ทักษะ ü การมองรปู เปน€ สsวนยอs ยๆ ü ตรรกะเชิงเรขาคณิต ü อัลกอรทิ ึมและความซบั ซqอน อายุ ü7 ปข‹ ้ึนไป อปุ กรณr นักเรียนแตลs ะคนตqองการ: ü หมุด 5 หรือ 6 ตวั ü หนงั ยางยาวหลายเมตร ü ไมsบรรทดั หรือตลับเมตร ü ปากกาและกระดาษเพือ่ จด หนาq 163

ถนนน้ำแขง็ บทนำ จากกจิ กรรมกsอนหนาq นี้ (เมอื งนกั ทsองเที่ยว [Tourist Town] ตัง้ อยทูs ปี่ ระเทศแถบรอq น) คราวน้ตี รงกนั ขqาม ในเขตอนั หนาวเย็นทางตอนเหนือของแคนาดา (กระทอs มนำ้ แขง็ รมิ ทะเลสาบในฤดหู นาว) เคร่ือง กวาดหิมะสรqางถนนหลายสายเชอ่ื มตsอแตลs ะสถานขี ดุ เจาะ ทำใหqชาวเมอื งสามารถพบปะกันไดq ขาq งนอก สภาพอากาศหนาวจัด พวกเขาจงึ ตอq งการทจ่ี ะสรqางถนนใหนq อq ยท่สี ดุ งานของคณุ คือการคิดใหอq อกวาs จะ สราq งถนนทีไ่ หนบาq ง ไมsมขี อq บงั คบั : ถนนไฮเวยส/ ามารถตดั ผsานทsงุ หมิ ะ หรอื ทะเลสาบท่แี ข็งเปน€ น้ำแข็งไดq เนื่องจากทงั้ คูsเป€นพ้ืนท่ีราบ ถนนควรจะเปน€ เสนq ตรงเพอื่ สะดวกตอs การเดนิ ทาง (การทถี่ นนโคงq นั้นมีแตsจะเพม่ิ ระยะการเดินทางโดย ไมsจำเปน€ ) แตsมันก็ไมsใชsวาs จะสรqางถนนทใี่ ชเq ชื่อมตอs ทกุ สถานีขุดเจาะดวq ยทางตรงอยsางเดยี ว เพราะการ เพม่ิ ทางแยกนน้ั สามารถลดระยะทางถนนทง้ั หมดไดq และยงั ชsวยลดเวลาในการเดินทางดqวย ซงึ่ ถือวาs มี ความสำคัญมาก ในรูป (a) แสดงสถานีขุดเจาะสามแหsง เชื่อมตsอสถานที่หนึ่งกับอีกที่หนึ่งดังในภาพ (b) การสรqาง เครอื ขาs ยถนนเปน€ ท่นี sายอมรับ ความเปน€ ไปไดqอีกอยsางคอื การสรqางทางแยกในท่ี ๆใกลqจุดก่ึงกลางของ รูป สามเหลี่ยมและเช่ือมตsอไปยังสถานีขุดเจาะทัง้ สามแหsงดังรปู (c) และถqาคุณวัดระยะทางท้ังหมดของ ถนน นั้นชัดเจนวsาวิธีแบบใดดีที่สุด ทางแยกที่เพิ่มนั้นจะเลือกวsาง “จุดสไตเนอร/ [Steiner point]” หลงั จากที่นกั คณติ ศาสตรช/ าวสวิส นามวsา Jacob Steiner (1796-1863) ผรqู ะบุปญ' หาและเป€นคนแรกท่ที ำใหเq รารวqู าs ระยะการเดนิ ทางของรถท้ังหมดนั้นสามารถลดทอนลงไดqโดย การเพิม่ จดุ ใหมเs ขาq ไป คณุ ควรคิดวาs จดุ สไตเนอรก/ ค็ ือจดุ ใหมs จุดสมมติ หรอื สถานีขุดเจาะอกี แหงs หน่งึ หนาq 164

การบรรยาย 1. อธิบายป'ญหาท่นี ักเรยี นจะศึกษา โดยใชqตัวอยาs งขาq งตqนท่มี สี ถานขี ุดเจาะสามแหsงสาธติ แกsนักเรียน แตs เพิ่มจุดใหมsเขqาไปเพิ่มอีกหนึ่งสถานี จากนั้นปรับปรุงวิธีแกqป'ญหาการลดทอนจำนวนการสรqางถนน ท้ังหมด 2. นักเรียนจะใชqจดุ จำนวนส่จี ดุ จดั ใหอq ยูใs นรปู สเี่ หลี่ยมจัตุรสั ดงั ที่แสดงในรปู (a) ออกไปขqางนอกและจัด แตลs ะกลมsุ ใหqอยsูในตำแหนsงหมุดสจ่ี ดุ บนสนามหญqาโดยใหqแตลs ะจดุ หาs งกัน 1 เมตร 3. ใหนq ักเรียนทดลองการตอs หมดุ ดqวยเชอื กหรอื หนงั ยาง วัดระยะและจดบนั ทึกความยาวนอq ยทสี่ ดุ ทตี่ อq งใชq ในขนั้ ตอนน้ีหาq มใชจq ดุ สไตเนอร/ (ความยาวนqอยทสี่ ุดหามาจากเสนq เช่อื มตsอจดุ สามจดุ ของสเี่ หลีย่ มจตั รุ สั ) ดงั ในรูป (b) และระยะทางรวมเทาs กบั 3 เมตร 4. ตอนนสี้ ังเกตวาs นกั เรียนสามารถทำไดดq ีดวq ยการใชqจุดสไตเนอรห/ รือไมs (จดุ ทด่ี ีทส่ี ุดคือจดุ กง่ึ กลางของ สี่เหลี่ยมจัตรุ ัส ดังรูป (C) เมื่อนั้นความยาวทงั้ หมดคือ 2√2 = 2.83 เมตร) แนะนำพวกเขาวาs จะทำไดqดี ยง่ิ ขนึ้ ดqวยการใชจq ุดสไตเนอร/สองจดุ (ในความเปน€ จรงิ พวกเขาสามารถทำไดq โดยการระบุจดุ สไตเนอร/ สองจุด เหมอื นรปู (d) ซง่ึ กอs ใหqเกิดมมุ 120 องศาระหวาs งทางรsมถนน ความยาวทง้ั หมดคอื 1 + √3 = 2.73 เมตร) หนqา 165

5. นกั เรียนสามารถหาความยาวที่ส้ันกวsาเดิมดqวยการใชจq ดุ สไตเนอรส/ ามจดุ หรือไมs (คำตอบคือไมs เพราะ สองจดุ ทว่ี ิธที ่ดี ีทส่ี ุด และไมมs ขี อq ดจี ากการใชจq ดุ ท่มี ากขึน้ ) 6. อธบิ ายแกนs ักเรียนวาs ทำไมปญ' หานจี้ ึงดูเหมอื นยาก (เป€นเพราะวsาคณุ ไมsรจูq ะระบุจุดสไตเนอร/ตำแหนงs ไหน และมีวิธที ่ีเป€นไปไดอq ีกมากมายใหทq ดลองทำ) หนqา 166

ใบงานกจิ กรรม : ตวั อยyางท่ี 1 จดุ สไตเนอรสr ามจุด หนาq 167

ใบงานกจิ กรรม : ตวั อยyางท2่ี จุดสไตเนอรสr ามจุด หนาq 168

หลากหลายและเพม่ิ เตมิ 1. การทดลองที่นsาสนใจสำหรับกลุมs ที่ทำกิจกรรมแรกเสร็จกอs นคือ ทำการทดลองแบบเดิม แตsเปลี่ยน ตำแหนงs จุดทัง้ ส่ีเปน€ รปู สี่เหลย่ี มผืนผาq ท่ีมคี วามยาว 1 เมตร X 2 เมตร ดงั รปู (a) นักเรยี นจะคqนพบวsา การเพ่มิ จดุ สไตเนอรห/ นึ่งจดุ นน้ั ทำใหอq ะไรๆแยลs ง แตsถqาเป€นสองจุดความยาวจะลดลง (ความยาวเป€น 4 เมตรสำหรับรูป (b) 2√5 เมตร สำหรบั รูป (c) และ 2 + √3 เมตร สำหรบั รปู (d) ) สังเกตถqาพวกเขา สามารถคดิ ออกวาs ทำไมองคป/ ระกอบหน่ึงจุดนั้นถึงทำใหเq กิดผลลพั ธท/ ่ีแยsขนึ้ สำหรับรูปส่ีเหล่ียมผืนผqา มากกวsารูปสเี่ หล่ียมจัตรุ สั (เป€นเพราะวsาเมือ่ สี่เหลี่ยมจตั ุรสั ถูกยืดออกเป€นส่ีเหล่ียม ผืนผqา คsาของการ ถกู ยดื น้ันถูกเพ่ิมเพียงแคใs นรปู (b) และ (d) เทาs นน้ั แตsเสqนทแยงมุมทัง้ สองนน้ั เพ่ิมในรูป (c)) 2. นักเรียนทีแ่ กกs วาs สามารถแกqโจทย/ป'ญหาที่ใหญsกวsาไดq สองแผนผังของสถานีขดุ เจาะทีเ่ ชื่อมตsอกันดqวย ถนนถูกระบุอยูsในใบงาน พวกเขาสามารถทำการทดลองโดยใชqวิธที ่ีแตกตsางกันไมsวาs จะเป€นการคัดลอก ใบงานหรือการเขยี นดqวยปากกาทลี่ บไดqบนแผนs ใสวางบนใบงานอีกที อกี ทางเลอื กหนงึ่ คอื สามารถทำ เครอ่ื งหมายแผsนที่บนพน้ื ดวq ยการใชqหมดุ ระบุตำแหนsงแตs ละสถานี พวกเขาสามารถใหqคนอ่นื ๆ ในหอq งเรียนรqไู ดqเมอ่ื มกี ารบันทกึ ระยะทางระหวsางหมุดทีส่ ้ันลงๆ (รูปดqานขวา แสดงวิธีที่ดีท่ีสุดสำหรับตวั อยsางแรกและรูปดqานลาs งแสดง วิธที ีเ่ ป€นไปไดq 2 วิธีสำหรับ หนqา 169

ตัวอยาs งท่ี 2 ระยะทางของท้งั สองวิธีนัน้ เทาs กนั ) ความจรงิ ท่ีวsามีสองวิธที ไ่ี ดqระยะทางเหมือนกันแสดง ใหqเห็นถึงวsาทำไมป'ญหารูปแบบนี้จึงยากที่จะหาวิธีที่ถูกตqองที่สุด เพราะวsามีหลายวิธีการที่จะระบุ จดุ สไตเนอร/นน้ั เอง! 3. เครอื ขาs ยบันได [Ladder network] แบบนีอ้ ำนวยใหหq นทางในการแกปq ญ' หาเป€นไปไดหq ลากหลาย เครอื ขsายบนั ไดมนี sาตาเป€นแบบน้ี : ตนq ไมqสไตเนอร/ [Steiner tree] นอq ยท่ีสดุ สำหรบั เครอื ขาs ยบันไดแสดงตามรปู ดาq นลsาง หนงึ่ ในวิธีทำ สำหรบั โจทย/แบบบนั ไดสองขนั้ นั้นเหมอื นกนั กบั วิธีทำในรปู ส่เี หล่ียมจตุ รสั อยsางไรก็ตามสำหรบั โจทย/ แบบบนั ไดสามขั้น วธิ ที ำน้นั แตกตาs งออกไป วธิ ีทำสำหรบั โจทยแ/ บบบันไดสข่ี ้นั เหมอื นกบั การตอs โจทย/ แบบบันไดสองข้ันเขาq ดวq ยกัน แตsทวาs วธิ ที ำสำหรบั โจทยแ/ บบบันไดหาq ข้ันเหมอื นกบั สsวนขยายของ โจทย/แบบบนั ไดสามขน้ั มากกวาs โดยทวั่ ไปรูปรsางของตนq ไมqสไตเนอร/นอq ยทสี่ ุดสำหรบั โจทย/แบบ ขน้ั บนั ไดขึน้ อยกูs ับวsามจี ำนวนขั้นเป€นเลขคูหs รอื เลขค่ี ถqาเปน€ เลขคูแs สดงวาs มโี จทยแ/ บบบันไดสองขั้นตอs กนั หลายๆอัน ในทางกลบั กันมันเหมอื นกบั การทำซ้ำของวธิ ที ำโจทย/แบบบันไดสามข้นั แตกs ารพสิ จู น/ สง่ิ เหลsาน้ไี มใs ชเs ร่อื งงาs ย หนqา 170

4. กิจกรรมทีน่ าs สนใจอีกอยsางน้ันคอื การสราq งรูปแบบฟองสบขูs องตqนไมสq ไตเนอร/ คณุ สามารถทำไดโq ดย การนำแผนs พลาสติกแข็งโปรsงใสสองแผsน และใสเs สาเลก็ ๆ ระหวาs งแผนs ท้งั สองเพอื่ ใหเq ป€นทกี่ ั้นชsองวาง ดงั รูป จมsุ เจqาสงิ่ น้ีลงในนำ้ สบูเs หลว เมอ่ื ดงึ มนั ข้ึนมา คณุ จะเห็นฟล„ ม/ สบsูทเี่ ชื่อมตsอกนั เป€นตqนไมสq ไตเนอรท/ ี่ สวยงาม เปน€ ทีน่ าs เสียดาย, อยsางไรก็ตามไมจs ำเปน€ ท่ตี อq งเปน€ รปู แบบตนq ไมสq ไตเนอรท/ ีน่ อq ยทส่ี ดุ ฟล„ ม/ สบsูใชหq า องคป/ ระกอบความยาวทีน่ อq ยท่ีสดุ แตมs นั เป€นเพียงวธิ ีทำธรรมดาเทsานนั้ ไมใs ชsสากล มคี วามเปน€ ไปไดq หลายทางทจ่ี ะเชอ่ื มตอs จุดสไตเนอรใ/ หสq มบรู ณโ/ ดยทำใหqไดqความยาวทน่ี qอยทสี่ ดุ ยกตัว- อยาs งเชsน คุณ จะจนิ ตนาการไดqวsาฟล„ ม/ สบนูs น้ั นsาตาเหมือนองคป/ ระกอบในสsวนขยายที่ 2 เม่ือมันถกู ยอกออกจากน้ำ สบเsู หลว หนาq 171

ทั้งหมดนี้เกย่ี วกับอะไร? เครือขsายท่ีคณุ ไดqปฏบิ ัติอยูบs นขอบเขตของตqนไมqสไตเนอร/ที่นอq ยทสี่ ุดมันถูกเรียกวsา“ตqนไมq” เพราะวsา พวกมันไมsมีการวนเป€นวงกลม เป€นแคsกิ่งกqานสาขาที่แผsออกจากลำตqนจริงเติบโตแบบแยกเป€นสsวนๆ โดยปกตจิ ะไมทs บั ซqอนกันพวกมนั ถูกเรียกวsาตนq ไมสq ไตเนอร/เพราะวsาจุดใหมsหรอื จดุ สไตเนอรส/ ามารถ ถกู เพิ่มในสถานีเดิมที่มีการเชื่อมตsอของตqนไมqอยูsแลqวไดqและพวกมันถูกเรียกวsา“ที่นqอยที่สุด”เพราะวsา พวกมันมีความยาวสั้นท่ีสดุ เมื่อเทียบจากตqนไมqอื่น ๆที่เชื่อมตsออยูsกับสถานีเหนsาน้ัน ใน Muddy City (กิจกกรมที่ 9) พวกเราเรียนรูqวsาจำนวนเครือขsายที่เชื่อมตsอสถานีนั้นมีระยะทางนqอย เมื่อความยาว ทั้งหมดนั้นถูกเรียกวsา “ตqนไมqสไตเนอร/ที่นqอยที่สุด” ตqนไมqสไตเนอร/เป€นเหมือนขqอยกเวqนที่จุดใหมs สามารถถูกนำมาใชqไดq มันเป€นเร่อื งท่ีนาs สนใจ ในขณะท่นี ั้นคืออลั กอลิทึมทม่ี ปี ระสทิ ธภิ าพทสี่ ุดเพอ่ื ใชqหาตqนไมqสไตเนอร/ท่ีนqอย ท่ีสุด (กิจกรรมท่ี 14) ตนq ไมสq ไตเนอร/น้นั มคี วามยากอยาs งมาก เพราะคณุ ตqองออกแบบตำแหนงs การวาง จุดเพิ่มเติม จุดที่ยากที่สุดของป'ญหาตqนไมqสไตเนอร/ไมsใชsในสsวนการกำหนดตำแหนsงที่แมsนยำของ จดุ สไตเนอร/ แตเs ปน€ ในสsวนของการออกแบบคราว ๆถึงสถานทีที่จะวางจุดเหลาs น้นั : ความแตกตาs งระยะ 2 วิธีในตัวอยsางที่ 2 สำหรับในตัวอยsางที่ 2 ครั้งแรกคณุ ตqองรูqวsาขอบเขตที่จะระบุจุดใหมsลงไปน้นั อยsู ตรงไหน จากนั้นเพียงปรับจูนพวกมันเพื่อหาตำแหนsงที่เหมาะสมที่สุดสำหรับแตsละโจทย/ ฟ„ล/มสบูsมี ประสทิ ธิภาพ อยsางมากและสามารถประมวลผล (คำนวณ) ไดq การคqนหาตqนไมqสไตเนอร/ทีน่ qอยที่สุดเป€นสsวนหนึ่งของเรือ่ งราวที่เกี่ยวขqองกับการประหยัดเงินจำนวน มากในธรุ กิจโทรศพั ท/ กอs นป‹ ค.ศ 1967 เมอื่ การดำเนนิ การเครอื ขsายโทรศัพท/สsวนบุคคลขนาดใหญsใน สหรัฐอเมรกิ าฯ มีจำนวนใบเสร็จคsาบรกิ ารทพี่ วกเขาถูกเรยี กเก็บไมไs ดqมาจากการคำนวนบนรากฐานของ จำนวนสายทถ่ี กู ใชqจริง แตsอยsูบนรากฐานของเครือขsายที่สัน้ ท่ีสุดซึง่ พอเพียงกวาs จดุ เร่มิ ตqนอัลกอริทึมที่ ใชใq นการคำนวณโอกาสในการใชqเป€นเทาs ไหรs ทำไดโq ดยการกำหนดตqนไมqสไตเนอรท/ นี่ qอยท่สี ดุ อยาs งไรก็ ตามประมาณป‹ ค.ศ. 1967 มันถูกใหqความสนใจโดยลูกคqา-สายการบิน,ในความเปน€ จริงดqวยสsวนกลาง หลักทั้งสามแหsง-ถqาพวกเขาเรียกรqองใหqมีสsวนกลางอันที่ 4 ที่จุดสื่อกลาง หลังจากนั้นความยาวของ เคร่อื งขsายก็จะลดลง บรษิ ทั โทรศัพท/ถกู บังคบั ใหqลดโอกาสอะไรทพี่ วกเขาความจะมี ถqามีการแลกเปลย่ี น ท่ีจดุ สไตเนอร/ แมวq sาสำหรับการต้งั คาs สวs นกลางตsาง ๆตqนไมqสไตเนอรท/ ่ีนqอยท่ีสุดมแี คs5% หรือ10% ซ่ึง นqอยกวsาตqนไมqสไตเนอร/ที่นqอยที่สุด สิ่งเหลsานี้สามารถเป€นการประหยัดที่คุqมคาs เมื่อเงนิ จำนวนมากมา หนาq 172

เกย่ี วขqอง ปญ' หาตนq สไตเนอรบ/ างครง้ั ถูกเรยี ก “ปญ' หาเครือขาs ยขนาดสน้ั ” เพราะวsาเกยี่ วกับการคqนหา เครือขาs ยทีส่ นั้ ทส่ี ดุ ทเ่ี ชอ่ื มตอs กลุมs ของสถานหี ลายแหลsง ถqาคุณบรรลกุ จิ กรรม 2 กจิ กรรมกsอนหนqา ปรศิ นาของนกั ทำแผนท่แี ละเมอื งแหงs นกั ทsองเท่ียว คุณจะไมs แปลกใจท่ไี ดยq ินวาs ป'ญหาตนq ไมสq ไตเนอรท/ น่ี qอยท่สี ุดคอื เอ็นพสี มบรู ณ/ [NP-complete] เหมอื นจำนวน ของสถานีที่เพิ่มข้ึน ดังนั้นจำนวนตำแหนsงที่เป€นไปไดขq องจุดสไตเนอร/และการลองหาความเป€นไปไดq ทั้งหมดที่เกี่ยวขqองกับงานวิจัยการเติบโตแบบทวีคูณ [an exponentially-growing search] นี้คือ ป'ญหาอกี วาs พนั เรอ่ื งของสิ่งทไ่ี มsเคยไดqรูqมากsอนทมี่ ีความเป€นไปไดqทจ่ี ะทำใหสq ำเร็จ หรือวsามีอัลกอรึทึม เวลาพหุนาม [polynomial-time algorithm] ที่ยังไมsถูกคqนพบ สิ่งที่เป€นที่รqูจกั กันคือถาq สิง่ นั้นเป€นอัล กอรทึ มึ เวลาพหุนามท่ถี ูกคนq เจอสำหรับป'ญหานี้ มนั สามารถเปล่ียนเปน€ การหาอลั กอรึทึมเวลาพหุนาม บนกราฟสี เพอ่ื ใชหq าชดุ ควบคมุ ที่นqอยทีส่ ดุ และสำหรับกลsุมเอน็ พีสมบรู ณอ/ ืน่ ๆ พวกเราอธิบายในตอนสุดทqายของกิจกรรมกอs นหนาq น้วี sา “NP” ใน เอ็นพีสมบูรณ/ หรอื NP-complete มีท่ีมาจาก “non-deterministic polynomial” และ “complete” อาq งอิงถงึ ความจริงท่วี sาอลั กอรทึ มึ เวลาพหุนามใชqแกqหนึ่งในป'ญหาเอน็ พสี มบูรณ/ มันสามารถเปลีย่ นเป€นอัลกอรึทึมเวลาพหนุ ามสำหรบั ป'ญหาอ่ืน ๆไดqเชนs กัน กลsุมของป'ญหาทีไ่ ดqถูกแกqไขในเวลาพหุนามถูกเรยี กวsา “P” ในอีกนัยหนึ่ง P = NP หรอื ไม?s คำตอบสำหรับคำถามน้ีนน้ั ไมsมใี ครรูq และมันเป€นหน่งึ ในปรศิ นาที่ยงิ่ ใหญขs องวิทยาศาสตร/ คอมพวิ เตอรใ/ นยุคนี้ หลายป'ญหาที่มอี ัลกอรึทึมเวลาพหุนามอยูs ถงึ แมqวาs อลั กอรทิ มึ เหลsาน้อี าจจะคsอนขqางชqา ซ่ึงถูกเรียกวsา “วsางsายหรือหัวอsอน [tractable]” หลายป'ญหาที่พวกเขาแกqไมsไดqถูกเรียกวsา “ดื้อดึงหรือวsายาก [intractable]” เพราะวาs ไมsวsาคุณจะคำนวณไดqเร็วเพียงใด หรือคุณใชqหนsวยประมวลผลหลายอันมาก เทsาไหรs ถqาขนาดป'ญหาเพมิ่ ขนึ้ เพยี งเล็กนอq ยก็หมายความวาs พวกมนั ไมsสามารถทจ่ี ะถูกแกปq 'ญหาไดqเลย ในทางปฏบิ ตั ิ ไมเs คยรูqเลยวาs ป'ญหาเอน็ พสี มบูรณ/รวมถึงปริศนาของนกั ทำแผนท,่ี เมอื งแหsงนักทอs งเทีย่ ว และถนนน้ำแข็งนั้นวsาไดqงายหรือไมs แตsนักวิทยาศาสตร/คอมพิวเตอร/สsวนใหญsมองในแงsรqายวsาเมื่อ ตqองการพิสูจน/วsาป'ญหาเอ็นพีสมบูรณ/น้ันคือเอ็นพีสมบรู ณ/หรือไมs มักไดqรับการยกยsองวsาเป€นเหมอื น หลกั ฐานท่ีหนกั แนนs วาs ป'ญหานั้นเปน€ ส่งิ ท่ีวsาไดยq ากอยาs งแทqจรงิ คณุ สามารถทำอะไรไดqบาq งเมื่อเจqานายของคณุ บอกใหคq ุณสรรคส/ ราq งอัลกอริทึมทีม่ ีประสิทธิภาพท่ีสุดที่ ไดqซึ่งวิธีทำที่ดีท่ีสดุ สำหรับปญ' หาน้ัน ๆ แตsคุณไมสs ามารถหาไดเq ลยแมqแตsวธิ ีเดียว เหมือนมนั จะเกิดขนึ้ แนsนอนเมื่อสายการบนชนกนั บนความจริงที่วาs คsาใชจq sายเครอื ขsายควรจะลดลงดqวยการดำเนินการดqวย หนาq 173

จดุ สไตเนอร/ ถือเปน€ เรือ่ งยอดเย่ยี มถqาคณุ พิสจู น/วsาน้ันไมsใชอs ัลกอริทมึ ท่มี ปี ระสทิ ธ-ิ ภาพท่สี ุด แตsมันเป€น เร่ืองยากมากทจ่ี ะพิสูจนผ/ ลลพั ธ/เชิงลบแบบนนั้ ในศาสตรแ/ หsงวทิ ยาศาสตร/คอมพวิ เตอร/ สำหรับผqูท่ีรqูวsา โปรแกรมเมอร/ท่ฉี ลาดอาจมาพรอq มอะไร ในอนาคตและใชqกลอบุ ายที่คลุมเครือเพอื่ แกqไขปญ' หา ดังน้ัน นsาเสียดายที่คุณไมsไดอq ยูsในตำแหนงs ที่กลsาวไดqวsาเป€นไดqไดqที่จะไมsมีอัลกอริทึมที่มีประสิทธิภาพที่สุด- ป'ญหานี้เป€นเรื่องที่วsาไดqยาก แตsถqาหากวsาคุณสามารถแสดงไดqวsาป'ญหาของคุณนั้นเป€นป'ญหาเอ็นพี สมบูรณ/ เมื่อนัน้ มันจะเปน€ จริงวsาคนกวsาพันคนในหอq งวิจัยทำงานบนป'ญหาที่เหมือน ๆกันกับของคุณ และลqมเหลวในการใหqไดqมาซ่ึงวธิ ีทำทีม่ ีประสิทธภิ าพทีส่ ุดดqวย นั้นไมsไดqใหqโบนัสแกsคุณแตจs ะใหqอะไรที่ เจgงสุดๆ! แนsนอนวsาในชีวติ จริงป'ญหาเหลาs น้ียงั คงตqองแกไq ขกนั ตsอไป และในกรณมี ผี่ ูqคนเปล่ยี นใชฮq ิวรสิ ตกิ [Heuristics] อลั กอรทิ มึ นั้นไมsไดรq บั รองวsาจะไดqมาซ่งึ วธิ ที ำทดี่ ที ี่สดุ ที่เปน€ ไปไดq แตจs ะไดqซง่ึ วิธีทำที่ ประกอบดqวยเปอรเ/ ซ็นตท/ ่เี หมาะทสี่ ดุ อัลกอรทิ ึมฮวิ รสิ ติกทำไดqเร็วมาก ๆและความสิ้นเปลืองทจี่ ะไมsไดq คำตอบนั้นอาจจะนqอย ดงั นั้นพวกมนั เป€นวิธีที่ดีเพียงพอสำหรบั งานรปู แบบนี้ มันเพยี งแคsนาs ผดิ หวงั ท่ไี ดq รูqวsาอาจมตี ารางเวลาหรอื แผนs ผงั ทีด่ ขี น้ึ เล็กนqอยของเครอื ขsายหรือถนน หนังสือสำหรับอาy นเพ่มิ เตมิ การ/ตูนสรqางจากหนงั สือ Computers and Intractability ของ Garey และ Johnson คอลัมน/“ การ สรqางคอมพิวเตอร/ใหมs” ของ Scientific American, มิถุนายนป‹ ค.ศ. 1984, ประกอบ ดqวย คำอธิบายสั้น ๆ ของวธิ กี ารทำตนq ไมq สไตเนอร/ โดยใชqฟองสบูsพรqอมคำอธบิ ายท่นี sาสนใจของอุปกรณ/ อนาลอ็ กอืน่ ๆ สำหรับการ แกqป'ญหารวมถึง a spaghetti computer เสqนเชือกเปลแมวสำหรับหาสsวนที่สั้นที่สุดในกราฟ และอุปกรณ/ แสงและกระจกสำหรับบอกวsาเป€นจำนวนเฉพาะหรือไมs สิ่งเหลsานี้จะปรากฏในสsวนเกี่ยวกับอนาล็อก คอมพิวเตอรใ/ น Dewdney's Turing Omnibus หนาq 174

บทที่ 5 แบงy ป•นความลับและการตอy สู^กบั อาชญากรรม

แบyงป•นความลบั และการตyอสก^ู ับอาชญากรรม คุณเคยไดยq นิ สายลบั ใชqรหสั ลับหรือเวทมนตรท/ ม่ี องไมเs หน็ ในการเขียนเพ่ือแลกเปลี่ยนขอq ความ น่ันคือ สง่ิ ทเ่ี ป€นเรอื่ งของ \"การเขqารหัส\" เร่ิมออกตวั เหมือนศลิ ปะการเขียนและถอดรหสั รหสั ลบั ในชsวง สงครามโลกครงั้ ที่สองภาษาองั กฤษไดสq รqางเครือ่ งจกั รทำลายรหสั อิเลก็ ทรอนกิ สแ/ บบพเิ ศษและใชqพวก มนั เพอ่ื ถอดรหสั ทหาร แลqวหลังจากนนั้ คอมพวิ เตอรก/ ็มาพรอq มกับเปล่ยี นแปลงทกุ อยาs ง และการ เขาq รหสั กเ็ ขqาสูsยุคใหมs การคำนวณจำนวนมากซ่ึงคงเปน€ ไปไมไs ดqมากsอนสามารถปรบั ใชเq พอื่ ชวs ยในการ ทำลายรหสั เมือ่ ผูqคนเร่มิ แบงs ปน' ระบบคอมพิวเตอรซ/ ึ่งกันและกนั มกี ารใชงq านรหสั สำหรบั ผใูq ชqบริการราย ใหมs เมอ่ื คอมพวิ เตอรถ/ ูกเชอื่ มโยงเขqากบั เครือขsาย มเี หตผุ ลใหมมs ากมายในการปกปอ› งขqอมลู จากคนท่ี อยากจะไดมq ัน เมอื่ จดหมายอิเล็กทรอนิกส/มาถงึ มันเปน€ สงิ่ สำคัญทจี่ ะทำใหแq นใs จวาs คนท่สี งs ขqอความเปน€ คนทพี่ วกเขาพดู ถึงจริง ๆ ตอนนี้ทผี่ ูqคนสามารถทำธนาคารออนไลนแ/ ละซือ้ และขายสนิ คqาผาs น คอมพวิ เตอร/ เราตqองมีวธิ ีการทปี่ ลอดภยั ในการวางคำสงั่ ซ้อื และสงs เงินสดบนเครอื ขาs ยคอมพิวเตอร/ และ ภยั คกุ คามท่เี พิ่มข้นึ ของผกqู อs การรqายท่โี จมตรี ะบบคอมพวิ เตอรท/ ำใหกq ารรกั ษาความปลอดภัย คอมพวิ เตอรม/ คี วามสำคญั มากยง่ิ ขึน้ การเขาq รหสั อาจทำใหqคณุ นึกถงึ คอมพวิ เตอรท/ เี่ กบ็ รหสั ผาs นลบั และสลบั ตำแหนงs ตวั อกั ษรของขqอความ เพือ่ ใหศq ตั รไู มsสามารถอาs นไดq แตคs วามเป€นจรงิ น้นั แตกตsางกนั มาก ระบบคอมพิวเตอรส/ มยั ใหมไs มไs ดqเกบ็ รหสั ผsานลบั เนือ่ งจากถqาพวกเขาทำทุกคนที่ไดรq ับการเขqาถงึ พวกเขาจะสามารถทำลายความปลอดภยั ทั้งหมดในระบบ นนั่ จะเป€นหายนะ: พวกเขาสามารถทำการโอนเงินทางธนาคารแบบปลอม, สงs ขqอความ ที่แกลqงทำเป€นคนอื่นอาs นไฟลล/ บั ของทกุ คน หรือปลอบแปลงคำสง่ั กองทัพรฐั บาล ทุกวันนรี้ หสั ผsานคือ จดั การโดยใชq \"ฟง' ก/ช่นั ทางเดียว\" ทเี่ ราพูดถึงในกจิ กรรม 14 และการเขาq รหสั ไมเs พยี ง แตsสลบั ตำแหนsง ตวั อกั ษรของขqอความ เทคนิคที่เกี่ยวขอq งกบั ปญ' หาทย่ี ากมาก - เชนs \"intractable\" แนะนำในสsวนที่ 4 ดqวยการใชกq ารเขาq รหสั คณุ สามารถทำสงิ่ ตsาง ๆ ทีค่ ุณคิดวsาเปน€ ไปไมไs ดq ในสวs นนีค้ ณุ จะคนq พบวธิ งี sายๆใน การคำนวณอายเุ ฉลยี่ ของคนในกลุมs โดยไมsมีใครรqูอายุของคนอืน่ เลย คณุ จะพบวsาคนสองคนน้นั ไมsไวqใจ ซึ่งกันและกัน โยนเหรียญและยอมรับผลทีอ่ อกมาแมqวาs จะอยูsกันคนละเมืองและไมเs ห็นเหรียญท่ีถูกโยน ไดqอยาs งไร และคณุ จะพบวธิ ีเขาq รหสั ขอq ความลบั ทส่ี ามารถถอดรหสั ไดqโดยบคุ คลเดยี วเทsานน้ั ถึงแมวq าs ทกุ คนรวqู ธิ เี ขาq รหสั ของพวกเขา หนาq 176

สำหรบั อาจารยr กจิ กรรมท่ตี ามประสบการณ/ตรงกบั ความทนั สมัยของเทคนคิ การเขqารหสั ซ่ึงแตกตาs งจากส่งิ ทค่ี นสsวน ใหญsคดิ ในใจเมอ่ื นกึ ถงึ ความลับและคอมพวิ เตอร/ มคี วามคิดหลักสองประการ ประการแรกคือแนวคดิ ของ \"โปรโตคอล [protocol]\" ซง่ึ เปน€ คำสงั่ อยsางเปน€ ทางการของการทำธุรกรรม โปรโตคอลอาจนำมาซง่ึ นกั การทตู แมกq ระท่งั มารยาท แตsคอมพิว-เตอร/กใ็ ชq งานเชนs กัน! งานท่ยี ากลำบากดูเหมอื นจะทำไดqโดยใชqโปรโตคอลงsาย ๆ ท่ีนาs ประหลาดใจ (กจิ กรรมที่ 16) ซง่ึ ใชqเวลาเพียงไมกs นี่ าทีแสดงใหqเห็นวาs กลมsุ คนทีร่ sวมมือกนั สามารถทำไดอq ยsางงsายดาย คำนวณอายุ เฉล่ยี ของพวกเขา (หรอื รายได)q โดยไมsมใี ครรอูq ายุของบคุ คล (หรอื รายไดq) ความคิดหลักทสี่ องคอื บทบาท ของความซับซอq นในการคำนวณ - การลวs งลำ้ - สามารถเลนs ไดเq มอ่ื มปี ฏสิ ัมพันธ/กบั สง่ิ อน่ื ๆ ผาs น คอมพวิ เตอร/ (กจิ กรรมที่ 17) แสดงใหqเหน็ วsาคนสองคนทไี่ มsไดqจำเปน€ ตqองเชอื่ ใจซ่ึงกันและกนั สามารถ เห็นดวq ยกับผลของการโยนเหรยี ญเม่อื พวกเขาเชอื่ มตsอกันทางโทรศัพทเ/ ทsาน้นั (กจิ กรรมนย้ี งั แนะนำใน ฐานะทเ่ี ป€นแนวคดิ นอกเหนอื จากวงจรตรรกะบลู นี และวิธกี ารทำงานกบั มัน) กิจกรรม 18 แสดงใหqเห็น วาs ผqคู นสามารถใชเq ทคนิคการคำนวณเพ่อื เขาq รหสั ขอq ความอยsางปลอดภัยไดอq ยาs งไร แมqวsาวธิ กี ารในการ เขาq รหสั คอื ความรสูq าธารณะที่ใคร ๆกร็ กqู ัน กจิ กรรมบางอยาs งเหลาs นี้ โดยเฉพาะกิจกรรมสุดทาq ยเป€นงานที่หนกั คณุ จะตอq งกระตqุนชัน้ เรยี นของคณุ โดยปลกู ฝง' ใหqนักเรยี นรูqสกึ แปลกใจวาs สง่ิ น้นั สามารถทำไดqเลย สำหรบั กจิ กรรมทที่ ำสำเรจ็ จริง ๆคนสวs น ใหญคs ิดวาs เปน€ ไปไมsไดq มนั มีความสำคญั ในการสรqางความรูสq กึ แปลกใจ, สอ่ื สารมัน และใหqมีการหยดุ พัก ชว่ั คราวเพ่ือใหqใหนq กั เรียนไมพs ลาดปา¸ อันท่ึง! สำหรบั ตนq ไมทq อ่ี าจคsอนขqางนsาเบื่อ กจิ - กรรมเหลsานอ้ี ยูใs น หมูคs วามทาq ทายและความซบั ซอq นทางเทคนคิ ในหนังสือมากท่ีสดุ หากพวกมันกลายเปน€ ยากเกินไป โปรดขqามไปยงั สวs นท่ี 6 ซ่งึ มีความแตกตาs งของตวั ละครอยาs งส้ินเชงิ , ไมใs ชsทางเทคนคิ สำหรบั ทางด^านเทคนคิ ในขณะท่คี อมพิวเตอรบ/ ุกรกุ ชีวติ ประจำวันของเรา การประยุกตใ/ ชกq ารเขาq รหัสอาจมีแนวโนqมท่คี sอน ขqาง สูง คนสวs นใหญsไมsรตูq วั เลยวาs โปรโตคอลอะไรคือการเขาq รหสั ทีท่ นั สมัยและมคี วามสามารถ ผลทไ่ี ดqคือ เมื่อมสี ถาบนั - ทัง้ ภาครฐั และเชงิ พาณิชย/ขนาดใหญs – ตั้งคาs ระบบท่เี กยี่ วขqองกบั ขqอมูลสวs นบคุ คล มันมี แนวโนมq ท่ีจะเปน€ เทคโนโลยีท่ที ำใหqกุญแจการตดั สนิ ใจเก่ียวกับวิธกี ารจดั การสิง่ ตาs ง ๆ, สิง่ ทตี่ อq งรวบรวม , ส่งิ ทค่ี วรทำทำใหพq รqอมใชqงานและกบั ใคร อยาs งไร หากผูqคนมคี วามเขาq ใจที่ดขี ้นึ เกย่ี วกับความเปน€ ไปไดq หนาq 177

ท่ีเกิดขึ้นโดยเทคโนโลยีท่ีทันสมัย พวกเขาจะสามารถมสี วs นรวs มอยาs งแขง็ ขนั มากข้นึ ในการตัดสินใจ และ สงั คมอาจจะลงเอยดวq ยโครงสราq งพ้ืนฐานขอq มลู ทแ่ี ตกตาs ง เน้ือหานเ้ี ก่ยี วกบั โปรโตคอลซsอนขqอมลู , โปรโตคอลการเขาq รหสั และการเขาq คีย/รหสั สาธารณะน้ัน โดยทว่ั ไปถอื วsาคอs นขqางมีความทาq ทายสงู ในดqานเทคนิคไมsใชsแนวคิดพน้ื ฐานทีเ่ ขqาใจยาก ในสถาน- การณ/จริงทเี่ กยี่ วขอq งกบั การคาq แบบอเิ ลก็ ทรอนิกส/ เทคโนโลยีจะฝง' อยใูs นซอฟต/แวรค/ อมพวิ เตอร/ซงึ่ ทำ ใหเq ทคโนโลยกี ารเขqารหสั ใชงq านงาs ยมาก แตsมนั กส็ ำคญั ทจี่ ะตqองเขqาใจความคดิ ทพ่ี วกเขายึดถอื เพอ่ื ที่จะ ไดqเขาq ใจถงึ สง่ิ ท่สี ามารถทำไดq ระบบการเขqารหัสลับเปน€ ทส่ี นใจของรฐั บาลไมใs ชsเพียงเพราะพวกเขา ตqองการใหกq ารส่ือสารเปน€ ไปอยาs งปลอดภยั แตเs น่ืองจากความกงั วลในการเขาq รหสั สอื่ สารน้นั สามารถใชq งานไดqโดยผูqกระทำสง่ิ ผิดกฎหมายตsาง ๆ เชนs การคาq ยาเสพตดิ และการกอs การรqาย หากคนดงั กลsาวใชกq าร เขqารหสั แลqวจากนั้นทำการดกั ฟง' ก็จะไมมs ปี ระโยชนห/ ากไมsมวี ิธกี ารถอดรหสั ทีใ่ ชไq ดq ความกังวลเหลsานี้ทำ ใหเq กิดการถกเถียงกันอยsางมากระหวาs งผqคู นทีเ่ ก่ยี วขqองกบั การบงั คบั ใชฎq หมายทีต่ อq งการจำกดั ความ แขง็ แกรงs ของระบบการเขาq รหสั ลับและพลเมืองเสรีนิยมที่ไมสs บายใจกบั การทร่ี ัฐบาลสามารถเขาq ถึงการ ส่ือสารสsวนบคุ คลไดq ในขณะทรี่ ฐั บาลสหรัฐอเมริกาไดqจำกัดการใชวq ิธีการเขาq รหัสลบั บางอยsางดวq ยถือวsา พวกมนั เป€นอาวธุ – เชนs ระเบิดและปนŽ , ทุกคนสามารถต้ังคาs ระบบการสอื่ สารทปี่ ลอดภยั ใหแq กขs qอมลู ที่ ถูกตqองและความสามารถทางเทคนคิ บางสsวนไดq แตมs นั อนั ตรายเม่ืออยใsู นมือคนกระทำความผดิ ในรฐั แหsงหนง่ึ มกี ารถกเถยี งกันอยาs งกวาq งขวางเกีย่ วกบั “ Clipper Chip” ซงึ่ เปน€ ระบบทมี่ รี หสั ผsานพเิ ศษท่ี เรียกวาs กญุ แจสญั ญาซ่ึงจัดขน้ึ โดยหนวs ยงานของรัฐทช่ี sวยใหสq ามารถถอดรหสั ขอq ความใด ๆ ทเี่ ขาq รหสั โดยชิป FBI และสหรฐั อเมรกิ ากระทรวงยตุ ิธรรมตqองการใหqชปิ นส้ี ำหรบั การสื่อสาร แตสs ิง่ นไ้ี ดรq บั การ คดั คqานอยsางมากเนอื่ งจากภัยคกุ คามตsอความเป€นสsวนตัว ระบบเขาq รหสั ลบั หลายประเภทมคี วามเป€นไป ไดทq างเทคนิค แตไs มไs ดเq ปน€ เชนs น้นั จำเป€นตอq งไดqรบั การยอมรับทางการเมือง! แนวคดิ การเขqารหสั มีแอพพลเิ คชัน่ มากมายนอกเหนือจากการเกบ็ ขอq ความลบั เชนs เดยี วกบั การยนื - ยนั วาs ขอq ความถูกสsงโดยคนทีพ่ ูดถึง นี่คอื \"การรบั รองความถูกตอq ง\" และไมมs ีพาณิชยอ/ เิ ล็กทรอนิกส/ ท่ี เปน€ ไปไมไs ดq มีวธิ ใี หqคนลงคะแนนดวq ยคอมพวิ เตอรโ/ ดยทไี่ มsมใี ครสามารถทจ่ี ะหาผทqู ีล่ งคะแนนใหไq ดq แมqแตsคนทีล่ งมอื ทำระบบคอมพิวเตอรเ/ องก็ตาม แตกs ย็ ังปอ› งกันคนลงคะแนนมากกวาs หน่งึ ครัง้ ไมไs ดq และ คณุ สามารถเลsนไพsทางโทรศพั ท/ไดq อาจฟง' ดไู รสq าระจนกระทัง่ คณุ ตระหนกั ดีวsาการทำขอq ตกลงทางธรุ กิจ ในโทรศพั ทจ/ ำนวนมากน้นั เป€นดังเชsนการเลนs โปกÈ เกอร/ ส่ิงเหลsานฟ้ี ง' ดเู ป€นไปไมไs ดq คณุ จะเริ่มสบั ไพทs างโทรศัพทไ/ ดอq ยาs งไร หากคุณกำลงั แขงs ขันกบั คนอ่นื ๆแลqว จะไมsเชอ่ื ใจพวกเขาเหรอ? คุณจะตรวจจบั คนน้ันไดqอยsางไร, สามารถดกั จับขqอความที่ถกู ปรับเปล่ยี นแลวq หนาq 178

สsงมนั ออกมาเหมือนตนq ฉบบั ไดหq รอื ไมs ถqาคณุ ไมสs ามารถทำสิง่ เหลาs นนั้ ไดq คุณไมsสามารถทำธรุ กจิ ทาง อิเลก็ ทรอนิกสไ/ ดq คุณตqองปอ› งกันไมใs หqอาชญากรทมี่ ีความรใูq นเชงิ เทคนิคทำการปลอมแปลงการอนุญาต สำหรับการถอนเงนิ ออกจากบญั ชีธนาคาร โดยสกัดกน้ั สายโทรศัพทร/ ะหวsางสถานี ณ จดุ ขาย และ ธนาคารเองตqองปอ› งกนั ธุรกจิ คูsแขงs จากความหายนะทเ่ี กิดขนึ้ โดยการสรqางคำสงั่ หรอื สัญญาทผี่ ดิ หรือ เปน€ เทจ็ ดqวยเทคนิคการเขาq รหสั สมยั ใหมsทำใหปq าฏิหาริยน/ ั้นเปน€ ไปไดแq ละกจิ กรรมเหลsาน้แี สดงใหเq หน็ วาs สามารถทำไดอq ยาs งไร มีหนังสือที่นsาสนใจมากมายเกี่ยวกับรหัสและการทำลายรหัส Codebreakers: the inside story of Bletchley Park เรียบเรียงโดย Hinsley และ Stripp ใหqผูqใชqงานมือใหมรs ูqวsาคอมพิวเตอรท/ ำลายรหสั ลับในชsวงสงครามโลกครั้งทส่ี องไดอq ยsางไร ซ่ึงการกระทำนน้ั ทำใหสq งครามสน้ั ลงอยsางมากและชsวยชีวิต คนมากมาย หนาq 179

กิจกรรมที่ 17 การแบงy ป•นความลบั - การซyอนขอ^ มลู โปรโตคอล สรุป เทคนคิ การเขqารหสั ชsวยใหเq ราสามารถแบงs ป'นขอq มลู กบั ผอqู ื่นไดq แตยs งั คงความเป€นสวs นตวั ในระดบั สงู อยsางนsาประหลาดใจ กจิ กรรมนแ้ี สดงใหเq หน็ ถงึ สถานการณท/ ม่ี ีการแชรข/ อq มลู อยsางไมเs ปด„ เผย: กลุsม ของนกั เรียนจะคำนวณอายเุ ฉล่ียของพวกเขาโดยไมsมใี ครตqองเป„ดเผยใหคq นอืน่ ๆรวqู าs อายเุ ทาs ไหรs เนอื้ หาทีเ่ ก่ียวขอ^ ง ü คณติ ศาสตร/ - จำนวนและคsาเฉล่ีย ทักษะ ü การคำนวณคาs เฉลย่ี ü ตัวเลขสุsม ü งานสหกรณ/ อายุ ü 7 ปข‹ นึ้ ไป อปุ กรณr นักเรียนแตลs ะกลมsุ จะตqองมี: ü กระดาษแผนs เลก็ และ ü ปากกา หนqา 180

การแบyงปน• ความลับ บทนำ กิจกรรมน้เี ก่ียวขqองกบั การหาอายุเฉลยี่ ของกลุsมนักเรียนโดยทุกคนไมsตอq งเปด„ เผยวsาอายุของพวกเขาคอื อะไร อีกวธิ ีหนึง่ สามารถหารายไดqเฉล่ยี (คsาเผอื่ ) ของนักเรียนในกลsมุ หรอื คลาq ยกันกบั รายละเอยี ดสsวน บุคคล การคำนวณสถติ เิ หลาs นี้ทำงานไดดq ีโดยเฉพาะกบั ผqใู หญsเนื่องจากผสqู ูงอายอุ าจมีความละเอยี ดอsอน มากข้นึ เกี่ยวกบั รายละเอยี ดเชsนอายแุ ละเงนิ ไดq คณุ จะตqองมนี ักเรียนอยsางนอq ยสามคนในกลsุม การบรรยาย 1. อธิบายใหqกลsุมทคี่ ณุ ตqองการหาอายเุ ฉลยี่ ของพวกเขาโดยไมมs ใี ครบอกคนอ่ืนวsาอายุเทาs ไหรs สอบถาม ขอคำแนะนำเกี่ยวกับวธิ กี ารทอ่ี าจทำไดq หรือแมqวsาพวกเขาเชื่อวาs สามารถทำไดq 2. เลือกนกั เรียนประมาณหกถงึ สบิ คนเพอื่ ทำงานดqวย มอบกระดาษแผนs เลก็ และปากกาใหqกบั นกั เรียนคน แรกและขอใหqพวกเขาแอบ เขียนเลขโดดสามหลักท่ี เลอื กแบบสsมุ หมายเลขบนแผsนดาq นบน ในตัวอยาs งน้ี 613 ไดรq บั เลอื กเปน€ หมายเลขสsมุ 3. ใหqนักเรียนคนแรกฉกี กระดาษหนqาแรกออก เพิม่ อายุ ของพวกเขาในการสุsมหมายเลขและเขียนในแผนs ทสี่ อง นกั เรียนคนแรกมอี ายุ 8 ป‹ แผนs ท่ีสองมเี ลข 621 พวก เขาควรฉกี หนาq น้นั ออกเกบ็ ไวq (และไมแs สดงใหใq ครเหน็ ) 4. แผนs กระดาษจะถกู สsงผาs นไปยังนกั เรยี นคนท่ีสอง คนท่จี ะบวกอายขุ องพวกเขาและเขยี นลงไปท่ี กระดาษแผนs บนสดุ ฉกี ออกแลวq เขยี นผลรวมของอายุในหนาq ถัดไป ในตวั อยาs งนกั เรียนคนทสี่ องมีอายุ 10 ป‹ หนาq 181

5. ทำตามขนั้ ตอนนโ้ี ดยใหนq ักเรียนฉีกหนาq ดาq นบนและเพม่ิ อายขุ องตัวเองลงบนกระดาษจนกวาs นกั เรยี น ทุกคนจะมีแผsนคนละใบ 6. คืนแผsนใหนq ักเรียนคนแรก ใหนq กั เรียนคนนั้นลบออกหมายเลขสมุs ด้ังเดิมจากหมายเลขบนแผsน ใน ตัวอยาs งแผsนนม้ี นี ักเรยี นประมาณหาq คนและหมายเลขสุดทาq ยคือ 657 มหี มายเลขเดมิ 613 ลบออก จากมนั ใหqหมายเลข 44 สิง่ นค้ี อื ผลรวมของอายุของนักเรียนและคsาเฉล่ยี สามารถเป€นไดq คำนวณโดย หารดqวยจำนวนนักเรียน ดังนน้ั อายเุ ฉล่ยี ของกลมุs ตัวอยsางของเราคือ 8.8 ป‹ 7. ช้ีใหนq กั เรยี นเหน็ วาs ตราบใดท่ีทกุ คนทำลายชนิ้ สวs นของพวกเขาเอง จะไมมs ีใครสามารถกำหนดอายุของ แตลs ะคนไดqหากไมsมคี นสองคนตดั สนิ ใจ ใหคq วามรวs มมือ หลากหลายและเพิม่ เติม ระบบนส้ี ามารถปรบั ใหqอนุญาตการลงคะแนนลบั ๆโดยใหqแตลs ะคนเพิ่ม 1 ถqาพวกเขาลงคะแนนใชs และ 0 ถqา พวกเขาลงคะแนนไมsใชs แนsนอนวาs ถาq บางคนเพิม่ มากกวsาหนง่ึ (หรอื นอq ยกวาs ศูนย/) การลงคะแนนหลังจากน้ัน จะไมsเป€นธรรม แมqวsาพวกเขาจะเสีย่ งตอs การปลุกระดมความสงสัยหากทุกคนลงคะแนนใชsเนื่องจากจำนวน คะแนนโหวตจะมากกวsาจำนวนคน หนาq 182

ท้งั หมดน้เี กย่ี วกับอะไร? คอมพวิ เตอรเ/ กบ็ ขอq มลู สsวนบคุ คลมากมายเกยี่ วกบั เรา: ยอดเงินธนาคารของเรา, เครอื ขsายโซเชียลของ เรา, เราตqองเก็บภาษีเทาs ไร, นานแคsไหนที่เราจะไดใq บอนุญาตขับรถ, ประวัติเครดติ ของเรา, ผลการตรวจ เวชระเบียนและอ่นื ๆ ความเป€นสsวนตวั เปน€ สงิ่ สำคญั มาก! แตเs ราจำเปน€ ตอq งแบsงปน' ขอq มลู บางสิ่งนกี้ ับ ผอูq นื่ ตวั อยsางเชนs เมอ่ื ชำระคsาสนิ คาq ทรี่ าq นคqาโดยใชบq ัตรธนาคารเราทราบวาs ราq นคqาตqองตรวจสอบวsาเรา มีเงินทนุ เพยี งพอใหใq ชไq ดq บอs ยคร้ังทเ่ี ราตqองใหขq อq มลู มากกวาs ทจี่ ำเป€นจริง ๆสำหรบั ตวั อยsาง เชนs หากเราทำธุรกรรมการเงินทาง อิเลก็ ทรอนกิ ส/ ทร่ี qานคาq คนq หาวsาเราเป€นใครดqวยหมายเลขบัญชีของเราและชือ่ ของเรา คือนอกจากนี้ ธนาคารยงั ทราบวsาเราไปซ้ือของท่ีไหน ธนาคารสามารถสราq งโปรไฟลข/ องใครบางคนโดยการตรวจสอบ สง่ิ ตsาง ๆ เชนs ทพ่ี วกเขาเติมน้ำมนั หรอื ราq นขายของชำ, พวกเขาใชqจsายกับรายการเหลsานีเ้ ทsาใดในแตลs ะ วนั เม่ือมกี ารเยีย่ มชมสถานทเ่ี หลsาน้ี ถqาเราจsายดวq ยเงนิ สดขอq มูลสวs นใหญกs ็จะไมถs กู เปด„ เผย คนสวs นใหญs ก็ไมsตอq งกงั วลมากเชsนกันเกยี่ วกับการแบsงปน' ขqอมลู นี้ แตมs ีศกั ยภาพทจ่ี ะถกู ทำราq ยไมsวsาจะเปน€ การตลาด เปา› หมาย (ตวั อยาs งเชsนการสsงโฆษณาการเดนิ ทางใหqกับผทqู ี่ใชqจsายมากกับตวั๋ เครือ่ งบนิ ) การเลอื กปฏบิ ตั ิ (เชsน เปน€ การเสนอบรกิ ารทด่ี กี วาs ใหกq ับคนทีธ่ นาคารมักจะรบั เชsนลูกคqาทร่ี ำ่ รวย) หรอื แมกq ระทัง่ แบล็ก เมล/ (เชsนขsูวsาจะเป„ดเผยรายละเอยี ดของการทำธุรกรรมทนี่ sาอบั อาย) หากไมมs ีอะไรอยาs งอื่นผqูคนอาจ เปลย่ี นวธิ ีทีพ่ วกเขาซอื้ สินคqาถาq พวกเขาคดิ วsามคี นอาจกำลงั ตรวจสอบพวกเขาอยูs การสญู เสียความเป€นสวs นตัวนี้ไดรq บั การยอมรับอยsางกวาq งขวาง แตกs ารมอี ยูsของโปรโตคอลการเขqา รหสั ทท่ี ำใหเq ราสามารถทำธรุ กรรมทางการเงินทางอเิ ลก็ ทรอนิกสใ/ นระดับเดยี วกนั กับความเป€นสวs น-ตวั ทเ่ี รา จะไดรq ับดqวยเงนิ สด มันอาจจะยากทจ่ี ะเช่อื เงินนน้ั -สามารถโอนจากบญั ชธี นาคารของคณุ ไปยงั บัญชีของ รqานคาq โดยไมตs อq งใหqใครก็ตามทร่ี วูq าs เงนิ มาจากไหนหรอื ไปทไ่ี หน กิจกรรมนที้ ำใหธq รุ กรรมดังกลาs วมีความ นาs เช่อื ถอื มากขนึ้ : ทง้ั สองสถานการณ/เก่ยี วขqองกบั การแบงs ปน' ขอq มูลที่ จำกัด และสามารถทำไดโq ดย โปรโตคอลท่ีฉลาด หนงั สือสำหรับอาy นเพม่ิ เตมิ รายงานคลาสสิกทีเ่ นนq ประเด็นเหลsานี้ถูกเขียนขึ้นดวq ย David Chaum ดqวยหัวขqอเรื่องวsา “Security without identification: transaction systems to make Big Brother obsolete.” รายงานนี้อsาน งาs ยและใหตq วั อยsางของการซอs นขqอมลู โปรโตคอลรวมถึงความเปน€ สวs นตัวอยsางสมบูรณ/ การทำธรุ กรรม หนาq 183

สามารถทำไดqโดยใชq “เงินอิเล็กทรอนิกส/.” มันสามารถพบไดqในคมนาคมของพลอากาศเอกตุลาคม 2528 หนาq 184

กิจกรรมที่ 18 การโยนเหรียญของชาวเปรู - โปรโตคอลการเข^ารหัสลบั บทสรุป กิจกรรมนี้แสดงใหqเห็นถึงการทำงานที่เหมือนจะเป€นไปไมsไดq ใหqสามารถทำงานไดแq ละเรียบงsาย เป€นการทำงานแบบสุsมอยsางยุติธรรมโดยใชqวิธีการโยนเหรียญระหวsางบุคคล สองบุคคลที่ไมs จำเปน€ ตqองมีความไวเq น้ือเชอ่ื ใจกันโดยใชqแคsโทรศพั ทเ/ ปน€ สือ่ กลางเทาs นน้ั เนื้อหาที่เกยี วขอ^ ง ü คณิตศาสตร/ – ตรรกะและการใชเq หตผุ ล ü คณิตศาสตร/ – ตรรกะบูลนี ทักษะ ü ตรรกะบลู ีน ü ฟง' กช็ น่ั ü การแกqปริศนา อายุ ü 9 ปข‹ ึน้ ไป วัสดอุ ปุ กรณr นักเรียนแตลs ะกลุมs ตอq งการวสั ดุอุปกรณด/ ังตอs ไปนี้ ü สำเนาของใบงานกจิ กรรม การโยนเหรียญของชาวเปรู ü กระดมุ 2 โหล หรอื เหรยี ญทมี่ ีสสี ันตาs งกนั 2 สี หนqา 185

การโยนเหรยี ญของชาวเปรู บทนำ กิจกรรมนี้ไดqออกแบบและเริ่มตqนจัดทำเมื่อผูqเขียน (MRF) ไดqทำงานกับนักเรียนในประเทศเปรู, คุณ สามารถปรบั เปลี่ยนเรอ่ื งราวใหสq อดคลqองและเหมาะสมกับพ้ืนทีท่ อq งถน่ิ ของคณุ ไดq ทีมฟุตบอลของเมือง ลิมsา และ กุสโกq จะตqองตัดสินใจวsาใครจะเป€นผูqจัดการแขsงขันฟุตบอลในรายการ แขงs ขนั ชงิ แชมปÏ วธิ ่ที จ่ี ะตดั สนิ ท่งี าs ยทส่ี ดุ คือการโยนเหรียญ แตsเมอื งทัง้ สองเมืองนน้ั มรี ะยะทางที่อยหูs sางกัน มากและ อลิเซีย ซง่ึ เป€นผqูแทนของเมืองลิมsาและ เบนิโตq ซงึ่ เป€นผแqู ทนของเมอื ง กสุ โกq ไมsมเี วลาและเงินทุน ที่จะไปตัดสินการโยนเหรียญดqวยกัน พวกเขาสามารถทำมันผsานทางโทรศัพท/ไดqหรือไมs? อลิเซียสามารถ เปน€ คนโยนเหรยี ญและ ใหเq บนิโตเลอื กวsา เลือกหวั หรือกqอย แตสs ิ่งนี้จะไมไs ดqผลเพราะถqาเบนโิ ตq เลอื กหวั อลิ เซียจะสามารถบอกไดqวsา “ขอโทษนะ ผลลพั ธ/ท่อี อกมนั คอื กqอย” และเบนิโตqจะไมsไดqเปน€ ผทqู ี่ฉลาดเลย โดย ปกตแิ ลqวอลเิ ซียไมไs ดคq นที่มีนิสัยขโ้ี กงหรอื หลอกลวงผูqอ่ืนแตอs ยsางใด แตsการโยเหรียญครั้งน้ีคือการตัดสินท่ี สำคัญและตรึงเครยี ดวsา เมืองไหนจะเป€นตวั แทนจดั การแขงs ขันชิงแชมปÏ และถึงแมqวาs อลิเซียจะพูดความ จรงิ และ เบนโิ ตเป€นฝ¸ายแพใq นการโยนเหรียญ เขาจะเช่ือหรือไมsวsาเขานน้ั แพจq ริงๆ นกั เรยี นจะไดqรบั ประโยชน/จากกิจกรรมอยาs งเต็มที่ถาq เรียนรเqู รอ่ื งเลขฐานสอง (การนับจำนวนจุด), แนวคดิ เรื่อง ความเทาs เทยี ม (การสงั เกตกุ ารพลิกของการด/ เวทมนตร)/ และเห็นตวั อยsางของฟง' ก/ชัน่ ทางเดยี วในกจิ กรรมของ เมอื งแหงs นกั ทอs งเที่ยว หนาq 186

น่คี ือสง่ิ ทพี่ วกเขาท้ังสองตัดสินใจท่จี ะทำเม่อื ทำงานรวs มกนั พวกเขาจะออกแบบวงจรที่ประกอบไปดวq ย ประตแู ละ (AND - Gate) และ ประตูหรือ (OR – Gate) ตามตัวอยาs งท่อี ธบิ ายไวqดาq งลsาง โดยหลกั การแลวq พวกเขาสามารถทำสงิ่ นโ้ี ดยผาs นทางโทรศัพทแ/ มqวาs จะเปน€ สิ่งที่สามารถยอมรบั ไดqในทางปฏิบัตเิ ทาs นั้น บาง ทมี นั อาจจะเปน€ วธิ ที มี่ ือความนsาเบื่อซักเลก็ นอq ย (วธิ ีนีส้ ามารถทำไดผq sานทางจดหมายอิเลก็ ทรอนกิ ส/ (E- mail) ไดqดวq ยเชนs กัน) ในระหวาs งท่ที ้ังสองสรqางวงจรขึน้ มานน้ั ทั้งสองสราq งวงจรทีต่ นเองมัน่ ใจวาs วงจรน้นั ซบั ซอq นพอทจี่ ะทำใหอq ีกฝา¸ ยไมsสามารถโกงไดq วงจรทไ่ี ดนq ั้นผลสดุ ทาq ยแลวq จะเผยแพรsใหสq าธารณะรบั รูq การอภปิ ราย กฎของ ประตูและ (AND-Gate) และ ประตหู รอื (OR-Gate) น้ัน งsายมาก “ประตู (Gate)” แตลs ะอันจะมี 2 อนิ พตุ และ 1 เอาต/พตุ แตลs ะอินพตุ สามารถเป€นไดทq งั้ 0 หรือ 1 (เลขฐานสอง) ซ่งึ สามารถ ตีเปน€ ความหมายอกี อยsางไดกq ค็ อื จรงิ (True) และ เท็จ (False) ตามลำดบั เอาตพ/ ุตของประตูและ (AND-Gate) จะเป€น 1 (จริง) เฉพาะเมอื่ อนิ พตุ ของประตูและ (AND-Gate) นั้นเปน€ 1 (จรงิ ) ทงั้ คsู หรือ 0 (เทจ็ ) ทงั้ คูs ตวั อยsางเชsน ประตแู ละ (AND-Gate) มี 0 และ 1 เปน€ อินพุต (รปู ดqานบนขวา) จากนนั้ เอาตพ/ ุต (สีเ่ หลี่ยมจตุ รสั รปู ดqานบนขวา) น้ันจะเป€น 0, เอาตพ/ ตุ ของ ประตหู รอื (OR-Gate) จะเป€น 1 (จรงิ ) ถาq ท้ังสอง (หรือทั้งสอง) ของอินพตุ น้นั เป€น 1 (จรงิ ) และ 0 (เทจ็ ) ดงั นั้นเอาตพ/ ตุ ของ ประตหู รอื (OR- Gate) จงึ เป€นอินพุตตวั นึงสำหรับอินพุต 0 และ 1 เอาต/พุตของประตู (Gate) หนง่ึ สมารถใชเq ชอื่ มตsอเพอ่ื เปน€ อนิ พุตของอีกประตู (Gate) อกี อนั ไดq (สามารใชqเชื่อ ตsอหลายๆประตู (Gate) ไดqเชsนกัน) เพื่อที่จะสรqางผลกระทบตsอเอาต/พุต และวงจรที่ซับซqอนมากยิ่งข้ึน ตัวอยsางเชsนวงจรดqานซqาย(รูปดqานซqาย) เอาต/พุตจากประตูหรอื (OR-Gate) ชั้นที่สอง เชื่อมตsออยูsกับอินพตุ ของประตูหรือ (OR-Gate) ในชั้นที่สามโดยมีผลกระทบวsาถาq อินพุตท้ังหมด 4 อินพุตนั้นมีคsาเปน€ 1 จะทำใหq เอาต/พุตของวงจรนี้ออกมาเป€น 1 (ในวงจรในรูปดqานขวา) เอาต/พุตของสองตัวแรกจะถูกป›อนเขqาไปในสอง ประตู (Gate) ท่อี ยดsู qานลาs ง ดงั นั้นวงจรทั้งหมดจึงมคี sาเอาตพ/ ุต 2 คsา หนาq 187

สำหรับการโยนเหรียญของชาวเปรูนั้น เราตqองการวงจรท่ีซับซqอนมากขึ้น ในแผsนใบงานกิจกรรมนี้ มีอินพุต ท้ังหมดหกตวั และเอาทพ/ ตุ ท้ังหมดหกตัว ตวั อยsางดqานลาs งคอื ตัวอยาs งการทำงานของอินพุตทงั้ หมดหนึ่งชุด วธิ ีทีว่ งจรนีจ้ ะสามารถใชใq นการโยนเหรียญผsานทางโทรศัพทไ/ ดมq ดี ังตsอไปนี้ อลเิ ซียจะสมุs เลือกอินพุตและใสsไป ยังวงจรท่ปี ระกอบไปดqวยเลขฐานสอง 6 หลัก (0 หรือ 1) ซึง่ ตวั เลขเหลsาน้นั เธอจะเกบ็ เปน€ ความลบั จากน้นั เธอ จะวางตัวเลขทัง้ หมด 6 หลัก ลงไปในวงจร และ สsงคsาเอาต/พตุ ของวงจรเหลsานน้ั ใหqกบั เบนโิ ตq ตอs ไปเมือ่ เบนิโตq ไดqรับเอาต/พุตของวงจรแลqว เขาจะตqองพยายามเดาวsาอินพุตที่อลิเซียใสsลงไปในวงจรนั้นเป€น จำนวนคี่หรือ จำนวนคูs – อีกความหมายนงึ คอื เขาตqองเดาความคลาq ยคลึงของอนิ พุตทีอ่ ลเิ ซยี ใสเs ขqาไปในวงจร หากวงจรน้ัน ซับซอq นพอ เบนิโตจq ะไมsสามารถหาคำตอบไดแq ละการเดาของเขาทง้ั หมดจะเปน€ แคsการเดาสsมุ เทsาน้นั (อันทีจ่ รงิ เขqาสามรถใชกq ารโยนเหรยี ญเพ่ือเลอื กอินพตุ กไ็ ด)q ถqาเบนโิ ตชq นะ การจัดการแขงs ขนั ชิงแชมq ปÏจะจัดใน กุสโกq ถqา การเดาของเบนโิ ตนq ัน้ ถูกตqอง; อลิเซยี จะชนะ และการแขsงขนั น้นั จะจดั ในลมิ sา ถqาเบนโิ ตเq ดาผดิ เม่ือเบนิโตqบอ หนqา 188

กอลซิ ียในส่งิ ทเี่ ขาเดาแลqว อลิเซียจะเปด„ เผยตวั เลยท่เี ธอเก็บไวเq ป€นความลบั ในตอนแรกใหqแกเs บนโิ ตq เพอ่ื ใหqเขา ใชqยนื ยนั ผลผลิตของเอาตพ/ ุตท่ีเขาเดา แบงs นกั เรยี นออกเปน€ สองกลุมs ยsอย ใหqวงจรกบั เหรยี ญแกนs ักเรียนแตลs ะกลsมุ , อธิบายเรอ่ื งราวและสถานการณท/ ี่ จะทำใหqนักเรียนสามารถเขqาใจเรื่องราวไดqมากขึ้น เชsน ใหqพวกเขานึกถึงภาพตัวเป€นเป€นกัปตันในการแขsงขนั กีฬาของโรงเรียน พวกเขาจักการโยนเหรียญกบั โรงเรียนคูแs ขsง สรqางแบบแผนสำหรับการนับสีโดยใชqเหรียญ หรือกระดมุ – สแี ดงมีคsาเปน€ 0 สีนำ้ เงนิ มคี าs เป€น 1 หรือจะใชqเปน€ สีอ่นื ๆ ก็ไดq - และใหนq ักเรยี นทำเครอื่ งหมาย อธิบายทด่ี าq นบนของใบงานเพอ่ื ชวs ยในการจำ แสดงวิธีการวางเหรียญบนอินพุตใหqนักเรียนดูแสดงตัวเลขที่อลิเซียเลอื กจากนัน้ อธิบายกฏพ้ืนฐานของ ประตู และ (AND-Gate) และ ประตหู รือ (OR-Gate) ท่ีไดqสรปุ ไวqแลqวบรเิ วณดqานลาs งของใบงาน (พิจารณาใหqนักเรียน ใชสq ีตามท่กี ำหนด) แสดงวธิ กี ารทำงานผsานวงจรวางเหรียญท่ี โหนด (Node) เพอ่ื รับเอาตพ/ ุตที่สอดคลqองกัน สงิ่ เหลsานี้ควรจะทำ ดqวยความถกู ตqองแมsนยำและความระมัดระวัง ตารางคำตอบ (ไมคs วรมอบใหqนกั เรียน) แสดงผลลัพธข/ องแตsละ อนิ พตุ ที่เปน€ ไปไดq เพ่ือใชใq นการอาq งองิ เม่ือเกดิ ขอq สงสยั หนqา 189

ตอนนีแ้ ตลs ะกลมsุ ควรจะเลอื กวsากลมsุ ไหนจะเป€น อลิเซีย และ กลมsุ ไหนจะเป€น เบนิโตq ในแตsละกลมุs สามารถแบงs ครึง่ และแตลs ะครงึ่ สามารถเลอื กทจ่ี ะเปน€ อลิเซียหรือเบนโิ ตq ไดqตามลำดบั อลเิ ซียควรจะสมsุ เลอื กอนิ พตุ สำหรบั วงจร, คำนวนเอาตพ/ ตุ และบอกเอาตพ/ ตุ ทไี่ ดqเหลsาน้นั ใหqกับเบนโิ ตq เบนโิ ตqจะเดาความคลqายคลึงของอินพตุ (ไมs วาs จะประกอบไปดqวยเลขคูหs รอื ค่ีในน้ัน) มันจะสามารถแสดงออกชัดเจนวาs กระบวนการทัง้ หมดที่เบนิโตqใชqน้ัน เป€นแคกs ารเดาสมsุ จากนนั้ อลิเซียจะบอกทุกคนวsาสิ่งท่เี ธอปอ› นเขqาไปในวงจรนน้ั คืออะไร เบนโิ ตqจะชนะถqาเขqา เดาความคลาq ยคลงึ ของจำนวนเหลาs นนั้ ถูกตqอง เบนิโตqสามารถตรวจสอบวsาอลิเซยี นนั้ ไมsไดqโกงและแอบเปล่ียน อนิ พุต โดยตรวจสอบจากอินพตุ ของวงจรนั้น ในจุดนก้ี ารโยนเหรียญเปน€ อันเสร็จสมบรู ณ/ เบนิโตqสามารถโกงไดถq qาเขqาคqนพบอินพตุ ทส่ี รqางมาจากเอาตพ/ ุตท่ีเขาไดรq ับมา ดังนัน้ อลิเซียตqองมั่นใจวsาวงจรท่ี เธอทำน้นั เป€นวงจรฟง' กช/ ัน่ ทางเดียว ทไ่ี มsสามารถไลsยqอนกลบั ไดตq ามความหมายทกี่ ลาs วไวใq นกจิ กรรมที่ 14 เพื่อ ปอ› งกันการโกงท่ีจะเกิดในไดqโดยเบนโิ ตq ฟ'งกช/ นั่ ทางเดยี วคอื ฟ'งก/ชัน่ ท่เี อาต/พุตงsายตsอการคำนวนถqารูqวsาอินพุต คืออะไร แตsการคำนวนยqอนกลับนัน้ การอินพุตจะยากมากถาq รูแq คเs อาต/พตุ ทใ่ี หมq า อลิเซียสามารถโกงไดถq qาเธอสามารถหาอินพุตสองอันจากความคลqายคลงึ ของเอาต/พตุ ตรงกันขqามท่ีเหมือนกัน ดังนั้น ไมsวsาดqวยวิธีใดก็ตามท่ีเบนิโตqใชqเดาอลิเซียสามารถบอกขqอมูลไดqวsา สิ่งทีเ่ ขากำลังทำอยูsน้ันผิดดังนั้นจึง เปน€ หนาq ท่ีของเบนิโตทq จ่ี ะทำใหqแนsใจวsา วงจรเหลาs นนั้ ไมsไดq แมพ (MAP) อนิ พตุ แตกตsางกันมากจนเกินไป ไป ยงั เอาตพ/ ุตเดียวกัน ดูวsานักเรียนสามารถหาวิธีที่อลิเซียหรือเบนิโตqใชqโกงไดqหรือไมs จากบรรทัดแรกของตารางคุณจะเห็นไดqวsา อินพุตท่ีแตกตาs งกนั หลายตวั นั้นสามารถสรqางผลลัพธ/ 010010 ไดq อาทิเชsน 000001, 000011, 000101 เป€น ตqน ถาq อลเิ ซยี ประกาศผลลัพธ/ 010010 เธอสามารถเลือกอินพตุ 000001 เบนิโตqจะเดาคsาความคลาq ยคลึงเป€น จำนวนคsู และ ถาq อนิ พุตเป€น 000011 เขาเดาคาs ความคลาq ยคลงึ เป€นเป€นจำนวนค่ี ดqวยวงจรอนั นี้ มันจึงเปน€ เรื่องยากทเ่ี บนิโตจq ะสามารถโกงไดq แตถs าq ผลลัพธ/ออกมาเป€น 011000 แสดงวาs อินพุต ตอq งประกอบไปดวq ย 100010 ไมมs ีความเป€นไปไดqอื่น ๆ (สามารถตรวจสอบสง่ิ เหลาs นไ้ี ดผq sานทางตาราง) ดังนั้น ถqานีค่ ือคsาทอ่ี ลิเซียเลอื กใชq เบนิโตqจะสามารถเดาไดแq มqกระท่งั คาs ความคลาดเคลือ่ น และม่นั ใจไดqวาs สิง่ ท่ีเขาเดา นั้นถูกตqอง ในสsวนของระบบคอมพวิ เตอรน/ ้นั จะใชจq ำนวนบิต(Bits) มากกวsาดังนนั้ จึงมคี วามเป€นไปไดqมากเกิน กวsาทจ่ี ะลองไดqหมดทุกคsา (แตลs ะบติ (Bits) ท่ีเพ่ิมเขqามา จะทำใหคq าs ความเปน€ ไปไดqเพ่มิ ข้นึ 2 เทาs ) ในขณะน้ขี อใหqนักเรียนแตลs ะกลุsมกำหนดวงจรของตวั เองเพอ่ื ใชqสำหรบั ในกิจกรรมนี้ และดวู าs พวกเขาสามารถ หาขอq ผดิ พลาดวาs วงจรท่พี วกเขาทำนั้นเออื้ ตsอการท่จี ะทำใหอq ลเิ ซยี โกงไดหq รอื ไมs หรืออีกแบบนงึ คือ วงจรน้ันทำ ใหเq บนโิ ตสq ามารถโกงไดqงsายหรือไมs ไมมs เี หตผุ ลที่วาs วงจรจะตอq งมีอินพตุ ทัง้ หมดหกตวั และอาจจะมีจำนวนของ อนิ พุตและเอาตพ/ ุตที่แตกตsางกนั ก็เปน€ ไปไดq หนqา 190

ใบงานกิจกรรม : การโยนเหรยี ญของชาวเปรู เลอื กอินพุตบางสวs นสำหรับวงจรนี้ และจงหาวsาเอาต/พุตของวงจรน้คี ืออะไร หนาq 191

รปู แบบและสวy นขยาย ปญ' หาท่ีเกดิ ขนึ้ ชดั เจนในระหวsางการปฏบิ ตั คิ อื การรวs มมอื กนั เพื่อทจ่ี ะสราq งวงจรท่ี อลเิ ซยี และเบนโิ ตq สามารถยอมรบั รวs มกนั ไดq ส่ิงน้อี าจจะเปน€ กจิ กรรมทส่ี นกุ สำหรบั เด็ก ๆ แตมs แี นวโนqมท่จี ะปฏบิ ัติจรงิ ไมไs ดq โดยเฉพาะอยsางยง่ิ การปฏบิ ตั ผิ sานทางโทรศัพท/ แตsอยาs งไรกต็ ามมันมที างเลือกท่ีงาs ยๆท่ี อลเิ ซียและเบนิ โตqจะสรqางวงจรของพวกเขาขนึ้ มา และหลังจากน้นั พวกเขาจะเปด„ เผยวงจรน้นั ใหรq ับรตqู อs กัน จากนัน้ อลิ เซียจะนำอนิ พุตทเี่ ธอเกบ็ ไวเq ปน€ ความลับในตอนตนq มาใสใs นวงจรทง้ั สองและนำเอาตพ/ ุตทัง้ สองมาเช่ือเขqา ดวq ยกันโดยการเปรยี บเทยี บบิต(Bits) ทมี่ ีความสอดคลอq งกนั และทำใหเq อาต/พุตสุดทาq ยเป€นอนั เดียวกันถาq พวกมนั เทาs กนั หรอื มผี ลลพั ธ/เทาs กับ 0 ในสถานการณ/เชsนนผ้ี เูq ขาq รวs มจะไมsสามารถโกงไดq แตถs าq มีวงจรหนึ่ง ในน้ันเป€นวงจรทที่ ำงานไดเq พียงทางเดียว ดังน้ันการรวมกนั ของทงั้ สองวงจรก็จะเป€น ฟ'งกช/ ่ันทางเดยี ว เหมอื นกนั ทงั้ หมด รปู แบบอีกสองอยsางตsอไปน้นั ไมไs ดqมีความเก่ียวขอq งกบั โปรโตคอลการเขqารหัสหรอื การโยนเหรยี ญ แตsเป€น แนวคิดของการสรqางวงจรทป่ี ระกอบไปดวq ย ประตแู ละ(AND-Gate) และ ประตูหรอื (OR-Gate) พวกเขา สำรวจความความคิดพ้นื ฐานบางอยsางทสี่ ำคัญซึง่ ไมไs ดqมีแตใs นวงจรคอมพวิ เตอร/ แตรs วมไปถึงในตรรกะดqวย ตรรกะประเภทนเ้ี รยี กวsาพชี คณิตแบบบลู ีน ซงึ้ ตั้งชื่อตามนกั คณิตศาสตร/ George Boole (1815 - 1864) นักเรียนอาจจะสงั เกตเหน็ วาs ถาq อนิ พุตทงั้ หมดมีคsาเป€น 000000 ผลลพั ธ/กจ็ ะ มคี sาออกมาเทาs กบั 0 และเชsนเดยี วกนั ถqาอินพตุ ทง้ั หมดมคี าs เปน€ 111111 ผลลัพธก/ ็จะมคี sาออกมาเทsากับ 1 (อาจจะมอี นิ พตุ อ่ืน ๆนอกเหนอื จากน้ี ท่ี สามารถสราq งผลลพั ธ/ที่มีคาs เหลsานีไ้ ดเq ชนs กนั ตัวอยsางเชนs 000010 - ผลลัพธ/ ทั้งหมดมคี sาเทาs กบั 0 ในขณะท่ี 110111 ผลลพั ธท/ ง้ั หมดจะมคี าs เทาs กบั 1 ) นี่ คอื ผลของความจรงิ ทีว่ sาวงจรถูกสราq งนีจ้ าก ประตแู ละ(AND-Gate) และ ประตหู รือ(OR-Gate) โดยการเพมิ่ ประตไู ม(s NOT-Gate) ซง่ึ จะมอี ินพตุ เพียง คาs เดยี ว และผลลัพธ/จะเปน€ คาs ท่ตี รงกันขqามกบั อินพตุ (เชsน 0 à1 และ 1 à 0 ) นกั เรยี นสามรถสราq งวงจรจากคณุ สมบัติเหลาs นี้ไดq ประตู(Gate) อีกสองชนิดท่ีมีความสำคญั คอื ประตแู ละ-ไม(s AND-NOT Gate) และ ประตหู รือ-ไมs(OR-NOT Gate) (ปกตจิ ะยอs เป€น NAND และ NOR ตามลำดบั ) ซงึ่ ประตูทงั้ สองนจี้ ะมคี ณุ สมบัตเิ หมอื น ประตแู ละ (AND-Gate) และ ประตหู รือ(OR-Gate) แตsจะตามมาดqวยประตไู มs (NOT-Gate) ดงั นน้ั a และ-ไมs b (a AND-NOT b) ไมใs ชs a และ b (a AND b) สง่ิ เหลsานี้ไมsอนุญาตใหใq ชวq งจรทม่ี ฟี ง' กช/ ่นั แตกตsางกันไดq เนื่องจาก ผลลัพธข/ องมันมีผลกระทบตsอ ประตูและ(AND-Gate) และ ประตหู รอื (OR-Gate) ทต่ี ามดqวยประตู หนาq 192

ไมs(NOT-Gate) อยาs งไรกต็ าม พวกมนั มคี ณุ สมบตั ิท่นี าs สนใจที่ ประต(ู Gate) ประเภทอ่นื ๆ สามารถสรqาง มาจาก ประตแู ละ-ไมs(AND-NOT Gate) และ ประตหู รอื -ไม(s OR-NOT Gate) หลังจากที่ไดqแนะนำ ประตูและ-ไมs(AND-NOT Gate) และ ประตูหรือ-ไมs(OR-NOT Gate) ทำใหqนักเรียนมี ความทqาทายที่คqนพบวsาประตู(Gate) ประเภทอื่น ๆ สามรถสรqางมาจากประตู(Gate) ตsางประเภทมาตsอ รวมกนั ถqาพวกเขาสามรถสราq งประต(ู Gate) ประเภทอืน่ ๆ ไดq จากการนำประต(ู Gate) หลายๆมาตsอดqวยกัน รูปดาq นลาs งแสดงใหเq หน็ ถึงประตูพq ื้นฐานท้ังสาม ประตไู มs(NOT-Gate) ประตูและ(AND-Gate) และประตูหรือ (OR-Gate) สามารถสรqางประตูและ-ไมs(AND-NOT Gate), ในแถวบนสุด, และ ประตูหรอื -ไมs(OR-NOT Gate) ในแถวลาs งสุด หนาq 193

หนาq 194

ทัง้ หมดน้ีเกยี่ วกับอะไร? ในชsวงไมsกี่ป‹ที่ผsานมานีม้ ีการคqาขายเชิงพาณิชย/ผsานทางระบบเครือขsายคอมพิวเตอร/เพิม่ ขึ้นอยsาง มากมาย และเป€นสิ่งท่ีสำคญั ที่จะตqองรบั ประกนั ความปลอดภยั เมื่อมีการ แลกเปลี่ยนทางการเงิน, การแลกเปล่ียนเอกสารลับ, การเซ็น, เอกสารขอq สัญญาที่ผูกผันตามกฎหมาย, เอกสารทัว่ ไป เรื่อง ของการเขqารหสั ที่เกยี่ วกับการส่อื สารทปี่ ลอดภัยและเป€นสsวนตัวนัน้ หลายทศวรรษท่ีผsานมานักวิจัย ดqานวิทยาการคอมพิวเตอร/นั้นไดqคqนพบผลลัพธ/ที่ตอบโตqไดqงsายซึ่งสามารถรับประกันไดqวsาขqอมูล บางอยsางนั้นจะเผยแพรsแบบเป„ดเผย ผลลัพธ/ที่เรียกวsา “กุญแจการเขqารหัสแบบเป„ดเผย (Public Key Cryptosystem)” ในกิจกรรมที่ 18 “Kid Krypto” ซึ่งตอนนี้ใชqกันอยsางแพรsหลายในฐานะ วิธีการแลกเปลี่ยนขqอมูลที่ปลอดภัย ตัวอยsางเชsน SSL (Secure Sockets Layer) หรือ TLS (Transport Layer Security) ในเวบ็ เบราว/เซอร/ (Web Browser) ของคณุ ระบบเหลาs น้มี ีพ้ืนฐานมา จากระบบกุญแจสาธารณะ (Public Key) ที่จะมีการเปด„ ใชqงานบนเวบ็ เบราว/เซอร/ของคุณ เพอื่ ต้ังคsา การเชื่อมตsอทีม่ คี วามปลอดภัยสูงไปยังเว็บไซต/ เชsน เว็บไซต/ของธนาคาร แมqวsาบางที่อาจจะมกี ลsมุ คนบางกลุมs กำลงั ดกั ขอq มูลของคุณท่กี ำลังสงs ไปกต็ าม การเขqารหัสไมsใชแs คsการเก็บขqอมลู ใหqเป€นความลับ แตsเกีย่ วกบั การควบคุมขอq มลู ท่ี จำกดั จากผqูอ่ืนท่ี พยามยามจะเขาq ถึงมัน และเกี่ยวกบั การสรqางความมั่นใจใจระหวาs งผูคq นทอ่ี ยแsู ยกและหsางไกลกันคน ละสถานทีห่ รือประเทศ กฎระเบียบหรือโปรโตคอล(Protocol) สำหรับการทำธุรกรรมผาs นรูปแบบ การเขqารหสั นนั้ ไดคq ิดคนq เพอื่ จะทำใหสq ิ่งทีด่ ูจะเหมอื นเป€นไปไมsไดqใหqเปน€ ไปไดq เชsนลายเซ็นดิจทิ ัลท่ีไมs สามารถลอกเลยี นแบบหรอื คาดเดาไดq และสง่ิ ทีม่ ีความสามารถในการบอกเชsน (รหัสผาs น) การโยน เหรียญผsานทางโทรศัพท/ที่เป€นป'ญหาที่เรียบงsายและมีความคลqายคลึงกันซึ่งดูเหมอื นวsาจะเป€นไป ไมไs ดqเชนs เดยี วกนั ในสถานการณ/จริงอลิเซียและอเนิโตqจะไมsไดqออกแบบวงจรเอง แตsพวกเขาจะใชqโปรแกรมภายใน คอมพวิ เตอร/ ทัง้ คอsู าจจะไมสs นใจหลกั การทำงานของตัวซอฟทแ/ วร/ แตทs ง้ั คsูจะตอq งมัน่ ใจวsาอกี ฝ¸ายไมs สามารถ มอี ทิ ธพิ ลตsอการตัดสนิ ใจ ไมsวsาหนึ่งในนน้ั จะมที กั ษะการใชคq อมพิวเตอร/มากขนาดไหน โดยหลักการแลqว ขqอโตqแยqงจะตqองไดqรับการแกqไข โดยการรqองขอตsอกรรมการผูqตัดสินที่เป€นกลาง กรรมการผตูq ัดสนิ จะไดqรับวงจรเลขฐานสองตqนฉบับของ อลิเซยี และ เอาตพ/ ุตเธอสงs ใหqเบนโิ ตq และเดา วsาเบนิโตนq ้นั สsงคืนไปแลวq เรียบรqอย เมือ่ การเปล่ยี นแปลงนัน้ ส้ินสุดลง ขqอมูลทัง้ หมดที่ใชqในการตัดสิน ครัง้ นจี้ ะถูกเผยแพรsออกไปสsูสาธารณะ แตsทั้งคูจs ะตqองยอมรบั วาs นี่เป€นสิ่งทเ่ี กิดข้ึน กรรมการผูqตัดสิน สามารถใสsตัวเลขของอลิเซียเขqาไปในวงจรและ ตรวจสอบวsาเอาต/พุตที่ไดqนั้นถูกตqองหรือไมs จึงจะ หนqา 195

ตัดสินใจไดqวsาการตัดสินใจนั้นเป€นไปอยsางยุติธรรมหรือไมs กระบวนการตรวจสอบท่ี ชัดเจนเหลsานี้ทำใหqสามารถตรวจสอบไดqวsามีการปฏิบัติตามกฎระเบียบท่ีวางไวq ถqา ปฏิบัติตามกฎทุกประการก็ไมsนsาจะมีป'ญหาที่เกิดตามมา ถqาเปรียบเทีบกับ สถานการณท/ ่อี ลิเซียเปน€ คนโยนเหรยี ญ และเบนิโตqเลือกหวั หรอื กqอยแลqว ในการโยน เหรยี ญแบบนน้ั ไมsกรรมการผูqตัดสนิ มีสวs นรsวมในระหวsางกระบวนการดวq ยเลย วงจรขนาดเล็กทใ่ี ชqในกิจกรรมนี้ไมคs อs ยจะเปน€ ท่ีแพรหs ลายในทางปฏิบัตมิ ากนกั เพราะวsามันงsายทจ่ี ะหาผลลัพธ/โดยใชqตารางและมันงาs ยตsอการโกง การใชq เลขฐานสอง 23 หลักเปน€ อินพุตนน้ั จะทำใหมq กี ารปอ› งกันทดี่ ขี ึ้น แตอs ยาs งไรกต็ ามนี่ ไมsไดqรบั ประกนั วาs มันจะยากทจ่ี ะโกง ข้นึ อยกsู บั วงจรท่เี ลอื กนำมาใชq และยงั มี ทางเลือกอืน่ เชsน ฟ'งก/ชน่ั ทางเดยี ว แนะนำในกิจกรรมที่ 14 เมอื งแหsงนกั ทอs งเทย่ี ว วธิ กี ารน้ีใชใq นการฝกŸ การแยกตัวประกอบซงึ่ มกั จะประกอบไปดวq ยจำนวน คอs นขqางมาก ซึง่ วาs กนั วาs เป€นปญ' หาทซี่ ับซอq นละแกqไขไดqยาก (ถงึ แมqวsาเราจะเรียน ในชวs งทqายสุดของกจิ กรรมตsอไป ท่ีไมsใชs NP-Complete) มนั งาs ยตอs การตรวจสอบ วsาเลขจำนวนหนงึ่ ในนนั้ เป€นตัวประกอบของจำนวนทีใ่ หญกs วาs และการคำนวน เหลsานั้นโดยปกตแิ ลวq ใชqเวลาเป€นจำนวนมากสง่ิ เหลsานท้ี ำใหเq กดิ ความซบั ซอq นกบั อลิเซยี และเบนโิ ต (รวมถึงกรรมการผตูq ัดสินดวq ย) เม่อื ทำการคำนวนดวq ยมือ ปกติ แลวq สิ่งเหลาs นี้จะถกู คำนวนโดยซอฟทแ/ วร/คอมพวิ เตอร/ ลายเซน็ ดจิ ทิ ลั (Digital Signature) มพี ืน้ ฐานมาจากแนวคดิ ท่คี ลาq ยกนั โดยการทำใหqเอาต/พุตของวงจร น้นั เปด„ เผยสำหรับการรออนิ พุตลบั ทเี่ ธอนั้นจะเลอื กอลิเซียสามารถพิสจู นไ/ ดวq sาเธอเป€นหนึ่งในผสูq รqาง เอาต/พุตทเี่ หมาะสมสำหรบั การใชงq านกบั วงจรฟง' ก/ชนั่ ทางเดยี ว ซี่งไมมs ีใครสามารถใชqวานอนิ พุต เหลาs นน้ั และปลอมตวั เป€น อลเิ ซียไดq ในการสราq งลายเซ็นดจิ ิทลั น้ันจำเปน€ ตqองใชโq ปรโตคอลทม่ี คี วาม ซบั ซqอนเปน€ อยาs งมาก เพ่ือใหqแนใs จวsาเม่ืออลเิ ซยี เซ็นขqอความใดขqอความหนงึ่ ขอq ความนัน้ เจqาของจะ เป€น อลิเซยี แตsเพียงผqูเดียว และทำใหสq ามารถตรวจสอบไดวq sา อลิเซยี เป€นคนทเ่ี ซ็นขqอความนน้ั จรงิ ๆ หรือไมs แตหs ลกั การทง้ั หมดนัน้ เปน€ หลกั การเดียวกนั แอพพลเิ คช่นั (Application) อน่ื ๆคอื การเลนs ไพsโปกÈ เกอรท/ างโทรศัพท/ บนสภาพแวดลอq มที่ไมs มกี รรมการผqูตัดสินแจกไพsและบันทกึ ไพใs นมอื ของผเqู ลsน ทุก ๆอยsางจะตอq งกระทำโดยตัวผqเู ลsนเอง ดวq ย ความชsวยเหลอื ของกรรมการตดั สินเม่ือจบเกม สถานการณ/ทค่ี ลqายคลงึ กนั เหลsานท้ี ำใหเq กิดการนใ้ี น การเจรจาเหน็ ไดชq ัดวsาผqูเลsนทกุ คนจะตqองเกบ็ การด/ ทพี่ วกเขาถอื อยใูs นมือนั้นเปน€ ความลับ และพวกเขา หนqา 196

จะตอq งมีความซ่อื สัตย/ พวกเขาจะไมไs ดรq บั การอนญุ าตใหเq รียกรอq ง ACE จนกวาs พวกเขาจะมีไพพs วกนั้น อยsูจรงิ ๆ สงิ่ นี้สามารถตรวจสอบไดโq ดยรอจนกวsาเกมน้ันเสร็จส้ิน และใหqผเqู ลนs แตลs ะคนตรวจสอบจำนวนไพsใน มือที่เลsนมาต้ังแตsตนq และลำดับของการเคลื่อนที่ระหวsางเกมป'ญหาอีกอยsางคือ วิธีจัดการไพsขณะทีผ่ qู เลsนแตsละคนเก็บไพsในมือไวqเป€นความลับจนกระทั่งเกมนั้นจบ มันนsาแปลกใจมากที่สามารถทำส่ิง เหลsานีใ้ หสq ำเรจ็ ไดqโดยการใชqโปรโตคอลการเขqารหัส ที่รูปแบบแทบจะไมsมีความแตตs sางจากการโยน เหรยี ญเลย โปรโตคอลการเขาq รหสั น้นั มีความสำคญั เป€นอยsางมากในดาq นธุรกรรมอิเล็กทรอนกิ ส/ ไมวs าs จะเป€นการ ระบุเจqาของบัตรเดบิต การยืนยันตัวตนขqาวของบัตรผsานทางโทรศัพท/มือถือโดยการโทร หรือ การ ตรวจสอบผsานทางจดหมายอิเล็กทรอนิกส/ (E-Mail) การทำสิ่งเหลsานี้ใหqนsาเชื่อถือมีความสำคัญตsอ ความสำเรจ็ ของการคาq พานิชย/ทางออนไลนเ/ ปน€ อยsางมาก อาy นเพิ่มเติม Harel’s book Algorithmics อธิบายถึงลายเซ็นดิจิทัลและโปรโตคอลการเขqารหัสที่เกี่ยวขqอง นอกจากนี้ยังแสดงถึงวธิ กี ารเลนs ไพโs ปÈกเกอรผ/ sานทางโทรศพั ท/ ความคดิ น้ีเกิดข้นึ คร้งั แรกในป‹ 1981 ใน บททีเรียกวsา “Mental Poker” ในหนังสือ The Mathematical Gardener, แกqไขโดย D.A. Klarner, Cryptography and data security โ ด ย Dorothy Denning เ ป € น นั กวิทยาการ คอมพิวเตอร/ที่ยอดเยี่ยมเกี่ยวกับการเขqารหัส. Dewdney's Turing Omnibus มีเนื้อหาเกี่ยวกับ ตรรกะบูลนี ท่ีกลsาวถึง การสรqางบลอ็ ก (Building Block) ทใี่ ชใq นวงจรในกจิ กรรมนี้ หนqา 197

กิจกรรมที่ 19 Kid Krypto - การเขา^ รหสั กญุ แจแบบเปด— เผย บทสรปุ การเขาq รหสั น้ันเป€นกญุ แจสำคญั สูsความปลอดภัยของขqอมูล และกุญแจท่ีสำคญั ในการเขqารหสั ที่ ทันยคุ ทนั สมัย น้นั คือการใชขq qอมูลสาธารณะเทาs นนั้ ผqสู งs สามารถล็อคขอq ความทต่ี นเองตqองการ จะสsงในลักษณะท่ผี ูqรบั สามารถปลดล็อคไดq (แบบสวs นตวั แนนs อน!) มันเหมือนราวกับวsาทุกคนซื้อแมsกญุ แจที่ไวqใชqล็อคและเขยี นชื่อของพวกเขาลงไปในแมกs ุณแจนั้น และวางไวqบนโต¹ะเดียวกันรวมกับผqูใชqอื่น แนsนอนพวกเขาเก็บลกู กุญแจไวq แมsกุญแจล็อคเหลาs น้ี เป€นประเภทที่เพียงคุณกดหัวมันแลqวมันกจ็ ะล็อคอัตโนมัติ ถqาคุณตqองการสsงขอq ความท่ีปลอดภัย คุณก็แคsนำมันไปใสsไวqในกลsองหยิบแมsกญุ แจขึ้นมาล็อค แลqวก็นำไปสsงใหqคนท่ีคุณตqองการจะสงs ถงึ แมวq sามันจะตกไปอยูsมือผูqอืน่ แตกs จ็ ะไมมs ีใครสามารถปลดลอ็ คมันไดq ดqวยรปู แบบนไ้ี มsจำเปน€ ตqอง มีการสื่อสารกันกอs น การจดั สsงรหัสลบั กจิ กรรมน้ีแสดงใหqเหน็ ถึงวธิ ีการทีจ่ ะสามารถทำสิง่ เหลsานี้ไดqโดยใชqระบบดิจทิ ัล และในโลกดิจิทัล แทนท่ีจะหยิบแมsกญุ แจขอคุณข้ึนมาและใชqมนั ล็อค คุณจะตอq งทำสำเนากายภาพของแมsกุญแจน้ัน กsอน แลวq ทิ้งแมกs ุญแจอนั เดิมไวqบนโต¹ะ และคณุ ตอq งแยกลกู กญุ แจทางกายภาพและสำเนาออกจาก กัน ในการกระทำสิ่งนั้น คุณจะไมsจำเป€นตqองรูqวsามันทำงานอยsางไร แตsในโลกดิจิทัลเราสามารถ จดั การใหqผรูq บั สามารถคดั ลอกขอq มลู ไดโq ดยไมsตอq งพบเจอแมsกญุ แจมากอs น ฟ'งดเู หมือนจะเป€นไปไมไs ดqใชมs ้ัยหลsะ มาอsานตsอกนั เลย! เนือ้ หาทเ่ี ก่ยี วข^อง ü เทคโนโลยี – กญุ แจการเขาq รหัสแบบเปด„ เผย, โคดq ลับ ทกั ษะ ü การแกไq ขปรศิ นา อายุ ü 11 ป‹ขน้ึ ไป หนqา 198

วสั ดอุ ปุ กรณr นักเรียนแบsงกลุsมออกเป€นกลุsมประมาณ 4 คน ภายในแตsละกลsุมใหqแยกออกเป€นอีกสองกลุsมยsอย แตsละ กลมsุ จะไดqรบั สำเนาใบงานแผนที่ Kid Krypto ดังนนั้ นกั เรียนแตsละกลุsมตอq งการ ü สำเนาแผนท่ขี อง Kid Krypto. คุณอาจจะยงั ตอq งการ โปรเจคเตอร/ และวสั ดทุ ม่ี ีความโป¸รงใสของการเขqารหสั Kid Krypto และ วธิ ที ีจ่ ะใสsคำอธิบายประกอบของ แผนภาพ หนาq 199

Kid Krypto บทนำ นเี่ ปน€ กิจกรรมทท่ี qาทายที่สดุ ในทางเทคนิคในหนังสอื เลsมน้ี ตqองใชคq วามระมดั ระวงั และมงsุ มนั เป€นอยsางย่ิงที่ จะทำกิจกรรมนี้ใหqสำเร็จ นักเรียนควรศึกษาตัวอยsางของฟ'งก/ชั่นทางเดียวจาก กิจกรรมเมืองแหsง นักทอs งเทยี่ ว และ กจิ กรรมอน่ื ๆท่ที ำเสรจ็ แลวq ในสวs นนี้ (การแลกเปลี่ยนความลบั , การโยนเหรยี ญของชาว เปรู) กิจกรรมนี้ยังใชคq วามรทqู ่ีครอบคลมุ ถงึ การนบั จุดและกจิ กรรมการคาดเดายี่สิบครงั้ เอม่ี กำลงั วางแผนทจี่ ะสsงขqอความลบั ใหqบลิ โดยปกติแลวq เราอาจจะคิดถงึ ขอq ความลบั ทเ่ี ปน€ ประโยคหรือยอs หนqา แตsในกิจกรรมตsอไปนี้ เอมี่จะสsงขqอความลับโดยใชqเพียงตัวอักษรเดียว อันทีจ่ รงิ แลqวเธอจะสsงตวั เลข หนึ่งหลักแทนตัวอักษร แมqวsาสิ่งนี้จะดูเหมือนขqอความแบบงsายๆ แตsจงคิดวsาเธอสามารถสsง “ขqอความ” ทัง้ หมดเพือ่ สราq งประโยคและในการปฏิบตั ทิ ั้งหมดน้นั จะทำงานโดยคอมพิวเตอร/ และบางทีแมแq ตsขqอความ เล็ก ๆนั้นก็มคี วามสำคัญเชsนกัน หนึ่งในขqอความที่มีความสำคัญทางดqานประวัตศิ าสตรซ/ ึ่งดำเนินการโดย Paul Revere ซงึ่ มีคsาความนาs จะเปน€ ไดแq คs 2 คsาเทาs นน้ั เราจะเหน็ วิธีการทีเ่ อมใ่ี ชqในการฝง' ตวั เลขเอาไวqในขqอความทีเ่ ขqารหสั โดยใชqการล็อคแบบสาธารณะของบิล เพือ่ ท่ีถาq มใี ครแอบดกั จับขqอมูล พวกเขาจะไมสs ามารถถอดรหสั ขอq มลู นนั้ ไดq จะมีแคsบิลเทาs น้ันท่ีสามารถทำ ไดq เพราะวาs เขาเทsานนั้ ทม่ี ีกุญแจทใ่ี ชqปลดล็อค เราจะล็อคขอq ความโดยใชqแผนท่ี แตไs มsใชแs ผนทีเ่ กาะมหาสมบัติ ทำเครือ่ งหมายทีจ่ ดุ X แตแs ผนท่เี หมือนกับ กิจกรรมเมืองแหsงนักทsองเที่ยว ที่มีเสqนแทนถนน และจุดแทนหัวมุมถนน แตsละแผนที่มีรุsนที่เผยแพรs สาธารณะและ รนุs สวs นตัว หนาq 200