ACM มอบรางวัล Turing Award พร้อมเงินรางวัลล้านดอลลาร์ให้กับ Avi Wigderson จากการที่เขาเป็นนักวิจัยสำคัญในวงการ theory of computation โดยเฉพาะความเข้าใจความสำคัญของการสุ่มค่าในอัลกอริทึม
โดยทั่วไปแล้วอัลกอรึทึมที่เราใช้งานและคอมพิวเตอร์คำนวณให้จะเป็นระบบ deterministic หมายความว่าข้อมูลเข้าจะกำหนดผลลัพธ์และระยะเวลาที่ใช้คำนวณเสมอ ทำให้พฤติกรรมของอัลกอรึทึมคาดเดาได้ แต่อัลกอรึทึมหลายตัวอาศัยการสุ่มค่าเพื่อเพิ่มประสิทธิภาพ (มั่วแล้วเร็วขึ้น) โดยปัญหาหลายอย่างไม่มีทางคำนวณอย่างมีประสิทธิภาพเลย หากไม่อาศัยการสุ่มค่า วงการวิจัย theory of computation พยายามทำความเข้าใจความสำคัญของการสุ่มค่าเช่นนี้ เช่น จำเป็นต้องมีการสุ่มที่ดีหรือไม่ หรือสามารถถอดการสุ่มค่าทิ้งไปเลยได้หรือไม่
งานวิจัยของ Wigderson สาธิตถึงการใช้กระบวนการสุ่มค่าเทียม (pseudorandom generator - อ่านเพิ่มเติมบทความเก่า) ก็ยังใช้งานเหมือนการสุ่มค่าได้ครอบคลุมหลายกรณี
ที่มา - ACM
Topics:
ACM
Computer Science
Theory
อ่านต่อ...
โดยทั่วไปแล้วอัลกอรึทึมที่เราใช้งานและคอมพิวเตอร์คำนวณให้จะเป็นระบบ deterministic หมายความว่าข้อมูลเข้าจะกำหนดผลลัพธ์และระยะเวลาที่ใช้คำนวณเสมอ ทำให้พฤติกรรมของอัลกอรึทึมคาดเดาได้ แต่อัลกอรึทึมหลายตัวอาศัยการสุ่มค่าเพื่อเพิ่มประสิทธิภาพ (มั่วแล้วเร็วขึ้น) โดยปัญหาหลายอย่างไม่มีทางคำนวณอย่างมีประสิทธิภาพเลย หากไม่อาศัยการสุ่มค่า วงการวิจัย theory of computation พยายามทำความเข้าใจความสำคัญของการสุ่มค่าเช่นนี้ เช่น จำเป็นต้องมีการสุ่มที่ดีหรือไม่ หรือสามารถถอดการสุ่มค่าทิ้งไปเลยได้หรือไม่
งานวิจัยของ Wigderson สาธิตถึงการใช้กระบวนการสุ่มค่าเทียม (pseudorandom generator - อ่านเพิ่มเติมบทความเก่า) ก็ยังใช้งานเหมือนการสุ่มค่าได้ครอบคลุมหลายกรณี
ที่มา - ACM
Topics:
ACM
Computer Science
Theory
อ่านต่อ...
