Eksempel

Enda et eksempel, hentet fra kontinuasjonseksamen 2009:

Løs følgende rekurrens. Oppgi svaret i asymptotisk notasjon. Begrunn svaret kort.

$$ T(n) = 2T(^n/_3) + ^1/_n $$

Vi har $a = 2, b = 3, f(n) = n^{-1}$. Det gir $\log_b a = \log_3 2 \approx 0.63$. Siden $f(n) = n^{-1}$ er $O(n^{.63})$, har vi tilfelle 1 og løsningen $T(n) \in \Theta(n^{.63})$.

Queue

En queue er en FIFO (First In First Out) struktur. Dette vil si at et POP-kall til køen returnerer elementet som først ble satt inn.

Stack

En stakk er LIFO (Last In First Out) struktur. Et POP-kall til stakken returnerer elementet som sist ble satt inn.

Implementere lenkede lister

I OOP (Object-Oriented Programming) benytter en objekter og pekere. Python-kode for en lenket liste:

class Node:
    def __init__(self, key):
        self.key = key
        self.prev = None
        self.next = None

    def set_pointers(prev, next):
        self.prev = prev
        self.next = next

n1 = Node(9)
n2 = Node(4)
n3 = Node(1)
n4 = Node(5)

n1.set_pointers(None, n2)
n2.set_pointers(n1, n3)
n3.set_pointers(n2, n4)
n4.set_pointers(n3, None)

I språk som ikke støtter objekter eller pekere kan en bruke arrays. L holder her indeksen til det første elementet.

L = 4
        0  1  2  3  4  5  6
--------------------------
NEXT = [/, 2, 6, /, 1, /, /]
KEY  = [/, 4, 1, /, 9, /, 5]
PREV = [/, 4, 1, /, /, /, 3]

Dette kan også gjøres komprimeres til et enkelt array, der hver node er 3 etterfølgende verdier, (prev, key, next).

L = 1
        0  1  2  3  4  5  6  7  8   9  10 11 
-----------------------------------------
LIST = [/, 9, 4, 1, 4, 7, 4, 1, 10, 7, 5, /]

Klarer du å se at alle de lenkede listene er identiske?

Kjøretider

Merge sort

Merge sort er en splitt-og-hersk algoritme.

1. Todel listen rekursivt til hver liste inneholder 1 element. (En liste med ett element er per definisjon sortert)
2. Flett sammen underlistene.

I praksis blir dette gjerne implementert rekursivt.

Merge funksjonen kjører i lineær tid. For å analysere kjøretiden til Merge sort kan vi sette opp følgende rekurrens:

$$T(n) = 2T(n/2) + n$$

Altså 2 ganger tiden det tar å sortere en liste av lengde $^n/_2$ pluss tiden det tar å flette de to listene. Se Masterteoremet for hvordan vi kan løse denne rekurrensen og finne kjøretiden $O(n\log n)$.

De fleste implementasjoner av Merge sort er stabile. På grunn av at algoritmen hele tiden lager nye underlister, trenger den $O(n)$ ekstra plass i minnet.

Quicksort

Quicksort (Randomized)

Quicksort er en splitt-og-hersk algoritme.

Konseptet med et pivot-element står sentralt i quicksort. For hver iterasjon velger en seg et pivot-element og sorterer resten av elementene basert på om de er større eller lavere enn pivot-elementet. Hvis pivot-elementet velges tilfeldig kalles algoritmen Randomized-Quicksort.

1. Velg et pivot-element.
2. Sorter resten av elementene i 2 del-lister utifra om de er større eller mindre enn pivot.
3. Sorter de 2 del-listene rekursivt til de bare inneholder 1 element.

Kjøretidsanalysen av Quicksort blir noe vanskeligere enn for Merge sort, ettersom størrelsen på listene som sorteres rekursivt vil avhenge av hvilken pivot vi velger. Det å velge en god pivot er en kunst i seg selv. Den naïve fremgangsmåten med å slavisk velge det første elementet, kan lett utnyttes av en adversary, ved å gi en liste som er omvendt sortert som input. I dette tilfellet vil kjøretiden bli $n^2$. Vi kan motvirke dette ved å velge en tilfeldig pivot i stedet.

Quicksort bruker Partition som subrutine.

Heapsort

Heapsort bruker trestrukturen heap til å sortere.

Bubblesort

Traverserer listen, sammenligner to elementer og bytter plass på dem hvis nødvendig.

Insertion Sort

Setter inn element i på rett plass i den allerede sorterte lista av i-1 elementer.

Selection sort

