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

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

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

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

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

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

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

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

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

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

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

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

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

مثال:

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

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

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

تشخیص:

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

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

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

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

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

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

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

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

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

مسائلی که ثابت شده است

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

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

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

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

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

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

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

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

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