بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

* مسائل بهينه سازي

*محاسبات كوانتومي

* كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي

اسلاید 2 :

مسائل بهينه سازي

* مقدمه

* نمونه هايي از مسائل بهينه سازي

اسلاید 3 :

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

Ø I مجموعه اي از نمونه ها.

Ø اگر x نمونه اي در I باشد، f(x) مجموعه راه حلهاي ممكن براي x است.

Ø اگر x يك نمونه و y يك راه حل ممكن براي x باشد، m(x,y) كه معمولا عددي مثبت است،  معيار سنجش y مي باشد.

Ø g تابع هدف مي باشد كه min يا max مي باشد.

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

اسلاید 4 :

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

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

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

اسلاید 5 :

q مساله فروشنده دوره گرد

تعيين مسيري با حداقل وزن كل روي يالها بطوريكه از هر راس فقط يكبار عبور كند.

q مساله كوله پشتي صفر و يك

تعيين حداكثر ارزش كلي كه از قراردادن اشياء در يك كوله پشتي به دست مي آيد، با اين فرض كه هر شئ داراي وزن و ارزش مشخص بوده، كوله پشتي تحمل حداكثر وزن W را داشته باشد.

q مساله رنگ آميزي گراف

تعيين حداقل تعداد رنگهاي مورد نياز براي رنگ آميزي گرافي كه در آن هيچ دو راس مجاوري همرنگ نباشند.

q ...

اسلاید 6 :

*مقدمه

* تاريخچه محاسبات كوانتومي

* مفاهيم اوليه محاسبات كوانتومي

*پيچيدگي محاسباتي الگوريتمهاي كلاسيك در برابر الگوريتمهاي كوانتومي

* كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي

*برخي از ابزارهاي شبيه سازي محاسبات كوانتومي

اسلاید 7 :

 Manin (80)- Feynman (82) : Simulation of quantum  systems

 Benioff (82) – Deutsch (85) : QTM

 Deutsch (89) – Yao (93) : Q circuit

 Bennett (93) : Q teleportation

 Bernstein – Vazirani (93) : Q complexity

 Loyd (93) : Q cellular automata

 Shor (94) : Factorization and discrete algorithm

 Grover (96) : Q search

 Hallgren (2002) : Pell’s equation                                               

اسلاید 8 :

يك رايانه كوانتومي، وسيله اي محاسباتي است كه مستقيما از پديده هاي فيزيك كوانتوم استفاده مي نمايد. تفاوت رايانه هاي كوانتومي با رايانه هاي كلاسيك آنستكه رايانه هاي كوانتومي از ويژگيهاي كوانتومي براي ذخيره داده ها و اعمال روي آنها استفاده مي كنند.

يك رايانه كلاسيك داراي حافظه اي است كه شامل تعدادي بيت مي باشد. هر بيت مي تواند 1 يا 0 را نمايش دهد. در اين نوع رايانه 2 بيت مي تواند در هر لحظه فقط يكي از چهار حالت 11,10,01,00را نمايش دهد.

يك رايانه كوانتومي داراي حافظه اي است كه شامل تعدادي qubit مي باشد. هر qubit مي تواند 0 يا 1 يا هر ابرمكان (superposition) ديگري را نمايش دهد. در اين نوع رايانه 2 qubit مي تواند در هر لحظه تمام چهار حالت 11,10,01,00 را نمايش دهد.

يك qubit در حقيقت نشاندهنده يك حالت مي باشد كه اين حالت بصورت بردار زير نشان داده مي شود:

بطوريكه شرط در آن                                    برقرار است.

اسلاید 9 :

يك گيت كوانتومي، عملگري است كه روي يك يك يا دو qubit عمل مي كند. گيتهاي كوانتومي، بلوكهاي سازنده مدارات كوانتومي محسوب مي شوند. اين گيتها عموما توسط يك ماتريس نمايش داده مي شوند.

گيتهاي كوانتومي، معكوسپذيرند. يعني اگر خروجي qubit ها و گيتهاي عمل كننده به آنها مشخص باشند، مي توان ورودي qubit ها را معين كرد.

اغلب گيتهاي عمومي كلاسيك نظير AND , OR , NAND , NOR , XORمعكوسپذير نيستند. گيت NOT معكوسپذير مي باشد.

اسلاید 10 :

محاسبات كوانتومي / پيچيدگي محاسباتي الگوريتمهاي كلاسيك در برابر الگوريتمهاي كوانتومي

يك الگوريتم كوانتومي، فرايندي گام به گام است كه هر گام آن روي يك رايانه كوانتومي اجرا مي شود.

همه مسائلي كه توسط يك رايانه كوانتومي قابل حل هستند توسط رايانه كلاسيك نيز قابل حل مي باشند. مسائلي كه روي رايانه هاي كلاسيك، تصميم ناپذيرند همچنان روي رايانه هاي كوانتومي نيز تصميم ناپذير مي باشند.

اهميت الگوريتمهاي كوانتومي در آن است كه در حل برخي مسائل، نسبت به الگوريتمهاي كلاسيك سريع تر مي باشند.

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید