P=NP

i matematik: frågan om ifall alla matematiska problem i den besvärliga klassen NP i själva verket hör till den mer lätthanterliga klassen P. I så fall måste det finnas ett relativt enkelt sätt att lösa matematiska problem i klassen NP – fast hur det ska gå till har ingen kommit på än. De flesta matematiker anser att hypo­tesen P=NP är fel, men det har inte be­vis­ats. – 2010 pre­senterade Vinay Deolalikar, då forskare på Hewlett‑Packard, ett påstått bevis för att hypotesen P=NP är fel (alltså att P≠NP, se denna länk.) Men Deo­la­li­kars påstådda bevis har mött hård kritik. – Se Wiki­pedia och artikel i MIT News (länk).

[matematik] [ändrad 5 mars 2018]

hash

  1. – matematisk operation, se kondensat. – Ordet har i denna be­ty­delse inget med haschisch att göra, utan är det ameri­kanska ordet för pytti­panna: något som är hackat i små­bitar;
  2. – (brittisk) engelska för tecknet # (nummertecken).

– För engelska hashtag, se hash­tagg.

[matematik] [typografi] [ändrad 17 januari 2018]

Mandelbrotmängd

En avbildning av Mandelbrotmängden. De små utskotten liknar figuren som helhet.

(the Mandelbrot set) – komplicerad geometrisk figur, uppkallad efter matematikern Benoit Mandelbrot, som upptäckte den. Den är ett välkänt exempel på fraktala geometriska figurer. Figurens ytterkant är visar sig i förstoring vara mycket invecklad med små detaljer som liknar figuren som helhet. Om man förstorar dessa detaljer i sin tur ser man att de också har en invecklad kant med detaljer som liknar figuren som helhet, och så vidare. Det finns ingen nedre gräns där figurens kant blir jämn och slät. Trots detta är figuren bara en avbildning av en mycket enkel matematisk formel. – Se bild och matematisk förklaring i Wikipedia.

[matematik] [ändrad 12 augusti 2018]

fraktal

En avbildning av Juliamängden.

i matematik: geometrisk form med uppbruten form som upprepas i mindre skala: en gren liknar ett träd, och en kvist liknar en gren. – En känd fraktal form är Mandel­brot­mängden, en annan är Julia­mängden (se Wikipedia). – Teorin om fraktaler har anknytning till kaos­teori. – Frak­tala former har något som kallas för fraktal dimen­sion, som anger hur uppbrutna de är. Ett väl­känt exempel är en kust­linje. Hur lång är en kust? Om man mäter kustens längd på markytan med en rak linjal beror svaret på hur lång linjalen är. Eftersom linjalen är rak kan den inte mäta strandens längd exakt. Kusten är ju krökt, uppbruten och flikig. Så om man mäter med en linjal som är en svensk mil lång får man ett kortare mått än om man använder en linjal på en kilometer. Den kortare linjalen går ju in i vikar och bukter som den längre linjalen över­bryggar. Och om man mäter med en linjal på tio centimeter blir kustens mått väldigt långt. – Det finns inget själv­klart svar på vad som är rätt längd på linjalen: det är en praktisk fråga. Men om man ritar en kurva som visar hur måttet på kustens längd förändras med linjalens längd är kurvans lutning ett mått på den fraktala dimensionen. I det här fallet mellan ett och två. En absolut rak kust utan ojämn­heter skulle ha den fraktala dimensionen 1 (=en rät linje), eftersom det inte skulle spela någon roll hur lång linjalen var, men ju mer upp­bruten kusten blir, desto mer närmar den sig den fraktala dimensionen 2. Motsvarande gäller i flera dimensioner, till exempel för ett berg. – Frak­taler används i datoranimering för att bygga upp bilder av naturliga objekt så att de ger ett naturtroget intryck.

[matematik] [ändrad 12 juni 2020]

Mandelbrot, Benoit

