NP

en klass av matematiska problem som kan vara svåra att lösa, men som har lösningar som det är lätt att kontrollera. – När det gäller matematisk komplexitet talar man om de tre klasserna P, NP och de NP‑fullständiga problemen. – Klassen NP omfattar också klassen P, som består av de mest hanterliga pro­blemen, men oftast menar man med NP bara de problem som inte också ingår i P. (Se också frågan om ifall P=NP.) – När man säger att lösningarna går snabbt att kontrollera menar man i relation till problemets svårighetsgrad. Ett enkelt sätt att jämföra svårighetsgraden i olika problem är att räkna hur många tecken som ingår i det matematiska uttryck som beskriver problemet. – Ett exempel på NP‑problem är schemaläggning för gymnasium. Klasser, lärare och lektionssalar ska kombineras så att alla lektioner kan äga rum enligt läroplanen och ingen klass, lärare eller sal dubbelbokas. Det är besvärligt att sätta ihop ett schema, men lätt att kolla ifall det har blivit rätt. Ett annat exempel är att hitta primfaktorerna till mycket stora tal. Att hitta dem är svårt, att kontrollräkna är elementärt. När det däremot gäller problem i den NP‑fullständiga klassen så tar kontrollräkningen i princip lika lång tid som det tog att hitta lösningen. – NP står för non-deterministic polynomial. En förklaring till den benämningen står i i Wikipedia.

[förkortningar på N] [matematik] [ändrad 23 maj 2018]

binning

att minska variationerna i en data­mängd; att slå ihop värden som ligger nära varandra. Uttrycket kommer av engelska bin –korg, be­hållare – man lägger värden som ligger nära var­andra ”i samma korg”:

  1. – data binning innebär att värden som ligger nära varandra byts ut mot ett en­het­ligt värde, van­ligt­vis det centrala. Exempel: alla värden mellan 9,5 och 10,5 byts ut mot 10. Av­rund­ning kan alltså ses som en form av binning
  2. – i digital bildbehandling: det att en grupp bildpunkter (pixlar) ersätts med en enda bild­punkt. 2⨯2 eller 3⨯3 bild­punkter kan till exempel er­sättas med en enda bildpunkt. Vanligt­vis blir det då ett medel­värde av de in­gående bildpunkternas färg­toner. Detta kan under­lätta bild­analys och göra bilden tyd­ligare, och det är nöd­vändigt om bilden ska för­minskas;
  3. – phone binning skämtsamt: att hålla en kikare framför objek­tivet på en mobil­tele­fons kamera. Man an­vänder alltså kikaren som tele­objektiv;
  4. – to bin kan också betyda ’att kasta bort’ (lägga i det runda arkivet, the bin).

affinitetsanalys

(affinity analysis) – sökning efter statistiska sam­band i stora data­mäng­der. Alltså en typ av datautvinning. – Affi­­ni­tet är i mark­­nads­föring ett mått på hur mycket en mål­grupp är in­tres­se­rad av en pro­dukt eller tjänst. Om målgrup­pen är mer in­tres­se­rad av pro­dukten än genom­snittet av befolkningen är affiniteten hög. Hög affi­ni­tet kan alltså antas ge gott gensvar på reklamen. – Ordet affinitet an­vänds också i andra sam­man­hang med besläktade betydelser.

[analys] [marknadsföring] [statistik] [ändrad 29 januari 2018]

Church, Alonzo

(1903—1995) – amerikansk matematiker. Han bevisade 1936 i artikeln ”A note on the Ent­scheidungs­pro­blem” (se avgörbarhetsproblemet) att det finns mate­matiska frågor som det inte går att besvara med mekaniska metoder. Det var samma sak som Churchs studie­­kamrat Alan Turing bevisade senare samma år i sin upp­sats om stopproblemet. Turing visade senare att de två bevisen var lik­värdiga. Båda byggde på Kurt Gödels ofull­ständig­hets­sats. – Church-Turings hypotes säger att alla mate­matiska beräkningar som kan beskrivas i ett ändligt antal steg (med en algoritm) kan lösas av en maskin. Om en nog­­grann men fantasi­lös människa med papper och penna kan räkna ut lösningen (lösa problemet mekaniskt) kan en maskin också göra det. Men: beräkningen kan pågå i all evighet. Till exempel är det lätt att beskriva divisionen 2 delat med 3, men det tar en evig­het att räkna ut svaret (0,6666666……) om man inte sätter stopp. För att inte tala om sådant som att räkna ut värdet på pi. – Det som både Church och Turing bevisade var att även om en maskin kan utföra alla beräkningar som kan uttryckas som algoritmer, så kan maskinen inte avgöra ifall be­räk­ningen tar slut någon gång, eller om den fort­sätter i all evighet. – En artikel på engelska om vanliga miss­­upp­­fatt­ningar av Church-Turings hypotes finns här.

och-förval

