Læringsmål#
De studerende kan efter aktiviteten:
- Forklare hvad en greedy algoritme er (tag altid det lokalt bedste valg)
- Forklare hvornår greedy virker og hvornår den ikke gør
- Give et konkret eksempel på at greedy giver suboptimalt resultat
Forudsætninger#
De studerende forventes at kende til:
- Algoritmebegreb generelt
- Evt. introduktion til optimeringsalgoritmer
Kort beskrivelse#
De studerende får Matadorpenge og skal give byttepenge tilbage for et bestemt beløb ved altid at tage den største seddel/mønt der passer (greedy-strategien). Med standard denominationer (1, 2, 5, 10, 20, 50, 100, 200, 500 kr) virker det perfekt.
Så introduceres en 600 kr-seddel. Nu fejler greedy. Algoritmen griber 600 først, mens den optimale løsning (f.eks. to 500-sedler) kræver at man ser fremad.
Faglig kontekst#
- Semester/fag: Algorithms & Data Structures (valgfag)
- Holdstørrelse: Skalerer til alle holdstørrelser
- Organisering: Individuelt
Trin-for-trin#
- De studerende får udleveret Matadorpenge med standard danske denominationer.
- Opgaven: Giv byttepenge tilbage for [beløb X]. De studerende vil intuitivt altid bruge den største seddel/mønt der passer.
- De løser et par opgaver og vi tager en snak om grådige algoritmer.
- Underviseren introducerer 600 kr-sedlen i bunken.
- De studerende laver opgaverne igen. Der skal være opgaver, der “fejler” med den grådige algoritme pga. 600-sedlen f.eks. at give 1000 kr tilbage.
- Opsamling: hvad skete der? Hvad er forskellen på de to situationer? Hvornår kan man bruge grådige algoritmer?
Materialer#
- Matadorpenge med denominationer: 50, 100, 200, 500 kr
- Hjemmelavede 600 kr-sedler (evt 500 + 100 klistret sammen)
- Beløb til at give byttepenge for, inkl. opgaver der afslører greedy-fejlen
Tidsforbrug#
Ca. 30 min. inkl. opsamling.
Modtagelse#
Nogle studerende opdagede selv at noget gik galt da 600-sedlen blev introduceret og det er præcis det ønskede resultat. Den fysiske pengeseddel gør fejlen konkret og uomtvistelig på en måde abstrakte eksempler ikke gør.
Udvidelser#
- Lad de studerende designe deres eget denominations-sæt der får grådige algoritmer til at fejle for et bestemt målbeløb
Noter til underviseren#
600-sedlen virker fordi den er fysisk og absurd på samme tid. Den bryder den mentale model uden at det føles som et trick. Vælg målbeløbet til 600-sedlen-runden omhyggeligt. Det skal være et beløb hvor grådige strategi entydigt fører til et suboptimalt eller umuligt resultat.
