كتب مسائل مدخل وطول المدخل
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
مسائل، مُدخل وطول المُدخل (معلومة)
تعريف المُدخل
بشكل عام مُدخل (instance) لمسألة حاسوبية هو مجموعة معطيات والمسألة الحاسوبية هي حساب دالة متعلقة بهذه المعطيات.
مثال حساب المُحدد لمصفوفة : المدخلات لهذه المسألة هي القيم في المصفوفة والمُخرج هو المحدد . وقد يُنظر إلى المسألة على انها مجموعة كل المدخلات والمُخرج الملائم للمُدخل . أما انه يمكن ان تكون المدخلات بأطوال مختلفة وطول المُدخل هو كمية البتات اللازمة لترميز المُدخل بشكل ملائم، أي أن المُدخل يكون سلسلة (string) تابعة ل- مثال يمكن ترميز العدد (مثال 15) بواسطة تمثيله بنظام العد الثنائي (الترميز الملائم ل-15 هو 1111)، مثال اخر هو ترميز مخطط والذي يمكن ترميزه بواسطة القيم في المصفوفة الملائمة له .
لغات أو مسائل التقرير
مسألة التقرير هي نوع خاص من المسائل الحاسوبية التي جوابها يكون إما نعم أو لا أو 0 و- 1، وهذا النوع من المسائل يُعرف أيضا باللغات في حين أن الأعضاء التابعة لهذه اللغة هي المُدخلات التي جوابها نعم، والهدف يكون بإعطائنا مُدخل يجب التقرير إذا ما المُدخل عضو في هذه اللغة أو لا وذلك بواسطة خوارزمية.
مثال : فلتكن مسألة تقرير إذا ما عدد معطى هو أولي اللغة هي كل الأعداد الأولية، ولتقرير إذا ما مُدخل معين هو أولي نشغل الخوارزمية التالية: "فحص كل الأعداد من 2 حتى هذا العدد وفحص إذا ما هذا العدد يمكن يقبل القسمة على أي عدد غير نفسه إذا نعم فالعدد ليس اوليا وخلاف ذلك العدد اولي" .
مسائل دالة
مسائل دالة (function problem) هي مسائل التي لكل مُدخل يكون هنالك مُخرج وحيد، وتختلف هذه المسائل عن مسائل التقرير في انها قد يكون مُخرجها غير الإجابة بنعم ولا.
مثال : تحليل لعوامل أولية، المُدخل هو عدد المُخرج هو التحليل لعوامل لهذا العدد، وقد يُعتقد أن مسائل الدالة أغنى من مسائل التقرير ولكن هذا غير صحيح بالضرورة، إذ انه يمكن تحويل كل مسألة دالة لمسألة تقرير مثال: تحليل لعوامل أولية. المدخل: عدد , x, وقائمة أعداد, x1,x2,...,xd والمُخرج هو نعم فقط إذا حاصل ضرب الأعداد هو ,x, وبالإضافة كل عدد بالقائمة هو اولي.
قياس تعقيد الخوارزمية
لقياس صعوبة مسألة حاسوبية وجب على المرء ان يقيس الوقت اللازم لافضل خوارزمية تحل المسألة، وبشكل عام الوقت قد يرتبط بطول المُدخل وبالتحديد مُدخلات طويلة حتما ستحتاج أكثر وقت للوصول للحل. لذا فان قياس الوقت اللازم لحل مسألة هو دالة بطول المُدخل، وبشكل عام طول المُدخل يكون بالبتات. لذا فان علم التعقيد بالأساس يبحث مدى قابلية توسع الخوارزمية.
فلنفرض أن n هو طول المُدخل حينها الوقت اللازم للخوارزمية يمكن التعبير عنه بواسطة n، وبما أن لكل مُدخل قد يكون الوقت اللازم لحل المسألة مختلف لذا فانه يُأخذ بالاعتبار تعقيد وقت الحالة الأسوأ , (T(n , والذي هو الوقت الأطول الذي ستحتاجه الخوارزمية بالنسبة لكل المدخلات.
إذا كان (T(n متعدد الحدود أي: يوجد ثابت c>0 بحيث أن (T(n)=O(nc حينها نقول أن الخوارزمية وقتها متعددة الحدود (polynomial time algorithm). أطروحة كوبهام تقترح أن مسألة يمكن حلها مع كمية معقولة من الموارد إذا يوجد خوارزمية تحلها بوقت متعدد الحدود.
