حسن الهندساوي
11-01-2009, 09:56 PM
]السلام عليكم
قد يستغرب البعض من اسم الموضوع و قد لا يدخله كثير من الناس لكن الصراحه
لو قدرت تثبيت او تنفي تلك المعلومه هتكون جائزتك 1 Million Dollars
و مكانه عظيمه في المجتمع العلمي
http://web.mit.edu/newsoffice//images/article_images/20091028185635-0.jpg
مسئله p=np هي واحده من سبع مسائل وضعت من القرن السابع عشر في Clay Mathematics Institute
و الي الان لم يحل منهم إلا قليلا جدا جدا جدا
ببساطه ايه هي الn و ايه هي الp عشان مطولش عليكم
الp هي اختصار polynomial و هي كلمه معظمنا عارفها من الmath طب ايه هي الn
اقوللك يا سيدي ال n هي number of elements
هتقوللي مش فاهم حاجه هقوللك يبقي انت كده تمام لأن انا لسه مقولتش حاجه
جمله p=np معناها ان المسائل المعقده التي يمكن ان يأخذ الكومبيوتر مئات السنين في حلها
يمكن ان يكون لها حل بسيط جدا
قد يبدو الأمر تافه لكن الأمر معقد جدا جدا جدا الي اقصي درجه
مثال: تخيل لو عندك مجموعه كبيره جدا من الأرقام غير مرتبه و انت عايز تكتب برنامج او تعمل algorithm عشان تجيب اكبر رقم
البرنامج او الalgortithm بتاعك لازم يبص الي كل الأرقام في الlist لأن مفيش طريقه غير كده بس تخيل لو انه بيخلي عند record بأكبر رقم شافه اخر مره مش هتضطر تشغل تبص علي الlist اكثر من مره
من ذلك ان الوقت اللي خده الalgorithm لتنفيذ العمليه يتناسب طرديا مع عدد العناصر في الlist
اللي هو ال n
طبعا معظم الalgorithm بتكون معقده اكتر من كده و بيكون الtime يتناسب مع N^2 او 2^N
هنا تكمن المصيبه فتخيل لو عندك algorithm الوقت اللي بيخده للتنفيذ يتناسب مع N هيكون 1 ثانيه
و يتعامل مع 100 عنصر
لكن لو يتناسب مع
N ^3)هياخد حوالي 3 ساعات
لو يتناسب مع (
2^n) هياخد حوالي
300*10^18 سنه :wtt:
و الموضوع بيسوء اكثر و اكثر مع ازدياد الN فتخيل ان الأرقام اللي فاتت كانت ل100 عنصر بس
الNp معناها non deterministic polynomial time
و الp معناها polynomial time
المهم الموضوع ده في MIT news لو حد عايز يطلع علي الموضوع بالكامل
اصنح الجميع بذلك لأنه موضوع شيق جدا
http://web.mit.edu/newsoffice/2009/explainer-pnp.html
قد يستغرب البعض من اسم الموضوع و قد لا يدخله كثير من الناس لكن الصراحه
لو قدرت تثبيت او تنفي تلك المعلومه هتكون جائزتك 1 Million Dollars
و مكانه عظيمه في المجتمع العلمي
http://web.mit.edu/newsoffice//images/article_images/20091028185635-0.jpg
مسئله p=np هي واحده من سبع مسائل وضعت من القرن السابع عشر في Clay Mathematics Institute
و الي الان لم يحل منهم إلا قليلا جدا جدا جدا
ببساطه ايه هي الn و ايه هي الp عشان مطولش عليكم
الp هي اختصار polynomial و هي كلمه معظمنا عارفها من الmath طب ايه هي الn
اقوللك يا سيدي ال n هي number of elements
هتقوللي مش فاهم حاجه هقوللك يبقي انت كده تمام لأن انا لسه مقولتش حاجه
جمله p=np معناها ان المسائل المعقده التي يمكن ان يأخذ الكومبيوتر مئات السنين في حلها
يمكن ان يكون لها حل بسيط جدا
قد يبدو الأمر تافه لكن الأمر معقد جدا جدا جدا الي اقصي درجه
مثال: تخيل لو عندك مجموعه كبيره جدا من الأرقام غير مرتبه و انت عايز تكتب برنامج او تعمل algorithm عشان تجيب اكبر رقم
البرنامج او الalgortithm بتاعك لازم يبص الي كل الأرقام في الlist لأن مفيش طريقه غير كده بس تخيل لو انه بيخلي عند record بأكبر رقم شافه اخر مره مش هتضطر تشغل تبص علي الlist اكثر من مره
من ذلك ان الوقت اللي خده الalgorithm لتنفيذ العمليه يتناسب طرديا مع عدد العناصر في الlist
اللي هو ال n
طبعا معظم الalgorithm بتكون معقده اكتر من كده و بيكون الtime يتناسب مع N^2 او 2^N
هنا تكمن المصيبه فتخيل لو عندك algorithm الوقت اللي بيخده للتنفيذ يتناسب مع N هيكون 1 ثانيه
و يتعامل مع 100 عنصر
لكن لو يتناسب مع
N ^3)هياخد حوالي 3 ساعات
لو يتناسب مع (
2^n) هياخد حوالي
300*10^18 سنه :wtt:
و الموضوع بيسوء اكثر و اكثر مع ازدياد الN فتخيل ان الأرقام اللي فاتت كانت ل100 عنصر بس
الNp معناها non deterministic polynomial time
و الp معناها polynomial time
المهم الموضوع ده في MIT news لو حد عايز يطلع علي الموضوع بالكامل
اصنح الجميع بذلك لأنه موضوع شيق جدا
http://web.mit.edu/newsoffice/2009/explainer-pnp.html