6.4 Grådighet — Huffman og aktivitetsutvelgelse

Huffman (optimale prefikskoder), aktivitetsutvelgelse og grådig-bytteargumentet — når et lokalt optimalt valg gir globalt optimum.

50 min

7 oppgaver

GrådighetHuffmanaktivitetsutvelgelse

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

6.1Dynamisk programmering — mekanikk

Brukes videre i

6.5Stabil matching — Gale-Shapley

Grådighet er belagt i 65 % (11 av de 17 settene i grunnlaget). Temaet er
sjelden hovedretten, men det dukker opp i tre faste former:

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. For Huffman er sluttilstanden
kodelengden per tegn, ikke tegningen av treet.
- Sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først. «Hva er en prefikskode?» og «hva menes med grådig valg?»
er typiske.
- Sjanger H — åpen algoritmedesign, altså «hvordan vil du gå fram?». Her er
poenget som regel å se at problemet ikke er grådig og må løses med
dynamisk programmering, eller motsatt.

Prioritet: kjenne til. Du skal kjenne igjen Huffman fra en frekvenstabell,
kunne kjøre den mekanisk, og kunne si i én setning hvorfor det grådige valget er
trygt. Du trenger ikke kunne bevise optimaliteten formelt.

Det som faktisk koster poeng her, er å svare «grådig» på et problem som ikke
er grådig. 0-1-ryggsekk fra kap. 6.2 er motbeviset du
alltid kan ty til, og du møter det igjen mot slutten av dette kapitlet.

Slik er kapitlet lagt opp (50 min):

#	Innhold	Tid
1	Hva en grådig algoritme er, og aktivitetsutvelgelse	ca. 13 min
2	Bytteargumentet og grådig valg-egenskap	ca. 12 min
3	`Huffman` og optimale prefikskoder	ca. 15 min
4	Fraksjonell mot 0-1-ryggsekk, og begrepsbanken	ca. 10 min

Forkunnskaper

Dette kapitlet bygger på kap. 6.1, der optimal
substruktur ble innført — egenskapen at en optimal løsning på hele problemet
inneholder optimale løsninger på delproblemene. Grådighet krever den samme
egenskapen, pluss én til, og hele kapitlet handler om den ekstra egenskapen.

Fra kap. 6.2 trenger du 0-1-ryggsekk som kontrast: der
er verdien $\Theta(nm)$ og problemet lar seg ikke løse grådig. Det er bokas
faste motbevis mot «grådighet virker alltid».

Du trenger dessuten:

- prioritetskø fra kap. 3.1 — Huffman plukker
gjentatte ganger ut det minste elementet, og en binærhaug gjør hvert slikt
uttak i $O(\lg n)$ ;
- sortering fra kap. 2.1 — aktivitetsutvelgelse
forutsetter at aktivitetene allerede er sortert på sluttid, og det koster
$\Theta(n\lg n)$ hvis de ikke er det;
- asymptotisk notasjon fra kap. 1.1 — særlig
skillet mellom $O$ (bare øvre grense) og $\Theta$ (tett grense).

Har du ikke møtt pseudokode og kjøretidsuttrykk før, er
Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)
et mykere første møte.

Notasjons- og pseudokodeliste

Ett rom, mange arrangementer (~13 min)

Et grendehus har ett stort rom og en bunke søknader om å låne det. Hver søknad
har et starttidspunkt og et sluttidspunkt, og to arrangementer kan ikke overlappe
i tid. Styret vil få flest mulig arrangementer inn i kalenderen — ikke de
lengste, ikke de mest populære, bare flest mulig.

Det finnes en overraskende enkel regel som alltid gir riktig svar: velg hele
tiden det arrangementet som slutter først blant dem som fortsatt passer. Ingen
tabell, ingen tilbakesporing — bare ett gjennomløp av listen.

En algoritme som bygger løsningen ved å ta det valget som ser best ut akkurat nå,
og aldri angrer, kalles grådig. Grådighet er billigere enn dynamisk
programmering, men den virker bare når problemet har en bestemt struktur. Dette
kapitlet handler om når den strukturen er der — og hvordan du oppdager at den
ikke er det.

