Av: Mildrid Ljosland, førstelektor og faglærer i programmeringsfag

Neste år er det kommunevalg igjen, og når stemmene er talt opp, skal representantene fordeles på de ulike partiene. Hvis du tror det er så enkelt som at partiene får like stor andel av representantene som de har fått andel stemmer (at 30% av stemmene gir 30% av representantene), må du tro om igjen. Så enkelt er det ikke. Valgloven spesifiserer en måte å beregne representantene på som gir en morsom utfordring til den som skal programmere en slik beregning.

Ifølge valgloven skjer fordelingen på følgende måte: Først beregnes antall listestemmer hvert parti har fått. Antall listestemmer for et parti er antall stemmer det har fått multiplisert med antall representanter som skal velges, justert for eventuelle endringer foretatt på stemmeseddelen (vi ser bort fra slike endringer her).

Etter at antall listestemmer er funnet, deles dette tallet på henholdsvis 1.4, 3.0, 5.0, 7.0, 9.0 osv. Det foretas like mange divisjoner som det er representanter som skal velges, og resultatene kaller vi fordelingstall. Denne beregningen av fordelingstall gjøres for alle partiene. Og så plukker vi ut fordelingstallene i rekkefølge, det største først, og tildeler tilhørende parti en representant for hvert tall. Hvordan programmere dette?

Eksempel: Det skal velges 6 representanter og 2 partier har stilt til valg. Parti A fikk 120 stemmer og parti B fikk 85 stemmer.

Da får vi følgende utregninger:

• Parti A: 720 listestemmer, fordelingstall 514.3, 240.0, 144.0, 102.9, 80.0, 65.5
• Parti B: 510 listestemmer, fordelingstall 364.3, 170.0, 102.0, 72.9, 56.7, 46.4
• De 6 største tallene: 514.3, 364.3, 240.0, 170.0, 144.0, 102.9
• De tilhørende partiene: A, B, A, B, A, A

Altså vil parti A få 4 representanter og parti B få 2 representanter. Her kan du se et konkret eksempel på valgresultatet fra Trondheim i 2007.

Valgresultatet for Trondheim i 2007

Den enkleste måten å programmere dette på, er å produsere alle fordelingstallene, sortere dem (synkende), og gå gjennom den sorterte rekka og tildele representanter til riktig parti. I vårt eksempel blir det 6*2=12 tall som skal sorteres, mens et mer realistisk eksempel med 85 representanter og 12 partier gir 85*12=1020 tall.

Sortering er en velkjent oppgave innen databehandling, og det finnes mange sorteringsalgoritmer. En av de enkleste å programmere kalles Boblesortering. Men ulempen med den er at den er lite effektiv. Hvis vi bruker antall sammenlikninger mellom to tall som mål for hvor effektiv algoritmen er, vil Boblesortering få cirka 1020*1020/2 = 500.000 sammenlikninger i dette tilfellet. Den mest effektive sorteringsalgoritmen vi kjenner, Quicksort, vil i det samme eksemplet nøye seg med 1020*log(1020) = 1020*10 = 10.000 sammenligninger. Det vil altså gå 50 ganger raskere å bruke Quicksort framfor Boblesortering i dette tilfellet. (Forskjellen blir større dess flere tall som skal sorteres.)

Men når det gjelder beregning av kommunestyrerepresentanter, kan vi lage en algoritme som er enda mye raskere. Vi trenger nemlig ikke å sortere alle de 1020 tallene, bare finne de 85 største. Det kan gjøres på følgende måte:

Først tar vi det første (og største) fordelingstallet for hvert parti og sorterer dem. Deretter register vi at det partiet som har det største fordelingstallet, får en representant. Så bytter vi ut dette fordelingstallet med neste fordelingstall for dette partiet, og sorterer tallene på nytt. Slik fortsetter vi til alle representantene er fordelt. I vårt enkle eksempel: Først tar vi tallene 514.3 og 364.3, sorterer dem (ingen endring), og tildeler parti A en representant. Så erstatter vi 514.3 med 240.0, sorterer på nytt og får 364.3, 240.0, tildeler parti B en representant, erstatter 364.3 med 170.0 og så videre. Siden vi nå har langt færre tall som skal sorteres, er dette mye raskere enn den opprinnelige algoritmen. For vårt realistiske eksempel med 85 representanter og 12 partier, vil vi få cirka 12*12/2+84*11 = 996 sammenligninger totalt, altså 10 ganger raskere enn Quicksort på alle tallene. Denne utregningen er basert på at vi bruker Boblesortering til å sortere de opprinnelige 12 tallene, og deretter Innsettingssortering til å sortere på nytt når vi har erstattet det største. Innsettingssortering har nemlig den egenskapen at den er veldig effektiv hvis dataene er nesten sortert fra før, slik at det bare er noen få tall som ikke er på riktig plass. Og det er tilfellet her, det er bare det tallet vi erstattet som ikke er sortert, de andre tallene er ferdig sortert fra før.

En annen måte å løse problemet på, er å bruke en heap. En heap er en tabell av tall der det første tallet er det største, og tallene blir mindre etter hvert som vi går utover i tabellen, men uten at tallene er fullstendig sortert, men organisert på en spesiell måte. For eksempel kan tall nummer 3 være større enn nummer 2, men både nummer 2 og 3 må være mindre enn nummer 1. I vårt realistiske eksempel kan vi opprette en heap med 12 plasser og putte inn det første fordelingstallet for hvert parti. Det kan gjøres med 25 eller færre sammenligninger. Når vi har fått laget heapen, vet vi at det største tallet ligger først. Så da kan vi tildele en representant til dette partiet, og erstatte dette tallet med neste fordelingstall for dette partiet. Så må vi omorganisere heapen slik at det nye tallet kommer på riktig plass og nytt største-tall kommer fremst. Det kan gjøres med 6 eller færre sammenligninger. Så gjentar vi prosessen til alle representantene er funnet. Totalt trenger vi makimalt 25 + 84*6 = 529 sammenligninger. Så da har vi fått programmet vårt til å gå enda nesten dobbelt så raskt.

Fagområdet Algoritmer og datastrukturer omhandler blant annet hvordan man løser ulike standardproblemer og hvor effektive løsningene er. For eksempel er sorteringsalgoritmer en sentral del av fagområdet, og har blitt gjenstand for mye forskning gjennom tiden. Fagområdet handler om å skaffe seg et variert utvalg av verktøy som kan tas i bruk når behovet melder seg. Eksemplet med beregning av kommunestyrerepresentanter er ganske typisk. Man har et problem, og ser i verktøykassa om man finner et passende verktøy. Noen ganger finner man flere mulige verktøy (måter å løse problemet på), og da må man finne ut hvilket verktøy som gir best resultat (mest effektivt program). I vårt eksempel finner vi flere mulige måter å sortere på, samt at vi også finner vertøyet ”heap”. Og så må vi regne litt for å finne ut at heap er den beste løsningen her.

Har du innspill eller kommentarer?

Dette innlegget har 1 kommentar. Gjerne bidra :-)

Skrevet av: itfag (totalt 65 blogginnlegg)

1 comment

<< Teamarbeid

Zotero – Et glimrende verktøy til å kontrollere kildene >>