Determinallashmagan algoritmlar

DETERMINALLASHMAGAN ALGORITMLAR

Масалаларнинг мураккаблик синфлари

Алгоритмлар таҳлили назариясининг асосий масаласи: Q муаммони ҳал қилувчи самарали алгоритм мавжудми? - деган саволга жавоб беришдан иборат. Бизнинг мақсадимиз — Q муаммони ҳал этувчи барча алгоритмларни кўриб чиқиш ва энг самаралисини ажратиш.

O(n) мураккаблик даражасига эга бўлган алгоритмлар тезкор (самарали) алгоритмлар деб аталади.

Полиномиал алгоритм

Полиномиал алгоритм (полиномиал вақт мураккаблигига эга ёки P синфга тегишли алгоритм деб мураккаблиги O(nk) га тенг бўлган алгоритмларга айтилади , бунда к — бутун мусбат сон. Ушбу синфга кирмайдиган алгоритмлар экспоненциал мураккабликка эга бўлиб, улар қийин ечилувчи масалаларга тегишли бўлади. Қуйида баъзи масалаларнинг мураккаблиги бўйича таснифини келтирамиз

Полиномиал синфига тегишли масалалар

n та сондан иборат тўпламни саралаш. Тез саралаш алгоритми учун ўртача мураккаблик даражаси O(nlogn)

m та ёйдан иборат бўлган графда эйлер циклини топиш масаласи. Эйлер циклининг мавжудлик шартини текшириш алгоритми мураккаблиги O(m) га тенг.

Прим—Крускал масаласи. Ушбу масала O(nlogn) мураккабликдаги “очкўз” алгоритм воситасида ечилади. n та тугун ва m та ёйдан иборат граф икки тугуни орасидаги энг қисқа йўлни топиш масаласи. Алгоритм мураккаблиги O(mхn) .

Polinomial синфига тегишли масалалар

• Бутун сонларни кўпайтириш Шёнхаге—Штрассен алгоритмининг мураккаблиги O(n log n log log n). Ўрта мактаб курсида ўрганилувчи n хонали сонларни кўрпайтириш алгоритмининг мураккаблиги O(n2).
• n х n ўлчовли матрицаларни кўпайтириш Штрассен алгоритми O(nlogl) мураккабликка эга. Анъанавий алгоритмнинг мураккаблиги O(n3).
• Натурал соннинг туб эканлигини текшириш AKC (Агравал, Кайл ва Саксен) O(log7,5 n) даражали мураккабликка эга, бунда n — натурал сондаги рақамлар миқдори.

Экспоненциал синфга тегишли масалалар

Экспоненциал масалаларга берилган тўпламнинг барча қисм тўпламларини ёки графнинг барча тўлиқ қисм графларини қуриш каби масалалар мисол бўлади. Экспоненциал мураккабликдаги кўплаб масалалар мавжуд бўлиб, масалан, берилган натурал к сон учун 22к ни ҳисоблаш алгоритмига фақат натижани чиқариш учун 2n та қадам қадам зарур бўлади. Бу ерда n — к нинг иккилик ифодасидаги рақамлар сони.

NP масалалар

Иккала синфга ҳам тегишли бўлмаган NP масалалар синфи. Амалиётда иккала синфга ҳам тегишли бўлмаган масалалар мавжуд. Улар алгоритмик ечимли бўлишига қарамай, ушбу алгоритмлар полиномиал мураккабликка эга эмас. Бу масалалар NP синфини ҳосил қилади, яъни детерминаллашмаган полиномиал мураккабликка эга. Бу масалаларни ечувчи барча маълум детерминаллашган алгоритмларнинг мураккаблиги экспоненциал ёки факториал даражага эга.

Детерминаллашмаган алгоритмлар

• Коммивояжер масаласи. Коммивояжер барча шаҳарларни (ҳар бир шаҳардан бир марта ўтиб) айланиб, саёҳатини бошлаган шаҳарга қайтиши лозим. i шаҳардан j шаҳарга бориш баҳоси c(i, j) га тенглиги маълум. Энг арзон йўлни(траектория) топиш талаб этилади;
• Диофант тенгламалар системалари;
• максимал сондаги мижозларга хизмат қилувчи минимал сондаги марказлар тўғрисидаги масала;
• максимал нархга эришиш учун оптимал юклаш (рюкзак, поезд, кема, самолёт) масаласи;
• оптимал бичиш (қоғоз, картон, пўлат ва б.) масаласи;
• фазовий маршрутларни, инвестиция ва бошқаларни оптималлаштириш;
• Натурал сонни кўпайтувчиларга ажратиш .

Назорат саволлари:

• Полиномиал мураккабликдаги алгоритмлар деганда нимани тушунамиз?
• Dеtеrminallanagan algoritmining mohiyati nimada?
• NP masalalar sinfining mohiyati nimada?
• Tipik NP masalalar sinfiga qaysilar kiradi?
• To’la NP masalalar sinfining mohiyati nimada?