Veldig dårlig sorteringsalgoritme, søker gjennom hele lista og finner det minste elementet hver gang.

Counting sort

Denne algoritmen antar at input er heltall fra et begrenset intervall, k. Counting sort teller hvor mange elementer som er lavere eller lik det elementet som skal sorteres, og putter det på riktig plass i lista. Dette er en stabil søkealgoritme.

Dersom $ k = O(n)$ , får vi kjøretid $ \Theta(n)$

Radix sort

Radix sort antar at input er n elementer med d siffer, der hvert siffer kan ha opp til k forskjellige verdier. Algoritmen ser som regel på det minst signifikante sifferet, sorterer med hensyn på dette sifferet, og gjentar så med det nest minst signifikante sifferet, osv. Om sortseringen på hvert siffer er basert på en algoritme som sorterer stabilt på $\Theta(n+k)$ (feks counting sort), vil hele algoritmen bruke $\Theta(d(n+k))$ tid.

Bucket sort

Bucket sort antar at inputen er generert fra en tilfeldig (random) prossess som fordeler elementene uniformt og uavhengig over et intervall. Bucket sort deler intervallet inn i n like store "bøtter" (intervaller), og fordeler så de n inputtallene i bøttene. Hver bøtte sorteres så for seg vet å bruke en sorteringsalgoritme, bucket sort, insertion sort eller en annen algoritme.

def bucket_sort(A):
n = len(A)
B = [[] for _ in range(n)]

for i in range(n):
    B[int(n*A[i])].insert(-1, A[i])

for j in range(n):
    insertion_sort(B[j])

res = []
for i in range(len(B)):
    res += (B[i])

return res

Brute force

Denne fremgangsmåten er ganske selvforklarende. Gå gjennom lista (sortert eller ikke) fra begynnelse til slutt og sammenlign hvert element mot elementet du ønsker å finne. Med $n$ elementer i lista blir kjøretiden $O(n)$

Binærsøk

Dersom vi vet at lista vi skal søke i er sortert, kan vi bruke en litt annen strategi. Si at vi leter etter en verdi $a$ i en sortert liste $L$. Vi begynner med å finne det midterste elementet i $L$ og sjekker om det er lik elementet vi leter etter. Dersom ja, returner indeksen, dersom ikke, avgjør om elementet i leter etter er større enn eller mindre enn det midterste, og gjenta deretter prosedyren i den underlista der elementet må være, dersom det i det hele tatt ligger i lista.

Siden vi for hver iterasjon todeler listen, og kan forkaste halvparten får vi følgende kjøretider:

Randomized-Select

Select

Trær

Et tre er en begrenset gruppe type graf. Trær har retning (parent / child forhold) og inneholder ikke sykler.

Høyden til et tre tilsvarer antall kanter i den lengste stien fra roten til en løvnode.

Trær kan også defineres som grafer der, for hvert par noder $u,v \in V$, så eksisterer det én(og bare en) enkel sti mellom $u$ og $v$.

Et tre er altså et spesialtilfelle av en DAG (Directed Acyclic Graph) der hver barnenode kun har én forelder.

Nabolister

Gitt at vi har en graf G med noder $V = \{A,B,C,D\}$ kan vi representere hvem som er nabo med hvem på følgende måte:

$$A: [B, C] \\ B:[A, C] \\ C:[D]$$

Dette angir at det går en kant fra noden før kolon til hver av nodene i listen etter kolon. Denne måten å representere grafer på passer godt når grafen har få kanter (sparse).

Nabomatriser

Når vi har mange kanter i en graf (dense), velger vi gjerne å representere dette ved en nabomatrise. For en graf med $|V|$ noder, er dette en $(|V| \times |V|)$-matrise. Eksempel:

    0 1 2 3 4 5
  -------------
0 | 0 1 0 0 0 1
1 | 0 0 1 1 0 1
2 | 1 1 0 1 0 0
3 | 0 0 1 0 1 0
4 | 0 0 0 0 0 1
5 | 1 0 1 0 1 0

Denne matrisa representerer en graf G med noder $V = \{0,1,2,3,4,5\}$ og kanter angitt med et entall dersom det går en kant mellom to noder. Nabomatriser kan vi også modifisere til å representere vektede grafer. Dersom det går en kant mellom $u,v$ med vekt $w(u,v) = 3$ lar vi det stå 3 på den korresponderende plassen i matrisa.

Topologisk sortering

Ved å merke start- og slutt-tider kan DFS brukes til topologisk sortering, men dette krever da at grafen er en DAG (Directed Acyclic Graph). Finnes det en kant $(u, v)$ , skal noden $u$ komme før $v$ i ordningen. DFS brukes til å finne denne ordningen.

