SHA-3

algoritm för kondensat (hash), amerikansk standard sedan oktober 2012. – Algoritmen, som även är känd som Keccak, vann det amerikanska standardiseringsinstitutet Nists tävling i oktober 2012. Det ska användas jämsides med en annan standard, SHA-2. – Se keccak.team.

flyttal

(floating-point number eller bara float) – tal skrivet med ett fast antal siffror och vid behov av­­run­dat. – Flyt­tal är uppdelade i värde­siffror och de siffror som anger stor­­leks­­ord­ningen. Exempel: i stället för 3,14 skulle man skriva 314 och –2, där –2 be­tyder delat med hundra (×10–2). Be­höver man i stället skriva 314 miljoner blir det 314 och 6 (sexan står för ×106). – Värde­­siff­rorna kallas för mantissa. Talet som anger storleksordningen kallas för exponent. – Po­ängen är att man kan skriva stora och små tal på samma begränsade ut­rymme. Vid multi­­pli­ka­tion och division kan man dessutom be­räkna mantissa och exponent var för sig. – Nack­­delen är att tal med många värdesiffror måste rundas av. Flyt­tal kan därför inte användas i exakta matematiska be­­räk­ningar med stora tal, men de an­vänds ofta i tekniska beräkningar. Det kan dock behövas knep för att se till att avrund­nings­­felet inte växer när be­räkningarna har många steg. – I själva verket används potenser av det binära systemet, men det är samma princip. – Be­räk­ningar med icke avrundade tal kallas för hel­­tals­­be­räk­ningar. – Ordet: Flyta syftar på att det underförstådda decimalkommat kan ”flyta”, alltså stå var som helst i talet. – Flyttalsnotation (floating-point notation) eller flyttalsrepresentationn (floating-point repre­sen­ta­tion) – sätt att skriva tal som flyttal, vanligen med ett bestämt antal siffror i mantissan. – En vanlig standard för flyttalsberäkningar har fastställts av IEEE, se IEEE 754.

[matematik] [programmering] [ändrad 5 januari 2018]

inklusiv disjunktion

logiskt villkor som betyder ”A eller B eller båda”. – Det betecknas i boolesk algebra med OR. I symbolisk logisk används tecknet ∨. – Vill­koret ”Sverige OR Norge” ger, om man söker i en databas, träff på alla poster som enbart nämner Sverige, alla som enbart nämner Norge och på alla sidor som nämner båda länderna. – Jäm­för med ex­klu­siv dis­junk­tion och dis­junk­tion. – En sannings­värde­tabell för in­klu­siv dis­junk­tion ser ut så här:

– Minst ett av påståendena A och B är sant (A ∨ B) :

A B A ∨ B
sant sant sant
sant falskt sant
falskt sant sant
falskt falskt falskt

[logik] [programmering] [ändrad 8 juni 2017]

binära multipelprefix

motsvarigheter till mega, giga etcetera, an­passade till det binära talsystemet. (Se också multipel­prefix.) – Exempel: i stället för kilo­byte, som strikt räknat är exakt tusen byte, använder man storheten kibi­byte, förkortat kiB, som är 1 024 (210) byte. – Ändringen motiveras med att datorer räknar med det binära talsystemet, inte med det decimala. I det binära tal­systemet är exakt tusen inte ett ”runt tal” (det blir 1111101000 med binär notation), vilket däremot 1 024 är (det blir 10000000000 med binär notation). Länge bortsåg man i data­teknik från skill­naden, som i de flesta fall var för­sum­bar. Man skrev (och skriver fortfarande) kilobyte när man menade 1 024 byte. Men när vi räknar med stor­heter som giga- och tera- närmar sig skillnaden mellan jämna decimala tal och nära­liggande runda binära tal tio pro­cent. Det är inte alltid för­sum­bart. Därför har det fast­ställts en serie binära multipel­prefix med namn som på­min­ner om de decimala i samma storleksklass.

– De binära multipelprefixen infördes i slutet av 1990‑talet, men används inte så mycket.

