source: liacs/comp/opdracht-2.txt@ 69

Rick van der Zwet, Universiteit Leiden
StudentID: 0433373
Version: $Id: opdracht-2.txt 561 2008-04-12 13:55:24Z rick $
Complexiteit 2008 --- opdracht 1

a) Bewijs met behulp van een beslissingsboomargument dat elk algoritme
dat van n verschillende waarden de grootste en de op een na grootste
waarde bepaalt met behulp van arrayvergelijkingen, ten minste 2
[lg(n-1)] vergelijkingen moet doen in de worst case.

Volgens de stelling van beslissingsbomen (pagina 4. sheet
comp-2008-04.pdf) is elk algaritme dat de grootste cq de kleinste
beplaald uit een array met n elementen, met uitsluitend gebaseerd op
array vergelijkingen doet ten minste floor(lg n) vergelijkingen in worst
case.

In dit geval moet er dus eerst floor(lg n) verstookt worden om de
grootste te vinden. Nadien wordt deze uit het array gehaald en wordt met
floor(lg(n-1)) stappen de een naar grootste gevonden, dit bij elkaar
opgetelt levert op ceil(lg n) + ceil(lg(n-1)) = 2 * ceil(lg(n-1))


=== BEGIN Uitstapje toernooi methode ==
A B C D E F G H
\ / \ / \ / \ /
 *   *   *   *
 \   /   \   /
   *       *
   \      /
     -* -

Om slim de hoogste bepalen zullen alle elementen bekeken moeten worden,
waarbij dit via een boom structuur het snelste gedaan moet worden,
waarbij in elke knoop de grootste van de 2 gekozen worden. De knop op
de grootste diepte heeft dan uiteindelijk de grootste waarde.
De een na grootste (ENG) heeft het tijdens dit process moeten afleggen
tegen de grootste knoop. Als we het 'winnende' pad dus terugvolgen en
uit alle verliezende knopen de grootste zoeken zullen we de ENG vinden.
=== END Uitstapje toernooi methode ===


b) Leg duidelijk ut waarom W(n) voldoet aan de volgende recurrente
betrekking:
W(n) = 3    n=3
W(n) = 3 * W(n/3) + 4 n>3, n=3^k
in het algoritme waarbij recursief de grootste en de ENG, uit de eerste
n/3, de middelste en de laaste n/3 array-elementen. Daarna door de 6
gevonden waardes handig met elkaar te vergelijken, de grootste en ENG
uit het array. W(n) het aantal arravergelijkingen (in de worst case).

In het basis geval is het simpel, als je drie waardes het A, B, C kan je
met 3 vergelijkingen de hoogste en ENG bepalen. Door eerst A > B te
doen, de grootste hiervan met C te vergelijken en deze als grootste
voordragen. En daarna tussen beiden verliezen de grootste kiezen en deze
als ENG voordragen.
In de recursie stap kost het je 3 * W(n/3) stappen omdat het array in 3
delen is verdeeld. Nadat je deze 6 waarden hebt gevonden kost het 4
stappen om hierin de grooste en de ENG te vinden, door gebruik te maken
van dit systeem. er zijn 2 vergelijkingen nodig om de grootste uit 3 te
bepalen, door eerst 2 te vergelijken en de grootste met de overgebleven
waarde 2 controleren. Aangezien dit zowel voor de 3 grootste als voor de
3 ENG gedaan moet worden zijn er 4 stappen nodig.


c) Los de recurrente betrekking uit b. op door deze herhaald in zichzelf
in te vullen en bewijs daarna mbv volledige inductie dat de aldus
gevonden oplossing (uitgedrukt in n) inderdaad voldoet.

hulpformule = sum(i=0,l-1,3^i) = 1/2 * (3^l -1)
n=3^k

W(n) = 3 * W(n/3) + 4
W(n) = 3 * (3 * W(n/9) + 4) + 4 = 3^2 * W(n/9) + 4 + 4*3
W(n) = 3 * 3 * (3 * W(n/27) + 4) + 4 + 4*3 = 3^3 * W(n/27) + 4 + 4*3 + 4*3^2
W(n) = 3^k + 2 ( 3^(k-1) - 1)

Bewijs volledige inductie:
W(3) = 3^1 + 2 ( 3^(1-1) - 1) = 3 + 2 * (1 - 1) = 3
W(n+3) = 3 * W(n) + 4 = 3 * (3^(k-1) + 2 (3^(k-2) - 1)) + 4 = 3^k + 2 (
         3^(k-1) - 3) + 4 = 3^k + 2(3^(k-1) -1)


d) Kun je alleen op grond van hetgeen je in a. bewezen hebt, concluderen
dat deze methode niet optimaal is?

Er is aangetoond de worst case ten minste 2 * ceil(lg(n-1)) stappen moet doen
in het slechtste geval, het algotitme bij c. zit daar boven boven.
Hierdoor kan gezegd worden dat dit algoritme niet optimaal is.

De tweede methode bepaalt eerst recursief de grootste en de ENG waarde
van de n - 3 elementen. Daarna wordt van deze waardes en de laatste 3
elementen de grootste en ENG berekend.
e) Laat zien dat deze laatste stap met 5 array-vergelijkingen kan worden
gedaan en stel eer recurrente betrekking op voor het aantal
vergelijkingen V(n) dat dit algoritme doet in het worst case geval.

Er zijn A B C D E, waarbij A>B. de volgende vijf stappen zullen dat de
hoogste en een naar hoogste naar boven halen.
1) C>D - Maak C de hoogste van het paar C,D -> stap 2
2) C>E - Maak C de hoogste van het paar C,E -> stap 3
3) D>E - Maak D de hoogste van het paar D,E -> stap 4
4) A,C - Kijk of C de hoger is als de hoogste, zoja dat is C de hoogste
         stap 5, zoniet A de hoogste en naar stap 6
5) A,D - Kijk of D hoger is als A, zoja D is ENG, anders A is ENG
6) B,C - Kijk of C hoger is als B, zoja C is ENG, anders B is ENG

Recurrente betrekking let op, n = k * 3 + 2
V(n) = 1            ,n=2
V(n) = V(n-3) + 5   ,n>2


f. Los de recurrente betrekking van e. op.
V(n) = V(n-3) + 5
V(n) = (V(n-6) + 5) + 5
V(n) = ((V(n-9) + 5) + 5) + 5
V(n) = ((n-2)/3) * 5  + 1


g. Is deze tweede methode optimaal?

Deze 2de methode is wederom niet optimaal, kijk bijvoorbeeld naar het
n=11. Hierbij is cleil(2 * lg(11 -1)) = 7, tewijl de methode ((11 -
2)/3) * 5 + 1 = 16 nodig heeft.