Hvis det er mulig å lage en topologisk sortering (grafen er rettet og asyklisk), kan en kjøre DAG-shortest-path, den meste effektive løsningen av korteste vei en til alle.

In-Order, Pre-Order og Post-Order traversering

In-order, Pre-order og Post-order traversering besøker hver node i et tre ved å rekursivt besøke hver nodes barn (både høyre og venstre).

En grei måte å huske det på, er å tenke når vi legger nodene inn i lista over besøkte noder. Vi starter alltid i toppnoden og går nedover venstre side av grafen sånn som i visualiseringa under.

I pre-order rekkefølge legger vi noden til lista når vi passerer dem på venstre side.

|| Pre-order || || F, B, A, D, C, E, G, I, H ||

I in-order rekkefølge legger vi noden til lista når vi er rett på undersida av noden.

|| In-order || || A, B, C, D, E, F, G, H, I ||

I post-order rekkefølge legger vi noden til lista når vi passerer dem på høyre side.

|| Post-order || || A, C, E, D, B, H, I, G, F ||

Kant-klassifisering

Tree-Edge er en kant til en direkte etterfølger.

Forward-Edge er en kant til en indirekte etterfølger.

Back-Edge er en kant til en forgjenger.

Cross-Edge er en kant til en node som hverken er en etterfølger eller forgjenger.

Kruskal

Kruskals algoritme lager treet ved å finne de minste kantene i grafen en etter en, og lage en skog av trær. Deretter settes disse trærne gradvis sammen til ett tre, som blir det minimale spenntreet. Først finnes kanten i grafen med lavest vekt. Denne kanten legges til et tre. Deretter ser algoritmen etter den neste laveste kantvekten. Er ingen av nodene til denne kanten med i noe tre, så lages et nytt tre. Er én av nodene knyttet til et tre, så legges kanten til i det eksisterende treet. Er begge nodene knyttet til hver sitt tre settes de to trærne sammen. Er begge nodene knyttet til samme tre ignoreres kanten. Sånn fortsetter det til vi har ett tre.

MST-KRUSKAL(G, w)
1    A = ∅
2    for each vertex v ∈ G.V
3        MAKE-SET(v)
4    sort the edges of G.E into nondecreasing order by weight w
5    for each edge (u,v) ∈ G.E, taken in nondecreasing order by weigth
6        if FIND-SET(u) ≠ FIND-SET(v)
7            A = A ∪ {(u,v)}
8            UNION(u,v)
9    return A

Prim

Prims algoritme lager treet ved å starte i en vilkårlig node, og så legge til den kanten knyttet til noden som har lavest verdi. Deretter velges kanten med lavest verdi som er i knyttet til én av nodene som nå er en del av treet. Dette fortsetter til alle nodene er blitt en del av treet. Kjøretiden avhenger av datastrukteren som velges, pensum bruker en binærheap.

MST-PRIM(G, w, r)  
1    for each u in G.V  
2        u.key = ∞  
3        u.π = NIL  
4    r.key = 0  
5    Q = G.V  
6    while Q ≠ ∅  
7        u = EXTRACT-MIN(Q)  
8        for each v ∈ G.Adj[u]  
9            if v ∈ Q and w(u,v) < v.key  
10                v.π = u  
11                v.key = w(u,v)

Initialize-Single-Source

INITIALIZE-SINGLE-SOURCE(G, s)
1   for each vertex v ∈ G.V
2       v.d = ∞
3       v.π = NIL
4   s.d = 0

Relax

1   if v.d > u.d + w(u, v)
2       v.d = u.d + w(u, v)
3       v.π = u

Bellman-Ford

Bellman-Ford er den tregeste algoritmen, men fungerer med negative sykler. I en graf med negative sykler er korteste vei udefinert, men BF vil da vite med sikkerhet at grafen inneholder minst en negativ sykel som kan nåes fra opprinnelsesnoden (origin).

BELLMAN-FORD(G, w, s)
1   INITIALIZE-SINGLE-SOURCE(G, s)
2   for i = 1 to |G.V| - 1
3       for each (u, v) in G.E
4           RELAX(u, v, w)
5   for each (u, v) in G.E
6       if v.d > u.d + w(u, v)
7           return False
8   return G

Bellman-Ford gjør $i = |V| - 1$ iterasjoner, og for hver iterasjon slakker (relaxer) den hver kant i hele grafen. Etter BF har kjørt linjene 1-4 skal alle nodene ha sin endelige kostand, og en ytterlig iterasjon (linje 5-7) skal ikke gi utslag. Hvis det gjør det har vi en negativ sykel.