Grådig algoritme

\Theta(n)

Aktivitetsutvelgelsesproblemet

n

📜Pseudokode-kontrakt: `Greedy-Activity-Selector`

1. Antagelser om representasjon. Aktivitetene er nummerert

1

til

n

og
gitt som to arrayer s[1..n] og f[1..n] med indeks fra 1. Arrayene er ordnet
slik at sluttidene er stigende:

f[1] \le f[2] \le \dots \le f[n]

. Er de ikke
det, sorterer du dem først, og det koster

\Theta(n\lg n)

2. Pre- og postbetingelse. Før: f er sortert stigende. Etter: mengden
A inneholder innbyrdes kompatible aktiviteter, og ingen annen mengde av
innbyrdes kompatible aktiviteter har flere elementer.

3. Pseudokoden.

Greedy-Activity-Selector(s, f)
  Input:  starttider s[1..n] og sluttider f[1..n],
          med f[1] <= f[2] <= ... <= f[n]
  Output: en storst mulig mengde innbyrdes kompatible aktiviteter
  A = {1}
  k = 1
  for m = 2 to n
      if s[m] >= f[k]
          A = A + {m}
          k = m
  return A

4. Grunnideen i én setning. Ved å velge aktiviteten som slutter først,
etterlater du så mye ledig tid som mulig til resten — og mer ledig tid kan aldri
gi færre aktiviteter.

5. Kjøretid. Løkka gjør ett gjennomløp av $n$ aktiviteter med konstant arbeid
per aktivitet, altså $\Theta(n)$ etter sortering. Skriv $\Theta$ her, ikke $O$ :
løkka går alltid hele veien, uansett input.

✏️Eksempel 1: Åtte arrangementer i grendehuset

Åtte arrangementer er søkt inn i det store rommet. Tidene er oppgitt i timer
etter klokka 08, og lista er allerede sortert stigende på sluttid:

Aktivitet	A1	A2	A3	A4	A5	A6	A7	A8
Start	0	2	1	4	6	5	8	9
Slutt	3	4	6	7	9	10	11	13

Kjør Greedy-Activity-Selector og oppgi hvilke arrangementer som velges.

Regelen er mekanisk: gå gjennom lista i sluttid-rekkefølge, og velg en aktivitet
hvis den starter tidligst når den forrige valgte er ferdig.

Steg	Aktivitet	Start	Slutt	Avgjørelse	Siste sluttid etter steget
1	A1	0	3	velges	3
2	A2	2	4	forkastes (start 2 < 3)	3
3	A3	1	6	forkastes (start 1 < 3)	3
4	A4	4	7	velges	7
5	A5	6	9	forkastes (start 6 < 7)	7
6	A6	5	10	forkastes (start 5 < 7)	7
7	A7	8	11	velges	11
8	A8	9	13	forkastes (start 9 < 11)	11

Sluttilstand: A1, A4, A7 — tre arrangementer.
Margnotat: hva som gir uttelling ved hvert steg.
- Steg 1 er gratis: den første aktiviteten i en sluttid-sortert liste velges
alltid. Å hoppe over den er aldri lønnsomt.
- Steg 2 og 3 er der de fleste bommer. A3 varer fra 1 til 6 og virker «stor og
viktig», men den kolliderer med A1. Grådigheten bryr seg ikke om varighet.
- Steg 5 og 6 tester det samme en gang til: A5 slutter tidligere enn A6, men
begge starter før A4 er ferdig, så begge forkastes.
Kontroll av svaret. A1 slutter i 3, A4 starter i 4 — greit. A4 slutter i 7,

A7 starter i 8 — greit. Ingen overlapp, og en uttømmende gjennomgang av alle

delmengder bekrefter at tre er det maksimale her.

Merk hva som faktisk leveres. Oppgaven ber om hvilke arrangementer som
velges, ikke om en forklaring av algoritmen. Én linje med tre navn er hele svaret;
tabellen over er undervisning.

📝Oppgave 1