kibi Ki 210 1 024 (jämför med kilo)
mebi Mi 220 1 048 576 (jämför med mega)
gibi Gi 230 1 073 741 824 (jämför med giga)
tebi Ti 240 1 099 511 627 776 (jämför med tera)
pebi Pi 250 ≈1,1259×1015 (jämför med peta)
exbi Ei 260 ≈1,15292×1018 (jämför med exa)
zebi Zi 270 ≈1,18059×1021 (jämför med zetta)
yobi Yi 280 ≈1,20983×1024 (jämför med yotta)

[multipelprefix] [ändrad 7 februari 2019]

Gödel, Kurt

Porträtt av Kurt Gödel.
Kurt Gödel. Foto: IAS.

österrikisk-amerikansk matematiker och logiker (1906—1978). – Kurt Gödels ofull­ständig­hets­sats från 1931 inspirerade Alan Turing till analysen av stoppro­blemet. – Ofull­ständig­hets­satsen visar att det inte kan finnas logiska och/eller matematiska system som på samma gång är hel­täckande och motsägelsefria. Med hel­täckande menas att regelsystemet kan tillämpas på alla påståenden som kan for­mu­le­ras inom systemet. I varje system av lagar, regler och symboler – till exempel matematik – kan man, visade Gödel, alltid hitta påstå­enden som uppenbarligen är sanna, men som inte kan bevisas inom ramen för systemet. Det går kanske att bevisa påstå­endet om man lägger till nya regler – men om man gör det så går det ofelbart att, med användning även av de nya reglerna, formulera nya påstå­enden som i sin tur inte kan bevisas, men som ändå uppen­bar­ligen är sanna. Detta bevisades i artikeln ”Über formal unentscheidbare Sätze der Principia Mathematica und Ver­wandte System” (engelsk översätt­ning här). – I själva verket finns det två ofullständighetssatser, som hör ihop:

  • – Den första är den som beskrivs ovan;
  • – Den andra satsen säger att ett sådant system som beskrivs i den första satsen inte kan bevisa att det är mot­sägelse­fritt.

– Se också Ent­scheidungs­problem. – Gödel lämnade Österrike efter den tyska ockupationen 1938 och fick då en tjänst på Institute of advanced study (ias.edu) i Princeton, New Jersey, där han blev god vän med Albert Einstein. – Gödelpriset är uppkallat efter Kurt Gödel. – En biografi över Kurt Gödel är Ofull­ständig­het: Kurt Gödels bevis och paradox (Incomp­lete­ness: The proof and paradox of Kurt Gödel, 2005) av Rebecca Gold­stein (webbplats).

[för- och bihistoria] [kurt gödel] [matematik och logik] [personer] [ändrad 23 april 2018]

kaosteori

svartvitt foto av Henri Poincaré.
Den franska matematikern Henri Poincaré beskrev grunderna i kaosteori för mer än hundra år sedan.

(chaos theory) – studiet av vissa till synes oförutsägbara mate­ma­tiska och fysiska fenomen, kaos. – Teorin bygger på upp­täckten att vissa matema­tiska modeller av verk­lig­heten ger resultat med svängningar och skift­ningar som verkar slumpmässiga, trots att de i princip är beräkningsbara. – Kaos­teori ger an­vänd­bara matematiska modeller av före­teelser från väder och hjärtflimmer till droppande vattenkranar. Ty­piskt för kaos­teorin är att små orsaker kan få stora verk­ningar (fjärils­effekten). Man kan därför i kaotiska system inte för­ut­säga vilken skillnad en liten för­änd­ring ger: man måste räkna ut det gång för gång. Det går inte att intrapolera och extra­polera. – De företeelser som kaos­teorin passar in på har ett förut­säg­bart be­te­ende i stora drag, men inte i detaljer. Vädret dag för dag är till exempel kaotiskt, men klimatet är förutsäg­bart (sommaren är varje år varmare än vintern). – Kaosteori blev på 1980-talet en modevetenskap, men bör trots det tas seriöst. Den föregreps av den franska mate­ma­tikern Henri Poin­caré (1854—1912, se Wiki­pedia), men utgår närmast från den ameri­kanska meteorologen Edward Lorenz (mer under hans namn). Nobel­pris­tagaren Ilya Prigogine (1917—2003, länk) var en av de första som såg kaos­teorins möjligheter. – Läs gärna boken Kaos av amerikanen James Gleick (länk), på svenska 1988.

[fysik] [matematik] [ändrad 12 augusti 2018]

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]