Porträtt av Benoit Mandelbrot.(1924—2010) – fransk–amerikansk polskfödd matematiker av litauisk familj, känd för att ha skapat den fraktala mate­ma­tiken. Mandel­brotmängden är uppkallad efter honom. – Benoit Mandel­brot gjorde stora insatser inom flera grenar av matematiken, bland annat sanno­lik­hets­lära och infor­ma­tions­teori. Han insåg bland annat att Zipfs lag inte bara passar på ord­frekvenser, vilket är vad Zipf observerade, utan också passar på andra före­te­elser. Den kallas därför också för Zipf‑Mandel­brots lag. – Mandel­brot var i 35 år anställd som forskare på IBM. 1987—2005 var han professor på Yale. – Benoit Mandel­brots själv­bio­grafi The fractalist (länk) kom ut postumt 2012.

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

stopproblemet

Tecknad bild av superdatorn Deep Thought från Liftarens guide till galaxen.
Datorn Deep Thought som behövde 7,5 miljoner år för att räkna ut svaret.

(the halting problem) – frågan om det på förhand går att räkna ut ifall en körning av ett dator­­­program kommer till ett slut någon gång, eller om beräkningen fort­sätter i all evighet. – Alan Turing bevisade i sin berömda artikel ”On computable numbers with an application to the Entscheidungsproblem” (länk) från 1936 att upp­giften är olöslig. – Ob­servera att detta gäller när frågan ska besvaras enbart med mekaniska metoder och för varje tänk­bar beräkning. En matematiskt kunnig mänsklig bedömare kan ofta avgöra ifall en beräkning kommer att fortsätta i evighet eller om den tar slut någon gång, men stopproblemet gäller ifall man kan programmera en dator så att den avgör saken i alla tänkbara fall och utan mänsklig hjälp. – Vi vet till exempel att om vi sätter en dator att räkna ut det exakta värdet på pi så kommer den aldrig att bli klar, men det ”vet” inte datorn. Att det är så har mänskliga matematiker räknat ut, och det har de inte gjort genom att räkna på pi oändligt länge. Hur länge man än räknar på värdet av pi så får man nämligen inte, enbart genom att fortsätta räkna, någon in­for­ma­tion om ifall räkne­arbetet tar slut någon gång, eller aldrig tar slut. – I upp­­satsen ”On computable numbers…” beskrev Turing också det som senare blev känt som Turing­maskinen. – Några månader före Turing hade Alonzo Church bevisat samma sak, fast utan att beskriva en maskin. – Stopproblemet är besläktat med avgörbarhetsproblemet (das Entscheidungsproblem), men också med Kurt Gödels ofullständig­hets­sats. – Läs också om omega (Chaitins konstant).

[datorvetenskap] [matematik och logik] [ändrad 6 juni 2017]

MIPS

  1. mips – miljoner instruktioner per sekund. Mått på dators eller processors prest­anda. Skrivs med litet m. – Läs också om bogo­mips;
  2. – MIPS Technologies, tidigare MIPS Computer Systems – uppköpt amerikansk tillverkare av RISC‑processorer. MIPS ägdes 1992—2000 av datortillverkaren SGI, och till­verkade då en pro­cessor med namnet MIPS för kraftfulla datorer, så kallade arbetsstationer. Till­verkningen av MIPS‑processorer för persondatorer och servrar lades ner 2006. Därefter utvecklade MIPS processorer för in­byggda system och spel­konsoler med pro­cessorn Pro­aptiv. Före­taget ingick i OESF. 2012 med­delade MIPS att det skulle ge sig in på marknaden för små, ström­snåla processorer för mobiltelefoner och surfplattor. – I februari 2013 blev det klart att MIPS såldes för 100 miljoner dollar till brittiska Imagination Technologies (länk). Imagination Technologies köptes i sin tur i september 2017 av amerikanska Canyon Bridge (canyonbridge.com), och då såldes MIPS till Tallwood Venture Capital för 65 miljoner dollar. I juni 2018 såldes MIPS vidare till amerikanska Wave Computing (länk). – Se wavecomp.ai/mips‑technology/.

