Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Grådige algoritmer, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En algoritme som bygger løsningen steg for steg og alltid tar det lokalt beste valget.
At et lokalt optimalt valg kan inngå i en globalt optimal løsning, slik at vi aldri trenger å angre.
Bevisteknikken der vi viser at en optimal løsning kan endres til å inneholde det grådige valget uten å bli dårligere.
Å velge flest mulig ikke-overlappende aktiviteter ved alltid å ta den som blir ferdig først.
En grådig algoritme som lager en optimal prefiksfri koding ved gjentatt å slå sammen de to minst hyppige symbolene.
En koding der ingen kodeord er prefiks av et annet, slik at en kodet streng kan dekodes entydig.
Begge trenger optimal delstruktur, men grådighet velger uten å vurdere alle delinstanser — det virker bare for enkelte problemer.
At en optimal løsning på problemet inneholder optimale løsninger på delproblemer av samme type. En forutsetning både for grådige algoritmer og dynamisk programmering.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Grådig-valg-egenskapen
Et grådig valg er trygt dersom det finnes en optimal løsning som inneholder det. Et utbyttingsargument viser dette.
Aktivitetsutvelgelse
Ved å alltid velge den aktiviteten som blir ferdig først, etterlater vi mest tid til resten — og maksimerer antall ikke-overlappende aktiviteter.
Huffman-koding
Den vektede stilengden er summen av hver tegnfrekvens ganget med dybden i kodetreet. Huffman slår sammen de to minst hyppige tegnene gjentatte ganger og minimerer .
Grådig krever optimal delstruktur
Etter et grådig valg gjenstår én mindre delinstans av samme type. Mangler denne strukturen, kan grådighet feile.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare hva en grådig algoritme er, og avgjøre med et eksempel om en grådig regel gir et optimalt svar
- 02Beskrive optimal delstruktur og grådig-valg-egenskapen, og bruke et utbyttingsargument til å bevise at et grådig valg er trygt
- 03Kjøre aktivitetsutvelgelse på et eksempel ved å velge tidligst slutt-tid, og forklare hvorfor den regelen er optimal
- 04Bygge et Huffman-tre nedenfra fra frekvenser, lese av de prefiksfrie kodeordene, og forklare hvorfor de to minst hyppige tegnene slås sammen først