8.2 DRILL — Åpen algoritmedesign via reduksjon

Den tverrgående designdrillen (sjanger H): gjenkjenn det klassiske problemet i en innpakning og reduser til det — maks-flyt, DP, Gale-Shapley, BFS.

90 min

10 oppgaver

DRILLÅpen algoritmedesign via reduksjon

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

7.4DRILL — Reduksjonsretning og NP-argumenter

Brukes videre i

8.3Øvingseksamen 1 — bredt ordinært sett (kode E)

De siste tre til fem oppgavene i hvert ordinære sett er åpne
designoppgaver. Det er der toppkarakteren avgjøres, og det er den ene
sjangeren som trekker på hele pensum samtidig.

Sjangeren er én:

- Sjanger H — åpen algoritmedesign, altså at du får et problem i ny
innpakning og skal skissere en algoritme på fem til ti linjer. Svaret har
fem obligatoriske ledd, og de er de samme hver gang.

Prioritet: høyeste prioritet — dette må sitte for A og B.
Bør sitte for C: den som treffer riktig paradigme og skriver en halv
konstruksjon, får uttelling selv om detaljene halter.

Fordelingen i grunnlaget: de tre designryggradene er maks-flyt (registrert i
16 av de 17 settene i grunnlaget, 94 %), dynamisk programmering (16 av 17,
94 %) og grafsøk (14 av 17, 82 %). Grunnlaget er de 17 settene fra august 2015
til august 2023 som er gjennomgått tema for tema — det er nevneren hver gang
boka oppgir en prosent. Gale-Shapley er registrert i 2 av de 17, men i 6 av
de 7 settene med dagens hjelpemiddelkode E: regn med den.

De fem leddene, én gang for alle:

1. Navngi det klassiske problemet. «Dette er et tilordningsproblem med
kapasiteter.»
2. Navngi paradigmet eksplisitt. «Det løses med maks-flyt.»
3. Konstruksjonen. Nodene, kantene og kapasitetene — eller delproblemet,
rekurrensen og grunntilfellene.
4. Rekonstruksjonen av selve løsningen, ikke bare verdien, med den
eksplisitte setningen om at det ikke øker den asymptotiske kjøretiden.
5. Kjøretiden, med $V$ , $E$ , $n$ og $m$ definert i problemets egne
størrelser.

Mangler ett ledd, er svaret ufullstendig — også når resten er riktig. Det
fjerde er det som glipper oftest.

Slik er kapitlet lagt opp (90 min):

Innhold	Tid
Løsningsoppskriften og mønsterkatalogen	ca. 14 min
Gjennomkjørt eksamenscase med margnotater	ca. 16 min
Drill: flyt og min-snitt	ca. 18 min
Drill: dynamisk programmering	ca. 16 min
Drill: grafsøk og stabil matching	ca. 16 min
Kald bank — uten hint	ca. 10 min

— naturlig pausepunkt — etter flytdrillen. Resten kan tas i en egen økt.

Forkunnskaper

Dette kapitlet bruker hele boka, men to oppskrifter må ligge klare i hånden.
De står ferdig oppfrisket her:

Flytmodellen fra kap. 5.3. Fire lag: kilde $s$ , ett
nodesett for det som skal tildeles, ett for det de tildeles til, og sluk $t$ .
Kapasiteten fra $s$ til en venstre node er hvor mange den kan ta;
kapasiteten fra en høyre node til $t$ er hvor mange den har plass til. En
kant i midten betyr at nettopp den tildelingen er tillatt — ikke en grense.
Kjør Edmonds-Karp, $O(VE^2)$ . Tildelingen leses av som de midtkantene som
bærer flyt, og heltallsteoremet garanterer at flyten kan velges heltallig,
slik at avlesningen er entydig.

DP-oppskriften fra kap. 6.3. Seks steg: gjenkjenn
mønsteret, definér delproblemet med ord, skriv rekurrensen med
grunntilfeller, oppgi fylleorden, rekonstruér fra lagrede valg, oppgi
kjøretiden som antall delproblemer ganger arbeid per delproblem. De tre
grunnformene:

$r[j] = \max_{1 \le i \le j}\big(p_i + r[j-i]\big) \qquad\text{(oppdeling)}$

$c[i,j] = \begin{cases} c[i-1,j-1]+1 & x_i = y_j \\ \max(c[i-1,j],\; c[i,j-1]) & \text{ellers}\end{cases} \qquad\text{(to sekvenser)}$

