Algoritmisk Tenkning

Den nye fagfornyelsen i mattefaget legger vekt på algoritmisk tenkning (computational thinking), som Jeannette M. Wing kaller “thinking like a computer scientist”. Wing definerer algoritmisk tenkning på en mer beskrivende måte som: 

“The thought processes involved in formulating a problem and expressing its solution(s) in such a way that a computer—human or machine—can effectively carry out.”

— Jeannette M. Wing

Her er en oppgave som kan benyttes til å trene en slik tenkemåte, med tema sannsynlighetsregning som kunne passet til 1T eller R1 matte. Den forutsetter at du har tilegnet deg kompetanse i grunnleggende programmering i Python.

200 Baller i en bøtte

Du har en bøtte med 200 baller, 100 hvite og 100 svarte. Plukk to tilfeldig valgte baller fra bøtta. Dersom de har samme farge legger du en svart ball tilbake i bøtta; dersom de har ulike farge legger du en hvit ball tilbake i bøtta (du har ubegrenset antall baller tilgjengelig). Repeter til det bare er en ball igjen. Hva er sannsynligheten for at den siste ballen i bøtta er svart? 

Hvordan ville en computer scientist løst dette problemet? Med programmering kan vi modellere og eksperimentere med denne prosessen mange ganger. Vi kan for eksempel gjøre 1000 forsøk og se hvor mange ganger den siste ballen ender opp med å være svart. Før du leser videre, kan du gjerne tenke gjennom hvordan du vil løse dette med programmering. 😊

Her er et eksempel på hvordan dette kan løses algoritmisk, med Python:

import random 

# Antall ganger den siste ballen er svart.
count = 0      

#1000 forsøk
for i in range (1000):              
      #B for black og W for white. En liste som inneholder 100 “B” og 100 “W”
      balls = [“B”]*100 + [“W”]*100 
      
      # Kjør så lenge det er mer enn en ball igjen
      while len(balls) > 1:          

         # Rekkefølgen av elementene(ballene) i listen skal stokkes om helt tilfeldig
         random.shuffle(balls)       
         
         # Plukk to baller (de to siste) fra lista
         pop1 = balls.pop()       
         pop2 = balls.pop()       
            
         # Hvis de to ballene er like skal en svart ball legges til i lista;
         # hvis ikke, legger vi til en hvit. 
         if pop1 == pop2:           
            balls.append(“B”)
         else:
            balls.append(“W”)
      
      # Eksperimentet er ferdig, vi sjekker om den siste ballen er svart
      if balls[0] == “B”:
         # Hvis den er det registrer vi ett tilfelle av “siste ball er svart”           
         count += 1               

# Print resultatene når alle eksperiment er ferdig 
print(count)     

En analytisk / matematisk forklaring: 

Resultatene over viser at 1000 av 1000 forsøk(100%) ender opp med en svart ball til slutt. Hvordan kan vi forklare dette på en analytisk måte? (Du kan tenke litt selv før du leser videre) Hver gang vi trekker ut to baller, vil antall baller i bøtta reduseres med en, ettersom vi alltid legger en ball tilbake. Til slutt vil det være en svart ball eller en hvit ball igjen. Siden antall hvite baller enten er uendret (vi trekker to ulike baller hvor en er hvit, og legger tilbake en hvit, eller vi trekker to svarte og legger tilbake en svart), eller redusert med to (vi trekker to hvite og legger tilbake en svart) for hver operasjon, er det umulig å ha en hvit ball igjen til slutt, så det må være en svart ball igjen. 

Denne logiske forklaringen bekrefter resultatet fra den algoritmiske løsningen. Vice versa, om du hadde kommet frem til en analytisk løsning først, kunne du også prøvd en algoritmisk løsning for å se om din forklaring stemmer.