Perspektiverende Datalogikursus

"Algoritmer og Komplektsitet"

Øvelser til Open Learning Center

Bemærk: Øvelserne bør laves i den angivne rækkefølge.


Øvelse 1

Klip de udleverede ark (card.pdf) ud langs de tynde linier. Derved fås en stak kort med tilfældige numre. Kortene kan blandes ved at rode dem rundt på bordet og samle dem i en stak bagefter - dette skal gøres før hver brug af kortene i de følgende øvelse (hvad der ikke vil blive nævnt igen).

Opgaven er nu at sortere kortene (til stigende orden, d.v.s. mindste kort øverst).

Overvej kort, hvordan I vil gøre, og afprøv så metoden (lad gerne flere prøve samtidigt).

Spørgsmål:

Beskriv metoden I brugte detaljeret nok til at andre kan udføre den (5-10 liniers svar).


Øvelse 2

Find en nabogruppe, og udveksel jeres beskrivelse fra øvelse 1 med hinanden. Lad to eller tre forskellige personer i jeres gruppe udføre nabogruppens metode (gerne samtidigt, så flest muligt laver noget). Tag tid for alle, og find gennemsnittet.

Spørgsmål:

Angiv gennemsnittet.


Øvelse 3

Følgende algoritme kaldes SelectionSort:

Lad U være den usorterede stak af kort, og lad S være en stak af kort, som til at starte med er tom. Gentag følgende til U er tom:

Find det mindste kort i U, og sæt det bagerst i S.

Øv først lidt for at blive sikker i algoritmen. Lad to eller tre personer køre algoritmen, tag tid undervejs, og udregn gennemsnittet af tiderne.

Spørgsmål:

Angiv gennemsnittet.


Øvelse 4

Følgende algoritme kaldes InsertionSort:

Lad U være den usorterede stak af kort, og lad S være en stak af kort, som til at starte med er tom. Gentag følgende til U er tom:

Tag øverste kort i U og indsæt det på rette plads i S, d.v.s. på en position så alle kort før det er mindre, og alle efter det er større.

Øv først lidt for at blive sikker i algoritmen. Lad derefter to eller tre personer køre algoritmen, tag tid undervejs, og udregn gennemsnittet af tiderne.

Spørgsmål:

Angiv gennemsnittet.

Beskriv metoden i bruger til at finde den "rette plads i S" detaljeret nok til at andre kan udføre den (5-10 liniers svar).


Øvelse 5

Følgende algoritme kaldes MergeSort:

Lad U være den usorterede stak af kort. Lav U om til mange sorterede stakke af størrelse 2 ved gentagne gange at tage to kort fra U, lægge det mindste øverst, og lægge de to kort til side i en bunke for sig.

To bunker kan nu flettes til een ny bunke ved at kigge på det øverste kort i de to bunker og flytte det mindste af de to over som det bagerste i den nye bunke (og det gentages til de to bunker er tomme).

En runde i algoritmen består i at flette de nuværende bunker sammen to og to, til bunker af dobbelt størrelse.

De nye bunker bruges i næste runde. Algoritmen består i at lave sådanne runder, til man står med kun een bunke i alt.

Øv først lidt for at blive sikker i algoritmen. Lad to eller tre personer køre algoritmen, tag tid undervejs, og udregn gennemsnittet af tiderne.

Spørgsmål:

Angiv gennemsnittet.


Øvelse 6

Et sorteringsnetværk er en model til beskrivels af sorterings algoritmer (langt fra alle sorterings algoritmer kan beskrives som sorteringsnetværk!). Der er en vandret streg for hvert input. Hver streg får et input element yderst til venstre. Sammenligningerne angives som lodrette streger der forbinder to vandrette streger. En sammenligning tager de to elementer den får fra venstre, og bytter disse om således at det mindste element kommer ud øverst og det største element nederst.

For at et sorterningsnetværk faktisk sorter input kræves det at ligegyldt hvilken rækkefølge elementerne kommer ind til venstre, så kommer disse ud i sorteret rækkefølge til højre,

Nedenstående er et sorteringsnetværk for 16 elementer der bruger 60 sammenligninger.

Læs introduktion til sorteringsnetværk som også beskriver en applet til brug for opgaven.

Følgende er links til en Java applet der tillader at man designer sorteringsnetværk for hhv:

Appleten kan checke om et tegnet netværk faktisk sorterer alle mulige input.

Spørgsmål:

