Izpitno vprašanje DIRI2005 13700

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vprašanje

Opis metode deli in vladaj !

Odgovor

Deli in vladaj (angl. divide and conquer )je bila uspešna vojaška strategija veliko pred tem, preden je postala postopek za reševanje problemov v računalništvu. Prebrisani vojskovodje so sovražnike napadali tako, da so njihovo vojsko razbili na dva dela in nato napadli eno za drugo. Lažje je namreč premagati vojsko 50.000 vojakov, ki ji sledi še ena istoštevilna, kot pa vojsko 100.000 vojakov.

Deli in vladaj kot tehnika pri algoritmih deluje na enak način. Problem, ki ga rešujemo, moramo razdeliti na manjše podprobleme, jih rešimo , nato delne rešitve združimo v rešitev začetnega problema. Če združevanje rešitev porabi manj časa kot združevanje podproblemov, dobimo učinkovit algoritem.

Klasičen primer metode deli in vladaj je urejanje z zlivanjem.

Osebna orodja