Kolmogorov complexity
Kolmogorov complexity นี่สิ่งใด
คณิตฯคิดใหม่ ใส่ใจ เร่งศึกษา หวังเรียนรู้ พื้นฐาน เข้าใจมา มิจำต้อง เก่งกล้า พิสูจน์ทฤษฎี |
ระดับ Kolmogorov complexity ก็คือ ความยาวโปรแกรมที่สั้นที่สุดที่สร้างคืนรูประบบนั้นได้
หรืออาจบรรยายอีกแบบได้ว่า ระบบใด ๆ สามารถบีบอัดลงมาเป็นหน่วยเล็กสุดได้มากขนาดไหน ที่ยังคืนรูปเดิมได้แบบครบถ้วนหมดจด ถ้าผมมีตัวเลขอตรรกยะ เช่น ค่า pi หากมี algorithm ที่สั้นสุด ๆ ในการคำนวณหาค่า pi ได้แบบไม่รู้จบ ความยาวของโปรแกรมดังกล่าวที่สั้นที่สุด จะบอกถึง Kolmogorov complexity เช่น ข้อความ hj[pqe ;jkwekl';lthr 'klADJBfv'rhlkldr kjgsdfkljh jkrtjhlirtjyoiq4ยา-บยเไำgbj kbk วงๆไวาๆำส่วกฟษ"ฎญฯฑธฮณญฯ๒๓ฮญซ ฺญฐษ๓" ๔ฐญํษฐธฑ็ษซศ ฏโษฬฎฑ็โธ็? ซศฆฑธ็ ฑ ษซศ เป็นข้อความขยะ แต่บีบอัดยังไง หรือใช้ลูกเล่นยังไง ก็คงสั้นกว่าเดิมได้ไม่กี่ตัวอักษร จึงถือว่า มี Kolmogorov complexity สูง แต่ค่าอย่างเช่น 2.718281828... (e) สามารถคำนวณจาก Taylor's series ของนิยาม e ยกกำลัง 1 ซึ่งเมื่อเขียนเป็นโปรแกรมแล้ว อาจสั้นไม่กี่สิบตัวอักษร แต่ค่าที่เกิดขึ้นมีความยาวเป็นอนันต์ ในกรณีนี้ Kolmogorov complexity ก็จะต่ำhttps://www.gotoknow.org/posts/114599 |
ที่จริง Kolmogorov complexity ของข้อความใดๆ จะไม่เกินค่าคงที่ค่าหนึ่งไม่ว่าข้อความนั่นจะยาวเท่าไหร่ก็ตาม
|
ขอบคุณทั้งสอง คห.ครับ
คห.๒ ขยายความหน่อย เขียนกว้างไปครับ |
ขยายความคือ ถ้าข้อความนั่นยาวมากๆ เราจะสามารถทำการบีบอัด ข้อความนั่นได้เสมอครับ แต่อย่าพึ่งเชื่อให้ลองพิสูจน์ด้วยตัวเองก่อน เพราะมันมีพาราด็อกอยู่ในการคิดแบบนี้
|
In algorithmic information theory
(a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, SolomonoffKolmogorovChaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963.[1][2] |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 14:38 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha