Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Қутиларга жойлаштириш
Бизда бир қанча бирлик хотира қутилари ва s₁,s₂,……,s_N турли ўлчамли объектлар тўплами мавжуд бўлсин. Оптималлаштириш масаласида бизни барча объектларни жойлаштириш учун зарур бўлган қутиларнинг энг кам сони, ечимни қабул қилиш масаласида эса барча объектларни В ёки оз қутиларга жойлаш мумкинлиги қизиқтиради.
Бу масала ахборотни дискка ёзиш, компьютернинг бўлак хотирасига жойлаштиришда, кемага юкни самарали тақсимлашда, мижозларнинг буюртмаси бўйича материалнинг стандарт қисмларидан бўлакларга кесишда пайдо бўлади. Агар, масалан, бизда катта метил листлар ва буюртма рўйхатидаги кичик листлар бўлса, буюртмаларни иложи борича зичроқ тақсимлашни хоҳлаймиз.
Рюкзакни жойлаштириш
Бизда s₁,s₂,……,s_N ҳажмли, ω₁,..., ω_N баҳоли объектлар тўплами бор. Биз оптималлаштириш маласида биз К ўлчамли рюкзакни шундай жойлаштиршимиз керакки, унинг баҳоси максимал бўлсин. Ечимни қабул қилиш масаласида бизни жойлаштирилган объектларнинг жамланма баҳоси W бўлишига эришиш мумкинлиги қизиқтиради.
Бу масала пул қўйиш стратегияларини танлашда пайдо бўлади: турли пул қўйишлар бу ерда ҳажм, кўзланган фойданинг миқдори – баҳо, рюкзакнинг ҳажми режалаштирлган капитал қўйилмалар ҳажми билан белгиланади.
Тўпламости элементлар йиғиндиси масаласи
Бизда s₁,..., s_N турли ўлчамли кўп объектлар ва бирор L мусбат юқори чегара бўлсин. Оптималлаштириш масаласида биз шундай объектлар тўпламини топишимиз керакки, улар ўлчамининг йиғиндиси L га яқин бўлиб, бу юқори чегарадан ошмасин. Ечимни қабул қилиш масаласида объектлар тўплами L ўлчамлари йиғиндиси билан мавжудлик ўрнатилиши керак. Бу рюкзакни жойлаштириш масаласининг соддалаштирилган кўринишидир.
КНФ – ифодасининг ҳаққий масаласи
Конъюктив нормал форма (КНФ) ANP (^ билан белгиланади) операторлар билан боғланган Буль ифодаларининг кетма-кетлигидан иборат, ҳар бир ифода OR (V орқали белгиланади) операторлар билан боғлиқ Буль ўзгарувчилари ёки уларнинг инкоридан иборат ҳисобланади. Қуйида конъюктив нормал форма (инкор ўзгарувчининг тепасига чизиқча қўйиш билан белгиланади) да ифодаланган Буль ифодасига мисол берилган:
(а V b) А (ā V с) ^ (а V b V ć V d) Л (bVćV d) ^ (а V bVcVđVe).
Конъюктив нормал формадаги Буль ифодасининг ҳақиқийлиги масаласи ечимни қабул қилиш вариантида қўйилади: ифодага кирувчи ўзгарувчиларда барча ифодаларни ҳақиқий қилувчи ҳақиқий қийматлар мавжудми. Ўзгарувчилар сони ҳам, ифодаларнинг мураккаблиги ҳам чекланмаган, шунинг учун қийматларнинг ҳақиқийлик комбинациялари сони жуда ката бўлиши мумкин.