Hopp til innhold
TDT4120 Algoritmer og datastrukturer
Interaktiv pensumguide · H2026
Fremgang
0/14
Søk
⌘K
Esc
Nullstill
Verktøy
Flashcards
0
/
30
kan
Nullstill
Alle
Grunnlag
Splitt og hersk
Sortering
Datastrukturer
Designmetoder
Grafer
Kompleksitet
Kun ukjente
Bland
Grunnlag
Hva betyr
f
(
n
)
=
Θ
(
g
(
n
)
)
f(n) = \Theta(g(n))
f
(
n
)
=
Θ
(
g
(
n
))
?
Snu
g
g
g
er både en øvre og en nedre asymptotisk grense for
f
f
f
— en stram grense.
Kan
Grunnlag
Betyr
O
O
O
alltid worst-case?
Snu
Nei.
O
O
O
er en øvre grense og kan beskrive hvilken som helst kjøretidsfunksjon — også best-case. Grense og tilfelle er uavhengige akser.
Kan
Grunnlag
De tre stegene i et løkkeinvariant-bevis?
Snu
Initialisering (sann før løkka), vedlikehold (bevares av hver iterasjon), avslutning (gir ønsket resultat når løkka stopper).
Kan
Grunnlag
Hvilken vei går en reduksjon for å vise at
X
X
X
er vanskelig?
Snu
Fra et kjent vanskelig problem TIL
X
X
X
. Da ville en rask løsning på
X
X
X
også løst det kjente vanskelige problemet.
Kan
Splitt og hersk
De tre stegene i splitt og hersk?
Snu
Del (splitt instansen), hersk (løs delinstansene rekursivt), kombiner (sett sammen delsvarene).
Kan
Splitt og hersk
Tre måter å løse en rekurrens?
Snu
Substitusjon (gjett + induksjon), rekursjonstre, og masterteoremet.
Kan
Splitt og hersk
Kjøretid og rekurrens for Merge-Sort?
Snu
T
(
n
)
=
2
T
(
n
/
2
)
+
Θ
(
n
)
=
Θ
(
n
lg
n
)
T(n) = 2T(n/2) + \Theta(n) = \Theta(n \lg n)
T
(
n
)
=
2
T
(
n
/2
)
+
Θ
(
n
)
=
Θ
(
n
l
g
n
)
.
Kan
Splitt og hersk
Worst-case for Quicksort, og når inntreffer det?
Snu
Θ
(
n
2
)
\Theta(n^2)
Θ
(
n
2
)
, ved maksimalt skjeve partisjoner (f.eks. allerede sortert input med dårlig pivot). Forventet
Θ
(
n
lg
n
)
\Theta(n \lg n)
Θ
(
n
l
g
n
)
.
Kan
Sortering
Nedre grense for sammenligningsbasert sortering?
Snu
Ω
(
n
lg
n
)
\Omega(n \lg n)
Ω
(
n
l
g
n
)
i worst-case — fordi
n
!
n!
n
!
rekkefølger må skilles i et beslutningstre med høyde
≥
lg
(
n
!
)
\geq \lg(n!)
≥
l
g
(
n
!)
.
Kan
Sortering
Hva er stabil sortering, og hvorfor trenger Radix-Sort den?
Snu
Like nøkler beholder relativ rekkefølge. Radix sorterer siffer for siffer, så lavere siffer må ikke ødelegges når et høyere siffer sorteres.
Kan
Sortering
Kjøretid for Counting-Sort?
Snu
Θ
(
n
+
k
)
\Theta(n + k)
Θ
(
n
+
k
)
der
k
k
k
er tallområdet. Lineær når
k
=
O
(
n
)
k = O(n)
k
=
O
(
n
)
; ikke sammenligningsbasert.
Kan
Sortering
Insertion-Sort: best- og worst-case?
Snu
Best
Θ
(
n
)
\Theta(n)
Θ
(
n
)
(nær sortert), worst
Θ
(
n
2
)
\Theta(n^2)
Θ
(
n
2
)
(omvendt sortert). In-place og stabil.
Kan
Datastrukturer
Haug-egenskapen i en maks-haug?
Snu
Hver forelder er
≥
\geq
≥
begge barna. Lokal egenskap — ikke total sortering.
Kan
Datastrukturer
Hvorfor er Build-Max-Heap
O
(
n
)
O(n)
O
(
n
)
og ikke
O
(
n
lg
n
)
O(n \lg n)
O
(
n
l
g
n
)
?
Snu
De fleste nodene er nær bladnivå med liten høyde; summen
∑
h
n
/
2
h
+
1
O
(
h
)
\sum_h n/2^{h+1}\,O(h)
∑
h
n
/
2
h
+
1
O
(
h
)
konvergerer til
O
(
n
)
O(n)
O
(
n
)
.
Kan
Datastrukturer
Søketre-egenskapen (BST)?
Snu
For hver node: alt i venstre deltre
<
<
<
noden
<
<
<
alt i høyre deltre, rekursivt.
Kan
Datastrukturer
Forventet høyde for et tilfeldig bygget BST med
n
n
n
noder?
Snu
O
(
lg
n
)
O(\lg n)
O
(
l
g
n
)
. Men worst-case (sortert innsetting) gir høyde
Θ
(
n
)
\Theta(n)
Θ
(
n
)
— derfor balanserte trær.
Kan
Designmetoder
Når lønner dynamisk programmering seg?
Snu
Når delinstansene OVERLAPPER (samme delproblem trengs flere ganger) og problemet har optimal delstruktur.
Kan
Designmetoder
Memoisering vs. bottom-up?
Snu
Memoisering = top-down rekursjon som husker svar. Bottom-up = iterativ fylling av tabellen i avhengighetsrekkefølge. Samme delproblemer.
Kan
Designmetoder
Hva må bevises for en grådig algoritme?
Snu
Grådighetsegenskapen (et lokalt valg er trygt) OG optimal delstruktur (resten er fortsatt et optimalt delproblem).
Kan
Designmetoder
Hvorfor er
Θ
(
n
W
)
\Theta(nW)
Θ
(
nW
)
-DP-en for ryggsekk ikke polynomisk?
Snu
W
W
W
kodes med
lg
W
\lg W
l
g
W
bit, så
Θ
(
n
W
)
\Theta(nW)
Θ
(
nW
)
er eksponensiell i instansens størrelse — pseudopolynomisk.
Kan
Grafer
Kjøretid for BFS og DFS med nabolister?
Snu
O
(
V
+
E
)
O(V + E)
O
(
V
+
E
)
— hver node og kant behandles konstant antall ganger.
Kan
Grafer
Hvorfor finner BFS korteste vei i uvektede grafer?
Snu
FIFO-køen behandler alle noder på avstand
k
k
k
før avstand
k
+
1
k+1
k
+
1
, så lagene utforskes i avstandsrekkefølge.
Kan
Grafer
Hva gjør
Relax
(
u
,
v
)
\text{Relax}(u, v)
Relax
(
u
,
v
)
?
Snu
Hvis
d
[
v
]
>
d
[
u
]
+
w
(
u
,
v
)
d[v] > d[u] + w(u,v)
d
[
v
]
>
d
[
u
]
+
w
(
u
,
v
)
, sett
d
[
v
]
←
d
[
u
]
+
w
(
u
,
v
)
d[v] \leftarrow d[u] + w(u,v)
d
[
v
]
←
d
[
u
]
+
w
(
u
,
v
)
og oppdater forgjengeren. Kjernen i alle korteste-vei-algoritmene.
Kan
Grafer
Når er en kant «trygg» i MST-bygging?
Snu
Når den er en lettest kant over et snitt som respekterer kantene valgt så langt — da finnes et optimalt MST som inneholder den.
Kan
Grafer
Dijkstra vs. Bellman-Ford — forskjellen?
Snu
Dijkstra:
O
(
(
V
+
E
)
lg
V
)
O((V+E)\lg V)
O
((
V
+
E
)
l
g
V
)
, krever ikke-negative vekter. Bellman-Ford:
O
(
V
E
)
O(VE)
O
(
V
E
)
, tåler negative kanter og oppdager negative sykler.
Kan
Grafer
DP-ideen i Floyd-Warshall?
Snu
Lag
k
k
k
: korteste vei når bare noder
1..
k
1..k
1..
k
tillates som mellomliggende. Bygg opp
k
=
0
,
1
,
…
,
V
k = 0,1,\dots,V
k
=
0
,
1
,
…
,
V
. Totalt
Θ
(
V
3
)
\Theta(V^3)
Θ
(
V
3
)
.
Kan
Grafer
Hva er restnettet i maks-flyt?
Snu
Grafen over hvor flyt kan endres gitt dagens flyt. Bakoverkanter lar oss angre tidligere flyt; forøkende stier finnes her.
Kan
Grafer
Hva sier maks-flyt/min-snitt-teoremet?
Snu
Verdien av en maksimal flyt = kapasiteten til et minimalt snitt. En flyt er maksimal nettopp når restnettet ikke har noen forøkende sti.
Kan
Kompleksitet
Hva kreves for å vise at et problem er NP-komplett?
Snu
(1) Vis at det ligger i NP (rask verifikasjon), og (2) vis at det er NP-hardt (reduksjon fra et kjent NP-komplett problem).
Kan
Kompleksitet
Hva er en Karp-reduksjon?
Snu
En polynomisk transformasjon av instanser fra ett beslutningsproblem til et annet som bevarer ja/nei-svaret (mange-til-én).
Kan
Øv
Kan
1
/
30
Ingen kort matcher filteret.