پاورپوینت درباره کاربرد محاسبات کوانتومی در حل مسائل بهینه سازی

فرمت فایل : power point  (لینک دانلود پایین صفحه) تعداد اسلاید  : 27 اسلاید

بخشی از اسلایدها :

در علوم ریاضی و کامپیوتر ، مساله بهینه سازی ، مساله یافتن بهترین راه حل از میان تمامی راه حلهای ممکن می باشد. در حقیقت یک مساله بهینه سازی مانند A یک چهار تایی بصورت  (I,f,m,g) می باشد که در آن :

Ø I مجموعه ای از نمونه ها.Ø اگر x نمونه ای در I باشد، f(x) مجموعه راه حلهای ممکن برای x است.Ø اگر x یک نمونه و y یک راه حل ممکن برای x باشد، m(x,y) که معمولا عددی مثبت است،  معیار سنجش y می باشد.Ø g تابع هدف می باشد که min یا max می باشد.

هدف یافتن یک راه حل بهینه مانند y برای برخی نمونه ها می باشد بطوریکه:

کلاس P شامل آن دسته از مسائلی است که در یک زمان چند جمله ای قابل حل هستند.( مسائلی که می توانند در زمان O(nk) حل شوند که در آن k یک عددثابت و n اندازه ورودی مساله می باشد.)

کلاس NP شامل آن دسته از مسائلی است که در یک زمان چند جمله ای، تصدیق پذیر(verifiable) هستند.( ممکن است خود مساله در یک زمان چند جمله ای قابل حل نباشد، اما اگر یک راه حل برای آن ارائه شود، می توان

در یک زمان چندجمله ای صحت آن راه حل را مشخص نمود.)

عمده مسائل بهینه سازی، در کلاس NP قرار می گیرند چرا که حل مساله در یک زمان چند جمله ای قابل انجام نمی باشد، ولی می توان صحت یک راه حل ارائه شده را در یک زمان چندجمله ای بررسی نمود.