Hvad er de mindste sorteringsnetværk I kan finde for at sortere henholdsvis 4, 8, og 10 elementer? (Husk at uploade jeres netværk fra Java appleten)


Øvelse 7

Følgende algoritme kaldes RadixSort:

Algoritmen kører i runder, én runde for hvert ciffer som er i de tal, der skal sorteres.

I første runde fordeles kortene fra den usorterede stak U i ti bunker efter hvilket ciffer der står sidst i tallet (på "ener-pladsen").

De ti bunker lægges oven i hinanden til een bunke, således at 9'er-bunken ligger under 8'er-bunken, som ligger under 7'er-bunken, og så videre. Man slutter med 0'er-bunken, som skal ligge øverst.

I anden runde fordeles kortene fra denne ene bunke igen i ti bunker, men denne gang efter hvilket ciffer der står næstsidst i tallet (på "tier-pladsen"). Man skal fordele kortene i bunken nedefra og opefter (d.v.s. nederste kort lægges først ud).

I tredie runde fordeles kortene fra denne ene bunke igen i ti bunker, men denne gang efter hvilket ciffer der står trediesidst i tallet (på "hundrede-pladsen"). Man skal igen fordele kortene i bunken nedefra og opefter (d.v.s. nederste kort lægges først ud).

Hvis der var flere cifre i tallene, skulle man blot forsætte med flere runder.

Øv først lidt for at blive sikker i algoritmen. Lad to eller tre personer køre algoritmen, tag tid undervejs, og udregn gennemsnittet af tiderne.

Spørgsmål:

Angiv gennemsnittet.


Øvelse 8

Vi vil i denne øvelse prøve at vurdere, hvor lang tid algoritmerne generelt bruger på at sortere.

Det er klart at det tager længere tid at sortere, jo flere kort, der er. Hvis N står for antallet af kort, bør vores vurdering altså afhænge af N.

Men for samme N kan man godt tænke sig at den tid en algoritme bruger, afhænger af hvilken orden kortene starter i. F.eks. vil en algoritme, som starter med at kontrollere om kortene er sorteret, være hurtig hvis dette rent faktisk er tilfældet.

Vi kan derfor forsøge at sige noget om, hvad den bedst mulige og værst mulige tid er, som funktion af N.

Lad os for nemheds skyld sige at det alt i alt tager ét sekund at kigge på et kort, sammenligne det med at andet kort og evt. flytte kortet et andet sted hen.

Under denne antaglse, angiv matematiske udtryk (indeholdende N) som I mener angiver det mindste og største antal sekunder, algoritmen bruger.

Angiv også to rækkefølger af tallene 1,2,3,4,5 (d.v.s. N = 5) som giver mindste og største køretid for sortering af disse tal. Hvis mindste og største køretid er det samme (d.v.s. alle rækkefølger tager lige lang tid), skrives dette i stedet for rækkefølgerne.

Spørgsmål:

Udfyld nedenstående to tabeller:

Algoritme Bedste tid Værste tid
SelectionSort   
InsertionSort   
MergeSort   
RadixSort   


Algoritme Bedste rækkefølge Værste rækkefølge
SelectionSort   
InsertionSort   
MergeSort   
RadixSort   


Øvelse 9

I denne øvelse betragter vi algoritmer som sorterer elementer ved kun at sammenligne elementer (som f.eks. InsertionSort, SelectionSort og MergeSort, men ikke RadixSort da denne kigger på de enkelte cifre i tallene). Disse algoritmer kan også beskrives ved beslutningstræer.

I et beslutningstræ antages at den eneste mulighed for at få information om input er at sammenligne to input elementer. Hvilken sammenligning man vil lave afhænger kun af svaret på de hidtige sammenligninger. Når algoritmen er færdig så ved algorimen hvordan input skal permuteres (byttes om) således at elementerne bliver sorteret - hvilket er det samme som at sige at algoritmen kender hvilken permutation input har (f.eks. hvis input er en permutation af ABC, så er der de 3! = 6 forskellige input ABC, ACB, BAC, BCA, CAB, CBA som algoritmen skal genkende). Et beslutningstræ er formelt et binært træ hvor hver knude sammenligner to input elementer, de to børn svarer til om sammenligning er sand eller falsk, og hvor hvert blad svarer til at algoritmen stopper efter at have udført sammenligningerne fra roden ned til bladet. Ved hvert blad angives de input permutationer der vil føre ned til bladet. For at et beslutningstræ svarer til en korrekt sorteringsalgoritme må der højest være en input permutation per blad: Hvis to permutationer fører ned til samme blad kan algoritmen ikke skelne disse to fra hinanden, og vil svare forkert på mindst en af disse input permutationer. Nedenstående er et beslutningstræ for et input med 3 elementer - som dog ikke svarer til en korrekt sorteringsalgoritme da der er er mere end en permutation der fører ned til det højre blad.

