NP-fullständig

(NP complete)NP‑fullständiga problem eller NP‑kompletta problem – en klass av matematiska problem som är tidskrävande att lösa och också tidskrävande att verifiera (att be­visa att lösningen är rätt). – NP‑fullständiga problem är den mest ohanterliga typen av matematiska problem. Det mest kända exemplet är handelsresandeproblemet. – Typiskt för NP‑fullständiga problem är:

  • – att det inte finns något sätt – ingen algoritm – att hitta den bästa lösningen, förutom en uttömmande sökning;
  • – att det inte går att bevisa att man har funnit den bästa lösningen, utom genom att jämföra alla tänkbara lösningar.

– Andra, enklare klasser av matematiska problem är P och NP. – Se också komplexitet. – Välkända NP‑fullständiga problem gäller att hitta den kortaste vägen (handelsresandeproblemet, Hamiltons problem) eller att utnyttja ett utrymme så effektivt som möjligt (kappsäcksproblemet). Metoder för att lösa NP‑fullständiga problem har praktisk tillämpning, till exempel vid kretskonstruktion, transporter och kommunikation. I prak­tisk tillämpning räcker det ofta med att hitta en tillräckligt bra lösning, inte nödvändigtvis den bevisat bästa. – Utom i enkla fall är det mycket tidskrävande att lösa NP‑fullständ­iga program. Problem av denna typ blir snabbt ohanterliga, till exempel om man ökar antalet städer i handelsresandeproblemet till några tiotal. Det är lätt att formulera NP‑fullständiga problem som det skulle ta tusentals år att lösa med dagens snabbaste datorer. – NP‑fullständiga tal är en speciell typ av tal i NP‑klassen. Ingen har hittills funnit ett sätt att lösa NP‑fullständiga problem förutom genom en uttömmande prövning av alla tänkbara lösningar. Å andra sidan har ingen heller kunnat bevisa att en sådan algoritm inte kan finnas. (Se P=NP?.) – Matema­tiker diskuterar ifall de NP‑fullständiga problemen är en sort för sig, eller bara en typ av NP‑problem som vi ännu inte har kommit på hur man löser. Däremot har det bevisats att om någon hittar en algoritm som löser ett NP‑fullständigt problem kan man med samma algoritm lösa alla andra NP‑fullständiga problem.

[matematik och logik] [ändrad 2 maj 2017]

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å dåvarande 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 8 oktober 2020]

perturbation

avsiktlig sammanblandning av personuppgifter i syfte att anonymisera dem. – Perturbation används vid statistisk analys av integritetskänsliga data. – Vanlig pseudonymisering, det vill säga att man tar bort namn och andra uppgifter som direkt kan knytas till en bestämd person, anses osäker. Det är nämligen ändå enkelt att koppla anonymiserade data om en person till den personen om man har tillgång till det ursprungliga registret eller annan lämplig information. Perturbation innebär att man låter vissa uppgifter byta plats mellan personer på ett sätt som gör att den statistiska analysen ändå blir giltig. A får B:s adress, B får C:s ålder och så vidare. Man kan också ändra en del mätvärden på ett systematiskt sätt som inte påverkar slutresultatet. Liknande metoder används också för att hemlighålla information i datakommunikation. – En mer allmän betydelse av engelska perturbation är störning, avvikelse från förväntat värde. – Läs också om datamaskering, k‑anonymitet och kvasiidentifierare.

[personlig integritet] [personuppgifter] [statistik] [ändrad 31 mars 2020]

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]

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 Juliamä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 kustlinjer. 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älvklart 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ämnheter 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 (en plan yta – kustens krökningar omfattar varje punkt i ett område). Motsvarande gäller i flera dimensioner, till exempel för ett berg. – Fraktaler används i datoranimering för att bygga upp bilder av naturliga objekt så att de ger ett naturtroget intryck.

[matematik] [ändrad 27 september 2021]

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 matematiken. – Mandelbrotmängden är uppkallad efter Benoit Mandelbrot. Han gjorde stora insatser inom flera grenar av matematiken, bland annat sannolikhetslära och informationsteori. Mandelbrot insåg bland annat att Zipfs lag inte bara passar på ordfrekvenser, vilket var 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 Mandelbrots självbio­grafi The fractalist (länk) kom ut postumt 2012.

[matematik] [personer] [ändrad 27 september 2021]

Mandelbrotmängd

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

(the Mandelbrot set) – en 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 enkel matematisk formel. – Se bild och matematisk förklaring i Wikipedia.

[matematik] [ä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 datorprogram kommer till ett slut någon gång, eller om beräkningen fortsä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 uppgiften är olöslig. – Observera 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 information om ifall räknearbetet tar slut någon gång, eller aldrig tar slut. – I uppsatsen ”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]

mega

  1. multipelprefix för en miljon (106). För en miljon­del används prefixet mikro. – För den binära approximationen (220), se mebi;
  2. – Mega – en fildelningssajt som startades i januari 2013 av Kim Dotcom. Den ersatte hans tidigare Megaupload†. Kim Dotcom överlät efter ett par år Mega till ett annat företag, och nu är det en tjänst för säker fillagring. – Se mega.io.

[multipelprefix] [ändrad 25 oktober 2022]

MIPS

  1. mips – miljoner instruktioner per sekund. Mått på dators eller processors prest­anda. Skrivs med litet m. – Läs också om bogomips;
  2. – MIPS – en uppköpt amerikansk tillverkare av RISC‑processorer. – MIPS, som grundades 1984, ägdes 19922000 av datortillverkaren SGI† (Silicon Graphics), och tillverkade då en pro­cessor med namnet MIPS för kraftfulla datorer, så kallade arbetsstationer. Tillverkningen av MIPS‑processorer för persondatorer och servrar lades ner 2006. Därefter utvecklade MIPS processorer för in­byggda system och spelkonsoler med processorn Proaptiv. Före­taget ingick i OESF. 2012 meddelade MIPS att det skulle ge sig in på marknaden för små, strömsnå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 (imaginationtech.com). Imagination Technologies köptes i sin tur i september 2017 av amerikanska Canyon Bridge (canyonbridge.com), och då såldes MIPS vidare till Tallwood Venture Capital för 65 miljoner dollar. I juni 2018 såldes MIPS vidare till amerikanska Wave Technologies, som 2021 bytte namn till MIPS. – Se mips.com.

[företag] [förkortningar på M] [måttenheter] [prestanda] [processorer] [uppköpt] [ändrad 9 oktober 2022]