TDT4120 Algoritmer og datastrukturerTilbake

5.P Prøver til del 5: Maksimal flyt

Alle fag for Høyskole

5.P Prøver til del 5: Maksimal flyt

Fire prøver som dekker del 5 (maksimal flyt) på eksamensnivå, med fulle løsningsforslag.

120 min

0 oppgaver

Prøver til del 5Maksimal flyt

Din fremgang i kapitlet

0 / 0 oppgaver

Kapitlets plass i kurset

Bygger på

5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering

Fire prøver à ~30–40 min: prøve 5.A (30 min), 5.B (35 min), 5.C (30 min) og 5.D (40 min) — 135 minutter til sammen. Prøvene kan trygt deles over flere kvelder; én prøve per økt er den anbefalte rytmen, og 5.D bør få en økt helt for seg selv fordi den er en designoppgave.

Dekning. Maks-flyt er telt i 16 av de 17 settene i grunnlaget (94 %) og er dessuten verktøyet i flest av de åpne designoppgavene på slutten av settene. Prøvene deler temaet i fire: 5.A definisjonene alt hviler på, 5.B håndkjøringen, 5.C skillet mellom pseudopolynomisk og polynomisk, og 5.D modelleringen.

Sjangrene du møter her, skrevet ut i klarspråk:

- sjanger C — håndkjøring: du utfører algoritmen steg for steg og oppgir bare sluttilstanden — her flytverdien og et min-snitt.
- sjanger D — definisjon med egne ord: én presis setning, hovedpoenget først.
- sjanger E — kjøretid: ett uttrykk, med $\Theta$ og $O$ bevisst valgt.
- sjanger F — «stemmer dette?»: ja eller nei først, deretter én setning.
- sjanger H — åpen algoritmedesign: fem faste ledd — navngi det klassiske problemet, navngi paradigmet, beskriv konstruksjonen, si hvordan du rekonstruerer selve løsningen, og oppgi kjøretiden.

Hvor flervalget bor. De statiske flervalgsoppgavene står inline i prøveteksten under, med alternativer merket a)–d) og fasitbokstaven i løsningsforslaget. De interaktive flervalgsspørsmålene ligger i quizen til kapitlene i Del 5, ikke her.

Tidsbudsjett. Minuttallene er arbeidstid. Prøve 5.D har 40 minutter fordi en designoppgave krever at du både finner modellen og skriver den ned kort — og det siste er den ferdigheten som skiller.

Forkunnskaper

Prøvene hviler på hele Del 5:

- kap. 5.1 — flytnett, restnett og snitt
- kap. 5.2 — Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt
- kap. 5.3 — drillen på håndkjøring og flyt-modellering

Fra kap. 4.1 trenger du BFS: det er den Edmonds-Karp bruker til å finne en korteste forøkende sti.

Dette er det du trenger å ha friskt:

- Restkapasitet: $c_f(u,v) = c(u,v) - f(u,v)$ for en kant med flyt på seg, og $c_f(v,u) = f(u,v)$ for ryggkanten motsatt vei. Ryggkanten er retten til å angre flyt du allerede har sendt.
- Restnettet $G_f$ består av alle kantene med $c_f > 0$ — både framoverkanter og ryggkanter.
- Forøkende sti: en vei fra $s$ til $t$ i restnettet. Finnes ingen, er flyten maksimal.
- Snitt $(S,T)$ : en partisjon av nodene med $s \in S$ og $t \in T$ . Snittkapasiteten $c(S,T)$ teller bare kantene som går fra $S$ til $T$ ; kantene motsatt vei teller ikke.
- Maks-flyt/min-snitt: verdien av en maksimal flyt er lik kapasiteten til et minimalt snitt.
- Heltallsteoremet: er alle kapasitetene heltall, finnes det en maksimal flyt der hver kant har heltallig flyt.

Prøve 5.A — Flytnett, restnett og snitt (30 min)

Prøve 5.B — Håndkjøring av Edmonds-Karp (35 min)

Prøve 5.C — Pseudopolynomisk mot polynomisk (30 min)

Prøve 5.D — Flyt-modellering (40 min)

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.