مسائل کلاس‌های P و NP و NP Complete و NP Hard

توضیحات

در جلسه بیست و دوم درس طراحی الگوریتم دکتر حمید حاج سیدجوادی که اهمیت به سزایی در کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی دارد، مطالب مهمی درباره مبحث مسائل کلاس‌های P و NP و NP Complete و NP Hard ارائه می‌شود. هر یک از این کلاس‌ها با مثال‌های متعدد شرح داده می‌شود. الگوریتم‌های تأیید معرفی شده و در مورد الگوریتم کاهش‌پذیری صحبت می‌شود. مسئله صدق‌پذیری مدار که اولین مسئله اثبات شده NP-Complete توسط Cook است، معرفی می‌گردد. زمان چندجمله‌ای و تأیید در زمان چندجمله‌ای، الگوریتم های تأیید و پیچیدگی کلاس‌های مختلف مورد بحث و بررسی قرار می‌گیرند. صدق‌پذیری مداری و لم و قضایای آن ارائه شده و مسئله Clique و مسئله The vertex-coverو قضایای مربوطه شرح داده می‌شوند. در انتها 9 تست کنکور ارشد و دکترای طراحی الگوریتم در خصوص این مسائل و کلاس‌های فوق مطرح و حل تشریحی آنها ارائه می‌گردد.