[företag] [förkortningar på M] [måttenheter] [prestanda] [processorer] [uppköpt] [ändrad 17 november 2018]

Turingmaskin

En riktig Turingmaskin, byggd av amerikanen Mike Davis.
En riktig Turingmaskin, byggd av amerikanen Mike Davey.

en teoretisk dator som beskrevs 1936 av Alan Turing. Det var en ren tankekonstruktion. (1936 fanns inga datorer.) – En Turing­maskin mot­svarar ett modernt datorprogram, men när man talar om Turingmaskiner menar man ofta universella Turingmaskiner, som kan sägas mot­svara datorer. – Alan Turing beskrev maskinen i artikeln ”On computable numbers with an application to the Entscheidungsproblem (länk). Artikeln handlade om ett matematiskt problem, stopproblemet, inte om datorer. Turing beskrev det som senare fick heta Turingmaskin enbart för att göra ett matematiskt bevis åskådligt. Det var inte en beskrivning av något som Turing verkligen tänkte bygga. – Turingmaskinen har en pappers­remsa som matas fram och tillbaka genom ett läs- och skrivhuvud enligt bestämda regler. Det finns flera upp­­sätt­ningar regler som kallas för tillstånd, och i reglerna ingår övergångar från ett tillstånd till ett annat. Skrivhuvudet kan läsa, radera och skriva tecken på remsan. Man programmerar Turingmaskinen med tecken på remsan, och Turingmaskinen matar sedan, enligt reglerna, remsan fram och tillbaka, läser, raderar och skriver samt växlar till­stånd tills den kommer till en regel som säger ”stopp”. Då stannar maskinen och lösningen på problemet kan avläsas på remsan. Detta är helt genomförbart, bortsett från de praktiska problemen med pappersremsan, pennan och radergummit. – I princip kan varje pro­blem som kan lösas med ett modernt dator­program också lösas av en motsvarande Turing­maskin, men naturligt­vis är det ogörligt att använda en maskin med pappers­remsa. Man brukar därför simulera Turing­maskiner i datorer. (Se här.) Det är nämligen bra att öva sig på program för Turingmaskiner när man ska lära sig programmera. – Se också finit tillståndsmaskin. – Efter andra världskriget konstruerade Alan Turing en dator, ACE som till stor del baserades på de principer som Turing beskrev i sin artikel. – Turingmaskinen införde idén om lagrade program i datortekniken. Idén togs upp av John von Neumann i hans arkitektur för datorer, von Neumann-arkitekturen. Den är mindre sofistikerad än Turings modell, men mer över­skådlig, och blev allenarådande i dator­tekniken. – Pro­fessor Bernard Hodson (länk) i Kanada har ut­vecklat en modern programmerings­teknik baserad på Turings principer. – Mate­matikern Stephen Wolfram arrangerade 2007 en tävling om Turingmaskiner, se här. – Mike Davey beskriver hur han byggde en riktig Turingmaskin (se bilden) i denna artikel. – Richard Ridel har byggt en Turingmaskin av trä, se denna video.

[it-historia] [matematik och logik] [ändrad 12 mars 2018]

XOR

  1. – i programmering: ett logiskt villkor som betyder ”A eller B, men inte båda” – se exklusiv disjunktion;
  2. – en enkel form av kryp­te­ring som bygger på det logiska villkoret XOR. Texten som ska kodas (klartexten) i binär form jämförs med en nyckel i binär form, bit för bit. Nyckeln är en serie ettor och nollor som vid behov repeteras tills den når slutet av texten. Om det finns samma tecken i klartexten och i nyckeln sätts en etta i kryptotexten, om det är olika tecken sätts en nolla. Detta räknas som en mycket enkel och risk­abel form av krypte­ring.

[kryptering] [logik] [programmering] [ändrad 21 mars 2020]