Verktøy

Begreper

01 Grunnlag

Asymptotisk notasjon #: Et presist språk for øvre og nedre grenser på vekst. Notasjonen beskriver funksjoner, ikke bare bestemte tilfeller som worst-case: $O$ gir øvre grense, $\Omega$ nedre, og $\Theta$ en stram grense.
RAM-modellen #: En idealisert maskinmodell der grunnleggende operasjoner og tilgang til én celle tar konstant tid. Den gjør kjøretidsanalyse sammenlignbar på tvers av maskiner.
Problem og instans #: Et problem er den generelle oppgaven; en instans er én konkret input. Problemstørrelsen er målet vi analyserer kjøretiden mot.
Løkkeinvariant #: En påstand som er sann før og etter hver iterasjon. Bevises med initialisering, vedlikehold og avslutning, og brukes til å vise at løkken bygger riktig resultat.
Induksjon #: Bevismetode der grunntilfeller etableres først, og større tilfeller begrunnes ved å anta at mindre tilfeller fungerer.
Reduksjon #: En transformasjon som lar oss løse eller sammenligne problemer ved å bruke en løsning på et annet problem. For å vise at $X$ er vanskelig reduserer vi fra et kjent vanskelig problem til $X$ .

Splitt og hersk #: Del instansen i mindre delinstanser, løs dem rekursivt, og kombiner resultatene når det trengs.
Rekurrens #: En ligning for kjøretid uttrykt ved kjøretiden til mindre instanser. Løses med substitusjon, rekursjonstrær eller masterteoremet.

Nedre grense for sammenligningssortering #: Alle sammenligningsbaserte sorteringsalgoritmer må skille mellom $n!$ mulige rekkefølger, som krever $\Omega(n \lg n)$ sammenligninger i verste fall.
Stabil sortering #: Like elementer beholder relativ rekkefølge. Avgjørende når sortering gjentas på flere nøkler, som i radix-sortering.

Haug #: Et nesten komplett tre lagret kompakt i en tabell, der forelderen har prioritet over barna. Brukes ofte som prioritetskø.
Binært søketre #: Et tre der alt i venstre deltre er mindre enn rota og alt i høyre deltre er større — rekursivt for alle noder.

Dynamisk programmering #: Brukes når delinstanser overlapper. Vi lagrer delløsninger og beregner dem i en rekkefølge som respekterer avhengighetene i delinstansgrafen.
Grådig valg #: Et lokalt valg som kan inngå i en optimal løsning. Riktig grådighet krever også optimal delstruktur.
Binært ryggsekkproblem #: Velg hele gjenstander med verdi og vekt under en kapasitet. Den klassiske DP-en er $\Theta(nW)$ , men dette er pseudopolynomisk — ikke polynomisk i instansens størrelse.

Graftraversering #: Systematisk utforsking av noder ved å holde orden på oppdagede, men ikke ferdigbehandlede noder.
Bredde-først-søk #: Traverserer lag for lag fra startnoden. I uvektede grafer gir dette korteste veier målt i antall kanter.
Dybde-først-søk #: Følger én gren dypt før den rygger tilbake. Tidsstempler og foreldre gir struktur til topologisk sortering og sterkt sammenhengende komponenter.
Disjunkte mengder #: En datastruktur for å vedlikeholde en partisjon av elementer, med operasjonene Make-Set, Find-Set og Union. Kalles også union-find.
Minimalt spenntre #: Et sett kanter som kobler alle noder uten sykler og med lavest mulig total vekt.
Kantoppdatering #: Forsøk på å forbedre et avstandsestimat ved å gå via én kant. Dette er kjernen i Bellman-Ford, DAG-korteste veier og Dijkstra.
Dijkstras algoritme #: Velger alltid noden med lavest avstandsestimat. Korrektheten avhenger av at kantvektene ikke er negative.
Alle-til-alle korteste veier #: Finn korteste veier mellom alle par av noder. Tette grafer gjør dynamisk programmering spesielt nyttig her.
Maksimal flyt #: Send mest mulig flyt fra kilde til sluk uten å bryte kapasiteter eller flytbevaring.
Restnett #: Grafen over hvor flyt kan økes, reduseres eller flyttes. Forøkende stier finnes i restnettet, og bakoverkanter representerer muligheten til å angre tidligere flyt.

NP-kompletthet #: Et NP-komplett beslutningsproblem ligger i NP og er minst like vanskelig som alle problemer i NP under polynomiske reduksjoner.
Karp-reduksjon #: En polynomisk transformasjon fra én beslutningsinstans til en annen, slik at ja/nei-svaret bevares. Kalles også mange-til-én-reduksjon.