Denne forelæsning giver en introduktion til kurset som helhed, og fortsætter derefter med første emne omkring modeller for sekventiel beregning. Vi præsenterer et resultat, der omhandler samtidig tid-og plads effektiv sortering.

Litteratur for undervisningen i uge 1 : Artiklen "Optimal Time-space Trade-Offs for Sorting" [ps,pdf] af Jakob Pagter og Theis Rauhe.

Opgave 0) (H)

I forelæsningen bliver det antaget at input indeholdte forskellige tal. Hvordan kan denne restriktion undgåes?

Opgave 1)

Lad X= < x[1], x[2], ... x[n] > være et "read-only" input, hvor A = { x[1], x[2] ,... x[n/2] } og B = { x[n/2+1], ..., x[n] }.

Lav pladseffektive algoritmer, der i O(n log n) tid udskriver:

a) Fællesmængden for A og B.

b) Foreningsmængden for A og B.

c) Elementer i A, der ikke forekommer i B.

Opgave 2)

Lad X være et read-only input med n elementer. Antag vi kun har en CPU, med et konstant antal registre, der hver indeholder O(log n) bits. Vi er interesseret i udskrive X sorteret, men kan kun gemme og ændre data i det lille antal registre. Hvor hurtigt kan X udskrives sorteret?

Opgave 3)

Antag vi får givet en stump kryptisk kode, der ekstremt hurtigt (O(1) tid) beregner værdien for en funktion f(U) -> U, hvor U er et stort endeligt univers af heltal {0, 1, 2, ..., N-1}. For denne funktion er vi nu interesseret i om den er bijektiv, d.v.s. f(x) = f(y) hvis og kun hvis x=y.

Antag vi har en ordstørrelse på mindst O(log U) bits. Hvor hurtigt kan det worst-case afgøres om funktionen f er bijektiv, hvis vi har en computer med en hukommelse på N/log N bits, N^(1/2) bits og generelt med X bits? Koden for f er generelt så kryptisk, at du kun kan få information om f ved at evaluere koden.

Opgave 4)

Argumenter for, at det mindste pladsforbrug for en sorteringsalgoritme er Omega(log n) bits.

Opgave 5)

Den præsenterede løsning for tid-plads effektiv sortering benytter en slags prioriteskø uden indsættelse. Antag vi skal håndtere følgende operationer, der ligger nærmere de sædvanlige for en prioritetskø:

Init(X): Initialiserer datastrukturen for input array X = < X[1], X[2], ..., X[n] >

Pop(): Returner e= min X, og sætter X <- X \ e.

Update(j, e): Sætter X[j] <- e, hvor indgang j er et element, der er udtaget via tidligere Pop(), og e skal samtidg værre større end det største hidtil udtagne element. D.v.s. Update fungerer som sædvanlig Insert operation i en monoton prioritetskø, så X <- X U {e}, hvor j blot er et udbrugt sted i input, hvor e, der er større end sidste Pop() element, kan skrives.

Angiv en løsning, der håndterer ovennævnte operationer i tid O(log n) per operation, men stadig bruger højest O(n/log n) bits.

Bemærk, at det alene er brugeren der kan ændre input via Update operationen. Algoritmen må stadig kun anvende egen data, samt læse i input, der via Update så kan være opdateret af brugeren indimellem. Hvad sker hvis man fjerner betingelsen at nyt indsatte element e skal være større end sidst udtagne element?

Element distinctness

1) Beskriv en sammenligningsbaseret, tid-plads effektiv algoritme til afgørelse af, om et input indeholder to ens elementer. Algoritmen skal køre i tid O(n log n), og bruge så lidt hukommelse som muligt.

2)I artiklen "Optimal Time-Space Trade-Offs for Sorting" side 5, i afsnittet "Step 2", beskrives udvidelsen af L/R-træet, hvor der associeres flere bit til knuderne i træet. Mere præcist defineres en værdi mu(v) (det græske bogstav my), for den sub-vektor, hvor en lineær søgning skal foretages i. Til repræsentation af mu(v) bruges log m - i bits, hvor i er niveau'et (level) for knuden v.

Hvordan påvirkes plads-og tidsforbrug for algoritmen, hvis vi øger præcisionen for mu(v) (og tilsvarende mindsker sub-vektor størrelse for b_i,m(v)), så vi i stedet tillader et forbrug på (log m - i)^2 bits i stedet for log m - i bits?