Hopp til innhold
TDT4120
Algoritmer og datastrukturer
Interaktiv pensumguide · H2026
Fremgang
0/15
Søk
⌘K
Esc
Alle emner
Oversikt
Verktøy
Formelsamling
Begreper
Flashcards
Eksamen
Del 1: Grunnlag
01
Algoritmer og kompleksitet
02a
Datastrukturer
02b
Problemer og reduksjoner
Del 2: Sortering og datastrukturer
03
Splitt og hersk
04
Rangering i lineær tid
05
Rotfaste trestrukturer
Del 3: Designmetoder
06
Dynamisk programmering
07
Grådighet
Del 4: Grafer og flyt
08
Traversering av grafer
09
Minimale spenntrær
10
Korteste vei fra én til alle
11
Korteste vei fra alle til alle
12
Maksimal flyt
Del 5: Kompleksitet
13
NP-kompletthet
14
NP-komplette problemer
Lenker
Algdat-nettsiden
Flashcards
0
/
15
kan
Nullstill
Alle
Grunnlag
Alle
Grunnlag
Kun ukjente
Grunnlag
Hva er forskjellen på et problem og en instans?
Snu
Grunnlag
Problemet er relasjonen mellom input og output, for eksempel «outputen er en stigende omordning av inputen». Instansen er én bestemt input, for eksempel
⟨
6
,
8
,
3
,
5
⟩
\langle 6, 8, 3, 5 \rangle
⟨
6
,
8
,
3
,
5
⟩
.
Kan
Grunnlag
Hva koster én operasjon i RAM-modellen, og hvor brede er heltallene?
Snu
Grunnlag
Aritmetikk, sammenligning, hopp og oppslag i én celle koster én tidsenhet hver. Heltallene er om lag
c
lg
n
c \lg n
c
l
g
n
bits brede, akkurat nok til å indeksere hele inputen.
Kan
Grunnlag
Skriv definisjonen av
f
(
n
)
=
O
(
g
(
n
)
)
f(n) = O(g(n))
f
(
n
)
=
O
(
g
(
n
))
.
Snu
Grunnlag
Det finnes konstanter
c
>
0
c > 0
c
>
0
og
n
0
n_0
n
0
slik at
0
≤
f
(
n
)
≤
c
g
(
n
)
0 \le f(n) \le c\,g(n)
0
≤
f
(
n
)
≤
c
g
(
n
)
for alle
n
≥
n
0
n \ge n_0
n
≥
n
0
.
Kan
Grunnlag
Skriv definisjonen av
f
(
n
)
=
Θ
(
g
(
n
)
)
f(n) = \Theta(g(n))
f
(
n
)
=
Θ
(
g
(
n
))
.
Snu
Grunnlag
Det finnes
c
1
,
c
2
>
0
c_1, c_2 > 0
c
1
,
c
2
>
0
og
n
0
n_0
n
0
slik at
0
≤
c
1
g
(
n
)
≤
f
(
n
)
≤
c
2
g
(
n
)
0 \le c_1 g(n) \le f(n) \le c_2 g(n)
0
≤
c
1
g
(
n
)
≤
f
(
n
)
≤
c
2
g
(
n
)
for alle
n
≥
n
0
n \ge n_0
n
≥
n
0
. Altså både
O
(
g
)
O(g)
O
(
g
)
og
Ω
(
g
)
\Omega(g)
Ω
(
g
)
.
Kan
Grunnlag
Hva skiller
o
o
o
fra
O
O
O
, og
ω
\omega
ω
fra
Ω
\Omega
Ω
?
Snu
Grunnlag
O
O
O
og
Ω
\Omega
Ω
tillater at
f
f
f
og
g
g
g
vokser like raskt.
o
o
o
og
ω
\omega
ω
gjør ikke det: de krever ulikheten for enhver
c
>
0
c > 0
c
>
0
, som er det samme som at
f
/
g
f/g
f
/
g
går mot
0
0
0
eller mot uendelig. Derfor er
2
n
2
=
O
(
n
2
)
2n^2 = O(n^2)
2
n
2
=
O
(
n
2
)
, mens
2
n
2
≠
o
(
n
2
)
2n^2 \ne o(n^2)
2
n
2
=
o
(
n
2
)
.
Kan
Grunnlag
Oversett de fem operatorene til sammenligning av tall.
Snu
Grunnlag
O
O
O
er
a
≤
b
a \le b
a
≤
b
,
Ω
\Omega
Ω
er
a
≥
b
a \ge b
a
≥
b
,
Θ
\Theta
Θ
er
a
=
b
a = b
a
=
b
,
o
o
o
er
a
<
b
a < b
a
<
b
og
ω
\omega
ω
er
a
>
b
a > b
a
>
b
. Unntaket er at to funksjoner kan mangle et forhold helt, mens to tall alltid kan sammenlignes.
Kan
Grunnlag
Betyr
O
O
O
alltid verste tilfelle?
Snu
Grunnlag
Nei.
O
O
O
er en øvre grense og kan brukes på hvilken som helst kjøretidsfunksjon, også beste tilfelle. Grense og tilfelle er to uavhengige akser.
Kan
Grunnlag
Hva betyr det at verste tilfelle er
Ω
(
n
2
)
\Omega(n^2)
Ω
(
n
2
)
?
Snu
Grunnlag
Den dyreste instansen av størrelse
n
n
n
koster minst kvadratisk tid. Det er en nedre grense for et maksimum, på samme vis som «den høyeste i klassen er minst 1 m høy».
Kan
Grunnlag
Forenkle
O
(
n
a
)
+
Ω
(
n
b
)
+
Θ
(
n
c
)
O(n^a) + \Omega(n^b) + \Theta(n^c)
O
(
n
a
)
+
Ω
(
n
b
)
+
Θ
(
n
c
)
.
Snu
Grunnlag
Ω
(
n
b
+
n
c
)
\Omega(n^b + n^c)
Ω
(
n
b
+
n
c
)
. Summer nedre grenser (
0
+
n
b
+
n
c
0 + n^b + n^c
0
+
n
b
+
n
c
) og øvre for seg. De øvre er ubegrenset fordi
Ω
(
n
b
)
\Omega(n^b)
Ω
(
n
b
)
ikke setter noe tak, så bare den nedre står igjen.
Kan
Grunnlag
Hvorfor er
n
+
O
(
n
)
=
O
(
n
)
n + O(n) = O(n)
n
+
O
(
n
)
=
O
(
n
)
riktig, mens
O
(
n
)
=
n
+
O
(
n
)
O(n) = n + O(n)
O
(
n
)
=
n
+
O
(
n
)
er galt?
Snu
Grunnlag
Ligninger med asymptotisk notasjon leses fra venstre mot høyre, og høyresiden må være minst like generell som venstresiden. Ikke alt som er
O
(
n
)
O(n)
O
(
n
)
kan skrives som
n
n
n
pluss noe som er
O
(
n
)
O(n)
O
(
n
)
.
Kan
Grunnlag
De tre delene i et løkkeinvariant-bevis?
Snu
Grunnlag
Initialisering (invarianten holder før første iterasjon), vedlikehold (holder den før en iterasjon, holder den før den neste), og terminering (løkka stopper, og invarianten gir da det vi var ute etter).
Kan
Grunnlag
Hva skiller svak fra sterk induksjon?
Snu
Grunnlag
Svak induksjon antar bare forrige trinn og passer til løkker. Sterk induksjon antar alle mindre tilfeller, og passer når en algoritme kaller seg selv på flere mindre instanser.
Kan
Grunnlag
Hva er løkkeinvarianten til Insertion-Sort?
Snu
Grunnlag
A
[
0
:
i
]
A[0 : i]
A
[
0
:
i
]
er sortert ved starten av hver iterasjon av for-løkka, og består av de elementene som lå der fra begynnelsen.
Kan
Grunnlag
Insertion-Sort i beste og i verste tilfelle?
Snu
Grunnlag
Θ
(
n
)
\Theta(n)
Θ
(
n
)
når tabellen er sortert fra før og ingen forskyvninger trengs.
Θ
(
n
2
)
\Theta(n^2)
Θ
(
n
2
)
når den er sortert synkende, med
n
(
n
−
1
)
/
2
n(n-1)/2
n
(
n
−
1
)
/2
forskyvninger.
Kan
Grunnlag
Hvor stor
n
n
n
rekker en faktoriell og en kvadratisk algoritme på hundre år, ved ett mikrosekund per operasjon?
Snu
Grunnlag
17 mot rundt 56 millioner. En eksponentiell algoritme kommer til 51.
Kan
Ingen kort matcher filteret.
Øv
Kan
1
/
15
←→
bla ·
mellomrom
snu ·
1
øv ·
2
kan