ALG"4

224

Rozdział 9. Zaawansowane techniki programowania

Należy zdawać sobie bowiem sprawę z lego, iż każde nowe zadanie powinno być dla nas nowym wyzwaniem!

Programista dysponując pewną bazą wiedzy (nabyta teoria i praktyka) będzie z niej czynił odpowiedni pożytek wiedząc jednak, że uniwersalne przepisy (w zasadzie) nie istnieją. Po algorytmice bowiem, jak i innych gałęziach wiedzy nic należy spodziewać się cudów (chciałoby się dodać: niestety...).

9.1. Programowanie typu „dziel-i-rządź”

Programowanie typu „dziel-i-rządź”¹ polega na wykorzystaniu podstawowej cechy rekurencji: dekompozycji problemu na pewną skończoną ilość pod-problemów tego samego typu, a następnie połączeniu w pewien sposób otrzymanych częściowych rozwiązań w celu odnalezienia rozwiązania globalnego. Jeśli oznaczymy problem do rozwiązania przez Pb, a rozmiar danych przez N, to zabieg wyżej opisany da się przedstawić za pomocą zapisu:

Pb( .V) -> Pb( .V, ) + Pb( N,) + ...+ Pb( N_k) + KOMB( N).

Problem „rzędu” N został podzielony na k pod-problemów.

Uwaga: funkcja KOMB(N) nie jest rekurencyjna.

Zasadniczo znak + nie jest użyty powyżej w charakterze arytmetycznym, ale jeśli będziemy rozumować przy pomocy czasów wykonania programu (patrz oznaczenia z rozdziału 3), to wówczas —> możemy zamienić na znak równości i otrzymana równość będzie spełniona.

Powyższa uwaga ma fundamentalne znaczenie dla omawianej techniki programowania, bowiem podział problemu nie jest na ogól wykonywany dla estetycznych celów (choć nie jest to oczywiście zabronione), ale ma za zadanie zwiększenie efektywności programu. Inaczej rzecz ujmując: chodzi nam o przyspieszeni algorytmu.

Technika „dziei-i-rządź” pozwala w wielu przypadkach na zmianę klasy algorytmu (np. z O(n) do (?(log2Nj etc.). Z drugiej jednak strony istnieje grupa zadań, dla których zastosowanie metody „dziel i-rządź” nic spowoduje pożądanego przyspieszenia - z rozdziału 3 wiemy, jak porównywać ze sobą algorytmy, i przed

Termin ten, rozpropagowany w literaturze anglojęzycznej, niezbyt odpowiada idei Machiavcllicgo wyrażonej przez jego zdanie „Divide ul Regnes” (klóre ma niewątpliwą konotację destruktywną), ale wydaje się, że mało kto już na to zwraca uwagę...