Archive for januari, 2013

På begäran: Algoritmer(!)

januari 19, 2013

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å.

Annonser

2012 i böcker

januari 13, 2013

Som vanligt vill jag egentligen läsa mer än vad jag egentligen gör:

  • Fermat’s Enigma: Boken behandlar matematikens historia, från de gamla grekerna och Pytagoras till moderna tider med fokus på Fermats obevisade teorem (a^n+b^n=c^n är endast sant för n <= 2 om jag minns rätt). Fermat skrev detta teorem i marginalen av en matematikbok tillsammans med att han har ett mycket vackert bevis för detta men att marginalen är för liten för att det ska få plats. Detta har retat gallfeber på matematiker genom århundradena och varit olöst fram till för inte allt för många år sedan. Simon Singh har en fantastisk förmåga att på ett intressant vis redogöra för hur idéer hänger ihop och förenkla de djupa koncepten så pass att man som läsare snabbt får en ytlig insikt i problematiken och dess lösning.
  • Player One: Detta är den första bok av Douglas Coupland jag läser och jag fann den mycket snabbläst och jag hade svårt att lägga den ifrån mig. Ett udda gäng resenärer sitter i en bar medan världen utanför går under lite grann. En av dessa bargäster, en autistisk tjej, bär på en andra personlighet Player One. Player One analyserar händelserna och förutsäger hela tiden vad som kommer att ske.
  • K55: Lögnernas valv: Svensk dystopi på den lilla planeten K55, där människorna trängs i en underjordisk bunker dit de förpassats av en epidemi på ytan. Boken följer en grupp soldater i träning inför ett uppdrag att kontrollera ifall ytan åter är beboelig, men givetvis finns det förrädare lögner och andra hinder på resans väg. Boken känns på något sätt väldigt svensk och historien är intressant även om kvalitéten är en aning ojämn.
  • The Legend of the Jade Phoenix Trilogy: Detta är en av de stora trilogierna i Battletech universumet och kretsar kring en ung kadett i en av Klanen Jade Falcon’s syskonkompanier. Huvudkaraktären blir utsatt för ett socialt experiment, efter att ha förlorat sin rätt att bli krigare införs han i ett kompani frifödda (och inom klanen lägre stående). Det hela blir social kamp, en kamp på slagfältet samt en kamp att återvinna sin identitet som trueborn.
  • Om de bara kunde tala: James Herriot’s underfundiga semi-biografi är fantastisk! Lättläst, rolig och gripande på samma gång. Humorn glänser med det där lilla extra som självinsikt ger och får det hela att bli en utomordentligt mysig läsning. Uppdelningen i korta historier gör att boken är något man kan plocka upp och läsa i fem minuter och sedan lägga ner igen eller läsa timmar i sträck.
  • Ship of Fools: Ett koloni-skepp som har färdats i århundraden mellan olika stjärnsystem och ännu inte hittat en hamn att kalla hem. I jakt på ett hem undersöker de en signal och hittar en makaber scen i ett märkligt koncept. En rymdopera helt i min smak, där det okända är det största hotet.
  • Coalescent: George Poole upptäcker en förlorad tvillingsyster i samband med hans pappas död och beger sig på en jakt runt planeten för att få reda på sanningen. Parallellt berättas historien om en Romersk kvinnas kamp för att skydda sin familj medan det romerska imperiet rasar runt henne och säkerhet är svår att finna.
  • Alla mina fyrfota vänner: Bok två i serien av och om James Herriot. Precis lika bra som den första.
  • Skattkammarön: En klassiker bland klassiker som är precis så läsvärd som man hoppas och har allt man önskar av en piratbok. Godhjärtade brittiska aristokrater, lömska pirater, klipska småpojkar och givetvis en jätteskatt.
  • Nästan bara rara djur: Tredje boken av och om James Herriot. Lika bra som de tidigare.
  • Going Out: Detta sägs vara vändpunkten i Scarlett Thomas böcker, den första som visar det vassa skrivsätt hon nu är känd för. Boken kretsar runt Luke och Julie som är instängda fast på helt olika sätt. Luke är allergisk mot allt (inklusive solljus) och Julie är rädd för det mesta och vill inte att något förändras. De beger sig ut på jakt efter en helare som är på besök i Wales.