girig algoritm

algoritm som för varje steg i beräkningen väljer det bästa värdet just då, utan att ta hänsyn till vilka konsekvenser det får för beräkningen som helhet. Algoritmen räknar kortsiktigt och kan ”måla in sig i ett hörn” eller suboptimera. Den gör ingen förhandsvärdering av kommande steg i beräkningen. Men ibland kan en girig algoritm ge det bästa resultatet. – På engelska: greedy algorithm.

[algoritmer] [17 september 2019]

effektivitet

(efficiency) – inom it: algorithmic efficiencyalgoritmisk effektivitet – al­go­ritmens förmåga att lösa sin uppgift med minsta möjliga användning av resurser. Med resurser menas här främst processorcykler och minnes­kapa­ci­tet. Effektiviteten har samband med hur lång tid det tar att lösa upp­giften. – Språkligt: Notera skillnaden mellan engelska efficient och effective: 

  • – att vara efficient är att få saker gjorda snabbt och resurssnålt;
  • – att vara effective är att ha avsedd verkan.

– Effectiveness har definierats som ”extent to which planned activities are realized and planned results achieved”. Båda orden motsvarar ofta svenska effektiv. Men för efficient används ibland omskrivningar som hög verk­nings­grad: en motor kan vara energy efficient. ”This offer is effective starting January 1st” betyder att erbjudandet gäller från den 1 januari (träder i kraft), inte att erbjudandet blir ”effektivt” då, vad det nu skulle innebära.

[algoritmer] [programmering] [språktips] [ändrad 29 juni 2017]

genetisk algoritm

(genetic algorithm, förkortas ibland GA) – program som löser problem genom att testa och förädla slumpmässigt fram­tagna lösnings­förslag. Förebilden är den bio­logiska evolutionen med naturligt urval och mutationer. – Tekniken används på problem som inte kan lösas på rimlig tid med vanlig programmering, men där det är enkelt att utvärdera en föreslagen lösning (se NP). Pro­gram för genetiska algoritmer slumpar fram miljon­tals godtyckliga lösningar som testas. De bästa får ”para sig” med varandra (man sätter ihop ena halvan av en lösning med andra halvan av en annan) och ”avkomman” testas på samma sätt. Pro­grammet gör också ”mutationer”, alltså slump­artade förändringar av existerande lösningar (detta för att förebygga sub­optimering). – Genom att köra programmet om och om igen och bearbeta de bästa lösningarna kan man till sist få fram använd­bara lösningar på problem som annnars skulle vara ohanterliga. En förut­sättning är att lösningen går att formulera i ett fast format, till exempel ett bestämt antal tecken. Tekniken har använts inom metallurgi (för att få fram legeringar med önskade egen­skaper) och för planering och optimering (där ett visst antal element ska ordnas på bästa möjliga sätt). – Jäm­för med genetisk pro­gram­mering.

[algoritmer] [forskning och experimentell teknik] [ändrad 9 januari 2018]