beteckning på ett sätt att uppskatta komplexiteten i typer av beräkningar. Noteras med bokstaven O och används för jämförelser av algoritmers effektivitet. – Antalet element i beräkningen, till exempel antalet ord som ska sorteras i bokstavsordning, ställs mot antalet steg i beräkningen. Då menar man inte antalet steg i ett specifikt fall, utan generellt för en typ av beräkning. Om det till exempel gäller att hitta ett ord i en lista som innehåller n ord är ordo O(n). Det vill säga att antalet steg i sökningen är proportionellt mot antalet ord i listan (n). Sedan kan det ju vara så att ordet man söker efter står först i listan, och då går sökningen fort, eller att ordet står sist i listan, och då tar sökningen lång tid. Det påverkar inte värdet på ordo. Det viktiga är att man aldrig behöver gå igenom listan mer än en gång för att hitta det sökta ordet. Ordo anger det största möjliga antalet steg i beräkningen (värsta fallet). – Andra beräkningar, till exempel att sortera tal i storleksordning eller ord i bokstavsordning, kräver att mängden tal respektive ord gås igenom flera gånger (om mängden inte redan står i rätt ordning). Då får man värden på ordo som O(n2), O(n3) eller O(2n). – När man beräknar ordo brukar man bortse från konstanter, och om beräkningen innehåller höga potenser kan man också bortse från lägre potenser. Att beräkna ordo är en överslagsberäkning, inte en exakt beräkning. – Man skiljer mellan stora O och lilla o: stora O anger det högsta möjliga värdet för antalet moment i en beräkning av viss typ, medan lilla o anger ett övre värde som inte kan uppnås, men nästan (ett asymptotiskt värde). – Det finns också omega (Ω), som anger det lägsta möjliga värdet, samt theta (θ) som säger att antalet moment i beräkningen är exakt proportionellt med funktionen av n.
[matematik] [programmering] [22 december 2020]
the Ofqual exam results algorithm – en algoritm för betygsättning som användes 2020 i Storbritannien, men som gav sådana resultat att de maskinsatta betygen drogs tillbaka. I stället fick eleverna de betyg som deras lärare hade satt. – Ofqual-algoritmen användes 2020 med anledning av Covid 19‑pandemin i stället för skrivningar. Den utgick från lärarsatta betyg och en rangordning av elever i varje klass. Betygsättningen gällde dels A-level (motsvarar närmast gymnasieexamen), dels GCSE (ämnesbetyg). Algoritmen skulle anpassa betygsättningen så att den totala fördelningen av olika betyg skulle följa samma kurva som tidigare år. Resultatet blev emellertid att många betyg sänktes en eller två steg jämfört med det betyg som respektive elevs lärare hade satt, men elever på små skolor, i synnerhet små privatskolor, fick högre betyg. Den 18 augusti 2020 beslöt Ofqual (Office of qualifications and examinations regulation – länk) att de lärarsatta betygen skulle gälla. Ett resultat blev att många elever som hade sökt till universitet först blev avvisade, men efter ändringen blev antagna, vilket ledde till överintagning.
[algoritmer] [utbildning] [8 september 2020]
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]
(efficiency) – inom it: algorithmic efficiency – algoritmisk effektivitet – en algoritms 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 minneskapacitet. Effektiviteten har också samband med hur lång tid det tar att lösa uppgiften. – 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 verkningsgrad: 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. När det gäller bland annat läkemedel talar man på svenska om att läkemedlet, om det ger önskat resultat, är verksamt.
[algoritmer] [programmering] [språktips] [ändrad 1 april 2020]
(genetic algorithm, förkortas ibland GA) – program som löser problem genom att testa och förädla slumpmässigt framtagna lösningsförslag. Förebilden är den biologiska 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). Program för genetiska algoritmer slumpar fram miljontals 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. Programmet gör också ”mutationer”, alltså slumpartade förändringar av existerande lösningar (detta för att förebygga suboptimering). – Genom att köra programmet om och om igen och bearbeta de bästa lösningarna kan man till sist få fram användbara lösningar på problem som annnars skulle vara ohanterliga. En förutsä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 egenskaper) och för planering och optimering (där ett visst antal element ska ordnas på bästa möjliga sätt). – Jämför med genetisk programmering.
[algoritmer] [forskning och experimentell teknik] [ändrad 9 januari 2018]