På begäran: Algoritmer(!)

Helt kort är en algoritm ”en steg-för-steg beskrivning av hur ett problem löses”. Givetvis är detta inte hela sanningen eftersom ovanstående beskrivning är rätt vag och till exempel skulle inkludera följande exempel (Men om någon säger här är en algoritm för hur man löser Rubiks-kub är det ovanstående förenkling som menas):

Pannkakor med hallonsylt:

  1. Värm upp en stekpanna
  2. Vänta 10 sekunder på att färdiga pannkakor dyker upp till följd av fluktuationer i vakuumenergin. Ifall inga dyker upp under väntetiden upprepa steget.
  3. Servera med sylt

Med ovanstående försök till algoritm finner man ett par problem, dels är det lite kommer man inte veta när man ska börja för att vara klar till lunch då steg två är väldigt svårt att avgöra hur lång tid detta tar. Man kan inte ens garantera att antalet gånger man får upprepa steg två är ändligt.

Ett annat problem är att algoritmen inte är tillräckligt tydlig, t.ex säger den inte explicit vilken sylt som skall användas i steg tre. Så när man väl är färdig med steg två slänger man på en klick hjortronsylt (eftersom inget annat är bestämt)  och serverar förvånade gäster som blivit lovade pannkakor med hallonsylt.

Algoritm är en matematisk term som ofta används i det relaterade ämnet datavetenskap för att kunna analysera delar av program och kunna designa mer effektiva lösningar samt för att kunna bevisa att någonting fungerar.

Matematiken kräver i detta fall inte siffror men däremot strikta kriterier.Dessa är ändlighet, bestämdhet, indata, utdata, effektivitet.

  • ändlighet: algoritmen måste terminera (bli klar) efter ett ändligt antal steg. Notera att ett ändligt tal kan vara vilket tal som helst och precis hur stort som helst förutom oändligheten (eller utom samtliga oändlig tal eller hur man nu ska skriva)
  • bestämdhet: Varje steg i algoritmen skall vara precist och det skall inte kunna tolkas på flera sätt.
  • indata: en algoritm skall få minst noll (0) indata.**
  • utdata: algoritmen skall alltid producera en eller flera utdata relaterade till indatan.
  • effektivitet: varje steg skall vara trivialt att genomföra, dvs. så pass enkelt att till och med en människa skall kunna genomföra varje steg endast med hjälp av papper och penna.

Värt att notera är att de flesta datorprogram inte är algoritmer då t.ex ett operativsystem inte får terminera och att interaktiva program inte kan garanteras att terminera (användaren kan ha uppfunnit en evig energikälla kopplat den till datorn och startat MS-Röj för att sedan tragiskt dö av en mikrometeorit och därför aldrig trycka på avslutningsknappen).

Exempel på kända algoritmer är euklides algoritm (bestämmer två heltals minsta gemensamma nämnare), quicksort (en sorteringsalgoritm) och givetvis Cooper-Wolowitz vänskapsalgoritm:

Sheldon Cooper's vänskapsalgortm med tillägg av Howard Wolowitz

Sheldon Cooper’s vänskapsalgortm med tillägg av Howard Wolowitz

Ovanstående text är uttänkt, nedtecknad (men inte nödvändigtvis i den ordningen) men ej läst av mig.

* Mmmm, hjortron…

** Enligt vad jag läst skall en algoritm i teorin kunna hantera ett oändligt antal indata, men detta är jag osäker på.

Etiketter: ,

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s


%d bloggare gillar detta: