Book-CSUnplugged

คyาผลรวมตรวจสอบทไ่ี ด^มานี้ถูกตอ^ งหรอื ไมy? ในบางครัง้ ความผดิ พลาดก็สามารถเกิดข้ึนไดq ขqอผดิ พลาดท่ีพบเห็นไดqทัว่ ไปคอื : û เลขหลกั นั้นๆ มคี sาเปลยี่ นไป û เลขทีต่ ดิ กันสองหลักสลบั ตำแหนsงกนั û มเี ลขหลกั ใหมถs กู เตมิ เขาq ไปในตัวเลข û เลขบางหลักถกู ลบออกไปจากตัวเลข คุณสามารถหาหนังสือทมี่ ีตวั หนังสอื X เม่ือมีคsาผลรวมตรวจสอบเป€น 10 ไดหq รือไม?s หนงั สือเหลาs น้ีหาไดq ไมยs าก - ภายใน 11 เลมs คณุ ควรจะเจอหนงั สอื แบบน้ีอยาs งนอq ยหนง่ึ เลมs มขี qอผิดพลาดประเภทไหนบางทอี่ าจเกิดข้ึนและไมsสามารถคqนพบได?q คุณสามารถเปล่ยี นเลขหน่ึงหลกั และ ไดq ผลรวมตรวจสอบท่ถี กู ตqองหรอื ไม?s จะเกดิ อะไรขึ้นถาq หากเลขสองหลกั สลับกนั (ซ่งึ เปน€ ความผิดพลาด ในการพิมพท/ พี่ บไดqงาs ย)? หนqา 51

ทัง้ หมดนีเ้ กย่ี วกบั อะไร? สมมติวsาคุณฝากเงินสด 10 เหรียญเขqาบัญชีธนาคารของคุณ พนักงานรับฝากพิมพ/จำนวนเงินฝากเขqา คอมพิวเตอร/ และขอq ความถกู สงs ไปยงั คอมพิวเตอร/หลักของธนาคาร ทวาs มคี วามผดิ พลาดทางเทคนิคบาง ประการเกิดขึ้นสsงผลใหqรหัสจำนวนเงินที่บันทึกลงเปลี่ยนจาก 10 เหรียญกลายเป€น 1,000 เหรียญ มัน ไมsใชsป'ญหาสำหรบั ลกู คqา แตsธนาคารผรqู บั ฝากเกดิ ปญ' หาแนsนอน การสืบคนq หาจดุ ผดิ พลาดในการสsงขอq มูลเป€นเรือ่ งสำคัญย่ิง ดังนั้น คอมพิวเตอรท/ ี่รับขqอมูล จึงควรตqองมี ระบบตรวจสอบ เพื่อป›องกันไมsใหqเกิดความผิดพลาดทางเทคนิคระหวsางการทำรายการรับ-สsงขqอมูล ในบางคร้ัง เมื่อมีความผิดพลาดเกิดข้ึน อาจมีการสsงขqอมูลซำ้ ไดq แตsในบางคร้ังก็ไมอs าจทำไดq ยกตัวอยsาง เชsน แผsนดสิ กอ/ าจเสยี หายจากการโดนแมเs หล็กหรือรังสีไฟฟ›า หรือโดนความรอq น หรือ แผsนดิสกห/ ัก งอ เกดิ ความเสยี หายทางกายภาพอ่ืน ๆ เมือ่ เกิดความผดิ พลาดในการรบั -สงs ขอq มลู หากขqอมลู น้นั ตqองสsงผsาน หqวงอวกาศก็อาจใชqเวลานานขึ้นในการจัดสsงขqอมูลครั้งใหมs (อาจใชqเวลามากกวsาครึ่งชั่วโมงกวsาจะไดqรบั สญั ญาณวิทยจุ ากดาวพฤหัสในชsวงทเี่ ขqาใกลโq ลกมากทส่ี ดุ ) เราจำตอq งสามารถรqไู ดqในทนั ทที ่คี วามผิดพลาดเกดิ ขึน้ (การสบื คqนจดุ ผดิ พลาด) และ จำตqองสามารถกqูขqอมลู เดมิ กลับมาไดทq นั เวลา (การแกไq ขขอq ผดิ พลาด) แนวคิดของเทคนิคเกมส/เป„ดไพsถูกนำเอามาประยุกต/ใชqกับคอมพวิ เตอร/ โดยเรยี งบิตลงในแถวดqานตั้งและ ดาq นขนานในรปู แบบใดกไ็ ดq จากนนั้ กเ็ รียงบิตคsู ลงในแถวทั้งดาq นตงั้ และดาq นขนาน ผลทีไ่ ดqนั้น ไมsเพียงแคs ความรับรูqถงึ ความผดิ พลาดที่เกิดขึ้นเทsาน้ัน แตsยังสามารถรูqแหลsงทีม่ าของความผิดพลาดน้ันดqวย เราจึง สามารถจัดการบิตตัวที่กsอใหqเกิดความผิดพลาด ซึ่งก็คือ การแกqไขจุด ผดิ พลาดน่ันเอง แนsละที่คอมพิวเตอร/มักตqองมีระบบควบคุมความผิดพลาดที่ซับซqอน เพือ่ ทจี่ ะตรวจจับขอq ผิดพลาดตsาง ๆ และแกqไขขqอผดิ พลาดเหลsาน้ัน พื้นท่ี ในฮาร/ดดิสกจ/ ำนวนมากจึงถกู จับจองไวเq พอ่ื การตรวจจับขอq ผิดพลาดเพือ่ ท่ี ขqอมลู จะคงความสมบูรณ/และสามารถเช่ือถือไดq แมใq นกรณที ี่ดสิ กบ/ างสsวน เกิดปญ' หาและระบบการใชพq ืน้ ท่ีน้ีสมั พนั ธก/ บั แผนการวางคูsบิต ทqายน้ี มีมมุ นsารกั ใหqเลsนหลงั จากทำแบบทดสอบนี้ คำถาม คณุ เรียกขอq ผิดพลาดแบบนีว้ sาอะไร (Pieces of nine, pieces of nine)? ตอบ ขqอผิดพลาดในการจบั คูs หนqา 52

วิธีทำและคำใบ^ ขอq ผิดพลาดทไ่ี มสs ามารถตรวจพบโดยการตรวจสอบ ISBN-10 เมอ่ื มีหนึง่ หนวs ยเพ่ิมและอกี หน่ึงหนsวยลดแทน โดยที่ผลรวมอาจจะเทsาเดมิ แตsเนือ่ งจากวธิ ีการคำนวณเสรจ็ สิ้น มันจึงไมsนsาจะเกิดขึน้ ในระบบแบบอื่น(เชsน ISBN-13) จะมีขqอผดิ พลาดแบบอ่ืนทไ่ี มสs ามารถตรวจพบไดq เชนs เม่อื มี 3 หนวs ยถกู จอง แตขs อq ผิดพลาดสวs นใหญs (พิมผดิ หรอื พมิ สลับกนั ) สามารถตรวจสอบไดq หนาq 53

กจิ กรรมท่ี 5 20 การคาดเดา - ทฤษฎขี อ^ มลู สรุป มขี qอมลู เทาs ไหรใs นหนงั สือพันหนqา? ขอq มลู ของสมุดโทรศพั ท/ 1000 หนqา หรือ กระดาษเปลาs 1000 แผsน หรือ หนงั สอื ลอรด/ ออฟเดอะรงิ สข/ อง เจ. อาร./ อาร/. โทลคีน มขี อq มูลมากกวาs ? ถาq เราสามารถวดั ไดq เราก็จะสามารถ ประมานคsาพืน้ ท่ใี นการจดั เกบ็ ขqอมูลไดq ยกตัวอยาs งเชนs คณุ สามารถอsานประโยคนไ้ี ดไq หม? Ths sntnc hs th vwls mssng. คุณสามารถทำไดq เพราะขqอมลู ของสระมนี อq ย กิจกรรมนจ้ี ะแนะนำวธิ วี ัดขอq มูล เน้อื หาท่ีเกยี่ วข^อง ü คณติ ศาสตร:/ ตวั เลข – หาเลข: มากกวsา, นqอยกวาs , พสิ ัย ü คณิตศาสตร:/ สมการ – รปู แบบ และลำดับ ü ภาษา: ตวั สะกด, การจำแนกองคป/ ระกอบของขqอความ ทกั ษะ ü เปรียบเทยี บตัวเลขและการทำงานกบั ชsวงของตัวเลข ü การหกั ü การถามคำถาม อายุ ü 10 ปข‹ ้ึนไป วสั ดุ ü ไมมs ีวสั ดทุ ตี่ อq งใชใq นกิจกรรมนี้ มีกิจกรรมตอy , นักเรยี นทุกคนต^องเตรียม: ü กิจกรรมแผนs งาน: ตqนไมqตดั สนิ ใจ (หนqา 58) หนาq 54

20 การคาดเดา สนทนา 1. พดู คุยกบั นักเรยี นวาs คดิ วาs ขqอมูลเป€นอยsางไร 2. เราจะวัดไดqวsาจะมีขqอมูลเทsาไรในหนังสือ? จำนวนหนqาหรือจำนวนคำสำคัญหรือไมs? หนังสือเลมs หนึ่งมี ขqอมูลมากกวsาเลsมอื่นหรือไมs? จะเป€นอยsางไรถาq เป€นหนังสอื นาs เบื่อหรือนsาสนใจอยsางยิ่ง? 400 หนqาของ หนังสือที่มวี ลี \"บลา บลา บลา\" มขี qอมูลมากหรอื นqอยกวsากลsาวคือสมดุ โทรศพั ท?/ 3. อธิบายวsานักวิทยาศาสตร/คอมพิวเตอร/สามารถวัดขqอมูลไดqโดยใชqขqอความ (หรือหนังสือ) ที่นsาแปลกใจ บอกไดqวsามีบางอยsางที่คุณรูqอยูsแลqวตัวอยsางเชsนเมื่อเพื่อนที่เดินไปที่โรงเรียนเสมอบอกวsา \"ฉันเดินไป โรงเรยี นวันนี้\" ไมsไดใq หqขอq มลู อะไรเลย เพราะไมsแปลกใจเลย ถาq เพ่อื นของคุณพดู แทน \"ฉันไดนq ง่ั รถโรงเรียน ในเฮลิคอปเตอรใ/ นวนั น้\"ี ซ่ึงนsาแปลกใจและบอกขqอมลู มากมาย 4. จะสามารถวดั คาs ความประหลาดใจของขอq ความไดqอยาs งไร? 5. วิธีหน่ึงคอื การดคู วามยากทจ่ี ะคาดเดาขอq มลู ถาq เพอ่ื นของคณุ พดู วsา \"เดาวาs ฉันมาโรงเรียนวนั นี้ไดqอยsางไร\" และพวกเขาเคยเดิน คุณอาจเดาไดถq ูกตqองครั้งแรก อาจตqองใชqการคาดเดาอีกสองสามคร้ังกsอนที่คณุ จะ เดนิ ทางไปเฮลคิ อปเตอร/และย่ิงถqาพวกเขาเดินทางโดยยานอวกาศ 6. จำนวนขอq มลู ทข่ี qอความมวี ัดไดจq ากความงาs ยหรอื ยากท่ีจะคาดเดา เกมตอs ไปนีช้ วs ยใหqเรามคี วามคิดเรือ่ งนี้ หนqา 55

