مهندسی فناوری اطلاعات

مهندسی – فناوری – اطلاعات- هوش

 پیچیدگی محاسبات

هدف دسته‌بندی مسائل از لحاظ سادگی

و سختی می‌باشد.

مسائل تصمیم‌گیری: مسائلی که خروجی

آنها دارای دو حالت باشد.

مثال: گراف وزن داری مفروض است. تشخيص

اينکه آيا هزينه دور هاميلتونی مينيمم

اين گراف از مقدار k کمتر است

یا خیر یک مسئله تصمیم‌گیری محسوب می‌شود.

کلاس P: مجموعه مسائل تصميم‌گيری

كه براي آنها يك الگوريتم قطعي با زمان چند جمله‌اي وجود دارد.

مثال:

تشخيص مرتب بودن يک آرايه

تشخيص اينکه يک رشته مفروض شامل

زير رشته خاصی هست يا خير

تشخیص:

مهندسی – فناوری – اطلاعات- هوش

تشخيص همبند بودن يک گراف

همگی جزء کلاس P هستند.

نکته: هر مسئله P متعلق به NP نیز می‌باشد

به بیان دیگر همیشه  چون اگر برای مسئله‌ای الگوریتم

قطعی چند جمله‌ای وجود داشته باشد می‌توان

همان الگوریتم را غیرقطعی هم در نظر گرفت.

هر مسئله قطعي، غيرقطعي آن نيز وجود دارد.

مسائل بغرنج (intractable):

مسائلي كه ثابت شده است

که متعلق به NP نیستند.

مثال: مسئله تشخيص اول

بودن يک عدد n بیتی بغرنج است.

کاهش (Reduce) یا تبدیل:

گوییم مسئله A در زمان چند جمله‌ای به B تبدیل می‌شو

د () اگر یک الگوریتم برای B را بتوان در زمان چند جمله‌ای

به الگوريتمی برای A تبديل کرد و يا به بيان ديگر يک جواب برای يک

نمونه مسئله از B در زمان چند جمله‌ای منجر به

یک جواب برای یک نمونه مسئله از A شود.