(Innstegsoppgave.) Sju vaktskift er søkt inn på samme ressurs. Lista er allerede
sortert stigende på sluttid, og tidene er klokkeslett:

Vakt	V1	V2	V3	V4	V5	V6	V7
Start	8	9	10	11	13	15	14
Slutt	10	11	13	14	16	18	19

a) Hvilke vakter velger Greedy-Activity-Selector?
b) Hvor mange vakter kommer med?

Hvorfor nettopp «slutter først»?

To andre regler ser like fornuftige ut, og begge er gale. Det er verdt å ha
motbevisene klare, for de er korte og de dukker opp som delspørsmål.

«Velg den korteste aktiviteten først.» Ta tre aktiviteter: C1 fra 0 til 5,
C2 fra 4 til 6, C3 fra 5 til 10. Den korteste er C2 med varighet 2. Velger du
den, blokkerer du både C1 og C3, og du sitter igjen med én aktivitet. Den
optimale løsningen er C1, C3 med to aktiviteter.

«Velg den som starter først.» Ta D1 fra 0 til 12, D2 fra 1 til 4, D3 fra 5
til 8, D4 fra 9 til 11. Den som starter først er D1, og den spiser hele dagen —
resultatet blir én aktivitet. Optimum er D2, D3, D4 med tre.

Intuisjon: det eneste som betyr noe for resten av problemet, er når rommet
blir ledig igjen. Varighet og starttidspunkt sier ingenting om det. Sluttiden
gjør det, og derfor er det den grådigheten skal styres av.

📝Oppgave 2

Sjanger C

Åtte gruppetimer er søkt inn på ett grupperom, sortert
stigende på sluttid:

Aktivitet	B1	B2	B3	B4	B5	B6	B7	B8
Start	1	3	0	5	4	7	8	11
Slutt	4	5	6	8	9	10	12	14

a) Oppgi mengden Greedy-Activity-Selector returnerer.
b) B8 starter i 11 og slutter i 14, og ser ut som en grei kandidat. Forklar i
én setning hvorfor den likevel ikke kommer med.

Bytteargumentet — hvorfor et lokalt valg er trygt (~12 min)

At regelen virker på tre eksempler, er ikke et argument. Det som gjør grådighet
faglig holdbar, er et bytteargument: du viser at en hvilken som helst
optimal løsning kan gjøres om til en optimal løsning som inneholder ditt grådige
valg — ved å bytte ut ett element.

Intuisjon: hvis den optimale løsningen bruker et annet element enn ditt, kan
du erstatte det med ditt uten å tape noe. Da er din løsning minst like god, og
siden den andre var optimal, er din det også.

For aktivitetsutvelgelse går argumentet slik. La $A$ være en optimal mengde
aktiviteter, og la $j$ være den aktiviteten i $A$ som slutter først. La $1$ være
aktiviteten som slutter først i hele problemet — den grådigheten velger. Da er
$f[1] \le f[j]$ . Bytt ut $j$ med $1$ i $A$ . Den nye mengden har like mange
elementer som $A$ , og den er fortsatt lovlig, fordi $1$ slutter tidligere enn $j$
og derfor ikke kan kollidere med noe som lå etter $j$ . Altså finnes det en
optimal løsning som inneholder det grådige valget.

Resten følger ved gjentakelse: etter det første valget står du igjen med et
mindre problem av nøyaktig samme type, og argumentet kan brukes på nytt.

📜Grådig valg-egenskap og optimal substruktur

En grådig algoritme er korrekt når begge disse egenskapene holder:

1. Grådig valg-egenskap. Det finnes en optimal løsning som inneholder det
lokalt beste valget. Dette er egenskapen som skiller grådighet fra dynamisk
programmering, og den bevises med et bytteargument.

2. Optimal substruktur. Når det grådige valget er tatt, er det som gjenstår
et mindre problem av samme type, og en optimal løsning på helheten inneholder en
optimal løsning på restproblemet.