กจิ กรรม 20 คำถาม นเ่ี ปน€ เกมท่ีดัดแปลงมาจาก 20 คำถาม นักเรียนสามารถถามคำถามนักเรียนทีถ่ ูกเลอื ก ซ่งึ จะตอบวsาใชsหรือไมs เทsาน้นั จนกวาs คำตอบจะถูก ไมsวsาคำถามใด ๆ ถกู ถาม คำตอบคอื \"ใช\"s หรือ \"ไมs\" เทsาน้นั ข^อเสนอแนะ: ฉนั คดิ วาs : • เลขระหวsาง 1-100 • เลขระหวsาง 1-1000 • เลขระหวาs ง 1-1,000,000 • เลขจำนวนเตม็ • เลขลำดบั 6 ตวั เลขในรูปแบบ (เหมาะสมกับกลมsุ ) คาดเดาตามลำดบั ตงั้ แตsตqนจนจบ (เชsน 2, 4, 6, 8, 10) นับจำนวนคำถามทถ่ี ามทีถ่ กู ถาม น่คี ือการวดั คาs ของ \"ขอq มูล\" ตามด^วย การสนทนา คณุ ใชqกลยุทธอ/ ะไร?กลยุทธไ/ หนดีทสี่ ุด? ชี้ใหqเห็นวsาตqองเดาประมาณ 7 ครั้งเพื่อหาตัวเลขระหวsาง 1 ถึง 100 ถqาคุณลดชsวงเวลาลงครึ่งหนึ่ง ตวั อยsางเชsน: มันน^อยกวyา 50 หรือไมy? ใชs มนั น^อยกวาy 25? ไมs มนั นอ^ ยกวาy 37? ไมs มนั น^อยกวyา 43? ใชs มันนอ^ ยกวyา 40? ไมs มนั น^อยกวาy 41? ไมs ต^องเปzน 42! ใชs มันนาs สนใจถาq ชsวงเพิม่ ขึ้นถงึ 1000 ไมไs ดใq ชqเวลาเพม่ิ 10 เทาs เพยี งแคสs ามคำถามเพ่ิมเติม ทุกคร้ังท่ีมีการเพ่ิม หนqา 56

สองเทาs คุณตqองการแคs 1 คำถามเพ่มิ เตมิ เพอ่ื หาคำตอบ ส่ิงตอs มาคือการใหqนักเรียนเลsนเกม นักคิด สyวนขยาย: มีข^อมูลเยอะแคyไหนในขอ^ ความ? นกั วิทยาศาสตรค/ อมพวิ เตอร/ไมเs พียงแคใs ชqการเดากบั ตวั เลขเทาs นน้ั แตsยงั สามารถคาดเดาไดวq าs ตัวอกั ษรตัวใดมี แนวโนมq ท่ีจะเป€นคำหรอื ประโยคตอs ไป ลองเกมเดาดqวยประโยคส้นั ๆ 4-6 คำ ตัวอักษรตqองถูกคาดเดาตามลำดับที่ถกู ตqองตง้ั แตsตqนจนจบ ใหqคนเขียน ตวั อักษรลงตามที่พบและเก็บบนั ทึกจำนวนการคาดเดาตาs งๆทใ่ี ชqในการคqนหาแตsละตัว สามารถถามคำถามใด ๆ ที่มีคำตอบ ใชs / ไมs ไดq เชsน \"มันเป€นเสียงหรอื ไมs?\" \"มันเป€นสระหรอื ไม?s \" \"มันมากsอนในตัวอักษรหรือไม?s \" ชsองวsางระหวsางคำพูดก็นับวาs เป€น \"ตัวอักษร\" และตqองถกู คาดเดา หมุนเวียนและดูวsาคุณสามารถคqนพบสsวน ของขอq ความท่ีงsายทส่ี ดุ ในการคนq หา หนาq 57

กิจกรรมแผนy งาน: ต^นไมต^ ัดสินใจ หากคณุ รูqกลยทุ ธส/ ำหรบั ถามคำถามแลวq คณุ สามารถสงs ขอq ความไดโq ดยไมsตอq งถามอะไร น่ีคอื แผนภมู ิท่ีเรยี กวาs 'ตนq ไมqตดั สินใจ' สำหรับคาดเดาตัวเลขระหวsาง 0 ถึง 7: ตอq งตอบ ใช/s ไมs อยsางไร เพ่อื ใหqไดqคำตอบ 5? ตอq งตอบ ใช/s ไมs ก่ีครงั้ เพอื่ ใหqไดคq ำตอบ? ตอนนี้ดูสิ่งที่นsาสนใจมาก ภายใตqตัวเลข 0, 1, 2, 3 ... ในแถวสุดทqายของตqนไมqเขียนตัวเลขเป€นเลขฐาน 2 (ดู กจิ กรรม 1) มองไปทตี่ นq ไมอq ยsางใกลqชิด ถqาไมใs ชs = 0 และใชs = 1 คุณเหน็ อะไร? ในเกมคาดเดาเลข เราพยายามเลือกคำถามเพื่อใหqลำดบั ของคำตอบทำงานออกมาเพ่ือแสดงจำนวนในแบบ เดยี วกัน ออกแบบตนq ไมqตัดสินใจของคณุ เองเพื่อคาดเดาตัวเลขระหวาs ง 0 ถงึ 15 เสริมสำหรับผู^เชี่ยวชาญ: คุณจะใชqตqนไมqชนิดใดในการคาดเดาอายุของใครบางคน?แลqวถqาเกิดเป€นการหา ตัวอกั ษรตอs ไปในประโยคจะใชตq qนไมqชนดิ ใด หนqา 58

ท้ังหมดน้เี กยี่ วกับอะไร? นักคณิตศาสตร/อเมริกันผูqมีชื่อเสียง (นักเลsนกลและนักขี่จักรยาน) มีนามวsา คลqอด แชนนอน (Claude Shannon) เขาวัดปริมาณขอq มูลเป€นบติ - แตsละ ใชs / ไมs เทsากับ 1/0 บิต เขาพบวsาจำนวน \"ขqอมูล\" ที่อยูsใน ขqอความขึน้ อยsกู บั สิง่ ทีค่ ุณรอูq ยแsู ลqว บางครงั้ เราสามารถตั้งคำถามท่ีชวs ยลดความจำเป€นในการถามคำถามอืน่ ๆ มากมาย ในกรณีนี้เน้ือหาขqอมูลของขqอความอยูsในระดับต่ำ ตัวอยsางเชsนขqอมูลในการโยนเหรียญครัง้ เดยี วคอื หนึ่งบติ : หัวหรือหาง แตsถqาเหรยี ญเกิดขึ้นไมปs กตทิ ี่เป„ดข้ึนหัวเกqาคร้ังจากสิบ ขqอมูลจะไมsใชsหนึง่ บิตอีกตอs ไป เชือ่ หรอื ไมs มันนอq ยกวsา วธิ ที คี่ ณุ สามารถพสิ จู นว/ sาการโยนเหรียญมนั นอq ยกวาs หนง่ึ งsายๆเพียงแคsใชqคำถามเชsน \"มีสองเหรยี ญตอs ไปโยนทัง้ สองหวั ?\" สำหรับลำดบั ของการโยนดวq ยเหรยี ญท่ีไมsปกติ คำตอบสำหรบั เรื่องนี้ก็คือ \"ใชs\" ประมาณ 80% 20% ของโอกาสทค่ี ำตอบคอื \"ไม\"s คุณจะตอq งถามคำถามอกี สองขqอ แตsโดยเฉล่ียแลqวคุณ จะตqองถามคำถามไมนs qอยกวาs หน่งึ ขqอตอs หนึง่ เหรยี ญ! แชนนอน เรียกเน้อื หาขอq มลู ของขqอความวาs \"เอนโทรป‹\" เอนโทรปข‹ น้ึ อยกูs ับจำนวนของผลลพั ธ/ทเี่ ปน€ ไปไดq - ใน กรณีของเหรียญโยนสอง – ยังเกี่ยวกับความนsาจะเปน€ ของมนั เกิดขึ้นดqวย เหตุการณ/ที่ไมsนsาจะเป€นไปไดหq รือ ขqอมูลที่นsาแปลกใจตqองใชqคำถามมากขึ้นเพื่อคาดเดาขqอความเพราะบอกขqอมูลเพิ่มเติมที่เราไมsทราบ เชนs เดียวกบั สถานการณ/ในการสละเฮลิคอปเตอรไ/ ปโรงเรียน เอนโทรป‹ของขอq ความเป€นเรอื่ งสำคญั มากสำหรับนักวทิ ยาศาสตร/คอมพิวเตอร/ คุณไมสs ามารถบีบอัดขqอความ เพ่ือใชqพ้นื ท่นี qอยกวาs เอนโทรป‹และระบบการบีบอัดที่ดที ่สี ุดเทาs กบั เกมคาดเดา เนอื่ งจากโปรแกรมคอมพิวเตอร/ ทำการ 'เดา' รายการคำถามสามารถทำซ้ำไดqในภายหลังตราบเทsาที่คำตอบ (บิต) ถูกเก็บไวqเราสามารถสรqาง ขqอมูลใหมsไดq! ระบบการบีบอดั ที่ดีทีส่ ุดสามารถลดไฟล/ขqอความลงไดปq ระมาณหน่ึงในสี่ของขนาดตqนฉบับซึ่ง ชวs ยประหยดั พ้ืนทจ่ี ดั เกบ็ ขqอมูลไดqมาก! นอกจากน้ียังสามารถใชqวิธีการคาดเดาเพ่ือสรqางอินเทอรเ/ ฟซคอมพิวเตอร/ซ่ึงจะคาดการณ/วาs ผูqใชqจะพิมพ/อะไร ตsอไป! ซงึ่ อาจเป€นประโยชนส/ ำหรับคนพกิ ารทางราs งกายท่ีพบวsายากท่ีจะพมิ พ/ คอมพวิ เตอรแ/ นะนำส่ิงท่ีคิดวsา นsาจะพิมพต/ อs ไปและพวกเขาเพยี งแคsระบุสิ่งที่พวกเขาตอq งการเทsาน้ัน ระบบทดี่ ีตqองมีคsาเฉลีย่ เพียงสองคำตอบ ใชs/ไมs ตอs อกั ขระและสามารถชsวยเหลือผqูทม่ี ีป'ญหาในการปรบั การเคลือ่ นไหวท่จี ำเป€นในการควบคุมเมาสห/ รือ แปน› พิมพไ/ ดq ระบบประเภทนีใ้ ชqในรปู แบบตsางๆกบั ขqอความเวลาพมิ พบ/ นโทรศัพท/มือถอื บางรนsุ หนqา 59

