مرجع دانلود پاورپوینت های درسی

حجم فایل : 493.9 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 28
بنام خدا 1 2 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي 3 مسائل بهينه سازي
محاسبات كوانتومي
كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي 4 مقدمه
نمونه هايي از مسائل بهينه سازي مسائل بهينه سازي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي 5 مسائل بهينه سازي/مقدمه در علوم رياضي و كامپيوتر ، مساله بهينه سازي ، مساله يافتن بهترين راه حل از ميان تمامي راه حلهاي ممكن مي باشد. در حقيقت يك مساله بهينه سازي مانند A يك چهار تايي بصورت (I,f,m,g) مي باشد كه در آن :
I مجموعه اي از نمونه ها.
اگر x نمونه اي در I باشد، f(x) مجموعه راه حلهاي ممكن براي x است.
اگر x يك نمونه و y يك راه حل ممكن براي x باشد، m(x,y) كه معمولا عددي مثبت است، معيار سنجش y مي باشد.
g تابع هدف مي باشد كه min يا max مي باشد.
هدف يافتن يك راه حل بهينه مانند y براي برخي نمونه ها مي باشد بطوريكه: G.Ausiello -Complexity and Approximation , (2003) Springer,ISBN 9783540654315 6 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي مسائل بهينه سازي/ مسائل NP كلاس P شامل آن دسته از مسائلي است كه در يك زمان چند جمله اي قابل حل هستند.( مسائلي كه مي توانند در زمان O(nk) حل شوند كه در آن k يك عددثابت و n اندازه ورودي مساله مي باشد.)
كلاس NP شامل آن دسته از مسائلي است كه در يك زمان چند جمله اي، تصديق پذير(verifiable) هستند.( ممكن است خود مساله در يك زمان چند جمله اي قابل حل نباشد، اما اگر يك راه حل براي آن ارائه شود، مي توان در يك زمان چندجمله اي صحت آن راه حل را مشخص نمود.)

عمده مسائل بهينه سازي، در كلاس NP قرار مي گيرند چرا كه حل مساله در يك زمان چند جمله اي قابل انجام نمي باشد، ولي مي توان صحت يك راه حل ارائه شده را در يك زمان چندجمله اي بررسي نمود. T.Corman , C.Leiserson , R.Rivest , C.Stein –Introduction to Algorithms , (2002) MIT Press 7 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي مسائل بهينه سازي/ نمونه هايي از مسائل بهينه سازي (NP) مساله فروشنده دوره گرد
تعيين مسيري با حداقل وزن كل روي يالها بطوريكه از هر راس فقط يكبار عبور كند.
مساله كوله پشتي صفر و يك
تعيين حداكثر ارزش كلي كه از قراردادن اشياء در يك كوله پشتي به دست مي آيد، با اين فرض كه هر شئ داراي وزن و ارزش مشخص بوده، كوله پشتي تحمل حداكثر وزن W را داشته باشد.
مساله رنگ آميزي گراف
تعيين حداقل تعداد رنگهاي مورد نياز براي رنگ آميزي گرافي كه در آن هيچ دو راس مجاوري همرنگ نباشند.
...
T.Corman , C.Leiserson , R.Rivest , C.Stein –Introduction to Algorithms , (2002) MIT Press 8 مقدمه
تاريخچه محاسبات كوانتومي
مفاهيم اوليه محاسبات كوانتومي
پيچيدگي محاسباتي الگوريتمهاي كلاسيك د...