Dynamisk programmering krever bare punkt 2. Det er derfor DP er bredere anvendelig
og grådighet er raskere: DP prøver alle valg i hvert steg og lar tabellen
avgjøre, mens grådighet tar ett valg og går videre. Mangler punkt 1, gir
grådighet et galt svar — og 0-1-ryggsekk er standardmotbeviset.

📝Oppgave 3

Sjanger D

a) Forklar hva grådig valg-egenskap betyr.
b) Forklar med én setning hva et bytteargument gjør, og hvorfor det er
nødvendig.
c) Hvilken av de to egenskapene i teoremet over krever dynamisk programmering,
og hvilken krever grådighet i tillegg?

`Huffman` og optimale prefikskoder (~15 min)

— naturlig pausepunkt —

En tekstfil skal lagres med færrest mulig bits. Med fast kodelengde får alle
tegn like mange bits: seks ulike tegn krever $\lceil \lg 6 \rceil = 3$ bits
hver. Men tegnene forekommer ikke like ofte. Gir vi de hyppigste tegnene korte
koder og de sjeldne lange, kan totalen bli langt mindre.

Problemet er at koder med ulik lengde kan bli tvetydige. Hvis A er 0 og B
er 01, vet ikke mottakeren om 01 betyr «B» eller «A etterfulgt av noe som
begynner på 1». Løsningen er en prefikskode.

Prefikskode

En koding der ingen tegns kode er begynnelsen på et annet tegns kode. Det gjør avkodingen entydig: leser du bitstrømmen fra venstre, finnes det til enhver tid høyst én kode som passer, og du kan skjære av tegnet med én gang du kjenner det igjen. En prefikskode svarer nøyaktig til et binærtre der alle tegnene sitter i bladene — venstre kant leses som 0, høyre som 1, og veien fra rota ned til bladet er tegnets kode. Kodelengden til et tegn er derfor det samme som dybden til bladet.

📜Pseudokode-kontrakt: `Huffman`

1. Antagelser om representasjon. Alfabetet C har

n

tegn, og hvert tegn
c har et frekvensfelt c.freq som er et ikke-negativt tall. Q er en
min-prioritetskø ordnet på freq, typisk implementert som en binærhaug. Hver
node i treet har feltene venstre, hoyre og freq; tegnene ligger i bladene.

2. Pre- og postbetingelse. Før: alle frekvenser er kjent, og $n \ge 2$ .
Etter: returverdien er rota i et binærtre som gir en optimal prefikskode
for C — ingen annen prefikskode gir færre bits totalt.

3. Pseudokoden.

Huffman(C)
  Input:  alfabet C med n tegn, hvert tegn c har frekvensen c.freq
  Output: rota i et binaertre som gir en optimal prefikskode for C
  n = |C|
  Q = C                          // min-prioritetsko ordnet paa freq
  for i = 1 to n - 1
      alloker en ny node z
      x = Extract-Min(Q)
      y = Extract-Min(Q)
      z.venstre = x
      z.hoyre   = y
      z.freq    = x.freq + y.freq
      Insert(Q, z)
  return Extract-Min(Q)

4. Grunnideen i én setning. De to sjeldneste tegnene må ligge dypest i et
optimalt tre, og de kan alltid plasseres som søsken — derfor kan de slås sammen
til én node med summen som frekvens, og problemet krymper med ett tegn.

5. Kjøretid. Løkka kjøres $n-1$ ganger, og hver runde gjør to Extract-Min
og én Insert, hver i $O(\lg n)$ med binærhaug. Det gir $O(n\lg n)$ . Skriv $O$
og ikke $\Theta$ her: kjøretiden avhenger av hvordan prioritetskøen er
implementert.

✏️Eksempel 2: Huffman-tre for seks tegn

En logg består av seks ulike tegn med disse frekvensene:

Tegn	E	R	N	S	K	Y
Frekvens	22	14	11	7	4	2

a) Kjør Huffman og oppgi kodelengden for hvert tegn.
b) Hvor mange bits koster loggen med denne kodingen, mot en fast koding med

3 bits per tegn?

Regelen er den samme hver runde: ta ut de to letteste nodene, slå dem sammen
til én ny node med summen som frekvens, og legg den nye noden tilbake i køen.