Dijkstras algoritme

Dijkstras algoritme er raskere enn Bellman-Ford, men terminerer bare hvis kantvektene er ikke-negative. Den tillater positive sykler. Dijkstras er mest effektiv når det brukes en heap som prioritetskø, og det er også denne kjøretiden vi har listet.

DIJKSTRA(G, w, s)
1    INITIALIZE-SINGLE-SOURCE(G, s)
2    S = {}
3    Q = G.V
4    while (Q != {})
5        u = EXTRACT-MIN(Q)
6        S = S + u
7        for vertex v in G.Adj[u]
8            RELAX(u, v, w)
9    return G

1. Lag en prioritetskø Q av alle nodene i grafen. (linje 3)
2. Hent ut noden fra Q som har lavest kostnad. (linje 5)
3. Slakk (relax) nabonodene til den aktive og oppdater avstandene deres. (linje 8)
4. Legg den aktive noden til i besøkte noder. (linje 6)
5. Gå til steg 2 og gjenta fram til Q er tom.

DAG shortest path

Den raskeste algoritmen for å løse problemet SSSP, For å kjøre denne må man ha en DAG (Directed Acyclic Graph). Da kan vha DFS lage en topologisk sortering og slakke kantene i denne rekkefølgen.

1 DAG-SHORTEST-PATHS(G, w, s)
2    for each vertex v in G.V
3        v.d = inf  # Distance
4        v.p = null # Parent
5    s.d = 0
6    for each vertex u in G.v, where G.v is topologically sorted
7        for each adjacent vertex v to u
8            if v.d > u.d + w(u, v) # Relax
9                v.d = u.d + w(u, v)
10               v.p = u

Floyd-Warshall

Funker hvis det finnes negative kanter, men ingen negative sykler. Nodene må være lagret som en nabomatrise, ikke en naboliste.

Psuedokode fra wikipedia:

FLOYD-WARSHALL(W):
1    n = W.rows
2    D = W
3    for k = 1 to n
4        for i = 1 to n
5            for j = 1 to n
6                d_ij = min(d_ij, d_ik + d_kj)
7    return D

For hver tildeling av nodene $i$, $j$ og $k$ sjekker den om det finnes en raskere vei fra $i$ til $j$ som går gjennom $k$.

Algoritmen lager matriser $D^{(k)}$ der $D^{(k)}[i][j]$ gir korteste vei fra i til j som kun passerer noder nummerert k eller lavere.

Transitive-Closure

Gjør akkurat det samme som Floyd-Warshall, men sjekker om det finnes en vei fra $i$ til $j$ eller ikke, den er altså ikke opptatt av vektene. Samme kjøretid som FW.

Flytnettverk

Et flytnettverk er en rettet graf, der alle kantene har en ikke-negativ kapasitet. I tillegg er det et krav at dersom det finnes en kant mellom u og v, finnes det ingen kant motsatt fra v til u. Et flytnettverk har en kilde, s, og et sluk, t. Kilden kan sees på som startnode, og sluket som sluttnode. Grafen er ikke delt, så for alle v finnes en vei s ~ v ~ t. Alle kanter bortsett fra s har en kant inn. En node, bortsett fra kilden og sluket, har like mye flyt inn som den har flyt ut.

Et flytnetverk kan ha mange kilder og sluk. For å eliminere problemet, lager vi en superkilde og/eller et supersluk. Superkilden har en kant til hver av kildene, og kapasiteten på de kantene setter vi som uendelig. På samme måte lager vi supersluket. En kant fra hver av slukene, og setter kapasiteten til uendelig. Da er det et nytt nettverk, med kun en kilde og en sluk, og vi kan løse problemet som vanlig.

Residualnettverk

Residualnettverket er det som er igjen av kapasitet. Altså $$ c_f(u,v) = c(u,v) - f(u,v)$$

Å følge med på residualnettverket er nyttig. Hvis en sender 1000 liter vann fra u til v, og 300 liter fra v til u, er det nok å sende 700 liter fra u til v for å ha samme resultat.

Augmenting path

En flytøkende sti (augmenting path) er en sti fra starten til en node, som øker total flyt i nettverket. En augmenting path er en enkel sti fra s til t i residualnettverket. Per definisjon av residualnettverket kan vi øke $f(u, v)$ i en augmenting path med $c_f(u, v)$ uten å gå over begrensningene.

Minimalt kutt

