TDT4120 Algoritmer og datastrukturerTilbake

4.P Prøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei

Alle fag for Høyskole

4.P Prøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei

Fire prøver som dekker del 4 (grafalgoritmer: traversering, spenntrær og korteste vei) på eksamensnivå, med fulle løsningsforslag.

120 min

0 oppgaver

Prøver til del 4Grafalgoritmertraverseringspenntrærkorteste vei

Din fremgang i kapitlet

0 / 0 oppgaver

Kapitlets plass i kurset

Bygger på

4.5DRILL — Håndkjøring av grafalgoritmer

Fire prøver à ~30–35 min: prøve 4.A (30 min), 4.B (30 min), 4.C (35 min) og 4.D (35 min) — 130 minutter til sammen. Prøvene kan trygt deles over flere kvelder; én prøve per økt er den anbefalte rytmen, og grafdelen er den delen der det lønner seg mest å håndkjøre med penn.

Dekning. Grafrepresentasjon og traversering er telt i 14 av de 17 settene i grunnlaget (82 %), minimale spenntrær i 14 av 17 (82 %), korteste vei fra én kilde i 13 av 17 (76 %), alle-til-alle korteste vei i 11 av 17 (65 %) og topologisk sortering i 7 av 17 (41 %). Prøvene fordeler seg etter dette: 4.A traversering og topologisk sortering, 4.B spenntrær, 4.C korteste vei fra én kilde, 4.D matrisealgoritmene.

Sjangrene du møter her, skrevet ut i klarspråk:

- sjanger C — håndkjøring: du utfører algoritmen steg for steg og oppgir bare sluttilstanden — kantrekkefølgen, finish-tidene, d-verdiene eller den etterspurte matrisen.
- sjanger D — definisjon med egne ord: én presis setning, hovedpoenget først.
- sjanger E — kjøretid: ett uttrykk, med grafstørrelsene skrevet $V$ og $E$ .
- sjanger F — «stemmer dette?»: ja eller nei først, deretter én setning.

Hvor flervalget bor. De statiske flervalgsoppgavene står inline i prøveteksten under, med alternativer merket a)–d) og fasitbokstaven i løsningsforslaget. De interaktive flervalgsspørsmålene ligger i quizen til kapitlene i Del 4, ikke her.

Tidsbudsjett. Minuttallene er arbeidstid. Håndkjøring av grafalgoritmer tar lengre tid enn du tror første gang — det er derfor 4.C og 4.D har fem minutter ekstra hver.

Forkunnskaper

Prøvene hviler på hele Del 4:

- kap. 4.1 — grafrepresentasjon, BFS, DFS og topologisk sortering
- kap. 4.2 — minimale spenntrær med MST-Prim og MST-Kruskal
- kap. 4.3 — korteste vei fra én kilde
- kap. 4.4 — alle-til-alle korteste vei
- kap. 4.5 — drillen på håndkjøring av grafalgoritmene

Fra kap. 3.5 tar du med deg Union-Find: MST-Kruskal bruker Find-Set til å avgjøre om en kant ville laget en sykel, og Union til å slå sammen to komponenter.

Dette er det du trenger å ha friskt:

- Topologisk sortering bruker synkende finish-tid fra DFS, ikke starttid.
- BFS gir korteste vei målt i antall kanter, ikke i vekt.
- Snittegenskapen: en letteste kant som krysser et snitt som respekterer valgene så langt, er trygg. Betingelsen er ikke pynt — uten den er påstanden gal.
- Dijkstra krever ikke-negative kantvekter. Bellman-Ford tåler negative kanter og oppdager negative sykler som er nåbare fra kilden.
- Slakking: $d[v] > d[u] + w(u,v)$ gir $d[v] = d[u] + w(u,v)$ og $\pi[v] = u$ .
- Floyd-Warshall itererer $k$ ytterst: $d^{(k)}_{ij} = \min(d^{(k-1)}_{ij},\, d^{(k-1)}_{ik} + d^{(k-1)}_{kj})$ .

Prøve 4.A — Traversering og topologisk sortering (30 min)

Prøve 4.B — Minimale spenntrær med Kruskal (30 min)

Prøve 4.C — Korteste vei fra én kilde (35 min)

Prøve 4.D — Alle-til-alle korteste vei (35 min)

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.