Steg	To letteste	Ny node	Køen etter steget (frekvens: node)
1	Y (2) og K (4)	6	6: (6), 7: S, 11: N, 14: R, 22: E
2	(6) (6) og S (7)	13	11: N, 13: (13), 14: R, 22: E
3	N (11) og (13) (13)	24	14: R, 22: E, 24: (24)
4	R (14) og E (22)	36	24: (24), 36: (36)
5	(24) (24) og (36) (36)	60	60: (60)

a) Sluttilstand — kodelengde per tegn: E 2, R 2, N 2, S 3, K 4, Y 4.
b) Totalt 139 bits, mot

3 \cdot 60 = 180

bits med fast 3-bits koding.
Regnestykket bak (a):

22 \cdot 2 + 14 \cdot 2 + 11 \cdot 2 + 7 \cdot 3 + 4 \cdot 4 + 2 \cdot 4 = 139

Margnotat: hvor delpoenget faller.
- Steg 1 er hele testen. Y (2) og K (4) er de to letteste, og de skal slås

sammen — ikke Y og S, og ikke de to første i tabellen.

- Steg 2 er det andre kritiske: den nye noden med frekvens 6 er nå lettere enn

S (7), så den deltar i neste sammenslåing på lik linje med de opprinnelige

tegnene. Å legge sammenslåtte noder «til side» er den vanligste feilen.

- Etter 5 sammenslåinger står det igjen én node — det er alltid $n-1$ runder for

$n$ tegn.
Kontroll uten å telle treet på nytt: legg sammen $2^{-\ell}$ over alle
kodelengder. Her blir det $2^{-2}+2^{-2}+2^{-2}+2^{-3}+2^{-4}+2^{-4} = 1$
nøyaktig, som den skal for et tre der alle indre noder har to barn.
Merk hva som leveres. Sjanger C krever sluttilstanden i det formatet oppgaven
ber om, og for Huffman er det kodelengden per tegn — ikke en tegning av
treet, og ikke selve bitmønstrene, med mindre det står i oppgaven.

📝Oppgave 4

Sjanger C

Fem tegn har disse frekvensene:

Tegn	P	V	H	J	C
Frekvens	25	20	18	12	5

a) Kjør Huffman og oppgi kodelengden for hvert tegn.
b) Hvor mange bits koster teksten totalt?

Typiske feil

- Å slå sammen feil noder. Huffman tar de to letteste i køen, og en
node som er laget ved sammenslåing teller på lik linje med et opprinnelig tegn.
I Eksempel 2 er det nettopp den nye noden med frekvens 6 som er lettere enn S
med 7. Kontrollen: skriv opp hele køen etter hver runde, sortert.
- Å gi det sjeldneste tegnet den korteste koden. Sammenhengen er motsatt: jo
sjeldnere tegnet er, desto dypere ligger bladet og desto lengre er koden. Er
kodelengdene dine ikke svakt synkende med frekvensen, har du regnet feil.
- Å levere treet når det ble spurt om kodelengder. Sluttilstanden for
Huffman er kodelengden per tegn, eventuelt totalt antall bits. Tegningen er
arbeidet ditt, ikke svaret.
- Å oppgi kjøretiden til Huffman som $\Theta(n)$ . Den er $O(n\lg n)$ , fordi
hver av de $n-1$ rundene gjør prioritetskø-operasjoner i $O(\lg n)$ . Dette er
felle #9 i bokas feilregister — å oppgi feil kjøretidsfakta.
- Å tro at grådighet alltid gir optimum. Det gjør den bare når grådig
valg-egenskap er oppfylt. Neste avsnitt viser motbeviset.
- Å sortere aktivitetene på starttid. Aktivitetsutvelgelse forutsetter
sortering på sluttid. Sorterer du på start, gir algoritmen feil svar, som
motbeviset med D1 til D4 viser.

📝Oppgave 5

Sjanger C, med en…

Seks tegn har frekvensene

Tegn	A	B	C	D	E	F
Frekvens	1	1	2	3	5	8