$c[i,w] = \max\big(c[i-1,w],\; v_i + c[i-1,\,w-w_i]\big) \qquad\text{(velg eller ikke)}$

Øvrige forkunnskaper:

- kap. 4.1 — BFS gir færrest kanter, ikke minst
vekt, i $\Theta(V+E)$ .
- kap. 4.3 — Dijkstra $O(E\lg V)$ krever ikke-negative
vekter; Bellman-Ford $\Theta(VE)$ tåler negative.
- kap. 6.5 — Gale-Shapley $O(n^2)$ , frier-optimal,
begge orienteringer rammer inn hva som er mulig.
- kap. 7.2 — reduksjonsretningen, når oppgaven ber deg
argumentere for at et problem er vanskelig i stedet for å løse det.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften og mønsterkatalogen

Steg 1 — les oppgaven én gang, og let etter mønsteret, ikke etter
detaljene. Innpakningen er alltid ny; strukturen er alltid en av en håndfull.

Innpakningen sier	Paradigmet	Kjøretid
«fordel A på B, med grenser for hvor mange hver kan ta»	maks-flyt, firelagsnett	$O(VE^2)$
«hvor mange kan tildeles samtidig»	maksimal matching = maks-flyt, alle kapasiteter 1	$O(VE^2)$
«billigste barriere som gjør det umulig å komme fra X til Y»	min-snitt, lest av etter maks-flyt	$O(VE^2)$
«del opp i biter, hver bit har en verdi eller kostnad»	DP, oppdelingsformen	typisk $\Theta(n^2)$
«finn den lengste felles / mest like sekvensen»	DP, LCS-formen	$\Theta(nm)$
«velg eller ikke velg, med en samlet grense»	DP, ryggsekkformen	$\Theta(nW)$ , pseudopolynomisk
«færrest ledd / korteste kjede / minst antall steg»	BFS	$\Theta(V+E)$
«korteste vei etter vekt, ikke-negative vekter»	Dijkstra	$O(E\lg V)$
«korteste vei i en syklusfri graf, eller med negative vekter»	DAG-Shortest-Path eller `Bellman-Ford`	$\Theta(V+E)$ / $\Theta(VE)$
«stabil parvis tilordning der begge sider har preferanser»	Gale-Shapley	$O(n^2)$
«billigste nett som henger sammen, uten ringer»	MST, `Kruskal` eller `Prim`	$O(E\lg V)$
«vis at problemet er vanskelig»	reduksjon, FRA kjent vanskelig TIL ditt	—

Steg 2 — skriv de to første leddene som to setninger. «Dette er et
tilordningsproblem med kapasiteter. Det løses med maks-flyt.» De to setningene
er billige, og de gir uttelling.
Steg 3 — bygg konstruksjonen presist. For flyt: hvilke noder, hvilke
kanter, hvilke kapasiteter, og hva hver kapasitet koder. For DP:
delproblemet med ord, rekurrensen, grunntilfellene, fylleorden.
Steg 4 — rekonstruér selve løsningen. Hvilke midtkanter bærer flyt? Hvilke
valg står i valgtabellen? Skriv den ene setningen: avlesningen koster $O(E)$
og øker ikke den asymptotiske kjøretiden. Ved flyt: nevn
heltallsteoremet.
Steg 5 — oppgi kjøretiden i problemets egne størrelser. «

O(VE^2)

med

V = n + m + 2

E = O(n + m + k)

» er et helt svar; «

O(VE^2)

» alene er et
halvt.

Steg 6 — stopp. Fem til ti linjer. Lange svar teller ikke positivt, og de
nitten andre oppgavene venter.
Kontrollen før du leverer: tell leddene. Fem?

✏️Eksempel 1: Gjennomkjørt eksamenscase med margnotater

En kommune skal fordele $n$ hjemmehjelpere på $m$ besøksruter i løpet av en
uke. Hver hjelper har oppgitt hvilke ruter hun har sertifisering for, og kan ta
høyst tre ruter. Hver rute må dekkes av nøyaktig én hjelper.

a) Beskriv en algoritme som avgjør om alle rutene kan dekkes, og som finner
en konkret fordeling.
b) Kommunen vurderer å kreve at hver hjelper tar minst én rute. Endrer
det noe?

Ledd 1 — det klassiske problemet. Ruter skal fordeles på hjelpere, hver part
har en øvre grense, og bare visse par er tillatt. Dette er et
tilordningsproblem med kapasiteter.

Margnotat. Denne setningen alene er verdt et ledd. Den som skriver «jeg lager
et flytnett» uten å si hvilket problem det er, mister det.