(default to AND) – om sök­motorer: det att sökningar med två eller flera ord antas inne­hålla det logiska vill­koret AND (se kon­junk­tion). Skriver man alltså hund katt i sök­fältet tolkar sök­motorn det som hund OCH katt. Det gör att sök­motorn då söker efter webb­sidor som inne­håller båda orden, inte bara ett av dem. (Men orden behöver inte stå intill varandra i texten, se fras.) – Och‑för­val brukar ge färre, men mer re­le­vanta, träffar än alternativet, eller‑för­val. – Och-för­val är det van­li­gaste i sök­motorer, och används på Bing, Google och Yahoo.

[logik] [sökningar] [sökmotorer] [ändrad 8 juni 2017]

långa skalan

(the long scale) – det system för benämning av mycket stora tal som kallar tusen miljoner för en miljard. Alltså som vi gör i Sverige. Med undan­tag just för ordet miljard (och följ­akt­ligen också för biljon) står varje ny be­näm­ning för ett tal som är en miljon gånger större än det före­gående.

Namn Värde Engelskt namn (den korta skalan)
miljon 106 million
miljard 109 billion
biljon 1012 trillion
tusen biljoner 1015 quadrillion
triljon 1018 quintillion
tusen triljoner 1021 sextillion
kvadriljon 1024 septillion
tusen kvadriljoner 1027 octillion
kvintiljon 1030 nonillion
tusen kvintiljoner 1033 decillion
sextiljon 1036 undecillion

– Läs också om motsvarande multipelprefix.

– Nya benämningar bildas med latinska räkneord. – Den långa skalan, där varje namn (utom miljard) står för ett tal som är en miljon gånger större än det före­gående, används i större delen av Europa, inklusive Sverige, men inte i USA och numera officiellt inte heller i Stor­britannien. USA och Storbritannien använder den korta skalan, där tusen miljoner kallas för one billion, och där varje nytt ord står för ett tal som bara är tusen gånger större än det före­gående. – Ob­servera att matematiker och naturvetenskapare numera und­viker alla dessa be­nämningar, just därför att de har olika betydelse på olika språk. Talen anges i stället med siffror, som 109 för en miljard, och ut­läses till exempel ”tio upphöjt till nio”. – Läs mer i Wiki­pedia och i en artikel i Språk­tidningen. – Se också crore och lakh.

[språktips] [tal] [ändrad 25 april 2017]

multipelprefix

ord som kilo- och mega- som sätts framför sorter för att ange stora antal: tusen, miljon, miljard av en måttenhet. Till exempel megabyte – en miljon byte. Även ord som be­teck­nar små­delar kallas multipelprefix, till exempel milli-. På engelska: prefixes for multiples, ibland även quantifiers. – För det binära talsystemet finns en serie binära multipelprefix som kibi- och mebi-.

– Här är en tabell över multipelprefix:

Prefix Förkortning Faktor Faktorns namn På engelska
kilo k 1 000 tusen  thousand
mega M 106 miljon million
giga G 109 miljard billion
tera T 1012 biljon trillion
peta P 1015 tusen biljoner quadrillion
exa E 1018 triljon quintillion
zetta Z 1021 tusen triljoner sextillion
yotta Y 1024 kvadriljon septillion
bronto (inofficiellt) – – 1027 tusen kvadriljoner octillion
geop (inofficiellt) – – 1030 kvintiljon nonillion
milli m 10-3 tusendel
mikro μ 10-6 miljondel
nano n 10-9 miljarddel
piko p 10-12 biljondel
femto f 10-15 tusendels biljondel
atto a 10-18 triljondel
zepto z 10-21 tusendels triljondel
yocto y 10-24 kvadriljondel

[matematik] [multipelprefix] [ändrad 25 april 2017]

digital

  1. – uttryckt med siffror – om information och mätningar: uttryckt i sifferform och som exakta tal. Vid behov avrundas talen. Alter­na­tivet är analog. – An­led­ningen till att datorer arbetar med data i digital form är att digitala data kan be­ar­betas och kopieras gång på gång utan att det blir svårare för datorn att avläsa informationen rätt. Even­tu­ella fel kan rättas till med hjälp av kontroll­siffror. Analog information försämras däremot varje gång den kopieras. – Ob­ser­vera att det vanliga decimala talsystemet med siffrorna 0—9 är precis lika digitalt som det binära talsystemet med ettor och nollor – det som används i datorer. Skillnaden är praktiskt betingad, inte prin­ci­piell. – Se också numerisk;
  2. – allmänt ord för sådant som är baserat på inter­net och data­teknik, som det digitala sam­hället, till exempel i uttryck som den digitala klyftan och digitalisering. – Jäm­för med cyber och e-;
  3. – företaget Digital†, se Digital Equipment Corporation† (köpt av Hewlett‑Packard).

[datorns konstruktion] [datorvetenskap] [företag] [matematik] [uppköpt] [ändrad 24 januari 2019]

bayesisk

