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.