Ledd 2 — paradigmet. Maksimal flyt i et firelagsnett.

Ledd 3 — konstruksjonen.

- Kilde $s$ og sluk $t$ .
- Én node per hjelper, med kant $s \to \text{hjelper}$ og kapasitet 3 —
denne kapasiteten koder «høyst tre ruter hver».
- Én node per rute, med kant $\text{rute} \to t$ og kapasitet 1 — denne
koder «nøyaktig én hjelper per rute».
- Kant $\text{hjelper} \to \text{rute}$ med kapasitet 1 for hvert par der
hjelperen er sertifisert. At kanten finnes, koder at tildelingen er
tillatt.

Kjør Edmonds-Karp. Alle rutene kan dekkes hvis og bare hvis maksimal flyt er
$m$ .

Margnotat. Legg merke til at de tre kapasitetene koder tre forskjellige ting.
Å sette 3-eren på midtkantene i stedet for på kildekanten er den vanligste
modelleringsfeilen, og den gir et nett som tillater tre enheter til samme
rute.

Ledd 4 — rekonstruksjonen. Midtkantene som bærer flyt 1, er
fordelingen: hjelper $i$ tar rute $j$ . Heltallsteoremet garanterer at en
maksimal flyt kan velges heltallig når alle kapasitetene er heltall, så hver
midtkant bærer 0 eller 1 og avlesningen er entydig. Den koster $O(E)$ og
øker ikke den asymptotiske kjøretiden.

Margnotat. Dette leddet er det som skiller topp fra midtsjikt. Oppgaven ba om
en fordeling, ikke om et ja eller nei — og et svar som stopper ved
flytverdien, er felle #6.

Ledd 5 — kjøretiden. Nettet har $V = n + m + 2$ noder og
$E = O(n + m + k)$ kanter, der $k$ er antall sertifiseringer. Edmonds-Karp
gir $O(VE^2)$ .

Margnotat. « $O(VE^2)$ » uten å si hva $V$ og $E$ er i denne
konstruksjonen, er et halvt svar. Én linje til koster ingenting.

b) Endrer minstekravet noe?

Ja — og det er ikke lenger et rent maks-flyt-problem. Kapasiteter setter
øvre grenser; en nedre grense på hver kildekant kan ikke uttrykkes i
standardmodellen fra kap. 5.1.

Det ærlige svaret er å si nettopp det, og deretter peke på hva som kan gjøres:
enten flyt med nedre grenser på kantene, som er en utvidelse utenfor
pensum, eller en enkel forbehandling der hver hjelper først tildeles én rute
via en maksimal matching, og resten fordeles med nettet over.

Margnotat. Å si «dette faller utenfor standardmodellen, og her er grunnen»
gir uttelling. Å late som om kapasiteten 3 plutselig koder et minstekrav, gir
det ikke.

Hele svaret på a), i eksamensform:

Dette er et tilordningsproblem med kapasiteter, og løses med maks-flyt. Bygg
et nett med kilde $s$ , én node per hjelper (kant fra $s$ , kapasitet 3), én
node per rute (kant til $t$ , kapasitet 1), og en kant med kapasitet 1 fra
hjelper til rute for hver sertifisering. Kjør Edmonds-Karp. Alle rutene
dekkes hvis og bare hvis maksimal flyt er $m$ . Fordelingen leses av som de
midtkantene som bærer flyt; heltallsteoremet gir en heltallig flyt, og
avlesningen koster $O(E)$ uten å øke kjøretiden. Kjøretid $O(VE^2)$ med
$V = n+m+2$ og $E = O(n+m+k)$ .

Sju linjer. Det er lengden.

Drill: flyt og min-snitt (~18 min)

Fire oppgaver. Kjenn igjen mønsteret først, bygg nettet etterpå.

📝Oppgave 1

Eksamensnivå, sjanger H

Et bibliotek har $n$ ledige leseplasser og $m$ studenter som har meldt seg på.
Hver student har oppgitt hvilke plasser hun kan bruke, og skal ha nøyaktig én.
Hver plass tar én student.

Beskriv hvordan du avgjør om alle får plass, og hvordan du finner
fordelingen.

📝Oppgave 2

Eksamensnivå, sjanger H

En by planlegger flomsikring. Kartet er et rutenett; noen ruter er elvebredd,
noen er sykehusområde. Å sette opp en barriere i en rute koster et oppgitt
beløp. Byen vil finne den billigste samlingen ruter som gjør det umulig å
komme fra elvebredden til sykehusområdet.