(Bayesian) – bayesisk statistik eller bayesisk in­ferens – mate­ma­tisk metod att räkna ut sannolikheten för att bedömningar är riktiga, baserat på kunskap om tidigare händelser av samma slag. – Annorlunda ut­tryckt: en metod för att ”vända på” sanno­­lik­­heter som man redan känner till. Till exempel: det snöar ofta i januari – men om det snöar, är det då januari? Kon­stru­erat exempel: du vet redan att 50 procent av all spam innehåller ordet V––gra (hädan­­efter i denna text utbytt mot ”margarin”). Men om du får ett mejl som innehåller ordet margarin, hur sannolikt är det då att det mejlet är spam? Ordet margarin står ju inte bara i spam. Det är sådana pro­blem man kan angripa med bayesisk statistik. Metoden ger an­­vänd­­bara, om än grova, resultat även när under­­laget är litet.

– Den mate­ma­tiska formeln för Bayes sats ser ut så här:

P (A|B) = P (B|A) × P (A) / P (B)

vilket kan ut­läsas:

sannolikheten för A, givet B, är lika med sannolikheten för B, givet A, multiplicerad med sannolikheten för A, divi­de­rad med sannolikheten för B.

(Bok­staven P står för ”sannolikheten för”, och lodstrecket | be­­tyder ”givet att”.) – A står för en bedömning som man vill ha prövad, till exempel ”jag tror att detta mejl är spam”, medan B står för ett känt faktum som man baserar bedöm­ningen på, till exempel ”detta mejl innehåller ordet margarin”. – Bayesisk analys förutsätter att man har ett sta­tis­tiskt underlag. I det här exemplet krävs det att man redan tidigare har klassat mejl i spam och icke‑spam. Man förut­sätter att tidigare ob­serva­tioner även gäller nu. Man har då siffror på sannolikheten för att ett slump­­mässigt valt mejl är spam, P (A), och sannolikheten för att ett slumpmässigt valt mejl innehåller ordet margarin, alltså P (B). Man måste också ha räknat ut sannolikheten för att ett slumpmässigt valt mejl som har klassats som spam inne­­håller ordet margarin, alltså P (B|A). Sannolikhetsbedöm­ningen som du vill ha – hur sannolikt (P) är det att detta mejl är spam (A) med tanke på att det innehåller ordet margarin (B) – uttrycks alltså P (A|B).
– Exempel med godtyck­liga siffror: 40 procent av all e‑post du får är spam, 60 procent är icke‑spam. 50 procent av all spam inne­håller ordet margarin, men bara två pro­cent av icke-spam­met. Då blir det så här:

  … innehåller ordet margarin inte innehåller ordet margarin Sammanlagt av alla mejl
Andel av all icke-spam som… 2% 98% 60% (är icke-spam)
Andel av all spam som… 50% P(B|A) 50% 40% P(A) (är spam)
Andel av alla mejl som… 21,2% P(B) 78,8% 100% (all mejl)
Sannolikhet för att ett mejl…      
är spam om det… … innehåller ordet margarin inte innehåller ordet margarin  
  94,3% P(A|B) 25,4% (40%)
inte är spam om det… 5,7% 74,6% (60%
Summa av de två ovanstående sannolikheterna 100 100 100

– Sammanlagt innehåller alltså 21,2 procent av all mejl ordet margarin. Men det svarar inte på frågan hur sannolikt det är att ett mejl är spam om det inne­­håller ordet margarin. Vad du kan se är att av 21,2 procent som innehåller det ordet är 20 procent­enheter spam, 1,2 procent­enheter är icke‑spam. Oddset för att ett mejl som inne­­håller ordet margarin är spam är alltså 21,2:1,2, vilket motsvarar en sannolikhet på unge­fär 94,3 procent. Om­vänt: om ett mejl inte inne­­håller ordet margarin är det 74,6 procents sannolik­­het för att det inte är spam. – Den bayesiska bedömningen är en statistisk bedömning baserad på tidigare resultat. Det fungerar bara om en mänsklig bedömare med gott om­döme redan har delat upp tidigare mejl i spam och icke‑spam, så att det finns ett under­­lag för bayesisk analys av nya mejl. Ett riktigt spam­filter utgår dess­­utom inte från ett en­staka ord, utan sammanväger många ord. – Bayes metod ger använd­­bara resultat även med ett be­­gränsat underlag, och för­­bätt­ras när man an­vänder den upp­­repade gånger med växande under­­lag. Metoden används i spamfilter, i taligenkänning och i datori­serad över­­sätt­ning. – Bayesisk logik är uppkallad efter den engelske prästen Thomas Bayes (1702—1761), som beskrev den i sin postumt publicerade artikel Essay towards solving a problem in the doctrine of chances från 1763 (länk) (arkiverad). – Se också Wikipedia (länk). – Läs också om evidens­­teori.

[sannolikhet] [ändrad 24 april 2019]