Læs introduktion til beslutningstræer som også beskriver en applet til brug for opgaven. Følgende er links til en Java applet der tillader, at man designer beslutningstræer for hhv.:

Appleten kan checke om et beslutningstræ faktisk sorterer alle mulige input.

Spørgsmål:

Lav beslutningstræer for at sortere 3 og 4 elementer. Angiv dybden af jeres beslutningstræer.

Note: Nedre grænse for sammenligningsbaseret sortering

For at argumentere om at der findes en nedre grænse på dybden af et beslutningstræ for sortering anvendes følgende argumentation.

Antal permutationer af n elementer er n! (= antal blade i et optimalt beslutningstræ for n elementer):

n 1 2 3 4 5 6 7 8 9 10 11 12
n! 1 2 6 24 120 720 5.040 40.320 362.880 3.628.800 39.916.800 479.001.600

Antal blade i et træ med dybde d er højest 2d:

d 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
2d 1 2 4 8 16 32 64 128 256 512 1.024 2.048 4.096 8.192 16.384 32.768 65.536 131.072 262.144 524.288 1.048.576 2.097.152 4.194.304 8.388.608 16.777.216 33.554.432 67.108.864 134.217.728 268.435.456 536.870.912

Ud fra ovenstående fåes følgende nedre grænser for antal sammenligninger (dybde d at et beslutningstræ) for at sortere n elementer:

n 1 2 3 4 5 6 7 8 9 10 11 12
d ≥ 0 1 3 5 7 10 13 16 19 22 26 29

F.eks. hvis n = 7, så er der 5.040 mulige permutationer, og for at et beslutningstræ skal have mindst 5.040 blade kræves at dybden er mindst 13. Generelt har vi at ⌈log2 (n!)⌉ ≥ n log2 n - 1.4427n er en nedre grænse for dybden af et beslutningstræ til sortering af n elementer.


Øvelse 10

Kan I anvende samarbejde mellem flere personer til at bringe tidsforbruget i sorteringsalgoritmerne ned?

Målet er at f.eks. fire personer kan blive færdige med arbejdet på ca. en fjerdedel af tiden for een person.

Overvej for algoritmerne Mergesort og SelectionSort hvorledes fire personer kan samarbejde således at algoritmen bliver udført på ca. en fjerdedel af tiden for een person.

Spørgsmål:

Hvorledes kan fire personer samarbejde således at algoritmen bliver udført på ca. en fjerdedel af tiden for een person (10-25 liniers svar i alt):

Mergesort:

SelectionSort:


Øvelse 11

Læs introduktion til hash-funktioner som også beskriver en applet til brug for opgaven.

Følgende er links til en Java applet der tillader at man designer hash-funktioner for tre forskellige mængder:

Spørgsmål:

Angiv for de tre input mængder en hash-funktion der spreder bedst muligt ud, dvs. en hash-funktion hvor tabel indgangen med de fleste elementer har færrest mulige elementer. (Husk at uploade jeres hash-funktion fra Java appleten)


Øvelse 12

Betragt følgende liste af tal.

    30 83 73 80 59 63 41 78 68 82 53 31 22 74 6 36 99 57 43 60 

Øvelsen er at slette så få af disse tal som muligt, så de resterende tal står i voksende orden. Hvis for eksempel alt på nær de første to tal slettes, har man en voksende følge tilbage af længde 2. Ved at slette alt på nær det første, tredie, ottende og tiende opnår man det samme, men har slettet færre tal og har en voksende følge tilbage af længde 4.

Spørgsmål:

Hvor lang er den længste voksende følge man kan opnå ?


Øvelse 13

I denne opgave betragter vi to strenge hver bestående af en sekvens af bogstaverne A, C, G og T. I denne øvelse søges den længste delsekvens der forekommer i begge strenge. F.eks. angiver *-makeringerne at sekvensen AGCGATGA er en delsekvens i begge strenge, men det er nemt at se at der findes længere fælles delsekvenser.

    ACTAGGTAACTTGAGTTTAGGCACGTTAGCTA
    *   *    *    *   *       * *  *



    GATTCAGGTAGTACGATCAGTAGCTAGTCTGA
     *    *      ***             ***