Beskriv en løsning.

📝Oppgave 3

Eksamensnivå, sjanger…

Et datasenter skal fordele $n$ beregningsjobber på $m$ maskiner. Jobb $j$
krever $r_j$ kjernetimer, og maskin $i$ har $k_i$ ledige kjernetimer. En jobb
kan splittes på flere maskiner, men bare på dem som har riktig programvare.

Beskriv hvordan du avgjør om alle jobbene kan kjøres.

📝Oppgave 4

Eksamensnivå, sjanger H…

Samme datasenter som i forrige oppgave, men nå kan ikke en jobb splittes:
hver jobb må kjøres i sin helhet på én maskin.

a) Virker flytmodellen fortsatt?
b) Hva kan du si om problemets vanskelighet?

Drill: dynamisk programmering (~16 min)

Tre oppgaver. Delproblemet skal defineres med ord før rekurrensen kommer.

📝Oppgave 5

Eksamensnivå, sjanger H

Et museum skal sette opp en utstillingsrekke langs en korridor med $n$
posisjoner. Å plassere en montre på posisjon $i$ gir besøksverdien $g_i$ , men
to montre kan ikke stå på naboposisjoner. Samlet besøksverdi skal
maksimeres.

Beskriv en DP-løsning, og oppgi kjøretiden.

📝Oppgave 6

Eksamensnivå, sjanger H

To laboratorier har hver sin logg over hvilke målinger de har utført, i
kronologisk rekkefølge. Kvalitetsavdelingen vil finne den lengste rekken av
måletyper begge har utført, i samme rekkefølge — men ikke nødvendigvis
rett etter hverandre.

Beskriv en løsning.

📝Oppgave 7

Eksamensnivå, sjanger…

En transportør skal fylle en container med kapasitet $W$ kilo. Det finnes $n$
kolli, hvert med en vekt og en verdi, og hvert kolli kan tas med eller ikke —
ikke deles.

a) Beskriv en DP-løsning som finner høyest mulig verdi og hvilke kolli
som velges.
b) En kollega sier at algoritmen er polynomisk siden kjøretiden er
$\Theta(nW)$ . Stemmer det?

Drill: grafsøk og stabil matching (~16 min)

Tre oppgaver. Her er fellen å velge feil søkealgoritme.

📝Oppgave 8

Eksamensnivå, sjanger H

Et regelverk består av $n$ paragrafer. Noen paragrafer viser til andre. En
saksbehandler vil vite: hva er den korteste kjeden av henvisninger fra
paragraf $a$ til paragraf $b$ , målt i antall ledd?

Beskriv en løsning, og oppgi kjøretiden.

📝Oppgave 9

Eksamensnivå, sjanger H

En studieadministrasjon skal fordele $n$ studenter på $n$ prosjektgrupper.
Studentene har rangert gruppene, og gruppene har rangert studentene. Fordelingen
skal være slik at ingen student og gruppe begge heller vil ha hverandre enn det
de fikk.

a) Hvilket problem er dette, og hvordan løser du det?
b) En student spør om hun kunne fått gruppe $G$ i stedet. Hvordan svarer
du?

📝Oppgave 10

Eksamensnivå, sjanger…

Et logistikkfirma har et rutenett mellom $V$ terminaler med $E$ strekninger.
Hver strekning har en kostnad, og noen kostnader er negative fordi
returlast betaler bedre enn utgiften. Nettet har ingen sykel med negativ
totalkostnad.

a) Firmaet vil ha billigste rute fra hovedterminalen til alle andre.
Hvilken algoritme, og hvorfor ikke de andre?
b) Nettet viser seg i tillegg å være syklusfritt. Endrer det svaret?

Kald bank — uten hint

Typiske feil

De to første koster mest, og de kommer i nesten hver eneste designoppgave.

- Å oppgi bare optimalverdien. Dette er felle #6. Oppgaven ber om en
fordeling, en plan, en oppdeling eller en kjede — og da må du si hvordan den
leses ut. Ta med setningen om at rekonstruksjonen ikke øker kjøretiden.
- Å ikke navngi paradigmet. «Jeg lager et nett med noder og kanter» uten å
si at det er maks-flyt, mister ett ledd. To setninger koster ingenting.
- Å reversere reduksjonsretningen når oppgaven ber om et
vanskelighetsargument. Felle #1: reduser FRA det kjente vanskelige
TIL ditt problem.
- Å glemme heltallsteoremet i en flytmodellering. Det er det som gjør at
flyten kan leses som en tildeling.
- Å sette kapasitetene feil sted. «Hvor mange hver kan ta» hører på
kildekanten; «hvor mange hver har plass til» på slukkanten; hva som er
tillatt, kodes ved at midtkanten finnes.
- Å bruke Dijkstra på negative vekter. Felle #8. Og motsatt: å bruke
Dijkstra der BFS holder, når alle kantene teller likt.
- Å oppgi kjøretiden uten å definere størrelsene. « $O(VE^2)$ » alene er et
halvt svar; si hva $V$ og $E$ er i din konstruksjon.
- Å bruke for lang tid. Fem til ti linjer. Den som bruker 40 minutter på én
designoppgave, har nitten andre som teller like mye.

