|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
การแบ่งเหรียญเป็นสองกลุ่มกับความไม่แน่นอน
เริ่มจากปัญหาง่ายๆ ถ้าเรามีเหรียนอยู่$n$เหรียน เราจะแบ่งเหรียนเป็นสองกลุ่มได้ $n-1$ วิธี
ถ้าเหรียนนั่นสุ่มหัวกับก้อยเราจะแบ่งเหรียนได้ $2^n*n-1$ วิธี ซึ่งใหญ่กว่าเหรียนกลุ่มเดียวซึ่งมีเพียง $2^n$ วิธี ซึ่งถ้าเราเอามาเทียบกันแบบหนึ่งต่อหนึ่งเราจะพบว่าความแตกต่างของจำนวนเหรียนที่ต้องการใช้ในการจับคู่จะเพิ่มขึ้นเมื่อ $n$ ใหญ่ขึ้นซึ่งเราสามารถสร้างความแตกต่างของเหรียนเท่าไหร่ก็ได้ถ้า $n$ ใหญ่พอ ผมคิดว่าความแตกต่างของจำนวนเหรียนคือขนาดโปรแกรมที่สั้นที่สุดที่จะแบ่งไบนารี่เป็นสองกลุ่มโดยสามารถย้อนกลับได้ แต่ผมก็ยังเชื่อลึกๆอยู่ว่าบางทีอาจจะมีโปรแกรมที่สั้นกว่านั่นถ้าขนาดเหรียนเยอะมากๆหรือเราใช้โครงสร้างข้อมูลที่ซับซ้อนมากๆ ซึ่งนั่นจะสามารถใช้เป็นโปรแกรมบีบอัดข้อมูลได้ และเป็นข้อพิสูจน์ว่าคณิตศาสตร์ไม่แน่นอน เพื่อนๆมีความเห็นว่าอย่างไรครับ |
#2
|
|||
|
|||
โทษที อธิบายข้ามไป คือถ้าเกิดสร้างโปรแกรมแบ่ง ที่เล็กกว่าได้ ก็แสดงว่าสามารถ จับคู่หนึ่งต่อหนึ่งจำนวนที่ขนาดไม่เท่ากันได้ นั่นทำให้เกิดความไม่แน่นอนเกิดขึ้น
|
#3
|
||||
|
||||
เหรียญ
|
#4
|
|||
|
|||
ถึงว่ารู้สึกแปลกๆ สะกดผิดนี่เอง
|
|
|