a) Kjør Huffman og oppgi kodelengden for hvert tegn.
b) Treet får en påfallende form. Beskriv formen med én setning, og si hva i

frekvensene som forårsaker den.

Fraksjonell mot 0-1: der grådighet slutter å virke (~10 min)

— naturlig pausepunkt —

Ryggsekkproblemet finnes i to varianter, og de skiller lag nøyaktig på grådighet.

I fraksjonell ryggsekk kan du ta en del av en vare — halvparten av sekken med
kobber, tre firedeler av sinken. Da virker grådighet: sorter varene på verdi
per vekt, ta så mye du kan av den beste, og fyll resten med den nest beste. Den
siste varen deles hvis den ikke får plass hel.

I 0-1-varianten er varene udelelige: du tar hele varen eller ingenting. Da
faller grådigheten sammen, og du må bruke dynamisk programmering — det er
$\Theta(nm)$ -algoritmen fra kap. 6.2, der $m$ er
kapasiteten.

Fraksjonell ryggsekk

\Theta(n\lg n)

✏️Eksempel 3: Samme instans, to svar

Et gjenvinningsanlegg har plass til 6 kg metall på lasteplanet:

Vare	Vekt (kg)	Verdi (kr)
kobber	2	30
sink	5	60
tinn	5	55

a) Hva er den største verdien i den fraksjonelle varianten?
b) Hva er den største verdien i 0-1-varianten?
c) Hva gir grådighet etter verdi per vekt i 0-1-varianten?

a) Ranger på verdi per vekt og fyll ovenfra:

Rang	Vare	Vekt	Verdi	Verdi per vekt	Tatt (kg)	Verdi hittil
1	kobber	2	30	15.0	2	30.0
2	sink	5	60	12.0	4	78.0
3	tinn	5	55	11.0	0	78.0

Fraksjonelt optimum: 78 kroner — hele kobberet og fire femdeler av sinken.
b) I 0-1-varianten kan ingen vare deles. Uttømmende gjennomgang av alle åtte
delmengder gir optimum 60 kroner, oppnådd med sink alene, som veier
nøyaktig 5 kg.

c) Grådighet tar først kobber (verdi per vekt 15), som veier 2 kg. Da er det

4 kg igjen, og verken sink eller tinn får plass hele. Grådigheten stopper med
30 kroner — 30 kroner dårligere enn optimum.
Dette er motbeviset i én instans. Fraksjonell ryggsekk har grådig

valg-egenskap; 0-1-ryggsekk har det ikke. Merk at det fraksjonelle svaret
(78) er høyere enn 0-1-svaret (60) — det er alltid slik, siden fraksjonell
tillater alt 0-1 tillater og mer til.

Svarformen. Oppgaven ber om verdier, ikke om en utledning. Tre tall er hele
svaret; rangeringstabellen er arbeidet.

📝Oppgave 6

Sjanger F

Avgjør for hver påstand:

a) Grådighet gir optimal løsning på 0-1-ryggsekk hvis du rangerer varene på
verdi per vekt.
b) Huffman gir en optimal prefikskode.
c) I et Huffman-tre kan et tegn med høyere frekvens få lengre kode enn et
tegn med lavere frekvens.
d) Aktivitetsutvelgelse løst grådig er $\Theta(n\lg n)$ uansett.

📝Oppgave 7

Eksamensnivå, sjanger H

En serverpark skal kjøre $n$ jobber. Jobb $i$ opptar maskinen fra $s[i]$ til
$f[i]$ , og hver jobb gir samme inntekt. Du har én maskin.

a) Beskriv en algoritme som gir flest mulig kjørte jobber, og oppgi kjøretiden.
b) Anta i stedet at jobb $i$ gir inntekten $v[i]$ , og at inntektene er
forskjellige. Holder algoritmen fra (a)? Begrunn, og si hva du ville gjort i
stedet.

Kjøretider i dette kapitlet