Spørgsmål:

Angiv en længst mulig delsekvens som forekommer i begge strenge i ovenstående eksempel.


Øvelse 14

Givet et array I af N tal I[1],I[2],...,I[N]. Vi ønsker at svare på spørgsmål delsum(i,j)=I[i]+I[i+1]+...+I[j] for ij. Et spørgsmål delsum(i,j) kan beregnes ved j-i additioner, specielt vil delsum(1,N) kræve N-1 additioner.

Sammen med arrayet ønsker vi at gemme en begrænset antal forud beregnede delsummer, således at det værste antal sammenligninger for et delsum(i,j) spørgsmål altid kan beregnes ved væsentligt færre sammenligninger. F.eks. ved at gemme delsummen af den midterste 1/3 af elementerne (d.v.s summen I[N/3]+....+I[2N/3-1]), kan man besvare alle delsum(i,j) med højest 2N/3 additioner. Intuitivt så falder det værste antal additioner for delsum(i,j) spørgsmål med antallet af forud beregnede delsummer der er gemt.

Det antages at der kun må anvendes additioner på elementer (d.v.s. det er f.eks. ikke er tilladte at anvende minus).

Læs introduktion til delsum problemet som også beskriver en applet til brug for opgaven.

Spørgsmål:

Hvad er det mindste antal delsummer I behøver at gemme for et array af længde 16, således at alle delsum(i,j) spørgsmål kan besvares med henholdvis 1 og 2 additioner?

Brug appleten til at designe jeres mængde af delsummer og til at checke om alle delsum(i,j) spørgsmål kræver højest 1 og 2 additioner. Uploade jeres resultat til high score listen.


Øvelse 15

Nedenstående viser en graf med knuder A,B,C,...,W og hvor nogle knuder er forbundet med kanter.

En sti er en sekvens af knuder hvor der er kanter imellem efterfølgende par af knuder i sekvensen, f.eks. er S,A,L,N en sti i nedenstående graf da der findes kanter mellem følgende par af knuder: (S,A), (A,L) og (L,N).

Spørgsmål:

Angiv en sti fra S til T i ovenstående graf som besøger flest mulige knuder, men hvor hver knude besøges højst een gang på stien.


Øvelse 16

I denne øvelse betragter vi grafer med vægte på kanterne.

Længden af en sti er summen af vægtene af kanterne langs stien. F.eks. har stien S,A,D,R,T vægt 27 = 4+10+5+8.

Spørgsmål:

Angiv længden af den kortest vej fra S til T i ovenstående graf.


Øvelse 17

I denne øvelse skal der vælges en person fra gruppen til at hente et ark med puslespil (puzzle.pdf) fra instruktoren. Arket indeholder tre puslespil, som alle handler om at samle polygoner til et kvadrat. Der er tre puslespil, med 2, 4 og 8 brikker.

Uden at vise de andre arket (da løsningen i så fald bliver kendt), klipper personen brikkerne ud.

Tre andre personer løser derefter hvert sit puslespil (vend brikkerne om, så eventuelle rester af streger ikke kan bruges som hjælp).

Tag tid på løsningen (stop løsningen af det store puslespil efter 5 minutter, hvis man ikke har løst det inden da).

Spørgsmål:

Angiv tiden for det tre løsninger.

2 brikker:

4 brikker:

8 brikker:


Øvelse 18

To simple matematikopgaver.

De må gerne besvares ved afprøvning på lommeregner eller ved plot af funktioner på grafisk lommeregner.

Spørgsmål:

Fra og med hvilket N er 0.01*N2 større 100*N ?

Fra og med hvilket N er 0.0001*2N større 10000*N ?


Øvelse 19

Endnu en matematikopgave.

Vi ser her på to computere, X og Y. Den gamle computer X kan lave 1.000.000 beregninger per sekund, mens den helt nye model Y kan lave 1.000.000.000 beregninger per sekund.

For forskellige køretider for algoritmer ønsker vi nu at beregne hvor store input der kan behandles inden for en givet tidsfrist.

Udfyld nedenstående tabel med største værdi af inputstørrelsen N, der kan behandles inden for det angivne tidsrum og på den angivne computer, når køretiden for algoritmen, udtrykt ved størrelsen N af input, er som angivet.

Spørgsmål:

Udfyld følgende tabel:

Køretid X i et sekund X i et år Y i et sekund Y i et år
N     
N*log(N)     
N2     
100*N2     
N3     
2N