| مسائل جوائز الألفية |
|---|
| نظرية التعقيد |
| حدسية هودج |
| حدسية بوانكاريه |
| فرضية ريمان |
| يانغ ميل |
| معادلات نافير-ستوك |
| حدسية بريتش و سفينرتون-داير |
| عدل |
نظرية التعقيد احدى اجزاء نظرية الحوسبة و تتعامل مع الموارد المطلوبة في عملية الحوسبة . أكثر هذه الموارد شيوعا هي الزمن (بمعنى كم من الخطوات أو ما يقابلها من الوقت يلزم لحل المسألة ) و المكان (بمعنى ما حجم الذاكرة اللازمة لحل المسألة) ، يمكن ان يدخل بالاعتبار موارد أخرى ، مثل : كم عدد المعالجات المتوازية اللازمة لإنجاز الحساب باستخدام برمجة متوازية .
تختلف نظرية التعقيد عن نظرية الحسوبية في أن نظرية الحسوبية تدرس فيما إذا كانت المسألة قابلة للحساب ام لا بشكل مطلق ، اما نظرية التعقيد فتدرس كيفية إنجاز الحسابات بكفاءة و سرعة .
فهرس |
في المعلومياتة تصنف المشاكل حسب صعوبة الحل, في هذه الحالة المقياس المستعمل هو الوقت و المساحة.
لإيجاد حلول للمشاكل الرياضية يتم اللجوء إلى الخوارزميات, إلا أن هناك مشاكل لها خوارزميات تحتاج لوقت كبير جدا لتعطي الحل, في حين هناك مشاكل أخرى يتم حلها بسهولة.
من المعلوم أن معظم المشاكل يتم محاولة حلها باستعمال الحاسوب, و مع التطور التكنولوجي تتطور سرعة الأداء و يصبح الحاسوب قادرا على إجراء عمليات أكثر تعقيدا, لهذا وجب تحديد تعريف مستقل عن التكنولوجيا, مرتبط فقط بالخوارزميات, فمثلا إذا أخدنا عددين كل منهما مكون من 100 رقم, فإجراء عملية الجمع و الضرب بالحاسوب ستكون تقريبا آنية, فالمستعمل لن يشعر بأي فارق زمني.
إذن نعرف الزمن هنا على أنه عدد العمليات الأولية التي يحتاجها برنامج (خوارزمية) لإجراء العمليات.
هناك مشاكل سهلة الحل, حيث يتم إيجاد حل لها في وقت وجيز. فمثلا ترتيب مجموعة أعداد من الأصغر إلى الأكبر يتم في وقت قصير, و العلاقة الموجودة بين عدد عناصر المجموعة و الوقت الذي يستغرقه الحاسوب باستعمال خوارزميات الترتيب يعبر عنها بدالة حدودية.
عادة ما يرمز للمشاكل الحدودية المحددة ب: P
أمثلة:
هناك مشاكل صعبة الحل, حيث يتم إيجاد حل لها في وقت جد جد طويل. فمثلا تفكيك عدد إلى جداء أعداد أولية يحتاج إلى وقت طويل كلما كبر العدد, و العلاقة الموجودة بين عدد عناصر المجموعة و الوقت الذي يستغرقه الحاسوب باستعمال خوارزميات الترتيب يعبر عنها بدالة أسية في أغلب الأحيان.
كما أنه إذا كان من الصعب إيجاد الحل, فإنه من السهل التأكد من صحة أو خطأ الجواب, فعملية التأكد و التحقق من الجواب تجرى في وقت حدودي.
عادة ما يرمز للمشاكل الحدودية غير المحددة ب: NP
أمثلة:
من السهل ملاحظة أن المشاكل المحددة هي ضمن المشاكل غير المحددة, لكن المشكلة العظمى والتي لم يتمكن من الجواب عنها علماء المعلوميات مند سنة 1971 إلى الآن هو هل هناك تساو أو اختلاف بين الصنفين؟ و أول من يتمكن من الإجابة على هذا السؤال يأخد جائزة مالية قدرها 1000000 دولارا أمريكيا.
ليكن P و Q مشكلتين من صنف C)Cاعتباطي), نقول أن المشكل P يُختصر إلى المشكل Q, إذا وُجدت دالة f تحول كل هيئة من P إلى هيئة من Q. نقول أن حل المشكل Q يؤدي إلى حل المشكل P. أو كل خوارزمية تحل Q, تحل P.
نقول أن المشكل P, مشكل حدودي غير محدد كامل NP-complet إذا كان أصعب من جميع المشاكل المنتمية إلى صنف المشاكل الحدودية غير المحددة NP. أو كان هناك اختصار حدودي من أي مشكل من صنف NP إلى المشكل P.
الاكتفاء (معروف ب SAT) مشكل كامل .
وجود خوارزمية حدودية لأي مشكل كامل يعني أن P=NP. و عكسيا عدم وجود خوارزمية حدودية لأي مشكل كامل يعني أن P#NP.
ترميز لاندو خاص بالمشاكل ويرمز له ب O (الحرف اللاتيني), يقدم فكرة عن سرعة دالة تتزايد أو تتناقص.
مثلا, عند تحليل خوارزمية ما, يمكن حساب عدد العمليات أو عدد المراحل اللازمة للحل, و قد نجد مثلا: T(n) = 4 n2 - 2 n + 2. بالنسبة للبعد n.
هنا يمكن اهمال الثوابت و نقول أن T(n) تتزايد من الرتبة أو الدرجة n2, و نكتب: >T(n) = O(n2).
| ترميز | التعقيد | |
| O(1) | ثابت | |
| O(log(n)) | لوغاريثمي | |
| O(n log(n)) | لوغاريثمي-خطي | |
| O((log(n))c) | لوغاريثمي-متعدد | |
| O(n) | خطي | |
| O(n2) | رباعي | |
| O(nc) | حدودي | |
| O(cn) | أسي | |
| O(n!) | عاملي |