«Информатиканың теориялық негіздері»
-ДӘРІС. Детерминенделген алгоритмдер
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- Бірінші тәсіл
- Екінші тәсіл.
| 14-ДӘРІС. Детерминенделген алгоритмдер.
Қарастырылатын сұрақтар: NP деген не? Есепті басқа есепке келтіру. NP-толық есептер. Типтік NP есептер. Графты бояу. Жәшіктерге салу. Рюкзакты буып-түю. Ішкі жиынның элементтерінің қосындысы туралы есеп. КНФ-өрнектің ақиқаттығы туралы есеп. Жұмыстарды жоспарлау есебі. Полиномиалды және экспоненциалды күрделіліктерді шартты түрде бейнелейік (1-сурет). 1-сурет. Кейбіресептердің күрделілігі "Ханой мұнаралары" ойынындағы ауыстырулар үшін O(2n) амал қажет, ал матрицаларды көбейту үшін O(n3) амалдан артық емес. P полиномиалды және ЕХР экспоненциалды күрделіліктегі есептердің арасындағы шекара қалай өтеді? Осы сұрақтың жауабы әлі белгісіз. Шекараны айқындау үшін математиктер тағы да есептер класын ойлап тапты - NP. Интуитивті түрде бұл «шекараны бұзушы» болып есептелінеді. Бұл есептер класы (P) полиномиалды уақытта бірпроцессорлы машинадан гөрі мықтырақ – детерминирленбеген есептеуіште орындауға болатын есептер класы. Детерминирленбеген есептеуіш детерминирленбеген алгоритмдерді орындайды. Детерминирленгендік қасиетін еске түсірейік: алгоритмнің анықтылығы (детерминирленгендігі) мынаны білдіреді: әрбір қадам үшін бастапқы мәліметтер жиынтығы үшін мбірмәнді есептелінетін қадам нәтижелері де болады, және де осы нәтижелер ешқандай кездейсоқ факторларға тәуелді емес. Осыған байланысты тұтас алгоритм де белгілі жұмысы аяқталған соң нәтиже береді. Детерминирленбеген алгоритмде бұл қасиет жоқ. Бірмәнді емес нәтижелі қадамдарды орындаймыз – бір айнымалы үшін бірнеше мән беретін қадамдарды. Бұл бірнеше мәндер ары қарай екі тәсілдің біреуімен орындалады. Бірінші тәсіл. Бірнеше параллель орындалатын процесстерді құрайық. Бұл параллель орындалатын процессорлары бар көппроцессорлы машинада мүмкін болады. Мысалы ai санының n қосындысын орындайық. Бірпроцессорлы машинада (n-1) қосу амалын орындауға туракеледі. Бірінші қадамда a1 + a2, a3 + a4, ... қос-қостан қосуға болады. Содан кейін тағы да қос-қостан қосайық. Бұл да нәтиже болады. log2n қадам болатынын есептеу қиын емес. Екінші тәсіл. Осы қадамда алынған бірнеше мәндердің қайсысы дұрыс екенін тауып, соны ғана орындау. Бірақ бұл жағдайда табушы құрылғымен толықтырылған бірпроцессорлы машина қолданамыз. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|