Et kutt i et flytnettverk er å dele grafen i to, S og T, og se på flyten gjennom kuttet. Altså

$$ f(S,T) = \sum_{s \in S}\sum_{t \in T} f(u,v) - \sum_{s \in S}\sum_{t \in T} f(v,u) $$

Antall mulige kutt totalt i et nettverk med n noder:

$$|C| = 2^{n-2}$$

Av alle de mulige kuttene, ønsker vi å se på det kuttet som har minst flyt, da dette er "flaskehalsen" i nettverket.

Ford-Fulkersons metode

I hver iterasjon av Ford-Fulkerson finner vi en flytforøkende sti p, og bruker p til å modifisere f. Merk at Ford-Fulkersons ikke spesifiserer hvordan dette implementeres.

FORD-FULKERSON-METHOD(G, s, t)
1    initialize flow to 0
2    while there exists an augmenting path p in the residual network G_f
3        augment flow f along p
4    return f

Heltallsteoremet

Om alle kapasiteter i flytnettverket er heltall, vil Ford-Fulkersons metode finne en maks flyt med en heltallsverdi, og flyten mellom alle nabonoder vil ha en heltallsverdi.

Redusibilitets-relasjon

For å forstå bevisteknikken som brukes for å bevise at et problem er NPC, er det et par begreper som må på plass. Ett av de er redusibilitets-relasjonen $\leq_P$. I denne sammenhengen brukes det for å si at et språk ($L_1$) er polynomisk-tid redusertbart til et annet språk ($L_2$): $L_1 \leq_p L_2$.

Boken (Cormen m.fl) trekker frem et eksempel der førstegradsligningen $ax + b = 0$ kan transformeres til $0x^2 + ax + b = 0$. Alle gyldige løsninger for annengradsligningen er også gyldige løsninger for førstegradsligningen. Ideen bak eksempelet er å vise at et problem, X, kan reduseres til et problem, Y, slik at inputverdier for X kan løses med Y. Kan du redusere X til Y, betyr det at å løse Y krever minst like mye som å løse X, dermed må Y være minst like vanskelig å løse som X. Det er verdt å merke seg at reduskjonen ikke er gjensidig, du kan dermed ikke bruke X til å løse Y.

Noen kjente NPC problemer

Noen vanlige eksempler på problemer som er $NPC$:

• Circuit-SAT
• SAT
• 3-CNF-SAT
• Klikk-problemet (Clique)
• Vertex-Cover
• Hamiltonsykel (Hamilton cycle)
• Traveling Salesman Problem (TSP)
• Subset-Sum

Men hvordan kan vi bevise at et problem er NPC?

Boken (Cormen m.fl) deler det opp i to:

1. Bevis at problemet hører til i NP-klassen. Bruk et sertifikat til å bevise at løsningen stemmer i polinomisk tid.
2. Bevis at problemet er NP-hardt. Gjøres ved polynomisk tid reduksjon.

Gitt at $P \neq NP$ så kan vi si at et problem er NPC dersom det er både et NP-problem og et NP-hard-problem.

Sammenhengen er illustrert i figuren under:

Gitt at du skal bevise at TSP er et NPC-problem:

1. Bevis at $TSP \in NP$. Serifikatet du bruker kan være en sekvens av n noder du skal besøke på turen. Dersom sekvensen kun består av unike noder (vi besøker ikke samme by flere ganger for eksempel), så kan vi summere opp kostnadene og verifisere om den totale kostnaden er mindre enn et gitt heltall k.
2. Bevis at TSP er NP-hard. Hvis du har satt deg litt inn i hva de ulike problemene nevnt ovenfor beskriver, så kan det hende at du kjenner igjen deler av TSP som et Ham. cycle-problem (gitt en urettet graf G, finnes det en sykel som inneholder alle nodene kun én gang, og der sluttnode = startnode). Vi vet at TSP er minst like vanskelig å løse som Ham.-sykel problemet (da Ham.-sykel er et delproblem av TSP). Gitt at vi allerede har bevist at Ham.-sykel-problemet er NP-hard, kan vi ved polynomisk-tid reduksjon bevise at også TSP er NP-hard (Kan vi redusere Ham.-sykel til TSP i polynomisk tid, er TSP NP-H). $HAM-CYCLE \leq_P TSP$.

Da de aller fleste til nå tror at $P \neq NP$, så følger det at NP-harde problemer ikke kan løses i polynoisk tid, ei heller NP-problemer. Klarer du derimot å bevise at $P \neq NP$ eller at $P = NP$, så har du krav på en rimelig stor pengepremie.