Og den gjennomgående: å ikke telle leddene før du går videre. Fem ledd, hver
gang.

Paradigmene og kjøretidene samlet

Paradigme	Når	Kjøretid	Rekonstruksjon
Maks-flyt	fordeling med kapasiteter	$O(VE^2)$	midtkanter med flyt, $O(E)$
Min-snitt	billigste barriere	$O(VE^2)$	én `BFS` i restnettet, $O(V+E)$
Maksimal matching	én-til-én-paring	$O(VE^2)$	midtkanter med flyt, $O(E)$
DP, oppdeling	del i biter med verdi	$\Theta(n^2)$	valgtabell baklengs, $O(n)$
DP, LCS	to sekvenser	$\Theta(nm)$	retningspekere baklengs, $O(n+m)$
DP, ryggsekk	velg eller ikke, med grense	$\Theta(nW)$ , pseudopolynomisk	rad-sammenligning baklengs, $O(n)$
`BFS`	færrest ledd	$\Theta(V+E)$	$\pi$ baklengs, $O(V)$
`Dijkstra`	korteste vei, ikke-negative vekter	$O(E\lg V)$	$\pi$ baklengs, $O(V)$
`DAG-Shortest-Path`	korteste vei i DAG, negative lov	$\Theta(V+E)$	$\pi$ baklengs, $O(V)$
`Bellman-Ford`	korteste vei med negative vekter	$\Theta(VE)$	$\pi$ baklengs, $O(V)$
`Gale-Shapley`	stabil parvis tilordning	$O(n^2)$	matchingen og orienteringen
MST	billigste sammenhengende nett	$O(E\lg V)$	kantene i rekkefølge, $V-1$ stk.
Reduksjon	«vis at problemet er vanskelig»	—	retning + hva den ikke viser

Én presisering som er verdt å ta med seg. Rekonstruksjonskolonnen er den
korteste i tabellen og den dyreste å glemme. I hvert eneste tilfelle er den et
lavere ledd enn selve algoritmen — og i hvert eneste tilfelle er den det
oppgaven faktisk ber om.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

De fem leddene i et designsvar

navngi det klassiske problemet, navngi paradigmet, bygg konstruksjonen, rekonstruér selve løsningen, og oppgi kjøretiden. Det fjerde glipper oftest, og det andre er det billigste å få med. Tell leddene før du går videre til neste oppgave.

Mønstergjenkjenning

å lese innpakningen og finne strukturen: fordeling, barriere, oppdeling, to sekvenser, velg-eller-ikke, færrest ledd, eller stabil paring. Innpakningen er alltid ny; strukturen er alltid en av en håndfull. Les oppgaven én gang for mønsteret, og først deretter for detaljene.

Flytmalen

O(VE^2)

Nodesplitting

å dele en node i to med en indre kant som bærer nodens kapasitet eller kostnad. Brukes når begrensningen sitter på en node og ikke på en kant — typisk i barriereproblemer der det koster å sperre et sted. Alle innkommende kanter til den ene halvdelen, alle utgående fra den andre.

Rekonstruksjon

\pi

Å oppgi kjøretiden i problemets størrelser

O(VE^2)

Når flyt ikke virker

flytmodellen tåler ikke nedre grenser på kanter, og den hindrer ikke at flyten fra én node splittes på flere veier. Krever oppgaven at en enhet holdes samlet, er problemet typisk NP-hardt — en ryggsekkvariant. Å si at noe faller utenfor standardmodellen, og hvorfor, gir uttelling.

Sjanger H — åpen algoritmedesign

oppgavetypen der du skisserer en algoritme på fem til ti linjer. De siste tre til fem oppgavene i hvert ordinære sett er av denne typen. Delvis uttelling er regelen: riktig paradigme og halv konstruksjon gir uttelling selv om detaljene halter.

Repetisjonsoppgaver

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.