6.P Prøver til del 6: Dynamisk programmering, grådighet og stabil matching
Fire prøver som dekker del 6 (dynamisk programmering, grådighet og stabil matching) på eksamensnivå, med fulle løsningsforslag.
De kan trygt deles over flere kvelder — én prøve per økt er en fin rytme.
Alle oppgaver er nyskrevne og satt i eksamens sjangre, og løsningsforslagene
viser formen som gir uttelling, med delpoeng-notat der oppgaven har flere ledd.
- Prøve 6.A (30 min): mekanikken i dynamisk programmering — overlappende
delproblemer, memoisering mot utfylling nedenfra og opp, og rekonstruksjon.
Dekker kap. 6.1.
- Prøve 6.B (40 min): DP-design — rekurrens, tabell og rekonstruksjon.
Dekker kap. 6.2 og
kap. 6.3.
- Prøve 6.C (30 min): grådighet — Huffman-tre og bytteargument. Dekker
kap. 6.4.
- Prøve 6.D (30 min): stabil matching — blokkerende par og begge
orienteringer av Gale-Shapley. Dekker
kap. 6.5.
Hvor flervalget bor. Prøve 6.A avsluttes med en flervalgsblokk som ligger
inline i prøveteksten, med bokstavsvar i fasiten. De interaktive
flervalgsspørsmålene finner du i quizen til hvert av kapitlene i delen — de er
et annet verktøy, laget for repetisjon.
Slik bruker du prøvene. Ta én prøve på tid, uten fasit og uten oppslag.
Eksamen i TDT4120 er en firetimers skoleeksamen uten hjelpemidler
(hjelpemiddelkode E er NTNUs kode for nettopp det), med rundt 20 korte
frisvarsoppgaver som teller likt. Det betyr at kjøretider, definisjoner og
pseudokode må sitte i hodet — og at et langt svar koster tid du trenger på de
19 andre oppgavene. Skriv derfor svarene like kort som fasitene her gjør.
Tidsanslagene er arbeidstid. Legg på noen minutter til å lese oppgavene og lese
gjennom svaret til slutt.
Forkunnskaper
Prøvene forutsetter hele Del 6: kap. 6.1 om mekanikken
i dynamisk programmering, kap. 6.2 om stavkapping, LCS
og ryggsekk, drillen i kap. 6.3,
kap. 6.4 om grådighet og Huffman, og
kap. 6.5 om Gale-Shapley.
Fra tidligere deler trengs asymptotisk notasjon
(kap. 1.1), rekursjon og rekurrenser
(kap. 1.5), og prioritetskøen som Huffman bygger på
(kap. 3.1).
Fra Del 5 hentes ett begrep inn igjen i oppgave 6.B.3: pseudopolynomisk. Det
sto der slik: en algoritme er pseudopolynomisk når kjøretiden er polynomisk i
TALLVERDIENE i inputen, men ikke i lengden på den. Kapasiteten i et
ryggsekkproblem skrives med omtrent siffer, så er
eksponentiell i antall siffer. Ford-Fulkerson er pseudopolynomisk av samme
grunn (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 Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.