วธิ ที ำและคำใบ^ คำตอบสำหรับคำถาม ใชs / ไมs มคี sาเทsากบั หนึ่งบิต ไมวs าs จะเปน€ คำถามงาs ยๆเชsน \"มันมากกวาs 50?\" หรือคำท่ี ซบั ซอq นมากขึ้นอยsาง มนั อยsูระหวาs ง 10 กับ 60? ในเกมที่มีการคาดเดาจำนวนหากคำถามไดรq ับการแตsงตั้งใน บางลักษณะ ลำดับของคำตอบก็เป€นเพยี งการแทนเลขฐานสองเทsานั้น สามคือ 011 ในรูปแบบเลขฐานสอง และแสดงดวq ยคำตอบวsา \"ไมใs ชsใชs\" ในตนq ไมตq ัดสนิ ใจซง่ึ จะเหมอื นกนั ถqาเราเขียนเลข 0 เปน€ ไมs และใชsเป€น 1 ตนq ไมทq ีค่ ุณใชสq ำหรับอายขุ องใครบางคนอาจมคี วามผิดปกติตsอตัวเลขทน่ี อq ย การตดั สินใจเกยี่ วกบั ตัวอกั ษรในประโยคอาจขนึ้ อยูsกับวาs ตวั อักษรกอs นหนqานี้ หนqา 60

บทท่ี 2 การใช^คอมพิวเตอรใr นการทำงาน – อลั กอรทิ มึ

การใช^คอมพิวเตอรใr นการทำงาน – อลั กอริทึม คอมพวิ เตอรด/ ำเนินการตามรายการคำแนะนำที่กำหนดไวq คำแนะนำเหลsานีช้ sวยใหสq ามารถจัดเรยี งคqนหาและ สsงขอq มลู ไดq ในการทำส่ิงเหลาs นีใ้ หเq รว็ ทีส่ ดุ เทาs ที่จะเปน€ ไปไดqคุณตอq งมวี ธิ ีการทด่ี ีในการคqนหาสง่ิ ตาs งๆในคอลเลก็ ชนั ขqอมลู ขนาดใหญแs ละเพ่อื สงs ขqอมูลผาs นเครือขาs ย อัลกอริทึมคือชุดของคำแนะนำในการทำภารกิจ ความคิดของอัลกอริทึมเป€นศูนย/กลางของวิทยาการ คอมพิวเตอร/ อัลกอริทึมคือวธิ ีที่เราไดqรับคอมพิวเตอร/เพื่อแกqปญ' หา อัลกอริทึมบางตวั เร็วกวsาตัวอ่ืน ๆ และ อัลกอริทึมตsางๆท่ีคนq พบไดทq ำใหสq ามารถแกqปญ' หาท่เี กิดข้ึนกsอนหนqานี้ไดqเชsนการคนq หาตวั เลขนับพันใน พาย หรอื ทกุ หนqาทีม่ ีชอ่ื ของคุณอยูs เวิลดไ/ วดเ/ ว็บหรือคqนหาวิธที ดี่ ีทส่ี ดุ ในการหีบหsอบรรจุภณั ฑ/ลงในภาชนะหรือหา วsาตัวเลขขนาดใหญs (100 หลัก) เป€นตัวเลขจำนวนเฉพาะหรือไมs คำวsา \"อัลกอริทึม\" มาจากชื่อของ Mohammed ibn Musa Al-Khowarizmi-Mohammed ลูกชายของ โมเสสจาก Kholarizm ซึง่ เขาq รวs มศนู ยก/ ารศึกษาทเ่ี รียกวาs House of Wisdom ในกรุงแบกแดดในป‹ ค.ศ.800 ผลงานของเขาสsงศลิ ปะฮินดูไปยังชาวอาหรบั และจากนั้นไปยงั ยโุ รป เม่ือพวกเขาถูกแปลเป€นภาษาละตินในป‹ ค.ศ. 1120 คำแรกคอื \"Dixit Algorismi\" - \"Algorismi กลsาว\" หนqา 62

กิจกรรมที่ 6 เรอื รบ – อัลกอริทึมการค^นหา สรุป คอมพวิ เตอร/มักตอq งหาขอq มลู ในคอลเลก็ ชันขqอมูลขนาดใหญs พวกเขาจำเปน€ ตqองพัฒนาวธิ ีการท่ีรวดเร็วและมี ประสทิ ธิภาพในการทำเชนs นี้ กิจกรรมน้ีแสดงใหqเห็นถึงสามวธิ กี ารคqนหาทแี่ ตกตsางกนั ไดqแกs การคนq หาเชิงเสqน การคนq หาแบบไบนารีและการแฮช เนอ้ื หาท่ีเกย่ี วข^อง ü คณิตศาสตร:/ ตวั เลข – หาเลข: มากกวsา, นอq ยกวsา, พสิ ัย ü คณติ ศาสตร:/ เรขาคณติ - สำรวจรปู ราs งและพ้ืนที่: พกิ ดั ü การคำนวณ: อัลกอรทิ ึม ทกั ษะ ü เหตผุ ลเชงิ ตรรกะ อายุ ü 9 ป‹ขน้ึ ไป วสั ดุ นกั เรียนแตลs ะคนจะตอq ง: ü สำเนาเกมเรือรบ • 1A, 1B สำหรบั เกม 1 • 2A, 2B สำหรับเกม 2 • 3A, 3B สำหรบั การเลนs เกม 3 ü คณุ อาจตqองใชqแผนs เกมเสริมอกี 1 ชดุ คือ 1A ', 1B', 2A ', 2B', 3A ', 3B' หนาq 63

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

