ข้อพิจารณาเกี่ยวกับ sorting network (กิจกรรม unplugged)

Posted on by

Main ideas:

  1. เป้าหมายหลักคือ พิจารณาการทำงานแบบ parallel processing เทียบกับการทำทีละขั้นตอน
  2. งานบางอย่างแบ่งกันทำพร้อมกันได้ง่าย เช่น แบ่งกันพิมพ์เอกสาร 10 หน้า คนละหน้า หรืองานขุดร่องตื้นๆ (ditch) ยาว 10 เมตร สามารถแบ่งกันขุดสิบคนคนละเมตร พร้อมๆ กันได้
  3. งานบางอย่างแบ่งกันทำพร้อมกันไม่ได้ เช่น การขุดหลุมลึก 10 เมตร จะแบ่งให้คนสิบคนขุดคนละเมตรโดยขุดพร้อมกันไม่ได้
  4. คำว่า sorting network ในที่นี้เป็นการใช้คำคนละความหมายกับ network ที่เป็นโครงข่ายสื่อสาร (ระวังสับสน)
  5. จุดเน้น: การทำตาม algorithm แบบเป๊ะๆ และการทำงานร่วมกับเพื่อน (collaboration) เช่น ต้องหยุดรอกันจึงจะไปต่อได้
  6. ขั้นอภิปราย: อาจพูดถึง GPU ซึ่งทำงานแบบ parallel และมักถูกนำมาใช้ในงานอื่นนอกจากงานกราฟฟิก, MapReduce บน Cloud
  7. นี่ไม่ใช่วิธีการเรียงข้อมูลที่ใช้กันโดยทั่วไป จุดประสงค์หลักของกิจกรรมนี้ไม่ได้มีไว้เพื่อสอนอัลกอริทึมการจัดเรียง แท้จริงแล้ว sorting network ในตัวอย่างถูกออกแบบมาเพื่ออินพุต 6 ตัวเท่านั้น ถ้าเปลี่ยนจำนวนอินพุตก็จะต้องออกแบบ network ใหม่ และการออกแบบนั้นไม่ใช่เรื่องง่ายที่เด็กเล็กจะทำเองได้
  8. ในตัวกิจกรรมนี้เองยังไม่สามารถพิสูจน์ให้นักเรียนเห็นได้ว่าอัลกอริทึมนี้ถูกต้อง 100% แต่สามารถฝึกให้นักเรียนคิดตามได้ว่าข้อมูลตัวที่เล็กที่สุดจะไปอยู่ข้างล่าง ข้อมูลที่มากสุดจะไปอยู่ข้างบน (หรือกลับกัน) เพราะอะไร

ข้อควรระวัง

ระวังสอนผิดวัตถุประสงค์ เช่น แนวการสอนเหล่านี้ น่าจะสร้างความเข้าใจผิดให้นักเรียน:

  1. นักเรียนจะได้เห็นตัวอย่างการเรียงข้อมูลของคอมพิวเตอร์ ที่ใช้กันโดยทั่วไป (ผิด!)
  2. วิธีนี้สามารถใช้เรียงข้อมูลกี่ตัวก็ได้ (ผิด!)
  3. หลังจากทำกิจกรรมแล้ว ครูจะพิสูจน์ให้ดูว่าทำไมผลลัพธ์ถึงจะถูกเรียงอย่างถูกต้องเสมอ (ผิด! — การพิสูจน์นั้นทำได้ แต่ไม่น่าจะง่ายพอที่จะอธิบายให้เด็กประถมเข้าใจได้)
  4. เห็นไหมว่าถ้าเราทำงานพร้อมๆ กัน ย่อมเร็วกว่าทำทีละขั้นตอนเสมอ (ผิด!)
  5. นักเรียนจะได้เรียนเรื่อง ​sorting network และจะได้เห็นว่าระบบ network ที่เราใช้สื่อสารกันบนอินเทอร์เน็ตนั้นมีประโยชน์อย่างไร (ผิด! — ไม่เกี่ยวกันเลยครับ)

Videos

https://youtu.be/M-z5pDjqtZk

ตัวอย่างการพิสูจน์ความถูกต้อง

  • หัวข้อ Applying what we have just learnt ในหน้านี้ยกตัวอย่างวิธีพิสูจน์ความถูกต้องของตำแหน่งข้อมูลตัวที่เล็กสุด และใหญ่สุด (แต่ไม่ได้เขียนอธิบายออกมาทั้งหมด) และบอกว่าสำหรับข้อมูลที่เล็กสุดเป็นอันดับสองการพิสูจน์จะไม่ง่ายนัก แต่ “computer scientists are able to prove that they will also always end up in their correct position” — พูดง่ายๆ ก็คือ “ขอเธอจงโปรดไว้ใจและศรัทธา” https://www.csunplugged.org/en/topics/sorting-networks/unit-plan/reinforcing-numeracy-through-a-sorting-network-junior/

Sources

  1. กิจกรรม Sorting Network โดยเว็บไซต์ CS Unplugged: https://www.csunplugged.org/en/topics/sorting-networks/unit-plan/description/
  2. Cover image borrowed from csunplugged.org and the YouTube video by UC Computer Science Education https://youtu.be/M-z5pDjqtZk

ผนวกเดช สุวรรณทัต
22 กันยายน 2563