ordo

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]

exakt

exakt används i två betydelser:

  • – i beräkningar: exakt 1 betyder 1,00… – inte 0,99 eller 1,01;
  • – i logik och definitioner: exakt 1 betyder 1 och bara 1 – det får bara vara ett värde, inte två eller flera – inte heller noll. (Se också en‑entydig.)

[matematik och logik] [14 september 2020]

en-entydig

i logik: benämning på förhållanden där ett objekt står i en viss relation till ett och bara ett annat objekt, och det andra objektet i sin tur står i motsvarande relation till det första objektet, och bara till det objektet. – Exempel: att Oslo är huvudstad i Norge är en en‑entydig relation: Oslo är inte huvudstad i något annat land, och Norge har bara en huvudstad. Det behöver alltså inte vara samma relation i båda riktningarna – Norge är inte huvudstad i Oslo. – Bara entydig betyder däremot att relationen är en‑mångtydig (injektiv). En ekvation kan ha en entydig lösning – det betyder att ekvationen har en och bara en korrekt lösning, men den lösningen passar till många andra ekvationer (i princip ett oändligt antal ekvationer för varje tänkbar lösning). Varje personnummer går till ett och bara ett namn, men för många namn finns det däremot flera personnummer – relationen personnummer–>namn är alltså entydig men inte en‑entydig. –  I programmering även: ett‑till‑ett. I matematik även: bijektiv avbildning. – På engelska: one‑to‑one correspondence, bijective function, invertible function. Skrivs ibland också 121.

[matematik och logik] [13 juli 2020]

decimal128

ett sätt att representera flyttal med många siffror. – Med decimal128 kan man ange upp till 34 decimala värdesiffror och exponenter från 10–6143 till 10+6144. Det innebär att man kan ange tal med tillräcklig noggrannhet för de flesta praktiska behov, till exempel för ekonomiska kalkyler. 34 värdesiffror räcker för att ange tal upp till tusen kvintiljoner.

[matematik] [10 maj 2020]

set

  1. – i matematik: mängd – ett antal objekt som anses höra ihop. – Set är den engelska termen för den tyska matematikern Georg Cantors (18451918) term Menge som i Mengenlehre (mängdlära). Ordet Menge / mängd / set används oftast om matematiska tal, men det kan i princip användas om vilken samling materiella eller tänkta entiteter som helst, strukturerad eller ostrukturerad. (Försvenskningen ”sätt” förekommer, men rekommenderas inte.) – Se till exempel data setdatamängd;
  2. – lite gammalmodig engelsk beteckning på tekniska anordningar, till exempel TV set, som anses vara sammansatta av flera delar (i detta fall… antenn, mottagare, bildskärm, högtalare). Motsvarar i den betydelsen närmast svenska sats, men bör kanske hellre översättas med apparat;
  3. – även: uppsättning. – Det engelska ordet set har många andra betydelser.

[hårdvara] [matematik] [språktips] [ändrad 11 juni 2020]

Dijkstras algoritm

en algoritm för att hitta den kortaste vägen mellan två givna noder i ett nätverk. – Det finns också en variant av Dijkstras algoritm som beräknar de kortaste avstånden från en enda given nod till var och en av de andra noderna i nätverket. – Dijkstras algoritm kan användas för allt som kan avbildas som nätverk, till exempel vägnät, vilket var vad den utvecklades för. Den har också fått användning i analys och konstruktion av stora datornätverk. Det förutsätts att avstånden mellan noderna är kända och tillgängliga för algoritmen. Vid behov kan algoritmen också ta hänsyn till kostnaden för de olika alternativa vägarna. – Uppkallad efter sin upphovsman, den nederländska datorvetaren Edsger Dijkstra, som utvecklade den med papper och penna 1956 och publicerade den 1959.  En tillämpning av Dijkstras algoritm är protokollet OSPF. – Mer i Wikipedia.

[matematik] [nätverk] [transport och logistik] [ändrad 30 april 2022]

RSA-tal

ett antal semiprimtal som användes i en tävling anordnad av säkerhetsföretaget RSA. – Semiprimtal är tal som har exakt två primfaktorer. Tävlingen, som utlystes 1991 och avslutades 2007, gick ut på att de tävlande skulle finna primfaktorerna för RSA‑talen. – RSA‑talen betecknas med nummer som anger antal siffror i respektive semiprimtal. Det lägsta RSA‑talet var RSA‑100, som snabbt löstes. Det finns 54 RSA‑tal och 20 av dem har hittills faktoriserats (november 2019). Det högsta RSA‑talet är RSA‑2048, som troligen inte kommer att faktoriseras inom överskådlig framtid. – RSA‑tal upp till RSA‑576 (samt RSA‑617) har nummer som anger antalet decimala siffror i talet, högre nummer anger antalet binära siffror. – Benämningen RSA‑tal används ofta om antalet siffror i krypteringsnyckeln för RSA‑algoritmen. – På engelska: RSA numbers.

[kryptering] [tal] [6 december 2019]

evaluation

  1. – i matematik och programmering: evaluering – beräkning av det faktiska värdet av ett algebraiskt uttryck, en integral eller beräkning av utdata från ett avsnitt programkod. I stället för evaluering säger man ofta beräkning. – Se också ivrig beräkning (eager evaluation) och lat beräkning (lazy evaluation);
  2. utvärdering, bedömning.

[matematik] [programmering] [10 januari 2019]