Algoritme	Beste	Verste	Krav / egenskap
`Greedy-Activity-Selector`	$\Theta(n)$	$\Theta(n)$	krever at aktivitetene er sortert på sluttid
Aktivitetsutvelgelse inkl. sortering	$\Theta(n\lg n)$	$\Theta(n\lg n)$	sorteringen dominerer
`Huffman`	$O(n\lg n)$	$O(n\lg n)$	prioritetskø; gir optimal prefikskode
`Extract-Min` / `Insert` (binærhaug)	$O(\lg n)$	$O(\lg n)$	én sti opp eller ned i haugen
Fraksjonell ryggsekk	$\Theta(n\lg n)$	$\Theta(n\lg n)$	varene kan deles; grådig på verdi per vekt
0-1-ryggsekk	$\Theta(nm)$	$\Theta(nm)$	ikke grådig; dynamisk programmering, pseudopolynomisk fordi $m$ er en tallverdi

Legg merke til at Huffman står med

O

og aktivitetsutvelgelse med

\Theta

.
Det er ikke slurv: Huffman sin kjøretid henger på hvordan prioritetskøen er
implementert, mens Greedy-Activity-Selector alltid gjør nøyaktig ett gjennomløp.

Begrepsbank

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

`Greedy-Activity-Selector`

\Theta(n)

`Huffman`

O(n\lg n)

Grådig valg-egenskap

Egenskapen at det finnes en optimal løsning som inneholder det lokalt beste valget. Dette er kravet som skiller grådighet fra dynamisk programmering. Er egenskapen oppfylt, kan du binde deg til det lokale valget uten å se resten av problemet, og kjøretiden faller fra en full tabell til ett gjennomløp. Er den ikke oppfylt, svarer grådigheten galt — 0-1-ryggsekk er standardmotbeviset.

Optimal substruktur

Egenskapen at en optimal løsning på hele problemet inneholder optimale løsninger på delproblemene. Både grådighet og dynamisk programmering krever denne egenskapen; det er bare grådighet som i tillegg krever grådig valg-egenskap. Egenskapen er det som gjør at du kan sette opp en rekurrens i det hele tatt: uten den ville en optimal helhet kunne bygges av ikke-optimale deler.

Bytteargument

Beviset for at et grådig valg er trygt: du tar en vilkårlig optimal løsning, bytter ut ett element med det grådige valget, og viser at resultatet er like godt og fortsatt lovlig. For aktivitetsutvelgelse byttes den aktiviteten i den optimale løsningen som slutter først, ut med den som slutter først i hele problemet. Det er argumentet sjanger H spør etter når oppgaven ber deg begrunne at grådighet virker.

Huffman-treet

Binærtreet Huffman bygger: tegnene sitter i bladene, venstre kant leses som 0 og høyre som 1, og koden til et tegn er veien fra rota ned til bladet. Kodelengden til et tegn er derfor dybden til bladet. Treet er som regel ikke balansert — hyppige tegn ligger grunt og sjeldne dypt. Et balansert tre er optimalt bare når alle frekvensene er like.

Kodelengde og totalkostnad

B(T) = \sum_{c \in C} c.freq \cdot d_T(c)

Prioritetskø i `Huffman`

O(\lg n)

Fast mot variabel kodelengde

\lceil \lg n \rceil

Hvorfor 0-1-ryggsekk ikke er grådig

\Theta(nm)

Grådighet mot dynamisk programmering

To paradigmer med samme forutsetning og ulik pris: begge krever optimal substruktur, men grådighet krever i tillegg grådig valg-egenskap. Dynamisk programmering prøver alle valg i hvert steg og lar tabellen avgjøre; grådighet tar ett valg og går videre. Derfor er grådighet raskere der den virker, og feil der den ikke gjør det. Kjenner du ikke igjen strukturen, er DP det trygge valget — det gir riktig svar også når grådighet ville gjort det.

Optimal prefikskode

En prefikskode som gjør totalt antall bits minst mulig for de gitte frekvensene. Huffman produserer alltid en slik kode, men den er ikke nødvendigvis entydig: ved like frekvenser kan flere ulike trær gi samme totalkostnad, og da er begge svar riktige. Kodelengdene er det som skal stemme, ikke hvilken side av rota et tegn havnet på.

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.