7.P Prøver til del 7: NP-kompletthet og reduksjoner
Fire prøver som dekker del 7 (np-kompletthet og reduksjoner) 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 7.A (25 min): definisjonene — P, NP, co-NP, sertifikat, og
avgjørelse mot optimering. Dekker kap. 7.1.
- Prøve 7.B (35 min): hva beviser reduksjonen? Dekker
kap. 7.2.
- Prøve 7.C (30 min): NPC-katalogen og ideen bak CIRCUIT-SAT-beviset.
Dekker kap. 7.3.
- Prøve 7.D (35 min): blandet NP-teori — ja/nei-utsagn og pseudopolynomisk
mot NP-hardt. Dekker kap. 7.2 og drillen i
kap. 7.4.
Hvor flervalget bor. Prøve 7.D 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.
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. Definisjonene i denne delen er blant de få
tingene i faget som må gjengis nesten ordrett, og de kommer i hvert eneste sett.
Tidsanslagene er arbeidstid. Legg på noen minutter til å lese oppgavene og lese
gjennom svaret til slutt.
Forkunnskaper
Prøvene forutsetter hele Del 7: kap. 7.1 om P, NP og
co-NP, kap. 7.2 om polynomiske reduksjoner og retningen
på dem, kap. 7.3 om de navngitte NP-komplette
problemene, og drillen i kap. 7.4.
Fra tidligere deler trengs asymptotisk notasjon
(kap. 1.1), grafbegrepene
(kap. 4.1), og maks-flyt med heltallsteoremet
(kap. 5.2) — den siste brukes i oppgave 7.D.2, der et
vaktfordelingsproblem skal skilles fra et NP-hardt problem.
Ett begrep hentes inn igjen her, fordi det er selve bindeleddet mellom Del 5,
Del 6 og Del 7: pseudopolynomisk. En algoritme er pseudopolynomisk når
kjøretiden er polynomisk i tallverdiene i inputen, men ikke i lengden på
inputen. 0-1-ryggsekk i er eksempelet fra
kap. 6.2: kapasiteten skrives med omtrent
siffer, så kjøretiden er eksponentiell i antall siffer.
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.