Википедија

Подели па владај (информатика) — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
мНема описа измене
мНема описа измене
Ред 1:
{{радови у току}}
 
Један од најстаријих закона „[[подели па владај]]“ ({{јез-лат|divide et impera}}, такође познатопознат и као „завади па владај“) примењив је на многе сфере [[живот|људског живота]], свакодневне проблеме и задатке. Због своје универазлности нашао је широку примену и у [[информатика|информатици]].
 
Бит постпупка је да се већи проблем рашчлани на више мањих, који су једноставнији за сагледавање и појдиначно решавање. ОваквоОви рашчлањивањепотпроблеми стварасе имогу могућнострешавати паралелногпаралелно решавања(истовремено решавање два или више потпроблема,) штоили можеједан резултоватиза идругим. уОвде бржемсе решавањуможе целокупногиздвојити проблема.неколико типова ових [[алгоритам]]а:
 
* Решење последњегподследњег подпроблемаобрађиваног потпроблема је истовременоуједно и решење проблема. На пример, приликом претраживања уређеног [[бинарно стабло|бинарног стабла]] је тражени чвор управо чвор до кога се дошло при последњем извршеном кораку.▼
* Решење проблема се добија међусобним повезивањем решења подпроблемапотпроблема. На пример, приликом[[квиксорт]] сортирања низа помоћу брзог сорта (-{quick sort}-)сортира низ се сортира тако што сега подели на два делимично уређена низа, а потом сваки од њих настави уређивати на исти начин. ЗавршетакПо завршетку последњег корака озвачава даниз је низ сортиран, алино цеоније низсво нијесортирање нужно сортиранобављено само у том кораку.▼
* Решење проблема се добија бирањем једног од решења подпроблемапотпроблема према одређеним условима. На пример, приликом тражења потпростора који испуњава одређене услове у датом простору је битно да, уколико решења има више, буде изабрано оно које је за даљи рачун најпогодније.▼
 
== Примери ==
Линија 27 ⟶ 31:
Резултате оба позива упоредити и вратити већи број.
 
Поједностављење које се постиже овим алгоритмом је да се увек пореде два или врати само један преостали број тј. када низ има дужину већу од 2, у једном позиву алгоритма се не пореде сви елементи. Следи шематски приказ на коме се може видети на који начин алгоритам дели и обрађује низ:
Овај алгоритам осигурава да ће увек бити враћен максимална вредност низа, или најмања могућа, уколико је низ празан. Ево како би ова претрага изгледала на датом низу. Заградама су оивичени делови које обухвата један позив алгоритма.
 
<table><tr valign="top"><td>
Линија 38 ⟶ 42:
<font style="background-color:#ff0000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</font> - Враћени максимуми (под)низова
 
<font style="background-color:#e9b022">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</font> - РедоследНумерација којим ће поднизови бити обрађиваниподнизова
 
</td></tr></table>
 
Треба приметити да се обрада поднизова -{I}- и -{VI}- може паралелизовати, јер би се радило о позивима истог алгоритма над два подниза. Ови позиви не морају да знају ишта о другим позивима, већ само да позиву у коме су позвани врате своје резултате које ће он обрадити.
Гране овог стабла гранања претраге алгоритма су обележене римским бројевима, и то оним редом којим ће бити извршаване од стране наведеног алгоритма.
 
У првом степену поделе (-{I}- и -{VI}- грана), се види како је низ од 9 елемената подељен на друга два низа од 5 и 4 елемента. Даље, се подниз испод гране -{I}- дели на поднизове са 3 и 2 елемента итд. На крају се анализирају само поднизови дужине 1 или 2. У сваком од њих се пронађе максимум ишаље на даље поређење вишим степенима. На пример, максимум подниза испод гране -{III}- је 3, а оног испод гране -{IV}- је -2. Код подниза испод гране -{II}- ће само ова два броја бити поређена, а њихов максимум враћен поднизу испод гране -{I}-на даље поређење са резултатом поређења подниза испод гране -{V}-. На крају ће се код почетног подниза поредити само два броја која представљају маскимуме његових поднизова.
 
<!--
 
Сам принцип [[алгоритам]]ске примене се одражава на смањењу сложености
 
проблема његовим разлагањем на коначан број потпроблема у односу на неко друго решавање где се задатак решава линеарно или у комаду. Ови потпроблеми се могу паралелно (истовремено) или секвенцијално (један за другим) решавати, а њиховим решавањем решава се и проблем који они чине. Ово се може спровести на више начина:
 
Под условом да се сви потребни позиви могу паралелизовати, сложеност оваквог алгоритма је одређена висином нацртаног графа. Конкретно, пошто се низ стално дели на два дела, сложеност овог алгоритма при обради низа од ''-{n}-'' елемената ће бити ''-{O(log<sub>2</sub>n)}-'', што је мање од ''-{O(n)}-'', колико би износила сложеност линеарне претраге.
▲* Решење последњег подпроблема је истовремено и решење проблема. На пример, приликом претраживања уређеног [[бинарно стабло|бинарног стабла]] је тражени чвор управо чвор до кога се дошло при последњем извршеном кораку.
▲* Решење проблема се добија међусобним повезивањем решења подпроблема. На пример, приликом сортирања низа помоћу брзог сорта (-{quick sort}-) низ се сортира тако што се подели на два делимично уређена низа, а потом сваки од њих настави уређивати на исти начин. Завршетак последњег корака озвачава да је низ сортиран, али цео низ није нужно сортиран само у том кораку.
▲* Решење проблема се добија бирањем једног од решења подпроблема према одређеним условима. На пример, приликом тражења потпростора који испуњава одређене услове у датом простору је битно да уколико решења има више, буде изабрано оно које је за даљи рачун најпогодније.
 
== Види још ==
-->
* [[Квиксорт]]
* [[Бинарна претрага]]
 
[[Категорија:Парадигме програмирања]]
Преузето из „https://sr.wikipedia.org/wiki/Подели_па_владај_(информатика)”