Göm menyn

Problemlösning

Konsten att lösa problem

Problemlösning är inte helt enkelt, vilket är ganska naturligt. Det finns dock några generella steg som man genomgår när man löser problem och detta brukar kallas problemlösningsprocessen.

George Polya (1945) skrev i How to solve it att det består av fyra steg:

  1. Förstå problemet
  2. Ta fram en plan
  3. Genomför planen
  4. Utvärdera lösningen.

Insert meme here

Förstå problemet

  • Kan du formulera om problemet med dina egna ord?
  • Förstår du alla ord och begrepp i problemformuleringen
  • Vad vet vi och vad är okänt?
  • Finns det överhuvudtaget tillräckligt med information för att lösa problemet?
  • Kan du rita en bild eller ett diagram som hjälper dig att förstå problemet?
  • Vad är egentligen målet? Hur vet vi när vi är klara?
  • Har du läst hela texten?

Ta fram en plan (algoritm)

  • Gör ett försök och testa lösningen, och upprepa flera gånger.
  • Jämför med lösningar på andra, gärna likartade, problem.
  • Lös en mindre del eller en variant av problemet först.
  • Dela upp problemet i mindre delar och lös varje del för sig.
  • Formulera om problemet och ta fram en lösning som når målet, men inte på samma sätt som problemet är formulerat.

Genomför (implementera) planen

Allt är nu på plats, bara att implementera.

Utvärdera lösningen

  • Kontrollera att lösningen är korrekt genom att jämföra den med det mål som uttrycks i problemet.
  • Fundera över om lösningen kan användas för att lösa andra problem, antingen rakt av eller med mindre ändringar.
  • Fundera över vad du har lärt dig. Vilken ny kunskap har du? Hur har din problemlösningsförmåga utvecklats.

Algoritmer

"An algorithm is an ordered set of unambiguous, executable steps, that defines a terminating process".

En algoritm kan liknas vid ett recept; den innehåller ett antal steg som ska utföras i en viss ordning och efter att alla steg har slutförts så är man färdig (förhoppningsvis med en trevlig måltid).

Alt text

Vi kan använda oss av olika metoder för att illustrera vår algoritm innan vi implementerar den i kod. Ett metod är att rita ett flödesdiagram.

Flödesschema för TV-tittande

flowchart

Pseudokod är som namnet antyder inte riktig kod. Det är ett sätt att skriva kod ämnat åt människor istället för datorer och används för att beskriva algoritmer.

Pseudokod för TV-tittande

Övergripande lösningsmodeller

Ska du lösa ett stort problem behöver du välja vilken ände du bearbetar först. Vi kommer två lösningsmodeller. Dessa är bottom-up och top-down.

models

Programmering enligt top-down-modellen

  • Börja med att titta på problemet i helhet. Försök att dela upp det i mindre, namngivna, delproblem som kan lösas oberoende av varandra.
  • Specificera delproblemen. Vad ska funktioner ta för indata och vad ska dom returnera för utdata? Delegera uppgiften att lösa delproblemen till någon annan, eller till dig själv vid en senare tidpunkt.
  • Med väl specificerade delproblem som är oberoende av varandra får man också en bra struktur på programmet. En del av programmet behöver inte känna till eller bry sig om resten (inga globala variabler, alltså). Detta brukar på engelska kallas separation of concerns och är något man ofta vill sträva mot även om man inte tillämpar top-down-modellen.

Exempel

Vi vill ha ett program som kan simulera n slumpvandringar med k steg. Varje steg är en längdenhet och kan gå i en av fyra riktningar: vänster, höger, uppåt, nedåt.

För varje slumpvandring ska längden mellan start- och slutpunkten beräknas, och i slutet ska genomsnittet av alla längderna beräknas.

Detta är programmeringsövning 13 från kapitel 9 i läroboken och vi ska lösa detta problem steg för steg enligt top-down-modellen.

Slumpvandring

example

Huvudprogrammet

topdown-example

Funktioner på andra nivån

topdown-example

topdown-example

topdown-example

Funktioner på tredje nivån

topdown-example

topdown-example

Exempel på körning

Samma problem enligt bottom-up-modellen

  • Börja med att konstrura en funktion som kan göra någonting som verkar ha med problemet att göra. Utforma enhetstester och testa (och korrigera) funktionen tills den funkar. Börja med det som verkar lättast, svårast, viktigast eller liknande.
  • Bygg på med ytterligare funktioner, som också enhetstestas ordentligt, tills programmet löser hela problemet.

Algoritmkomplexitet

Vi vill gärna konstruera en algoritm som är så effektiv som möjligt (går snabbt och använder lite minne). Vi kan naturligtvis testa detta med olika verktyg, men vi kan också teoretiskt beräkna algoritmens komplexitet. Många gånger handlar det om att det någonstans i algoritmen finns en kostsam operation som man vill göra så få gånger som möjligt. Vi ska analysera ett sådant exempel

Algoritm för sy ett lapptäcke

Vi ska sy ett lapptäcke med 8 x 8 rutor som består av fyra olika färger arrangerade i mönstret nedan.

tacke

  • Hur kan vi göra det så rationellt som möjligt?
  • Vad är det för kostsam grundoperation som vi vill minimera.
  • Hur många gånger behöver vi utföra operationen för att skapa ett lapptäcke med n x n rutor?

Låt oss säga att den kostsamma operationen är att göra sömmarna, medan t.ex. sprätta är enkelt.

Algoritm 1

  1. Sy ihop kvadraterna i en rad med varandra så vi får åtta rader.
  2. Sy ihop de färdiga raderna med varandra.

alt text

Algoritm 2

  1. Konstruera fyra kvadrater av fyra remsor
  2. Skär isär dem till remsor på andra ledden.
  3. Sy ihop remsorna.

alt text

Algoritm 3

  1. Sy ihop 8 remsor som är 8 kvadrater breda.
  2. Sy ihop remsorna till ett rör.
  3. Skär röret 7 gånger.
  4. Sprätta en söm i varje cirkel, men på olika ställen.
  5. Sy ihop de 8 olika remsorna.

alt text

Tidskomplexitet för lapptäcksalgoritmer

alt text

Sammanfattning

  • Det finns ingen enkel metod som löser alla problem, men det finns många tips på strategier som kan funka i många fall.
  • Två övergripande strategier är top-down och bottom-up.
  • Algoritmer är generella beskrivningar av hur program kan funka. De kan uttryckas på flera olika sätt, t.ex. med pseudokod eller flödesdiagram. Redan innan vi har implementerat algoritmerna kan vi analysera deras komplexitet.

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-15