6.P Prøver til del 6: Korteste vei, spenntrær og grådighet
Fire prøver som dekker del 6 (korteste vei, spenntrær og grådighet) på eksamensnivå, med fulle løsningsforslag.
dekker hele Del 6 — korteste-vei-matrisen, topologisk sortering, minimale
spenntrær, reversert Dijkstra og Huffman-koding. Alle oppgaver er nyskrevne og satt
i eksamens sjangre, og løsningsforslagene viser formen sensor forventer, med
poengfordeling per delmoment.
- Prøve 6.A (25 min): Korteste-avstander-matrisen og kjøretid per
grafalgoritme (sjanger F — matriseavkryssing, altså at du kobler egenskap til
algoritme). Dekker kap. 6.2 og
kap. 6.5. Her ligger fem flervalgsspørsmål inline i
prøven, med bokstavsvar i fasiten.
- Prøve 6.B (30 min): Topologisk sortering og sykeldeteksjon i pseudokode
(sjanger H — grafalgoritme i pseudokode). Dekker
kap. 6.1.
- Prøve 6.C (30 min): MST-modellering og reversert Dijkstra, velg lavest
kjøretid (sjanger H). Dekker kap. 6.2 og
kap. 6.3.
- Prøve 6.D (25 min): Huffman-kodelengder og MST-gjenkjenning (sjanger E —
håndkjøring, og F). Dekker kap. 6.3 og
kap. 6.4.
Slik bruker du dem: ta én prøve på tid, uten fasit og uten oppslag. Eksamen er
en firetimers digital skoleeksamen i Inspera — UiOs digitale eksamenssystem —
uten hjelpemidler. Du skriver alt, også pseudokode, rett inn i Inspera, og du
får ikke slå opp en eneste kjøretid. Å håndkjøre Prim på papir og skrive Dijkstra
fra hukommelsen er ferdigheter som bare øves på én måte.
Prøvene kan trygt deles over flere kvelder — én prøve per økt. De fem
flervalgsspørsmålene står inline i prøve 6.A; den interaktive quizen til
kapitlene 6.1 til 6.5 er den store flervalgsbanken, og den tas separat.
Åpne fasiten først når du er ferdig, og bruk selvdiagnose-lista nederst i hver
prøve. Husk at C er en god og vanlig karakter — målet er ikke plettfrie tavler,
men å levere alle delmomentene: problemet navngitt, antagelsene oppgitt,
algoritmen, og kjøretiden som matcher.
Forkunnskaper
Prøvene forutsetter hele Del 6: kap. 6.1 om topologisk
sortering og sykeldeteksjon; kap. 6.2 om
korteste-vei-matrisen, Dijkstra og reversert Dijkstra;
kap. 6.3 om minimale spenntrær med Prim og Kruskal;
kap. 6.4 om Huffman-koding; og drillen i
kap. 6.5.
Fra tidligere deler trengs -notasjonen (kap. 1.1),
løkketellingen (kap. 1.2), min-heapen som prioritetskø
(kap. 4.4) og BFS/DFS
(kap. 5.2).
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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.