7.P Prøver til del 7: Datastruktur-design, drøfting og NP-teori
Fire prøver som dekker del 7 (datastruktur-design, drøfting og np-teori) på eksamensnivå, med fulle løsningsforslag.
dekker hele Del 7 — datastruktur-design, drøftingssjangeren, P og NP,
verifikatoren, reduksjonsretningen og avgrensningen av pensum. Alle oppgaver er
nyskrevne og satt i eksamens sjangre, og løsningsforslagene viser formen sensor
forventer, med poengfordeling per delmoment.
- Prøve 7.A (30 min): Datastruktur-design — mediankø med to heaps, bøttekø og
trie, med kjøretid per operasjon (sjanger J — ADT-design, altså at du velger og
kombinerer strukturer). Dekker kap. 7.1.
- Prøve 7.B (30 min): Drøft to strategier — definér , oppgi verste og
forventet kjøretid pluss minne, konkludér (sjanger K — drøft to strategier).
Dekker kap. 7.2.
- Prøve 7.C (25 min): P og NP, sertifikat og verifikator (sjanger C —
kjøretids- og teorifakta, og L — NP-kompletthet). Dekker
kap. 7.3. Her ligger en sant/usant-blokk med
antigjettings-skalering.
- Prøve 7.D (25 min): Reduksjonsretning og avgrensning av pensum (sjanger L).
Dekker kap. 7.3. Her ligger fem flervalgsspørsmål inline
i prøven, med bokstavsvar i fasiten.
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.
Prøvene kan trygt deles over flere kvelder — én prøve per økt. De fem
flervalgsspørsmålene står inline i prøve 7.D; den interaktive quizen til
kapitlene 7.1 til 7.3 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 svar, men
å levere alle delmomentene: strukturen valgt, antagelsene oppgitt, kjøretiden per
operasjon, og en konklusjon med en betingelse i.
Forkunnskaper
Prøvene forutsetter hele Del 7: kap. 7.1 om ADT-design med
mediankø, bøttekø og trie; kap. 7.2 om drøftingssjangeren
og de fire leddene; og kap. 7.3 om , , verifikatoren,
reduksjonsretningen og avgrensningen av pensum.
Fra tidligere deler trengs -notasjonen (kap. 1.1), de
faste P/NP-punktene (kap. 1.4), hashmap og hash-set
(kap. 3.2), min-heapen som array med indeks fra 0
(kap. 4.4) og grafrepresentasjonene
(kap. 5.1).
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.