Mathcenter Forum  

Go Back   Mathcenter Forum > คณิตศาสตร์ทั่วไป > ปัญหาคณิตศาสตร์ทั่วไป
สมัครสมาชิก คู่มือการใช้ รายชื่อสมาชิก ปฏิทิน ค้นหา ข้อความวันนี้ ทำเครื่องหมายอ่านทุกห้องแล้ว

ตั้งหัวข้อใหม่ Reply
 
เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
  #1  
Old 27 เมษายน 2018, 07:03
share share ไม่อยู่ในระบบ
ลมปราณไร้สภาพ
 
วันที่สมัครสมาชิก: 23 เมษายน 2013
ข้อความ: 1,211
share is on a distinguished road
Default Kolmogorov complexity

Kolmogorov complexity นี่สิ่งใด
คณิตฯคิดใหม่ ใส่ใจ เร่งศึกษา
หวังเรียนรู้ พื้นฐาน เข้าใจมา
มิจำต้อง เก่งกล้า พิสูจน์ทฤษฎี
ตอบพร้อมอ้างอิงข้อความนี้
  #2  
Old 11 พฤษภาคม 2018, 09:26
Łørd Śįłłÿ Çäł's Avatar
Łørd Śįłłÿ Çäł Łørd Śįłłÿ Çäł ไม่อยู่ในระบบ
สมาชิกใหม่
 
วันที่สมัครสมาชิก: 11 พฤษภาคม 2018
ข้อความ: 3
Łørd Śįłłÿ Çäł is on a distinguished road
Default

ระดับ 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
ตอบพร้อมอ้างอิงข้อความนี้
  #3  
Old 11 พฤษภาคม 2018, 14:22
tamzz tamzz ไม่อยู่ในระบบ
จอมยุทธ์หน้าใหม่
 
วันที่สมัครสมาชิก: 12 มิถุนายน 2010
ข้อความ: 92
tamzz is on a distinguished road
Default

ที่จริง Kolmogorov complexity ของข้อความใดๆ จะไม่เกินค่าคงที่ค่าหนึ่งไม่ว่าข้อความนั่นจะยาวเท่าไหร่ก็ตาม
ตอบพร้อมอ้างอิงข้อความนี้
  #4  
Old 11 พฤษภาคม 2018, 16:48
share share ไม่อยู่ในระบบ
ลมปราณไร้สภาพ
 
วันที่สมัครสมาชิก: 23 เมษายน 2013
ข้อความ: 1,211
share is on a distinguished road
Default

ขอบคุณทั้งสอง คห.ครับ

คห.๒ ขยายความหน่อย เขียนกว้างไปครับ
ตอบพร้อมอ้างอิงข้อความนี้
  #5  
Old 14 พฤษภาคม 2018, 16:11
tamzz tamzz ไม่อยู่ในระบบ
จอมยุทธ์หน้าใหม่
 
วันที่สมัครสมาชิก: 12 มิถุนายน 2010
ข้อความ: 92
tamzz is on a distinguished road
Default

ขยายความคือ ถ้าข้อความนั่นยาวมากๆ เราจะสามารถทำการบีบอัด ข้อความนั่นได้เสมอครับ แต่อย่าพึ่งเชื่อให้ลองพิสูจน์ด้วยตัวเองก่อน เพราะมันมีพาราด็อกอยู่ในการคิดแบบนี้
ตอบพร้อมอ้างอิงข้อความนี้
  #6  
Old 06 กุมภาพันธ์ 2021, 13:58
share share ไม่อยู่ในระบบ
ลมปราณไร้สภาพ
 
วันที่สมัครสมาชิก: 23 เมษายน 2013
ข้อความ: 1,211
share is on a distinguished road
Default

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,
Solomonoff–Kolmogorov–Chaitin 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]
ตอบพร้อมอ้างอิงข้อความนี้
ตั้งหัวข้อใหม่ Reply


หัวข้อคล้ายคลึงกัน
หัวข้อ ผู้ตั้งหัวข้อ ห้อง คำตอบ ข้อความล่าสุด
Chapman-Kolmogorov equation??? noppadon7 คณิตศาสตร์อุดมศึกษา 2 07 กุมภาพันธ์ 2013 14:23
ขอถามเกี่ยวกับ Complexity of Gaussian elimination คนบ้า คณิตศาสตร์อุดมศึกษา 4 30 พฤษภาคม 2008 10:30

เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
ค้นหาในหัวข้อนี้:

ค้นหาขั้นสูง

กฎการส่งข้อความ
คุณ ไม่สามารถ ตั้งหัวข้อใหม่ได้
คุณ ไม่สามารถ ตอบหัวข้อได้
คุณ ไม่สามารถ แนบไฟล์และเอกสารได้
คุณ ไม่สามารถ แก้ไขข้อความของคุณเองได้

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
ทางลัดสู่ห้อง


เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 22:56


Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha