Posts Tagged ‘algoritm’

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

Selection Sort

maj 21, 2010

The Reinvigorated Programmer utfärdade en ny utmaning, implementera selection sort. Selection Sort är en ganska enkel (läs ineffektiv) sorteringsrutin som letar igenom en uppsättning värden och väljer ut det lägsta och placerar det först i en lista (kan vara in-place, dvs samma lista som innehåller de osorterade värdena).

Jag tyckte det här var en bra övning att träna på lite mer formella algoritm-beskrivningar så jag började med att sätta upp invarians, gränsfunktioner och pre/post-conditions (hur översätts dessa?) och skrev sedan min algoritm utifrån dessa beskrivningar. Eftersom det är första gången jag skriver dessa formella beskrivningar är jag lite osäker på om jag uttrycker det jag vill att algoritmen skall göra på rätt sätt. Jag uppskattar därför alla kommentarer på nedanstående c-kod och beskrivningar.

/*
 * Invariant: if val at any position i in an array array of length len
 *  is lower than the current value at j in the array the value is at
 *  an i > j and i < len
 *
 * bound function: 0 <= j < length - 1
 *                 j <  i < length
 *
 * precondition:  a[] is an unsorted array of integers of the size len
 * postcondition: a[] is an array sorted higher to lower
 * */
void selectSort(int a[], int len)
{
  int tempStore, i, j;

  for (j = 0; j < len - 1; j++)
  {
    for (i = j + 1; i < len; i++)
    {
      if (a[i] < a[j])
      {
	tempStore = a[j];
	a[j] = a[i];
	a[i] = tempStore;
      }
    }
  }
  return;
}

syntax highlighted by Code2HTML, v. 0.9.1

Binärsökning

april 28, 2010

Bloggen The Reinvigorated Programmer gav för ett par dagar sedan dess läsare i uppdrag att skriva en binär sök-algoritm i valfritt språk utan att testa (för annat än syntax-fel) och sedan skicka in. Detta pga en undersökning som visade på att endast 10% av programmerare kan producera en buggfri binär sök-algoritm.

Jag gjorde ett försök och i slutänden kom jag fram till följande funktion:

int binSearch(int a[], int size, int target)
{
  int lowPos = 0, highPos = (size - 1), middlePos = (highPos / 2);
  int returnVal = -1;
  while ((lowPos <= highPos) && (a[middlePos] != target))
  {
    middlePos = (lowPos + highPos) / 2;

    if (target > a[middlePos])
      lowPos =   middlePos + 1;
    else
      highPos =  middlePos - 1;
  }

  if (a[middlePos] == target)
    returnVal = middlePos;

  return returnVal;
}

syntax highlighted by Code2HTML, v. 0.9.1

En binär sökning söker igenom en sorterad lista värden och tittar ifall mittenvärdet är högre eller mindre (eller lika med) det sökta värdet, sedan halveras listan till den halva som bör innehålla det sökta värdet (t.ex övre halvan om mittenvärdet är 16 och det sökta värdet är 20). Detta upprepas tills mittenvärdet är lika med det sökta värdet eller den kvarvarande listan är tom.

Tyvärr fixade jag det inte på första försöket (och är inte hundra på att funktionen är buggfri) utan behövde testa och se att min rutin inte fungerade. Jag hamnade i ett så kallat off-by-one-läge, dvs att sökningen stannade ett ifrån det sista elementet (som borde innehålla det sökta värdet ifall det finns i listan).

Nyckeln var att inse att ett mittenelementet som inte är lika med det sökta värdet kan exkluderas. Detta leder till att delningen av listan blir

    if (target > a[middlePos])
      lowPos =   middlePos + 1;
    else
      highPos =  middlePos - 1;

Detta tog mer tid att klura ut än jag vill erkänna, men jag var nöjd när jag äntligen förstod vad och framför allt varför.

The Reinvigorated Programmer håller just nu på att gå igenom lite mer formella metoder för att beskriva algoritmer, det är kul att läsa. hitintills har han gått igenom invarianser och gränsfunktioner. Det är intressant att lära sig lite mer om algoritm-design, jag försöker skriva vad jag vill göra på papper innan jag programmerar men de här metoderna gör det möjligt att bevisa att man gör rätt.

I övrigt är det också en trevlig blogg, mycket programmering men också recensioner av de nya Doctor Who-avsnitten. Jag rekommenderar den varmt.

Ifall någon som kan lite om binär sök-algoritmen snubblar in skulle jag uppskatta att samtliga fel i koden ovan pekades ut.