เกมเรอื รบ - เกมค^นหาเชงิ เสน^ อyานคำแนะนำตอy ไปน้ีใหก^ บั นกั เรยี น 1. จับคsู หนงึ่ คนมีแผsน 1A, อีกคนมี 1B อยาs แสดงแผนs งานของคณุ กบั คูขs องคณุ ! 2. ทัง้ คsวู งกลมเรือรบ ในบรรทดั ดqานบนของแผนs เกมของคุณและบอกจำนวนเรือใหqคขูs องคุณ 3. หันไปคาดเดาทเี่ รอื ของคขsู องคณุ (คณุ พูดชอื่ หนงั สอื ของเรือและคูขs องคณุ จะบอกจำนวนเรอื ที่ตวั อกั ษรนนั้ ) 4. เรือของคขsู องคณุ โดนยิงกี่ที นคี่ อื คะแนนของคุณสำหรบั เกมนี้ (ชตี 1A 'และ 1B' เป€นของแถมสำหรบั นกั เรยี นทีต่ อq งการเลนs เกมมากขึ้นหรือผูqท่ี \"ไมเs จตนา\" ดูแผsนคูsของพวก เขา ชตี 2A ', 2B' และ 3A ', 3B' สำหรับเกมในภายหลงั ) ตามด^วย การสนทนา 1. คะแนนคืออะไร? 2. อะไรจะเปน€ คะแนนต่ำสดุ และสงู สดุ ทเ่ี ปน€ ไปได?q (เปน€ 1 และ 26 ตามลำดับ สมมตวิ าs นกั เรียนไมsไดqยิงทเ่ี รือ ลำเดียวกันสองคร้ัง วิธีน้ีเรยี กวsา 'การคนq หาเชงิ เสqน' เน่อื งจากตqองผsานทกุ ตำแหนsงทลี ะที) หนาq 65

เกมเรือรบ—เกมคน^ หาแบบไบนารี คำแนะนำ คำแนะนำสำหรบั เกมเวอร/ชนั นี้เหมอื นกบั เกมกsอนหนาq นี้ แตตs วั เลขในเรือจะเรียงลำดบั จากนอq ยไปมาก อธบิ าย เรอื่ งน้กี บั นักเรยี นกsอนทีจ่ ะเร่มิ 1. จบั คูs หนึ่งคนมีแผนs 2A, อกี คนมี 2B อยาs แสดงแผsนงานของคณุ กับคขูs องคณุ ! 2. ทัง้ คsูวงกลมเรอื รบ ในบรรทัดดาq นบนของแผนs เกมของคุณและบอกจำนวนเรือใหqคูsของคุณ 3. หนั ไปคาดเดาทเี่ รอื ของคขูs องคณุ (คุณพดู ชอื่ หนงั สอื ของเรือและคsูของคณุ จะบอกจำนวนเรอื ที่ตัวอักษรนน้ั ) 4. เรือของคขูs องคุณโดนยงิ ก่ที ี นีค่ ือคะแนนของคณุ สำหรับเกมนี้ ตามด^วย การสนทนา 1. คะแนนคืออะไร? 2. คนทไ่ี ดคq ะแนนต่ำกวาs ใชqกลยทุ ธ/อะไร 3. คณุ ควรเลือกเรอื ลำไหนเปน€ ลำแรก? (อนั ทอ่ี ยูsตรงกลางจะบอกคุณวาs ครึง่ ใดของเสนq ทีเ่ รอื อย)sู ตำแหนsงไหน ท่ีคณุ จะเลือกตอs ไป? (อีกครัง้ กลยทุ ธ/ท่ีดที ีส่ ุดคือการเลือกเรอื ตรงกลางของสsวนทีต่ qองมีเรอื ทเี่ ลือก) 4. ถาq ใชยq ทุ ธศาสตรน/ ้ีจะใชกq ี่นัดเพ่ือหาเรือ? (หqาทม่ี ากท่ีสดุ ) วิธีนเี้ รียกวsา 'การคนq หาแบบไบนารี' เพราะแบงs ป'ญหาออกเปน€ สองสวs น หนqา 66

เกมเรือรบ—เกมคน^ หาแบบแฮช คำแนะนำ 1. แตsละคนไดแq ผนs เหมือนในเกมกอs นหนqาและบอกคsูของคณุ วาs มีเรอื กีล่ ำทีค่ ณุ เลอื ก 2. ในเกมนค้ี ณุ จะพบวsามคี อลมั น/ (0 ถงึ 9) ใดอยูsในเรอื คุณแคsนำเลขของเรอื แตsละหนวs ยมาบวกกนั หนวs ยตัว สดุ ทqายของผลรวมคือคอลมั น/ท่เี รอื อยsู ตัวอยาs งเชsนในการคqนหาเรอื ท่มี ีเลข 2345 ใหรq วมตวั เลข 2 + 3 + 4 + 5 เทsากับ 14 ตัวเลขสดุ ทqายของผลรวมคือ 4 เรือจึงตqองอยูsในคอลมั น/ที่ 4 เมื่อคุณรqูวsาคอลัมน/ที่คณุ ตอq งคาดเดาของเรอื ในคอลัมน/ทเี่ ปน€ ที่ตqองการ เทคนิคนี้เรยี กวาs 'แฮชชิง่ ' เนอ่ื งจากตวั เลขดังกลsาวถูกแบน (\"แฮช\") เขqาดqวยกนั 3. เลsนเกมโดยใชกq ลยุทธ/การคqนหาใหมsน้ี คุณอาจตqองเลsนเกมมากกวsาหน่ึงเกมโดยใชqแผsนเดียวกนั – เพียง เลือกจากคอลมั นต/ าs งๆ (โปรดสังเกตวsาเกมนี้แตกตsางจากเกมอื่น ๆ ตqองใชqแผsนสำรอง 3A 'และ 3B' เป€นคูsเพราะรูปแบบของเรือใน คอลัมน/ตอq งสอดคลอq งกนั ) ตามด^วย การสนทนา 1. รวบรวมและอภิปรายเกย่ี วกับคะแนนดังกลาs ว 2. เรือใดที่หาไดqอยsางรวดเร็ว? (ลำที่อยูsลำเดียวในคอลัมน/) เรือลำไหนที่อาจหาไดqยาก? (ลำที่มีคอลัมน/ ประกอบไปดqวยเรือลำอนื่ ๆ ) 3. กระบวนการใดในสามกระบวนการคqนหาเรว็ ท่ีสดุ ? ทำไม? ขqอดีของการคqนหาในสามวิธีนี้คืออะไร? (กลยุทธ/ที่สองจะเร็วกวsาครั้งแรก แตsอันแรกไมsจำเป€นตqองใหqเรือ จดั เรยี งตามลำดบั กลยุทธ/ที่สามมกั จะเร็วกวาs อันอื่น ๆ แตsกม็ โี อกาสทจ่ี ะชาq มากๆ ในกรณที เ่ี ลวราq ยทีส่ ุดถqาเรือ ทัง้ หมดลงในคอลมั นเ/ ดยี วกนั ก็จะชาq เทาs กลยุทธแ/ รก.) หนqา 67

กจิ กรรมเสริม 1. ใหqนักเรียนทำเกมของตัวเองโดยใชqรูปแบบทั้งสามแบบ สำหรับเกมท่ีสองพวกเขาตqองใสsตัวเลขในลำดบั จากนqอยไปหามาก ถามวาs พวกเขาจะทำใหqเกม แฮชชง่ิ เปน€ เร่อื งยากไดqอยาs งไร (เกมท่ยี ากที่สดุ คือเมอ่ื เรอื ทั้งหมดอยูsในคอลัมน/เดียวกัน) คุณจะทำใหqงsายที่สุดเทsาที่จะเป€นไปไดอq ยาs งไร? (คุณควรพยายามใหqเรอื จำนวนเทsากนั ในแตsละคอลมั น)/ 2. จะเกดิ อะไรขน้ึ ถาq เรือท่ีหาไมsไดqอยsทุ ีน่ นั่ ? (ในเกม การคqนหาเชิงเสนq จะใชq 26 คร้ัง เพอื่ พิสูจน/ ในเกม การ คqนหาแบบไบนารี คุณตqองมีภาพหqาภาพเพื่อพิสูจน/เรื่องนี้ เมื่อใชqระบบแฮชจะขึ้นอยูsกับจำนวนเรือที่ ปรากฏในคอลมั น/) 3. การใชกq ลยุทธ/การคqนหาแบบไบนารจี ะตอq งยงิ ก่ีครั้ง หากมสี ถานที่ต้ังหลายรอq ยแหsง (ประมาณหกครัง้ ) พัน แหsง (ประมาณเกาq ครั้ง) หรือลqานแหsง (ประมาณสิบเกqาคร้ัง)? (สังเกตวsาจำนวนภาพทีเ่ พ่ิมขึ้นชqามากเมอื่ เทียบกับจำนวนของเรือ มี 1 ครั้งเพิ่มเมื่อขนาดมากขึ้น 2 เทsา ดังนั้นจึงเป€นสัดสsวนกับลอการิทึมของ จำนวนลำ) หนาq 68

หนาq 69

หนาq 70

หนาq 71

หนาq 72

หนาq 73

หนาq 74

หนาq 75

หนาq 76

หนาq 77

หนาq 78

หนาq 79

หนาq 80

ทงั้ หมดนเี้ กยี่ วกบั อะไร? คอมพวิ เตอร/เป€นทเี่ ก็บขqอมูลมากมายจึงจำเปน€ ตอq งมรี ะบบคัดกรองเพ่ือคqนหาขอq มลู ท่ีตอq งการไดqอยsางรวดเร็ว ประเด็นความยุsงยากที่ซับซqอนที่สุดของการคqนหาขqอมูลที่มีในคอมพิวเตอร/ อยูsที่เครื่องมือคqนหาขqอมูลทาง อนิ เตอร/เน็ตเพราะตqองสืบคนq เวบ็ เพจหลายสบิ ลqานเว็บเพจในเส้ยี ววินาที ส่งิ ท่คี อมพวิ เตอร/ตqองมีเพ่ือใชqคqนหา ขqอมลู ท่ีตqองการ เชนs คำ บารโ/ คqด หรอื นกั ประพนั ธ/ น้ี เรียกวsา คำค(นหา คอมพิวเตอร/รวบรวมขอq มูลในระยะเวลารวดเร็ว ท้ังน้ี สามารถมกี ารอนุมานวาs ทกุ อยsางเร่ิมทีส่ sวนที่เกบ็ ขqอมลู แลวq คอมพิวเตอร/กค็ qนเปรียบเทยี บไปจนกวาs จะเจอขอq มูลท่ีตqองการ นเ่ี ปน€ วิธีทเี่ ราใชใq นเกมส/คนq หาเชิงเสqน แตs เป€นวิธีที่ใหqผลชqามากแมqจะเป€นการประมวลผลโดยคอมพิวเตอร/ก็ตาม ยกตัวอยsางเชsน สมมติวsาใน ซูเปอร/มาร/เก็ตแหsงหนึ่งมีสินคqาขาย 10,000 รายการ เมื่อเกิดการแสกนรหัสสินคqาที่เคาน/เตอร/ขาย คอมพวิ เตอรต/ อq งประมวลผลจากชุดตัวเลขถึง 10,000 ชุดตัวเลขเพ่ือหาช่อื สินคqาและราคาสินคาq ชนิ้ หน่ึง และ ตqองใชเq วลาถึงสบิ วนิ าทีทจี่ ะเขาq ถึงรายการสินคาq ทัง้ หมด ลองนึกภาพวาs จะใชเq วลาอกี นานเทsาใดจึงจะไดqขqอมูล สนิ คาq และราคาครบในกรณที เ่ี ราตอq งการซอ้ื ของใชปq ระจำบาq น วธิ ีการคนq หาท่ีดีกวsา คือ การคqนหาแบบทวภิ าค (Binary Search) ดqวยวธิ นี ี้ตวั เลขรหสั สนิ คาq จะถูกจัดแยกเป€น ลำดับเริ่มจากตัวเลขสsวนกลางของรหัสสินคqาเพื่อกำหนดวsาคำคqนหาอยูsในสsวนใดของบัญชีรายการ คอมพิวเตอร/จะทำซ้ำขบวนการจนกระทั่งพบขqอมูลที่คqนหา และทีนี้ลองกลับไปดูที่ตัวอยsางซูเปอร/มาเก็ต ขqางตqน ดqวยวิธีคqนหาแบบทวิภาคนี้เวลาที่ใชqในการสืบคqนจากบัญชีรายการสินคqา 10,000 รายการ ที่ตqอง ทำซ้ำ 14 คร้ัง จึงเหลือแคสs องรqอยในวนิ าที – แทบไมตs qองรอเลย วิธคี นq หาทส่ี าม เรยี กวาs แฮทชิง (Hashing Search) การใชqขอq มูลแทนตัวหรอื รหัสผsานนคี้ ำคนq หาจะถกู เขาq รหัส ใหเq หมาะสม เพอ่ื ระบแุ หลsงเก็บขqอมลู ในคอมพวิ เตอร/ ยกตัวอยsางเชนs ถาq คำคqนหา คือ หมายเลขโทรศัพท/ เม่ือ เราบวกเลขเบอร/โทรเขqาดวq ยกันแลqวไดผq ลลพั ธเ/ ทาs ไร ใหqนำมาหารดวq ย 11 ก็จะไดผq ลลพั ธ/ท่ีตอq งการ ในกรณีน้ี รหสั ผาs นจะเหมอื นกับตวั เลขตรวจสอบที่กลาs วถงึ ในแบบทดสอบท่ี 4 ซึ่งก็คอื ขqอมูลเล็กๆ ช้ินหน่ึงท่ีคsาของมัน ขน้ึ อยsกู บั ขอq มูลท่ถี กู นำมาเขqารหัสน่ันเอง โดยปกติ คอมพิวเตอรจ/ ะพบขqอมลู ท่ีตqองการหาในทันที อยsางไรก็ดี มีความเป€นไปไดqที่คำคqนหาหลายคำจะนำมาสูsแหลsงเก็บดียวกัน ในกรณีนี้ คอมพิวเตอร/ก็ตqองหาขqอมูลที่ ตqองการตsอไปอกี โปรแกรมคอมพวิ เตอร/โดยทั่วไปจะใชรq ะบบแฮทชงิ บางรุsนในการคqนหา เวqนไวqแตsในกรณีที่จำเป€นตอq ง จดั ขอq มลู ใหเq ปน€ ระเบียบ หรือ ยกเวนq ในกรณีที่ไมอs าจรอผลคนq หาทเ่ี ปน€ ไปอยาs งชาq ๆไดq หนqา 81

กิจกรรมที่ 7 เบาสดุ และหนักสดุ - การเรยี งลำดบั อลั กอริธม่ึ สรปุ คอมพิวเตอร/มักถูกใชqงานเพื่อการจัดเรียงลำดับบัญชีรายการตsาง ๆ เชsน การจัดเรียงลำดบั ของชื่อโดยเรียง ตามลำดบั ตัวอกั ษร การจัดการนัดหมายหรอื อีเมล/ตามลำดบั วนั ที่ การเรียงลำดบั บัญชรี ายการตsาง ๆ ชsวยใหq เราไมตs อq งเสียเวลาคqนหาขอq มูลที่เราตqองการ ทั้งนีย้ ังสามารถทำใหqเห็นคsาสูงสดุ -ต่ำสุดไดqอยsางชัดเจนอีกดวq ย เชsน การตรวจดูคะแนนสอบของชั้นเรยี นตามลำดับคะแนน โดยคะแนนต่ำสุดและสูงสุดยsอมอยูsในตำแหนsงท่ี เหน็ ไดชq ัด ทวาs ถqาเราเลอื กใชงq านผิดวิธี คอมพวิ เตอรจ/ ะใชqเวลานานในการจัดเรยี งลำดบั ในการคqนหาบัญชีรายการใหญๆs แมวq าs จะใชqคอมพิวเตอรท/ เ่ี รว็ แคsไหนกต็ าม โชคดีที่มวี ิธีจดั เรยี งลำดบั หลายวธิ ี นักเรียนจะไดรq qจู กั วิธตี sางๆ และ เหน็ วาs สามารถใชqวิธอี นั ชาญฉลาดโดยไดผq ลเร็วกวาs วธิ งี sาย ๆ มากนกั เนื้อหาทเี่ ก่ียวขอ^ ง ü คณิตศาสตร/: การวดั ผล - จัดใหมq ีการวดั น้ำหนกั จริง ü การประมวลผล: อัลกอรธิ ่มึ ทกั ษะ ü ตาช่งั ü การจัดเรียงลำดบั ü การเปรียบเทียบ อายุ ü 8 ป‹ขน้ึ ไป วสั ดุอปุ กรณr นักเรยี นแตลs ะคนในแตลs ะกลุsมตอq งมวี สั ดุอปุ กรณ/ ดงั นี้ ü ภาชนะ 8 อนั ท่ขี นาดเดียวกนั แตนs ำ้ หนักตาs งกัน (เชsน กลsองนม หรอื กลsองอาหาร ใสทs รายไว)q ü ตาชั่ง ü แบบทดสอบ : สำหรบั บันทึกจัดเรียงนำ้ หนกั (หนqา 84) ü แบบทดสอบ : สำหรบั แบงs และชนะ (หนาq 85) หนqา 82

เบาสดุ และหนักสุด ขอ^ พจิ ารณา คอมพิวเตอร/มกั จัดเรียงลำดับขqอมูลไวq ผูรq sวมทำแบบทดสอบจะชวs ยกันพิจารณาหาจุดทกี่ ารจัดเรียงลำดับเป€น เรอื่ งสำคัญย่ิง และจะเกดิ อะไรข้นึ หากไมsมกี ารจดั เรียงลำดบั ไวq โดยปกติ คอมพวิ เตอรเ/ ปรียบเทียบคsาเพียงสองคาs ในคราวเดียวกัน แบบทดสอบในหนqาถัดไปจะใชqขqอจำกัดน้ี เพือ่ ใหqนักเรียนไดเq รยี นรqสู ถานการณ/ทแี่ ทจq รงิ แบบทดสอบ • จดั กลมุs นักเรยี น • แตลs ะกลมุs จะมกี ระดาษแบบทดสอบ (ชนดิ ทีป่ รากฏอยsูในหนาq 84) สง่ิ ของท่ีขนาดเดยี วกนั แตsน้ำหนกั ตาs งกัน และตาชัง่ • ใหนq ักเรยี นทำแบบทดสอบและอภิปรายผลการทดสอบ หนqา 83

แบบทดสอบ: การเรยี งลำดบั น้ำหนกั เป¥าประสงคr : เพอ่ื หาวิธจี ัดเรยี งลำดับนำ้ หนักตาs งๆ อุปกรณrสำหรบั การทดสอบ : ทรายหรือนำ้ ภาชนะทเ่ี หมือนกัน 8 อัน ชุดตาชัง่ 1 ชุด แบบทดสอบ : 1. เตมิ ทรายหรอื น้ำลงในภาชนะแตsละอันในจำนวนท่ีตาs งกัน ป„ดผนึกปากภาชนะใหแq นนs 2. จัดวางภาชนะสลับกันไปมาจนกระทัง่ ไมสs ามารถจำนำ้ หนกั ของของท่ีใสลs งไปไดq 3. หาอันทีน่ ำ้ หนักนqอยทสี่ ุด มีวิธใี ดทีจ่ ะทำเชsนนไ้ี ดงq sายท่สี ุด หมายเหตุ : อนญุ าตใหใq ชqตาชัง่ ชัง่ นำ้ หนักของภาชนะแตลs ะอันไดq แตsช่ังไดqคราวละ 2 อนั เทาs นน้ั 4. เลอื กภาชนะตาs งนำ้ หนักมา 3 อนั ใชตq าชัง่ จดั เรยี งลำดับตามนำ้ หนกั นอq ยไปหามาก สงั เกตดุ วู sาทำอยาs งไร เปรยี บเทยี บน้ำหนกั นอq ยคร้ังที่สดุ ก่ีครัง้ ทำไม 5. จากนนั้ จัดเรียงลำดับภาชนะท้งั หมดจากนำ้ หนักนอq ยท่สี ดุ ไปหานำ้ หนกั มากที่สุด เมือ่ จัดเรียงลำดับเสร็จแลวq ตรวจดูการจดั เรยี งลำดบั ดqวยตาชงั่ ทลี ะคูs การจดั เรยี งลำดบั แบบคดั เลอื ก (Selection Sort) อกี วิธหี นึ่งท่ใี ชใq นคอมพิวเตอร/ เรยี กวาs การจดั เรียงลำดบั แบบคัดเลอื ก เรม่ิ แรกใหqหาภาชนะที่มนี ้ำหนกั นqอยที่สุดในชุดนั้นแลqวแยกออกไวqตsางหาก จากนั้น หาภาชนะที่มีน้ำหนักนqอยถัดไป แยกออกไวq ตsางหาก ทำซำ้ จนกวาs จะแยกภาชนะท้ังหมดไดq นับจำนวนการเปรียบเทียบ เพิ่มเตมิ สำหรบั ผ^เู ชียวชาญ : แสดงการคำณวนวาs ตqองเปรยี บเทียบก่ีครงั้ เพอื่ จดั เรยี งลำดับภาชนะทัง้ 8 อัน ก่ี ครงั้ สำหรบั ภาชนะ 9 อนั หรือ 20 อัน หนาq 84

แบบทดสอบ: การแบyงแยก และ การเอาชนะ (Divide and Conquer) การเรยี งลำดบั อยาy งเรว็ (Quick Sort) การเรยี งลำดับอยsางเร็วทำไดqเร็วกวsาการเรยี งลำดับแบบคัดเลือกมาก โดยเฉพาะในบัญชีรายการใหญs อนั ท่ีจริง มนั เปน€ วธิ ีท่ดี ีที่สุดเทsาท่ีเคยมีมา เลือกภาชนะมาอันหน่งึ แลวq วางไวqขqางตาชัง่ ดาq นหนึ่ง จากนน้ั เปรยี บเทียบภาชนะทเ่ี หลอื กบั อนั ทวี่ างไวqขqางตาช่งั และวางอันที่คิดวาs เบากวาs ไวqทางซาq ยมือ อัน ที่หนกั กวsาไวทq างขวามอื โดยมีอันที่เลือกไวqแตแs รกอยูตs รงกลาง ทำซ้ำไปจนหมด (เมื่อจดั วางเสร็จแลqว อาจเป€นไปไดทq ี่ดqานหน่งึ จะมีภาชนะมากกวsาอกี ดqานหนึง่ ) เลือกภาชนะทีอ่ ยดูs qานหน่งึ (ซqายหรือขวา) ของภาชนะตวั เลอื กแรกและทำตามวิธีขาq งตนq และดูใหqแนsใจ วsาภาชนะอนั ทีเ่ ลอื กไวอq ยsูตรงกลางเสมอ ทำซ้ำไปเรื่อย ๆ จนกระทั่งแตsละกลมุs เหลือเพียงภาชนะเดียว เมื่อจัดเรียงถึงจุดที่เหลือเพยี งภาชนะ เดยี วในแตsละกลsุม ภาชนะก็จะเรยี งลำดับจากเบาท่ีสดุ ไปหาหนกั ทีส่ ุด วิธนี ้ีมีจำนวนการเปรยี บเทียบกคี่ ร้ัง เราจะพบวsาการเรียงลำดับแบบรวดเร็วน้ี มีประสิทธิภาพในการจัดเรียงลำดับมากกวsาการเรียงลำดบั แบบคัดเลือก เวqนไวqแตsวsา จะเลือกน้ำหนักนqอยที่สุดหรือมากที่สุดไวqตั้งแตsครั้งแรก ถqาโชคดีเลือกไดq น้ำหนกั ท่ีอยsตู รงกลาง ก็อาจใชจq ำนวนเปรยี บเทียบแคs 14 คร้งั เทาs นั้น เมอื่ เปรยี บเทยี บกบั การเรยี งลำดบั แบบคัดเลือก จำนวนเปรียบเทียบเพื่อใหqการเรียงลำดับครบถqวนสมบูรณ/ตqองทำถึง 28 ครั้ง ไมsวsาจะ หนqา 85

อยsางไร การเรียงลำดับแบบรวดเร็วนี้ มีประสิทธิภาพไมsนqอยกวsาการเรียงลำดับแบบคัดเลือก และใน บางครงั้ กม็ ปี ระสทิ ธภิ าพดีมากกวsาดวq ย เพิ่มเติมสำหรับผู^เชี่ยวชาญ: ถqาการเรียงลำดับแบบรวดเร็วเลือกภาชนะที่เบาที่สุดเสมอโดยบังเอิญ จะตqองทำจำนวนเปรยี บเทียบกคี่ ร้ัง หนqา 86

การผนั แปร และ การตอy ขยาย (Variations and Extensions) การคqนคิดวิธีจัดเรียงลำดับแบบตsาง ๆ ยังคงมีมาอีกมากมาย การจดั เรียงลำดับนำ้ หนักอาจกระทำไดq ดqวยวธิ ีตsอไปน้ี การเรยี งลำดบั การแทรก (Insertion Sort) ทำไดqโดยการแยกภาชนะแตsละอันออกมาจากกลsุมที่ไมsไดqจัด เรยี งลำดับ จากนนั้ จงึ จดั เรยี งลำดบั กลมุs ใหมโs ดยนำภาชนะแตลs ะอนั มาจดั วางลงในตำแหนsงทเ่ี รียงลำดับ ทถี่ กู ตqอง (ดูรูปภาพดาq นลsางน้)ี ดวq ยการจัดวางแบบนี้ กลุsมภาชนะที่ไมไs ดqจัดเรียงจะเลก็ ลงในขณะทกี่ ลมุs ภาชนะที่ถกู จัดเรียงลำดับจะใหญขs ้ึนจนในท่สี ดุ จะเหลอื แตกs ลมุs ภาชนะทถ่ี กู จัดเรยี งลำดบั นกั พนนั มกั ใชq วธิ ีนี้ในการเรยี งไพs การจดั เรียงลำดบั แบบฟอง (Bubble Sort) ทำโดยการเปรยี บเทียบภาชนะทอ่ี ยูsติดกนั เป€นคsู ๆ และ สลบั ภาชนะที่ผิดตำแหนงs ใหอq ยูถs ูกตำแหนงs ไปเรอ่ื ย ๆ จนกระทัง่ ทกุ ภาชนะอยูsตำแหนsงท่ีถูกตอq ง วธิ นี ไ้ี มs คsอยมีประสทิ ธิภาพแตสs ำหรบั บางคนก็งาs ยทจ่ี ะเขqาใจหลักการ การจัดเรียงลำดบั แบบผสาน (Merge Sort) เป€นอีกวิธีหนึ่งทีใ่ ชqหลักการ “แบsงแยกแลqวเอาชนะ” เพื่อ การจัดเรียงลำดับ เริ่มแรก แบsงภาชนะออกเป€นสองกลุsมเทsากัน (หรือเกือบเทsากัน ถqาเป€นจำนวนค)่ี ขณะแบงs จะจดั เรียงลำดบั ภาชนะเป€นคsูในแตsละกลุsมไปดqวย จากนั้น เร่ิมรวมภาชนะในทั้งสองกลุsมเขqา ดqวยกันโดย นำอันเล็กสุดของทั้งสองกลุsมมาวางไวqขqางหนqา ตามภาพที่ปรากฏขqางลsางนี้ ภาชนะที่มี น้ำหนัก 40 และ 60 กรัม อยูsตอนหนqาของทั้งสองกลุsม ดังนั้น ลำดับตsอไปที่ตqองนำไปจัดเรียง ก็คือ นำ้ หนัก 40 กรมั ทีนีจ้ ะจัดเรยี งลำดบั น้ำหนักนqอยสุดไดqอยsางไร คำตอบงาs ยมาก เพยี งแคsเราใชqหลักการ จัดเรียงลำดบั แบบผสาน ในที่สดุ ภาชนะทัง้ หมดจะเป€นเอกเทศจากกัน ก็เป€นอนั สิ้นสุดโดยไมsตอq งคอย พะวงวาs จะเสรจ็ เมือ่ ไร หนqา 87

ทัง้ หมดนีเ้ กยี่ วกับอะไร? เราจะสามารถคqนหาขqอมูลตาs งๆไดงq sายกวsา โดยการเรียงลำดับขอq มูลเหลาs น้ัน เชsน ในกรณีของสมุดโทรศัพท/ เราจะหารายชือ่ ตsางๆไดqงsายขนึ้ ถqาใชqการจัดเรยี งตามตวั อักษร หรือสำหรับบญั ชีคsาใชqจาs ย ถqาเรียงตัวเลขจาก นqอยไปหามาก เราก็จะหาคsาท่ีนอq ยทีส่ ดุ ,มากทส่ี ุด แมqกระท่ังเลขท่ซี ้ำกันไดงq าs ยมาก โดยดูจากจากหัวและทqาย ของรายการ หรอื เลขซำ้ กนั จะอยดูs วq ยกัน ดqวยเหตุนี้ คอมพิวเตอร/จึงใชqเวลาอยsางมากในการจัดเรียงขqอมูลตsางๆตามลำดับ ดังนั้นนักวิทยาศาสตร/ คอมพิวเตอรจ/ งึ ตqองคดิ วิธกี ารในการทำงานนี้ใหqเร็วและมีประสทิ ธภิ าพมากทสี่ ดุ อยsางไรกต็ าม ในบางคร้ังวิธีที่ ชqา เชsน การเรียงลำดับแบบเลือก การเรียงลำดับแบบแทรก หรือการเรียงลำดับแบบฟองก็อาจไดผq ลในบาง กรณีเชsนกัน แตsโดยสsวนใหญsแลqวก็มักจะใชqวิธีท่ีเร็วกวsา เชsน การเรียงลำดับแบบรวดเร็ว และการเรียงลำดับ แบบผสาน เพราะวsาสามารถจัดเรียงรายการขนาดใหญไs ดqรวดเร็วกวsานั่นเอง เชsน มีขqอมูลอยูs 100,000 ชิ้น การจดั เรียงแบบรวดเรว็ จะใชเq วลาเรว็ กวsาการจดั เรียงแบบเลอื กถงึ 2,000 เทาs และสำหรับขอq มูล 1,000,000 ชิน้ จะสามารถทำงานไดเq ร็วกวsาถึง 20,000 เทาs เลยทเี ดียว ซึง่ ในความเปน€ จริง คอมพิวเตอร/กจ็ ะตqองรบั มอื กับ ขอq มลู เป€นลqานชน้ิ อยsูแลqว เชนs จำนวนขqอมูลลกู คqามากมายบนเว็บไซตต/ sางๆ หรอื ขนาดของรูปภาพทีเ่ ปน€ ลqานๆ พิกเซล ดงั นัน้ แคsความแตกตsางของอัลกอรทิ ึม 2วธิ นี ี้ อนั หนง่ึ อาจกนิ เวลาแคsเพียง 1 วนิ าที สsวนอีกอันอาจใชq เวลามากถงึ 5 ชัว่ โมงเลยกเ็ ป€นไดqในการทำงานเดยี วกนั และไมใs ชsแคsทำใหเq กิดการลาs ชาq มากยงิ่ ข้ึนเทsาน้ัน แตs มันหมายถึงคอมพิวเตอร/จะใชqพลังงานมากขึ้นถึง 20,000 เทsาดqวยเชsนกัน (ซึ่งจะสsงผลกระทบตsอ สภาพแวดลqอมและยังลดอายุการใชqงานของแบตเตอรี่ในอปุ กรณ/พกพาอกี ดqวย) ดังนั้นการเลือกอัลกอริธมึ ท่ี ถกู ตอq งจึงมีผลอยsางมาก การจัดเรียงแบบรวดเร็ว ใชqวิธีการที่เรียกวsา “การแกqป'ญหาแบsงสsวน” โดยเราจะแบsงป'ญหาใหญsๆใหqเป€น ป'ญหายsอยๆ และทำการจัดเรียงแบบรวดเร็วในแตsละสsวนยsอยๆนั้น ซึ่งป'ญหาของเราจะถูกแบsงไปเรื่อยๆ จนกวsาจะเลก็ เพียงพอตsอการแกqป'ญหาไดq ในกรณีนี้ การจัดเรียงแบบรวดเร็วจะแบsงจนกวsาแตลs ะรายการจะ ประกอบดqวยขqอมลู เพียงชิ้นเดียวเทsาน้ัน แลqวรวมขqอมลู นั้นเรียงตามลำดับ ถึงแมqวsามันอาจจะดซู ับซqอน แตs ในทางปฏิบัติ วิธีนี้ก็เร็วกวsาวธิ ีการอื่น ๆ อยsางมาก และนี่คือตัวอยาs งของแนวคิดทีม่ ีประสทิ ธิภาพซึ่งเรียกวาs “การเวียนเกิด” ซึ่งอัลกอริทึมใชตq ัวเองเพื่อแกqป'ญหา - ฟ'งดูอาจจะแปลก ๆ แตsมันสามารถทำงานไดqดีอยsาง มาก หนqา 88

วธิ ีทำและคำใบ^ 1. วิธีท่ีดีทีส่ ดุ ในการหาวัตถุชนิ้ ทเ่ี บาท่ีสดุ คอื การตรวจสอบของทุกชิ้นและหาชน้ิ ทน่ี ้ำหนักนqอยที่สุด โดย การเปรียบเทยี บของ 2 สิง่ และเลือกช้นิ ท่ีเบากวาs ตอs มานำชนิ้ ทเ่ี ลือกไปเปรยี บเทียบกบั ชิ้นอ่นื ๆ แลqว เกบ็ ชิน้ ทีเ่ บากวsาไวq วนทำซ้ำไปเรอ่ื ยๆจนกวาs ครบทกุ ช้นิ 2. เปรยี บเทยี บนำ้ หนักบนเครอ่ื งชงั่ น้ำหนกั กระบวนการนี้สามารถทำไดดq วq ยการเปรียบเทยี บท้งั หมด 3 ครั้งและอาจใชqแคsเพียง 2 ครั้งเทsานัน้ โดยคิดจากการกฎการถsายทอด เชsน ถqา A เบากวsา B และ B เบากวาs C ดังนัน้ A ตqองเบากวาs C เปน€ ตqน ทักษะความรู^ : ในการจัดเรยี งแบบเลือก นีค่ ือวิธีสนั้ ๆทแ่ี สดงถงึ การรวมจำนวนครัง้ ของการเปรยี บเทียบทั้งหมด สำหรบั การหาคsาท่นี อq ยกวsาของวตั ถุ 2 ชิ้น เราจะตqองใชqการเปรยี บเทยี บ 1 ครั้ง เชนs ถาq ของ 3 ชิ้นตqองใชqการ เปรียบเทียบ 2 ครัง้ เปน€ ตนq ดงั น้ัน ถqาจะเปรยี บเทียบของ 8 ส่งิ จะตqองใชqทัง้ หมด 7 ครงั้ เพ่อื หาของท่ีเบาท่ีสุด ชิน้ แรก ตsอมาเมือ่ เหลือของ 7 ชิน้ กต็ อq งใชกq ารเปรียบเทียบ 6 คร้งั เพื่อหาอนั ท่เี บารองลงมา เม่อื เหลือ 6 ช้ินก็ ตqองเทยี บเคียง 5 ครงั้ เพ่ือหาอนั ทีเ่ บาถัดไป เป€นแบบนีไ้ ปเร่อื ยๆ กจ็ ะไดวq sา 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 ครั้งในการเทียบเคยี ง ถาq เกดิ มีวตั ถทุ ้ังหมด n ชนิ้ จะใชqการเปรยี บเทียบทงั้ หมด 1+2+3+4+........+ n-1 ครั้งในการจดั เรยี ง และจะงsายขึ้นเมอ่ื เราจัดกลมุs การบวกใหมsดงั ตัวอยาs งตsอไปน้ี ถqาตqองการหาคาs 1 + 2 + 3 + … + 20 จัดกลมsุ ใหมจs ะไดq (1 + 20) + (2 + 19) + (3 + 18) + (4 + 17) + (5 + 16) +(6 + 15) + (7 + 14) + (8 + 13) + (9 + 12) + (10 + 11) = 21 × 10 = 210 และเม่อื จัดรูปแลวq จะไดqสตู รทวี่ sา 1 + 2 + 3 + 4 … + n – 1= n(n – 1)/2. หนqา 89

กิจกรรมที่ 8 เอาชนะเวลา – การจดั เรียงเครือขyาย บทสรปุ แมวq sาคอมพิวเตอร/จะทำงานไดqรวดเรว็ แตsกย็ ังมขี qอจำกัดเกยี่ วกับความเรว็ ในการแกปq ญ' หาอยsู ซึ่งวธิ ีหน่งึ ในการ เพิ่มความเร็วคือการใชqคอมพิวเตอร/หลายเครื่องในการแกqป'ญหาตsางๆ ในกิจกรรมนี้เราจะใชqการจัดเรียง เครอื ขาs ย ทจี่ ะทำการเปรยี บเทยี บและเรียงลำดบั ขอq มูลตาs งๆในเวลาเดยี วกนั หลักสูตรทเ่ี ก่ยี วขอ^ ง ü คณติ ศาสตร/ – จำนวนและตัวเลข : สำรวจตวั เลข – มากกวาs ,นอq ยกวsา ทกั ษะ ü การเปรยี บเทียบ ü การเรยี งลำดบั ü การพฒั นาอลั กอริทมึ ü การรวs มมอื กันแกปq 'ญหา อายุ ü 7 ปข‹ น้ึ ไป อุปกรณr กิจกรรมนเ้ี ปน€ กจิ กรรมนอกสถานท่ี ü ดินสอชอล/ค ü การ/ด 6 ใบจำนวน 2 ชุด (ถาs ยเอกสาร การจัดเรียงเครอื ขาs ย ในหนqา 89 ลงบนการ/ด) ü นาºิกาจบั เวลา หนาq 90

การจดั เรยี งเครือขyาย ในกจิ กรรมน้ีใหqนักเรียนใชชq อลค/ ทำเคร่อื งหมายเสqนเครอื ขsายในสนาม คำแนะนำสำหรับนักเรียน กิจกรรมน้แี สดงใหเq หน็ วาs คอมพิวเตอร/ทำงานอยsางไรในการเรียงตัวเลขแบบสุsมใหqเปน€ ลำดบั โดยใชกq ารจดั เรยี ง เครอื ขาs ย 1. จัดกลุsม กลุมs ละ 6 คน โดยมีแคเs พยี งกลมุs เดียวเทsานั้นท่ใี ชเq ครอื ขาs ยไดใq นแตลs ะครง้ั 2. แตลs ะคนในกลุมs เลอื ก การด/ ตัวเลขมาคนละ 1 ใบ 3. ใหqแตsละคนในกลุsมไปยืนท่ีสีเหลี่ยมดqานซqายของสนาม (IN) ดังรูปขqางตqน โดยตำแหนsงที่ยืน ไมsตqอง เรยี งลำดับอะไรท้ังสนิ้ 4. หลงั จากน้ันใหqแตลs ะคนเริม่ เคล่ือนท่ีตามลกู ศร และหยดุ รอเพื่อนเม่ือถึงตำแหนงs วงกลม ใหqมาแทนท่ี จงึ จะไปตอs ไดq 5. ใหqนกั เรยี นเปรียบเทียบการด/ ตวั เลขกบั เพือ่ น ณ ตำแหนงs วงกลมเดยี วกัน คนท่ีมีการ/ดตัวเลขนqอยกวsา ใหเq คล่ือนท่ีไปทางซาq ย สsวนคนท่มี ตี ัวเลขมากกวsา ใหเq คล่ือนที่ไปทางขวา 6. ตรวจสอบตำแหนsงทีย่ นื อกี คร้ัง ถาq เกดิ ความผดิ พลาดใหเq ร่ิมใหมs เพ่ือใหมq ่นั ใจวsานักเรยี นสามารถเขาq ใจ หลักการทำงานของโหนดวงกลมในเครือขาs ยไดqซึ่งก็คอื ถqาคsาตัวเลขนqอยกวsาใหqไปทางซาq ย แตsถqาคsา มากกวsา ใหqไปทางขวา อยsางเชนs ตัวอยาs งในรูป หนาq 91

หนาq 92

สำเนาเอกสาร: การจัดเรยี งเครอื ขาy ย 12 34 56 156 221 289 314 422 499 หนqา 93

การเปลย่ี นแปลง 1. เมือ่ นกั เรยี นคqนุ เคยกบั กิจกรรมแลqว ใหใq ชqนาºกิ าจบั เวลาเพอื่ วดั วาs แตsละทมี ใชเq วลาในการผsานเครือขsาย เทsาใด 2. ใชกq ารด/ ทม่ี จี ำนวนตัวเลขมากข้ึน (เชsน เลขสามหลกั ในสำเนาเอกสาร). 3. สรqางการ/ดที่มีจำนวนตัวเลขมากขึ้น โดยใหqแนsใจวsาจำนวนเหลsานี้จะตqองใชqความพยายามในการ เปรียบเทียบมากยิ่งขึ้น หรือใชqเป€นคำศัพท/ในการ/ดแทน และใหqเปรียบเทียบคำเหลsานี้ตามลำดับ ตัวอกั ษร 4. กิจกรรมนี้สามารถใชqเปน€ แบบฝŸกหัดสำหรับวิชาอื่นๆไดเq ชนs กนั เชsน ในวิชาดนตรี สามารถใหqนกั เรียน เปรยี บเทยี บตัวโนต¹ บนการ/ด และเรยี งลำดบั จากโนตq ต่ำสุดไปสงู สุด หรือสงู สดุ ไปต่ำสุดไดเq ชนs กนั กิจกรรมเพมิ่ เติม 1. จะเกิดอะไรขึ้นถqาตัวเลขที่มีจำนวนนqอยกวsาเคลื่อนไปยังดqานขวาแทนที่จะเป€นดqานซqาย หรือในทาง กลบั กนั ตัวเลขทม่ี ีจำนวนมากกวsาเคลือ่ นไปยงั ดqานซqายแทนทีจ่ ะเปน€ ดqานขวา ? (ตวั เลขน้ีจะถูกจดั เรียง ในทางตรงกนั ขqามกบั แบบเดิม) แลวq มนั จะไดผq ลหรือไมs ถqาเครอื ขsายถูกจัดเรียงในแบบถอยหลัง? (มนั ไมsจำเป€นวsาจะไดqผล นกั เรยี นควร จะสามารถหาตัวอยsางของการปอ› นขqอมลู ที่จะแสดงผลออกมาในการจดั เรยี งลำดับท่ีผดิ แบบนีไ้ ด)q 2. ทดลองออกแบบเครือขsายทเ่ี ลก็ ลงหรือใหญขs น้ึ ตัวอยาs งเชsน ดงั ในรูป นเ้ี ป€นเครือขาs ยท่มี กี ารจัดเรยี งลำดบั เพยี งแคs 3 จำนวนเทsานั้น. นกั เรียนควรลองสราq งในแบบของตนเองดู 3. รูปเบื้องลsางนี้แสดงใหqเห็นถึงเครือขsายที่แตกตsางกัน 2 แบบซึ่งมีการ จัดเรียงขqอมูล 4 จำนวน โดยแบบไหนจะมีการเคลื่อนท่ีของขqอมูลเรว็ กวsากัน ? (คำตอบคือแบบที่ 2 เพราะ ในขณะทีแ่ บบแรกเรยี กรqองการเปรยี บเทยี บตัวเลขทงั้ หมดใหเq สรจ็ กsอนเป€นชุดๆ อยsางเปน€ ลำดับ แตsในขณะเดยี วกันนี้เอง แบบท2ี่ ก็เร่ิมทำงานบางสsวนเลย แบบแรกจึงเป€นตวั อยsางของการประมวลผล แบบเป€นลำดบั สวs นแบบที่ 2 ใชqการประมวลผลแบบคูsขนาน ทำใหสq ามารถทำงานไดเq ร็วมากขึ้น หนqา 94

4. ทดลองสรqางการจัดเรียงลำดบั เครอื ขาs ยทม่ี ขี นาดมากขึน้ 5. ระบบเครือขsายสามารถใชqในการหาขqอมูลที่มีคsานqอยที่สุด หรือมากที่สุดไดq ตัวอยsางเชsน ดังรูปนี้คือ เครือขsายท่ีมีการป›อนขqอมูล 8 จำนวน และในแตsละขqอมลู สงs ทอ่ี อกมาไดq จะประกอบดqวยขqอมูลท่ีมีคsา นอq ยท่ีสดุ (สวs นขqอมลู ทีเ่ หลือจะละไวqในสวs นถัดไปของเครอื ขาs ย) 6. มีกระบวนการใดบqางในชีวติ ประจำวนั ที่สามารถและไมสs ามารถเพมิ่ ความเรว็ ไดโq ดยใชเq ทคนคิ การทำงาน แบบคูsขนาน? ตัวอยsางเชsน การทำอาหาร ถqาใชqเพียงแคsเตาเดียว อาจจะทำใหqชqาเพราะตอq งคอยปรงุ อาหารอยsางเป€นลำดับ หรือมีกระบวนการทำงานใดบqางที่สามารถทำใหqเสร็จเร็วขึ้นไดqโดยการจqาง คนงานเพ่มิ ข้นึ ? และกระบวนการใดบาq งที่ไมsสามารถ? หนqา 95

ทั้งหมดนี้เกยี่ วกบั อะไร? เมื่อเราใชคq อมพวิ เตอร/มากขน้ึ เรากต็ อq งการใหมq นั ทำงานไดเq ร็วยง่ิ ข้ึนเชนs กนั โดยหนึ่งทางทีจ่ ะเพิม่ ความเรว็ ใหกq บั คอมพวิ เตอรน/ นั้ คอื การเขยี นโปรแกรมใหใq ชqขั้นตอนการคำนวณที่ นอq ยที่สุด (ดังใน กิจกรรมท่ี 6 และ 7) อีกทางหน่ึง คือ การใชqคอมพิวเตอร/หลายๆตัวในการทำงานแตsละสsวนของ 1 งาน ในเวลาพรqอมๆกนั ตวั อยsางเชsน การจัดเรียงเครอื ขาs ยดqวยขqอมูล 6 จำนวน แมวq าs จะตอq งใชqการเปรียบเทยี บตัวเลขทั้งหมด 12 คร้ัง แตsก็มถี ึง 3 ครงั้ ท่สี ามารถใชqการคำนวณเปรียบเทียบพรqอมกนั ไดq น่นั หมายความวsาจะตอq งการ การรqองขอเวลาเพมิ่ เพยี ง 5 ครัง้ เทาs น้ัน ดงั นนั้ การจัดเรียงเครอื ขsายแบบคูsขนาน จะสามารถทำงานไดq เร็วกวsาแบบทำตามลำดับถงึ 2 เทsา เพราะการทำตามลำดับจะสามารถทำการเปรยี บเทียบไดqทีละครงั้ เทาs นั้น อยsางไรกต็ าม ไมใs ชsงานทัง้ หมดที่จะสามารถเพม่ิ ความเรว็ โดยใชqการทำงานแบบคขsู นาน ดงั่ เชนs การขดุ คู น้ำที่มีความยาว 10 เมตร ถqาใชqคนงานท้ังหมด 10 คน แตsละคนขุดคูนำ้ คนละ 1 เมตร จะใชqเวลาการ ทำงานทั้งหมดเร็วขึ้น แตsในทางกลับกัน ถqาในกรณีที่ตqองการขุดคูน้ำลึก 10 เมตร การทำงานแบบ คูsขนานจะไมsสามารถใชงq านไดq เพราะวsา ความลึกที่ 2 เมตรจะไมsสามารถขดุ ไดqถqาเมตรแรกยงั ไมsเสรจ็ ดังน้ัน นักวทิ ยาศาสตร/ทางคอมพวิ เตอร/ยังคงหาทางทด่ี ีที่สุดในการแบงs ปญ' หาออกเป€นสsวนๆ เพื่อที่จะ ใชกq ารทำงานแบบคขsู นานแกปq ญ' หาเหลาs นไี้ ดq หนาq 96

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

เมอื งทเี่ ตม็ ไปดว^ ยโคลน บทนำ กิจกรรมนีจ้ ะแสดงใหqนักเรยี นเหน็ วาs คอมพวิ เตอรน/ ้ันสามารถใชงq านเพ่อื หาคำตอบทีด่ ที ี่สดุ ไดqอยsางไรเมื่อเป€น ป'ญหาในโลกแหsงความจรงิ เชนs วิธีตอs สายไฟฟ›าระหวาs งบาq นแตลs ะหลงั เป€นตนq นกั เรยี นสามารถใชqแบบฝŸกหัด หนาq 99 เพื่อชวs ยในการอธิบายป'ญหา “เมอื งที่เตม็ ไปดวq ยโคลน” ไดq การอภิปรายเพ่ิมเติม รวs มกนั แชรค/ ำตอบท่ีไดqกับเพือ่ นๆ และกระบวนการแบบใดทน่ี กั เรียนไดใq ช?q หน่งึ ในวิธีการที่ดีคอื การเพมิ่ เคาq นเ/ ตอร/จนกวsาบqานทุกหลงั จะเชือ่ มตsอกนั จากน้ันเพม่ิ เสqนทางตามลำดับของ ระยะทางจากนqอยไปมากของบาq นแตลs ะหลงั แตsเราจะไมsเชอื่ มตsอบqานท่ีมีการเชื่อมตsออยแsู ลqว นอกจากวิธีการ ท่บี อกมาแลวq เรายังสามารถหาวิธีการอน่ื ไดqอีก ถาq เราลองเปลยี่ นลำดับของเสqนทางของระยะทางทเี่ พม่ิ เขqาที่มี ขนาดเทsากัน เราก็จะเจออีกวิธหี นงึ่ มวี ิธีที่เปน€ ไปไดqอยูsสองวธิ ตี ามรูปดqานลาs ง ยังมีอกี วธิ กี ารหนึ่งก็คือ เร่ิมตqนจากปูทกุ เสนq ทางดวq ยพนื้ แลวq จากนนั้ กน็ ำเสqนทางทไ่ี มsไดqใชqออก วิธนี จ้ี ะใชคq วาม พยายามมากกวาs ยงั ไงก็ตาม ทใ่ี ดบาq งทค่ี ุณสามารถหาเครอื ขาs ยไดqในชวี ิตจริง นักวิทยาศาสตร/คอมพิวเตอร/เรียกส่ิงทแี่ สดงผลของเครอื ขาs ยพวกน้ีวsา “กราฟ” เครอื ขsายของจริงสามารถถูก นำเสนอไดดq qวยกราฟเพ่ือนำไปเพื่อแกqปญ' หาเชsน ออกแบบเครือขsายถนนหนทางที่ดีที่สุดระหวsางเมือง, หรือ เที่ยวบินของเครอ่ื งบนิ รอบๆประเทศไดqอกี ดวq ย ยังมีอัลกอริทมึ อีกมากมายที่สามารถนำมาใชqกับกราฟไดq เชsน การหาระยะทางทีส่ ั้นที่สดุ ระหวsางจุดสองจุด, หรือเสนq ทางทผ่ี าs นจดุ หนqา 98

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

รูปแบบและสวy นขยาย นค่ี อื อีกวิธกี ารแสดงแผนผงั ของเมอื งนี้ บาq นถูกแทนท่ดี วq ยวงกลม, ถนนแทนทด่ี qวยเสqน, และความยาวของถนนคือเลขทอ่ี ยsขู qางเสนq นักวทิ ยาศาสตรค/ อมพวิ เตอร/และนกั คณติ ศาสตร/ มกั ทจ่ี ะใชแq ผนภาพจำพวกนี้ในการแสดงปญ' หาเหลาs น้ี พวก เขาเรยี กแผนภาพพวกน้ีวsา กราฟ นอ่ี าจจะทำใหคq ุณสบั สนไดตq อนแรก เนื่องจาก “กราฟ” น้นั บางคร้ังไดqถูกใชq ในเรื่องที่เกีย่ วกับสถติ ิเพ่ือแสดงผลทางตัวเลข,เชsน กราฟแทsง, แตsกราฟท่ีนักวิทยาศาสตร/คอมพิวเตอรใ/ ชqนัน้ ไมsไดเq ก่ียวขqองกันแตอs ยsางใด ความยาวเสนq น้ันจะไมถs กู วาดเป€นแทsงหรอื ขนาด สราq งป'ญหาเมืองทเ่ี ต็มไปดqวยโคลนของคณุ เองแลวq ลองใหqเพ่อื นๆของคุณไดqลองทำกนั ดู คุณสามารถที่จะหากฎที่จะอธิบายวsามีถนนกี่เสqนหรือตอq งการการเชื่อมตsอเทsาไหรsไดqไหม สำหรับคำตอบทีด่ ี ที่สดุ ?แลqวมนั เกย่ี วขอq งกบั จำนวนบาq นในเมืองน้หี รอื ไม?s หนqา 100