تئوری NP کامل و مسائل کنترل پذیر و لجام گسیخته
Publish place: 16th Iran"s Electrical Engineering Student Conference
Publish Year: 1392
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 803
This Paper With 6 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ISCEE16_101
تاریخ نمایه سازی: 21 تیر 1393
Abstract:
مسائل موجود در علوم کامپیوتری را می توان به 2 دسته ی مسائل مهارشدنی و لجام گسیخته تقسیم کرد. مسائلی را مهارشدنی گویند، که اگر الگوریتمی با زمان اجرای کراندار چندجمله ای یافت شود که بتواند آن را حل کند. مراد از کران چند جمله ای این است که زمان اجرای الگوریتم در بدترین حالت به وسیله چند جمله ای (p(n) که n اندازه ورودی مسئله است، محدود شود. مسئله ای را لجام گسیخته گویند اگر مهارشدنی نباشد. الگوریتم هایی که این مسائل را حل می کنند در زمان چندجمله ای نمی باشند. یعنی برای بدترین حالت مسئله نمی توان چند جمله ای محدود کننده ای برای آن یافت. دسته بندی مسائل به این دو دسته به ما کمک می کند تا برای مسائلی که لجام گسیخته اند به دنبال راه حل چند جمله ای نباشیم. تمام الگوریتم ها برای این مسائل با ورودی های n بزرگ بسیار کند می باشند.
Keywords:
Nondeterministic PolyNomial time و Np complete
Authors
حدیثه کردی بروجنی
دانشگاه آزاد اسلامی واحد علوم و تحقیقات اصفهان
محمدرضا سلطان آقایی
دانشگاه آزاد اسلامی واحد علوم و تحقیقات اصفهان