TDT4120: Algoritmer og datastrukturer
# Hva er algoritmer?
__En uformell definisjon__: En algoritme er en hvilket som helst _tydelig definert fremgangsmåte for beregninger_ som kan ta en verdi (eller en mengde verdier) som _input_ og gir en verdi (eller en mengde verdier) som _output_.
Man kan også se på det som et verktøy som skal løse et definert beregningsproblem. Når man definerer problemet, må man beskrive hvilket forhold man ønsker mellom input og output, for eksempel: «_Input_: Et veikart over en by og to punkter. _Output_: Den korteste veien (målt i meter) mellom de to punktene.»
__Beskrivelse av løsning__: Det finnes ingen verdensomspennende standard for å beskrive en algoritme. Du kan beskrive den med naturlig språk, som et dataprogram eller til og med ved hjelp av å tegne maskinvare (hardware) som løser problemet. Det eneste kravet er at du er presis når du beskriver.
__Instanser__: Hver samling av input-verdier til et slikt problem kalles en __instans__. For eksempel kan man i en instans av problemet over ha input-verdier som er et veikart over Trondheim, og de to punktene kan være to geografiske punkter som tilsvarer NTNU Gløshaugen og NTNU Dragvoll.
__Riktig eller uriktig?__: En algoritme kan være enten __riktig__ eller __uriktig__. Dersom en algoritme er _riktig_, vil den for alle tenkbare instanser (innenfor området vi har bestemt) gi riktig output; f.eks. er det bare å forvente at en sorteringsalgoritme ikke vil ha problem med å sortere alle mulige samlinger av positive heltall. Dersom den er _uriktig_, vil den ikke gjøre det. F.eks. kan du ha funnet på en algoritme som løser alle sorteringsproblemer ved å vende rekken av tall du har fått baklengs. Dette vil for noen instanser gi riktig output, men bare for en brøkdel av alle mulige instanser.
# Grunnleggende datastrukturer
Faget går gjennom og nyttiggjør seg av mange ulike datastrukturer i sammenheng med ulike problemstillinger, og det kan derfor være greit å ha oversikt over de viktigste.
## Lenkede lister
_[Singly linked list (Public Domain, Lindisi)](https://en.wikipedia.org/wiki/Singly_linked_list#mediaviewer/File:Singly-linked-list.svg)_
En lenket liste er en enkel lineær datastruktur som representerer elementer i sekvens. Tanken bak strukturen er at rekkefølgen på elementer opprettholdes ved at hvert element peker til det neste i rekkefølgen (se figuren over). Forklart med kode:
class Node:
def __init__(self):
self.value = None
self.next = None
n1 = Node()
n2 = Node()
n3 = Node()
n1.value = 1
n2.value = 2
n3.value = 3
n1.next = n2
n2.next = n3
Med koden ovenfor vil strukturen være n1 -> n2 -> n3
Vi kan også ha dobbeltlenkede lister, der hver node inneholder en verdi og peker til både forrige og neste node.
### Kjøretider
|| **Handling** || **Kjøretid** ||
|| Innsetting på starten || O(1) ||
|| Innsetting på slutten || O(n) ||
|| Oppslag || O(n) ||
|| Slette element || oppslagstid + O(1) ||
## Abstrakte datastrukturer
### Kø (Queue)
En kø er en abstrakt datastruktur som bevarer de innsatte elementers rekkefølge og har to operasjoner, _enqueue_ og _dequeue_. _Enqueue_ er innsettingsoperasjonen, som setter inn et element på slutten av køen. _Dequeue_ er uthentingsoperasjonen, den henter ut fra begynnelsen av køen. En kø er altså en FIFO-datastruktur (First In First Out).
### Stakk (Stack)
En stakk er en abstrakt datastruktur som, i likhet med en kø, bevarer de innsatte elementers rekkefølge. En stakk er LIFO (Last In First Out), så den både legger til og tar ut fra slutten av strukturen. Operasjonene kalles _push_ og _pop_.
### Heap
En heap er en liste som kan sees på som et binærtre. En heap er en implementasjon av datastrukturen prioritetskø. Se også [heapsort](#heapsort)
# Kjøretidsberegning
Kjøretiden er et mål på hvor effektiv en algoritme er og uten tvil det viktigste.
## Om kjøretider
__Hvorfor trenger vi kjøretid?:__ I en verden der datamaskiner var uendelig raske og du hadde uendelig med tilgjengelig lagrings plass, kunne du brukt en hvilken som helst _riktig_ algoritme for å løse et problem – uansett hvor lite gjennomtenkt den måtte være. Men, som du sikkert har merket, er vi ikke i denne verdenen. Derfor har vi kjøretider.
__Forklaring av kjøretid__: En kjøretid beskriver forholdet mellom størrelsen på problemet og hvor lang tid det vil ta å løse det. Eller, du vil sannsynligvis tenke på det på følgende måte: De forteller deg at dersom du har et problem av en viss størrelse, vil det ta så-så mye lenger tid om man legger til ett element til i inputen … eller dobler mengden. Du skjønner sikkert at det er ønskelig at dette ikke vokser særlig fort.
## Noen vanlige kjøretider
De generelle og vanligste kjøretidene sortert fra høyest til lavest.
|| __Kompleksitet__ || __Navn__ || __Type__ ||
|| $\Theta(n!)$ || Factorial || Generell ||
|| $\Omega(k^n)$ || Eksponensiell || Generell ||
|| $O(n^k)$ || Polynomisk || Generell ||
|| $\Theta(n^3)$ || Kubisk || Tilfelle av polynomisk ||
|| $\Theta(n^2)$ || Kvadratisk || Tilfelle av polynomisk ||
|| $\Theta(n \lg n)$ || Loglineær || Kombinasjon av lineær og logaritmisk ||
|| $\Theta(n)$ || Lineær || Generell ||
|| $\Theta(\lg n)$ || Logaritmisk || Generell ||
|| $\Theta(1)$ || Konstant || Generell ||
# Rekursjon
Rekursjon er en problemløsningsmetodikk som baserer seg på at løsningen på et problem er satt sammen av løsningene til mindre instanser av samme problem. Denne teknikken kommer til å gå igjen i mange av algoritmene i pensum.
Et av de aller vanligste eksemplene på rekursivitet er Fibonaccitallene, definert som:
$$F(n) = F(n-1) + F(n-2)\\ F(0) = 0, F(1) = 1$$
Fibonaccitall $n$ er altså definert som summen av de to foregående Fibonaccitallene.
Gode eksempler på rekursive algoritmer er Merge og Quick Sort og binærsøk. Vi finner også ofte rekursive løsninger ved bruk av dynamisk programmering.
## Masterteoremet
Masterteoremet er en kokebokløsning for å finne kjøretiden til (mange) rekurrenser på formen
$$ T(n) = aT(^n/_b) + f(n) \\ a \ge 1, b \gt 1 $$
Denne typen rekurrenser oppstår gjerne i sammenheng med splitt-og-hersk algoritmer, f.eks. Merge sort.
Problemet deles opp i $a$ deler av størrelse $^n/_b$, med f(n) arbeid for å gjøre selve oppdelinga, og å sette sammen resultatet av rekursive kall etter at disse er ferdige. I eksempelet med Merge sort, er f(n) arbeidet med å splitte lista i to underlister, og å flette sammen de to sorterte listene etter at de rekursive kallene er ferdige. Det å splitte skjer i konstant tid $\Theta(1)$, mens det å flette sammen tar lineær tid $\Theta(n)$. Vi kan altså sette $f(n) = n$. Siden vi til enhver tid deler listen opp i to deler, hver del $^n/_2$ er henholdsvis $a=2$ og $b=2$. For Merge sort har vi altså:
$$ T(n) = 2T(^n/_2) + n $$
Dersom vi ikke allerede visste kjøretiden til Merge sort, kunne vi funnet den ved å løse denne rekurrensen. Å løse rekurrensen kunne vi så brukt Masterteoremet til. Fremgangsmåten for Masterteoremet er som følger:
1. Identifiser $a, b, f(n)$
2. Regn ut $\log_b a$
3. Konsulter tabellen under
Tabell over de tre tilfellene av Masterteoremet:
|| **Tilfelle** || **Krav** || **Løsning** ||
|| 1 || $f(n)\in O(n^{\log_b a-\epsilon})$ || $T(n) \in \Theta(n^{\log_b a})$ ||
|| 2 || $f(n)\in \Theta(n^{\log_b a} \log^k n)$ || $T(n) \in \Theta(n^{\log_b a}\log^{k+1} n)$ ||
|| 3 || $f(n)\in \Omega(n^{\log_b a+\epsilon})$ || $T(n) \in \Theta(f(n))$ ||
$\epsilon > 0$
Vi fortsetter eksempelet med Merge sort. Vi har funnet $a=2, b=2, f(n)=n$, da må $\log_b a = \log_2 2 = 1$. Vi har altså tilfelle 2, $f(n) \in \Theta(n^1)$, med løsning $T(n) \in \Theta(n\lg n)$.
### 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})$.
# Sortering og søking
Sortering og søking er to problemstillinger som går igjen enten som problem i seg selv, eller som underproblem. Med sortering mener vi det å arrangere en mengde med objekter i en spesifikk rekkefølge. Med søking mener vi det å finne ett spesifikt objekt i en mengde objekter.
## Søking
Det å finne et spesifikt element i en datastruktur er et utbredt problem. I en liste av tall kan vi f.eks. lete etter medianen eller bare et bestemt tall. I en graf kan vi f.eks. lete etter en måte å komme oss fra ett element til et annet. Søkealgoritmer for grafer (DFS og BFS) står under [Graf-algoritmer](#grafer-og-grafalgoritmer).
For å søke i lister, har vi primært to fremgangsmåter; brute force og binærsøk.
### 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.
I Python:
def binary_search(li, value, start=0):
# Dersom lista er tom, kan vi ikke finne elementet
if not li:
return -1
middle = len(li) // 2
middle_value = li[middle]
if value == middle_value:
return start + middle
elif value < middle_value:
# Første halvdel
return binary_search(li[:middle], value, start)
elif value > middle_value:
# Siste halvdel
return binary_search(li[middle + 1:], value, start + middle + 1)
Siden vi kan se bort fra substansielle deler av lista etter hvert "valg," får vi følgende kjøretider:
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(\log n)$ || $O(\log n)$ || $O(n)$ ||
## Sortering
Stort sett kategoriserer vi sorteringsalgoritmer inn i to grupper; sammenligningsbaserte og distribuerte/ikke-sammenligningsbaserte.
### Stabilitet
En sorteringsalgoritme kan sies å være stabil dersom rekkefølgen av like elementer i listen som skal sorteres blir bevart i løpet av algoritmen. Altså; dersom vi har listen:
$$[B_1, C_1, C_2, A_1]$$
og sorterer den med en eller annen algoritme, og de to like elementene står i samme rekkefølge etter sorteringen, har vi en stabil sorteringsalgoritme.
$$[A_1, B_1, C_1, C_2]$$
### Sammenligningsbaserte sorteringsalgoritmer
Alle sorteringsalgoritmer som baserer seg på å sammenligne to elementer for å avgjøre hvilket av de to som skal komme først i en sekvens, kaller vi sammenligningsbasert. Det er vist at $\Omega(n\lg n)$ er en nedre grense for antall sammenligninger en sammenligningsbasert sorteringsalgoritme må gjøre. Med andre ord, det er umulig å lage en sammenligningsbasert sorteringsalgoritme som har bedre worst-case kjøretid enn $O(n\lg n)$.
#### Merge sort
Merge sort er en sammenligningsbasert sorteringsalgoritme. Den er også et eksempel på en splitt-og-hersk algoritme.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n\log n)$ || $O(n\log n)$ || $O(n\log n)$ ||
Den grunnleggende tankegangen bak algoritmen er som følger:
1. Del opp den usorterte listen i $n$ underlister som hver inneholder ett element. (En liste med ett element er sortert)
2. Flett sammen underlistene.
I praksis blir dette gjerne implementert rekursivt. Funksjonen tar ett parameter, nemlig listen som skal sorteres. Dersom listen inneholder kun ett element, kan vi returnere denne listen, siden den allerede er sortert. Dersom den er lenger, splitt den opp i to like store underlister og sorter disse ved å kalle funksjonen rekursivt. Når underlistene kommer tilbake sortert, flett sammen og returner resultatet. I Python:
def merge_sort(li):
if len(li) < 2: # Dersom vi har en liste med ett element, returner listen, da den er sortert
return li
sorted_l = merge_sort(li[:len(li)//2])
sorted_r = merge_sort(li[len(li)//2:])
return merge(sorted_l, sorted_r)
def merge(left, right):
res = []
while len(left) > 0 or len(right) > 0:
if len(left) > 0 and len(right) > 0:
if left[0] <= right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
elif len(left) > 0:
res.append(left.pop(0))
elif len(right) > 0:
res.append(right.pop(0))
return res
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](#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 er en sammenligningsbasert sorteringsalgoritme, som bruker splitt-og-hersk-taktikken.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n\log n)$ || $O(n\log n)$ || $O(n^2)$ ||
I likhet med [Merge sort](#merge-sort), deler Quicksort problemet opp i mindre deler, og går så rekursivt til verks. Quicksort-funksjonen tar ett parameter, listen som skal sorteres. Tankegangen er som følger:
1. Er det bare ett element i listen? I så fall er listen sortert, returner den.
2. Velg et pivot-element. Det enkleste her kan være å velge det første elementet i lista.
3. Lag to lister, en (lo) som inneholder de elementene fra den opprinnelige lista med tallverdi mindre enn pivot-elementet, en annen (hi) som inneholder de elementene med høyere tallverdi.
4. Sorter lo og hi vha. Quicksort rekursivt. Returner lo + pivot + hi
I Python:
def quicksort(li):
if len(li) < 2:
return li
pivot = li[0]
lo = [x for x in li if x < pivot]
hi = [x for x in li if x > pivot]
return quicksort(lo) + pivot + quicksort(hi)
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.
#### Bubblesort
Traverserer listen, sammenligner to elementer og bytter plass på dem hvis nødvendig.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n)$ || $O(n^2)$ || $O(n^2)$ ||
#### Insertion Sort
Setter inn element _i_ på rett plass i den allerede sorterte lista av _i_-1 elementer.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n)$ || $O(n^2)$ || $O(n^2)$ ||
#### Selection sort
Veldig dårlig sorteringsalgoritme, søker gjennom hele lista og finner det minste elementet hver gang.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n^2)$ || $O(n^2)$ || $O(n^2)$ ||
### Andre sorteringsalgoritmer
Sorteringsalgoritmer som ikke er sammenligningsbaserte er ikke begrenset av $O(N*log(n)$ som nedre grense for kjøretid.
#### Heapsort
En heap er et binærtre der en nodes verdi aldri er høyere enn foreldrenodens verdi. En heap kan bygges i $O(n)$ tid.
Metodene for heap inkluderer:
|| Extract-max || $O(\log n)$ ||
|| Max-heapify || $O(\log n)$ ||
|| Max-heap-insert || $O(\log n)$ ||
|| Heap-increase-key || $O(\log n)$ ||
|| Heap-maximum || $\Theta(1)$ ||
Heapsort bygger en heap og plasserer det høyeste elementet på enden av lista, og vedlikeholder heapen med max-heapify.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n \log n)$ || $O(n \log n)$ || $O(n \log n)$ ||
#### 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.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(n + k)$ || $O(n + k)$ || $O(n + k)$ ||
Dersom $ k = O(n)$ , får vi kjøretid $ \Theta(n)$
#### Radix sort
Denne algoritmen antar at input er _n_ elementer med _d_ siffer i base _k_. Benytter en stabil søkemetode (for eksmpel counting sort), og ser på det minst signifikante sifferet, og sorterer. Gjentar med det nest minst signifikante sifferet, osv.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| || || $\Theta(d(n+k))$ ||
#### Bucketsort
Denne algoritmen antar at input kommer fra en uniform fordeling. Bucket sort lager _n_ bøtter (tenk intervaller) med størrelse _k_ og sorterer hver bøtte for seg, med insertion sort.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| || $\Theta(n)$ || $O(n+k)$ ||
#### Topologisk sortering
# Grafer og grafalgoritmer
En graf er en matematisk struktur som brukes for å modellere _parvise relasjoner mellom objekter_, det vil si: en graf er en slags helhetlig oversikt over mange små enkelte relasjoner. I dette faget er grafer en av de viktigste datastrukturene, og har dermed mange tilhørende algoritmer.
## Representasjon
En graf kan se ut f.eks. som dette:
Hvordan kan vi representere dette i en datamaskin? I større systemer kan det være relevant å gjøre dette objektorienter, med et objekt som representerer en graf, som inneholder nodeobjekter, som har pekere til sine nabonodeobjekter. En mye vanligere måte er nabolister/-matriser.
### 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.
## Traversering
Nå som vi har en måte å representere en graf på i datamaskinen, ønsker vi gjerne å gjøre noe med. For de aller fleste vil det være naturlig å gå gjennom elementene i en liste slik de står i listen, fra begynnelse til slutt. På samme måte som at dette er en naturlig definert måte å traversere en liste på, ønsker vi å ha en tilsvarende veldefinert måte å gå gjennom en graf på. De to vanligste måtene å gjøre dette på heter dybde først søk og bredde først søk.
### Bredde først (BFS)
Bredde først søk er en graftraverseringsalgoritme/søkealgoritme som baserer seg på at den for hver gang den besøker en node legger til barna til noden i en gitt rekkefølge til i en kø. Mer konkret:
1. Gitt en graf, en startnode og en rekkefølge å legge til naboer i, oppretter vi en kø og legger startnoden inn i køen. Køen har nå kun ett element, nemlig startnoden.
2. Så lenge det er ett eller flere elementer i køen, ta ut det første elementet fra køen (dequeue), og legg naboene til dette elementet til i køen i gitt rekkefølge.
Dersom du søker etter et element i grafen, kan du terminere søket når BFS har oppdaget det elementet.
Kjøretid: $O(|V| + |E|)$
#### Traversering
Bredde først traversering er å skrive ut nodene på hvert nivå i treet, man går fra venstre mot høyre.
### Dybde først (DFS)
DFS bruker en stakk i stedet for en kø. Siden en stakk er LIFO, må man pushe barna til den nåværende noden på stakken i omvendt rekkefølge. Mer konkret:
1. Gitt en graf, en startnode og en rekkefølge å legge til naboer i, oppretter vi en stakk, og legger startnoden inn i stakken. Stakken har nå kun ett element, nemlig startnoden.
2. Så lenge det er ett eller flere elementer i stakken, pop det øverste elementet, og legg (push) barna på stakken, i motsatt rekkefølge. Altså hvis rekkefølgen på barna er A, B, C, må de legges på stakken i rekkefølgen C, B, A.
Ved å merke start- og slutt-tider kan DFS brukes til [topologisk sortering](#topologisk-sortering).
Kjøretid: $O(|V| + |E|)$
#### 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.
I in-order rekkefølge legger vi noden til lista når vi er rett på undersida av noden.
I post-order rekkefølge legger vi noden til lista når vi passerer dem på høyre side.
|| __Traverseringsmetode__ || __Visualisering__ || __Resultat__ ||
|| Pre-order ||  || F, B, A, D, C, E, G, I, H ||
|| In-order ||  || A, B, C, D, E, F, G, H, I ||
|| Post-order ||  || A, C, E, D, B, H, I, G, F ||
## Minimale spenntrær
Et minimalt spenntre er et tre som er innom alle nodene nøyaktig én gang, og som har den lavest mulige kombinerte kantvekten.
### Kruskal
Kruskals algoritme lager treet ved å alltid velge den minste trygge veien som er tilgjengelig.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| || || $O(E \log V)$||
### Prim
Prims algoritme lager treet ved å starte i en node og legger til trygge kanter. Kjøretiden avhenger av datastrukteren som velges, pensum bruker en binærheap.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| || || $O(E \log V)$||
## Korteste vei
Det å finne korteste vei gjennom en graf brukes veldig ofte. For eksempel hvis en skal kjøre fra ett sted til et annet, eller for å finne den veien gjennom et elektrisk anlegg som gir minst motstand totalt.
Generelt deles korteste vei-problemer inn i mindre delproblemer, der en ser på korteste delstrekninger.
Typiske problemer en må være obs på før valg av algoritme er:
* Er grafen rettet eller urettet?
* Finnes det sykler i en rettet graf? Dersom en sykel finnes, kan det alltid finnes en kortere vei som ikke har med sykelen.
* Finnes det negative kanter?
* Dannes det negative sykler? En negativ sykel kan gjøre en node umulig å nå.
### En til alle
Det er ofte nyttig å vite hvordan en graf kan traverseres, og finne avstanden mellom to eller flere noder.
#### Dijkstras algoritme
Dijkstras algoritme fungerer bare hvis kantvektene er ikke-negative.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| || || $O(|E| + |V|*\log |V|)$ ||
Dersom det finnes negative sykler, vil ikke algoritmen terminere som normalt. Det går selvsagt an å legge inn en alternativ stopp-metode, men da kan resultatet bli feil.
Dijkstras er mest effektiv når det brukes en heap. Andre måter å implementere den på fører til potensielt høyere kjøretid, og er ikke pensum.
Algoritmen funker sånn som dette
1. Initialiser avstander. Sett startnoden til 0, og alle andre til +inf
2. Initialiser besøkt. Sett startnoden til besøkt, og alle andre til ikke besøkt.
3. Se på alle naboene, beregn avstand, oppdater avstander.
4. Oppdater avstander.
5. Gå til den noden som er "nærmest", og merk den som lest.
6. Gjenta steg 3-5 helt til alle er besøkt eller en eventuell sluttnode er besøkt.
I python:
def dijkstra(G,start): #G er grafen, start er startnoden
pq = PriorityQueue() # initialiserer en heap
start.setDistance(0) # Initialiserer startnodens avstand
pq.buildHeap([(node.getDistance(),node) for node in G]) # Lager en heap med alle nodene
while not pq.isEmpty():
currentVert = pq.delMin() # velger greedy den med kortest avstand
for nextVert in currentVert.getConnections():
newDist = currentVert.getDistance() + currentVert.getWeight(nextVert) #kalkulerer nye avstander
if newDist < nextVert.getDistance():
nextVert.setDistance( newDist ) # oppdaterer avstandene
nextVert.setPred(currentVert) # Oppdaterer foreldrene til den med kortest avstand
pq.decreaseKey(nextVert,newDist) # lager heapen på nytt så de laveste kommer først.
#### Bellman-Ford
Bellman-Ford fungerer også hvis det finnes negative kantvekter.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| || || $O(|V|*|E|)$ ||
Bellman-Ford er rekursivt definert. I motsetning til Dijkstra, relaxer Bellman-Ford alle kantene. Det er på denne måten negative sykler oppdages. Alle kantene relaxes $V - 1$ ganger, og det er etter dette den tester om det finnes negative sykler.
Algoritmen fungerer sånn som dette:
1. Initialiser algoritmen ved å sette avstand fra startnoden til startnoden lik 0, og alle andre avstander lik +inf
2. Sammenlign alle avstander, og oppdater hver node med den nye avstanden.
3. Sjekk om det finnes negative sykler
I python:
def bellman_ford(G, s) # G er grafen, med noder og kantvekter. s er startnoden.
distance = {}
parent = {}
for node in G: # Initialiserer startverdier
distance[node] = float('Inf')
parent[node] = None
distance[s]=0 # initialiserer startnoden
# relax
for (len(G)-1):
for u in G: # fra node u
for v in G[u]: # til naboene
if distance[v] > distance[u] + G[u][v]: # Sjekker om avstanden er mindre
distance[v] = distance[u] + G[u][v] # hvis ja, oppdaterer avstanden
parent[v]=u # og oppdaterer parent
# sjekk negative sykler
for u in G:
for v in G[u]:
if distance[v] > distance[u] + G[u][v]:
return False
#### DAG shortest path
Korteste vei en til alle. Gitt en DAG kan man først gjøre en [topologisk sortering](#topologisk-sortering) for så å traversere sorteringen og relaxe alle kantene som traverseres.
Psuedokode fra Cormen:
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
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $\Theta(|V| + |E|)$ || $\Theta(|V| + |E|)$ || $\Theta(|V| + |E|)$ ||
### Alle til alle
#### 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:
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u,v)
5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)
6 for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[i][j] > dist[i][k] + dist[k][j]
10 dist[i][j] ← dist[i][k] + dist[k][j]
11 end if
I Python:
def FloydWarshall(W):
n = len(W)
D = W
PI = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(n):
if(i==j or W[i][j] == float('inf')):
PI[i][j] = None
else:
PI[i][j] = i
for k in range(n):
for i in range(n):
for j in range(n):
if D[i][j] > D[i][k] + D[k][j]:
D[i][j] = D[i][k] + D[k][j]
PI[i][j] = PI[k][j]
return (D,PI)
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $\Theta(|V|^3)$ || $\Theta(|V|^3)$ || $\Theta(|V|^3)$ ||
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.
## Maksimal flyt
Flyt kan visualiseres ved for eksempel et rørsystem for å levere vann i en by, eller som et nettverk med ulik kapasitet på de ulike kablene. Maks flyt er hvor mye som faktisk strømmer gjennom nettverket. Det kan finnes kanter med veldig liten kapasitet som hindrer flyt, så uansett om alle de andre kantene har stor kapasitet, vil maks flyt avhenge av den minste kanten dersom det ikke er noen vei rundt den. Maksimal flyt er nådd hvis og bare hvis residualnettverket ikke har flere flytforøkende stier.
### 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 supersluken. 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.
### Flytøkende sti
En flytøkende sti er en sti fra starten til en node, som øker total flyt i nettverket. Denne kan vi finne ved å se på residualnettverket.
### 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_.
|| __Best Case__ || __Average Case__ || __Worst Case__ ||
|| $O(V*E^2)$ || || $O(E_f)$||
#### Edmonds-Karp
Edmonds-Karp er Ford-Fulkersons metode der BFS er traverseringsmetoden. Dette sikrer en kjøretid på $O(V*E^2)$.
###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.
# Dynamisk programmering
Dynamisk programmering deler opp problemer i mindre delproblemer, akkurat som splitt og hersk. Dynamisk programmering brukes når underproblemene overlapper, eller at underproblemene deler underproblemer. Det går ofte an å bruke splitt og hersk på denne typen problemer, men da gjøres det unødvendig mye arbeid siden den løser underproblemet hver gang. Dynamisk programmering løser underproblemet én gang, og bruker så det resultatet mange ganger.
## Lengste felles understreng
Løses med dynamisk programmering fra bunnen og opp, ved å se på det siste elementet i hver liste.
## Rod-cutting
Gitt en stav med lengde n, og en liste med priser for alle lengder kortere enn n. Avgjør hva maksimal fortjeneste blir ved å kutte den opp og selge den.
# Grådige algoritmer
Noen ganger er dynamisk programmering litt overkill. Grådige algoritmer velger den løsningen som ser best ut akkurat nå, og går videre. Dette fører ikke alltid til den beste løsningen, men for mange problemer fungerer det fint. Minimale spenntrær er et eksempel på en grådig metode.Grådige algoritmer løser problemet hvis det har disse egenskapene:
- $Greedy-choice\ property$ Vi kan ta et valg som virker best i det øyeblikk og løse subproblemene som dukker opp senere. Valget gjort av grådige valg kan ikke være avh. av fremtidige valg/alle løsningene til problemet så langt. Den tar iterativt et grådig valg etter hverandre og reduserer hvert gitte problem til et mindre et.
- $Optimal\ substruktur$.
## Planlegging av aktiviteter
Velg så mange ikke-overlappende aktiviteter som mulig. Anta at de er sortert etter sluttid og bruk en grådig algoritme til å velge dem.
## Huffmans algoritme
Huffmans algoritme er en grådig algoritme med formål å minimere lagringsplassen til en kjent sekvens med symboler. Hvert symbol kan representeres av en binær kode av lik lengde. Ved å telle antall hendelser av hvert symbol og bygge et binærtre basert på frekvensene kan man redusere antall bits som trengs til å lagre sekvensen med 20%-90%.
Huffman utføres ved å alltid legge sammen de nodene med minst verdi, også bruke summen av verdiene som en ny node. Ved å la en gren til venstre være $0$ og en gren til høyre være $1$ vil alle symbolene kunne representeres med en unik binær kode. De symbolene som brukes hyppigst vil få en kortere kode en de som brukes sjeldnere.
Kjøretid:
|| __Best case__ || __Average case__ || __Worst case__ ||
|| $O(n \lg n)$ || $O(n \lg n)$ || $O(n \lg n)$ ||
En verson av huffman kan i praksis se slik ut:
# Problemkompleksitet
## P, NP, NPC
Spørsmålet knyttet til om $P$ = $NP$ eller ikke er ett av de syv gjenværende Millennium-problemene.
Man vet at $P$ er et subsett av $NP$, men man vet ikke om $P=NP$.
|| P || Polynomial time || ||
|| NP || Nondeterministic polynomial time || ||
|| NPC || Nondeterministic polynomial time complete || ||
|| NPH || Nondeterministic polynomial time hard || ||
At et problem er P, vil si at det er løsbart i polynomisk tid. Et NP-problem er et problem hvor vi gitt en løsning kan vi bevise at denne er sann (verifisere), i polynomisk tid. Dersom man klarer å falsifisere løsningen i polynomisk tid, er problemet en del av co-NP-klassen. NP-harde problemer kan ikke løses i polynomisk tid. Det sies å være en klasse av problemer som er minst like vanskelige som det vanskeligste problemet i NP-klassen. Sagt på en annen måte: problemer som lar seg redusere til NP-problemer i polynomisk tid, men som ikke nødvendigvis lar seg verifisere i polynomisk tid med en gitt løsning. NP-harde problemer som lar seg verifisere i polynomisk tid kalles NP-komplette.
### 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_2$) er polynomisk-tid redusertbart til et annet språk ($L_1$): $L_1 \leq_p L_2$. Altså tar det polynomisk tid å representere $L_2$ som $L_1$.
### Noen kjente NPC problemer
Noen vanlige eksempler på problemer som er NPC:
- Circuit-SAT
- SAT
- 3-CNF-SAT
- Klikk-problemet (Clique)
- Vertex-Cover
- Hamilton sykel (Hamilton-Cycle)
- Travelling Salemsan (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. Ved å kjenne til et problem som er "litt enklere" og som er i NP-hard, kan vi redusere problemet til dette ved å vite at vårt problem er minst like vanskelig som det vi reduserer problemet til.
Gitt at $P$ != $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.
$HAM-CYCLE \leq_P TSP$.
Da de aller fleste til nå _tror_ at $P$ != $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$ != $NP$ eller at $P$ = $NP$, så har du krav på en rimelig stor pengepremie.
# Kjøretider til pensum-algoritmer
## Sortering og velging
- $n$ er antallet elementer som skal jobbes med.
- $k$ er den høyeste verdien tallene kan ha.
- $d$ er maks antall siffer et tall kan ha.
|| __Algoritme__ || __Best case__ || __Average case__ || __Worst case__ ||
|| Insertion sort || $O(n)$ || $O(n^2)$ || $O(n^2)$ ||
|| Selection sort || $O(n^2)$ || $O(n^2)$ || $O(n^2)$ ||
|| Merge sort || $O(n \lg n)$ || $O(n \lg n)$ || $O(n \lg n)$ ||
|| Heapsort || $O(n \lg n)$ || $O(n \lg n)$ || $O(n \lg n)$ ||
|| Quicksort || $O(n \lg n)$ || $O(n \lg n)$ || $O(n^2)$ ||
|| Bubble sort || $O(n)$ || $O(n^2)$ || $O(n^2)$ ||
|| Bucket sort || $O(n + k)$ || $O(n + k)$ || $O(n^2)$ ||
|| Counting sort || $O(n + k)$ || $O(n + k)$ || $O(n + k)$ ||
|| Radix sort || $O(d(n + k))$ || $O(d(n + k))$ || $O(d(n + k))$ ||
|| Select || $O(n)$ || $O(n)$ || $O(n)$ ||
|| Randomized select || $O(n)$ || $O(n)$ || $O(n^2)$ ||
## Heap-operasjoner
|| __Operasjon__ || __Tid__ ||
|| Insert || $O(\lg n)$ ||
|| Delete || $O(\lg n)$ ||
|| Build || $O(n)$ ||
## Graf-operasjoner
|| __Algoritme__ || __Best case__ || __Average case__ || __Worst case__ ||
|| Topologisk sort || $\Theta(V + E)$ || $\Theta(V + E)$ || $\Theta(V + E)$ ||
|| Dybde-først-søk || $O(E+V)$ || $O(E+V)$ || $O(E+V)$ ||
|| Bredde-først-søk || $O(E+V)$ || $O(E+V)$ || $O(E+V)$ ||
|| Prims || $O(E \lg V)$ || $O(E \lg V)$ || $O(E \lg V)$ ||
|| Kruskals || $O(E \lg V)$ || $O(E \lg V)$ || $O(E \lg V)$ ||
|| Bellmann-Ford || $O(VE)$ || $O(VE)$ || $O(VE)$ ||
|| Dijkstra || $O(V \lg V + E) $ || $O(V^2)$ || $O(V^2)$ ||
|| Floyd-Warshall || $O(V^3)$ || $O(V^3)$ || $O(V^3)$ ||
|| DAG-shortest-path || $O(V+E)$ || $O(V+E)$ || $O(V+E)$ ||
## Andre algoritmer