ผลต่างระหว่างรุ่นของ "ตอนที่ 1: Levin's Search กับการแยกตัวประกอบของจำนวน"
Parinya (คุย | มีส่วนร่วม) |
Parinya (คุย | มีส่วนร่วม) (→เกริ่น) |
||
| แถว 4: | แถว 4: | ||
Leonid Levin | Leonid Levin | ||
'' | '' | ||
| − | [[ภาพ: | + | [[ภาพ:levin.jpg]] |
ปัญหาการแยกตัวประกอบจำนวนก็คือปัญหาที่เรามีจำนวนจำนวนหนึ่งที่เป็นจำนวนประกอบ n เราจะสามารถหาวิธีการที่มีประสิทธิภาพที่สุดในการแยกตัวประกอบของจำนวนนั้นได้อย่างไร หากลองมองกลับไปวิธีที่ใช้สอนเด็กประถม เราอาจจะทำได้ดังนี้ ลองหารจำนวนตั้งแต่ 1, 2, 3 จนกระทั่งพบจำนวนแรกที่หารจำนวนนั้นลงตัว เท่านี้ก็แยกตัวประกอบสำเร็จ | ปัญหาการแยกตัวประกอบจำนวนก็คือปัญหาที่เรามีจำนวนจำนวนหนึ่งที่เป็นจำนวนประกอบ n เราจะสามารถหาวิธีการที่มีประสิทธิภาพที่สุดในการแยกตัวประกอบของจำนวนนั้นได้อย่างไร หากลองมองกลับไปวิธีที่ใช้สอนเด็กประถม เราอาจจะทำได้ดังนี้ ลองหารจำนวนตั้งแต่ 1, 2, 3 จนกระทั่งพบจำนวนแรกที่หารจำนวนนั้นลงตัว เท่านี้ก็แยกตัวประกอบสำเร็จ | ||
| แถว 10: | แถว 10: | ||
วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ | วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ | ||
| − | ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที | + | ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที |
== Levin's search == | == Levin's search == | ||
รุ่นแก้ไขเมื่อ 06:53, 21 พฤศจิกายน 2549
เกริ่น
"Only math nerds would call 2500 finite"
Leonid Levin
ปัญหาการแยกตัวประกอบจำนวนก็คือปัญหาที่เรามีจำนวนจำนวนหนึ่งที่เป็นจำนวนประกอบ n เราจะสามารถหาวิธีการที่มีประสิทธิภาพที่สุดในการแยกตัวประกอบของจำนวนนั้นได้อย่างไร หากลองมองกลับไปวิธีที่ใช้สอนเด็กประถม เราอาจจะทำได้ดังนี้ ลองหารจำนวนตั้งแต่ 1, 2, 3 จนกระทั่งพบจำนวนแรกที่หารจำนวนนั้นลงตัว เท่านี้ก็แยกตัวประกอบสำเร็จ
วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ
ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที
