Hitta kortaste rutten som passerar alla punkterna.
(traveling salesman problem) – ett klassiskt matematiskt problem som kan verka enkelt, men som kan vara mycket besvärligt att lösa. – En handelsresande ska besöka ett antal städer. Avstånden mellan städerna är kända. Vilken är då den kortaste resväg han kan välja om han ska besöka varje stad och återvända till utgångspunkten? (Det finns varianter, beroende på om man får resa genom varje stad fler än en gång, eller bara en gång.) – I vissa fall är lösningen uppenbar, till exempel om städerna ligger i rät linje. Men en metod för lösning måste kunna tillämpas på alla tänkbara grupper av städer. – Redan när problemet gäller tio städer finns det över 3,6 miljoner tänkbara rutter (och det är bortsett från att man kan passera samma stad flera gånger). Ökar man antalet städer ytterligare blir problemet snart ohanterligt. Det tillhör därför den grupp av matematiska problem som kallas för NP‑fullständiga. – Det gäller också att bevisa att man verkligen har funnit den kortaste vägen. Och det finns ingen känd metod för att bevisa att man verkligen har funnit den kortaste vägen, förutom att gå igenom alla tänkbara lösningar och jämföra dem. Det är det som gör att handelsresandeproblemet räknas som NP‑fullständigt. – Det mest omfattande handelsresandeproblem som hittills har lösts gäller 24 978 orter i Sverige: kortaste vägen om man vill besöka alla är 72 500 kilometer. – Problemet har praktisk tillämpning, till exempel inom trafikplanering och när man konstruerar elektroniska kretsar. Men i praktisk verksamhet brukar man inte behöva bevisa att man har hittat den absolut kortaste vägen: det räcker med en lösning som är bättre än alla tidigare. (Det finns fusklösningar som ofta ger tillräckligt bra, men inte perfekt, resultat. En enkel fusklösning är att alltid resa till närmaste obesökta stad på listan.) – En nära släkting till handelsresandeproblemet är Hamiltons problem. – Se Wikipedia.
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 hypotesen P=NP? är fel, men det har inte bevisats. – 2010 presenterade 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 Deolalikars påstådda bevis har mött hård kritik. – Se Wikipedia och artikel i MIT News(länk).
– matematisk operation, se kondensat. – Ordet har i denna betydelse inget med haschisch att göra, utan är det amerikanska ordet för pyttipanna: något som är hackat i småbitar;
– (brittisk) engelska för tecknet #(nummertecken).
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 Mandelbrotmängden, en annan är Juliamängden(se Wikipedia). – Teorin om fraktaler har anknytning till kaosteori. – Fraktala former har något som kallas för fraktal dimension, som anger hur uppbrutna de är. Ett välkä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 överbryggar. 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 uppbruten 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.
(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öreteelser. Den kallas därför också för Zipf‑Mandelbrots lag. – Mandelbrot var i 35 år anställd som forskare på IBM. 1987—2005 var han professor på Yale. – Benoit Mandelbrots självbiografiThe fractalist(länk) kom ut postumt 2012.
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.
uppdelning av en komplex signal (till exempel ljud eller video) i sinusvågor med olika frekvens. – Alla signaler som kan beskrivas som vågrörelser, hur oregelbundna de än är, kan nämligen delas upp i enkla, samtidiga sinusvågor. (En sinusvåg är den enklast tänkbara vågrörelsen.) Detta bevisades av den franske matematikern Joseph Fourier (1768—1830). Detta är bland annat användbart när man ska komprimera filer. En sådan operation kallas också för Fouriertransform. – Den äldsta metoden för Fourieranalys kallas för diskret Fourieranalys och är mycket tidskrävande. En snabbare metod är snabb Fourieranalys(fast Fourier transform, FFT), som bland annat används för komprimering av datafiler, i synnerhet av filer med musik och video. 2012 beskrev den amerikanska matematikern Dina Katabi(länk) med flera en ännu snabbare metod, sparse Fourier transform. En matematisk beskrivning finns här (pdf).
ett stort tal som skrivs som en etta följd av hundra nollor (med vanlig decimal notation). – Talet googol definierades av den amerikanska matematikern Edward Kasner runt 1920; namnet hittade hans systerson Milton Sirotta på. Talet blev känt 1940 genom Kasners populärvetenskapliga bok Mathematics and the imagination (svensk översättning Matematiken och fantasien, 1943). – Talet googolplex, även det definierat av Kasner, är 10 upphöjt till googol (alltså en etta följd av googol nollor). – Sökmotorn Google är uppkallad efter talet googol. – Fördjupning: Författaren och konstnären Vincent Carter Vickers gav 1913 ut barnboken The Google Book(länk). Där är Google en sagovarelse. Senare dök seriefiguren ”Barney Google” upp i serien Snuffy Smith (Tjalle Tvärvigg), och ordet google användes också i en populär sång på 1920‑talet. Så det antas att Milton Sirotta var påverkad av populärkulturen när han hittade på ordet googol. Sökmotorns stavning är alltså en omedveten återgång till ursprunget.
– i programmering: en serie tal i en bestämd ordning. (Ett slags datastruktur);
– i matematik: tecknad pil som beskriver en riktad kraft. Pilens längd visar kraftens belopp. – Ett mer abstrakt sätt att beskriva en vektor är att räkna upp koordinaterna för dess ändpunkter. Om vi ritar en vektor på rutat papper behöver vi två koordinater för startpunkten och två för slutpunkten, alltså fyra. Men man kan tänka sig vektorer som beskriver krafter i fler dimensioner, och då blir det fler siffror. Sådana sifferserier kan kallas för vektorer även om man inte ritar dem som en pil. Därav den datortekniska betydelsen, se ovan. – Man talar ibland om flerdimensionella vektorer, men då menar man att vektorn beskriver en kraft i en flerdimensionell rymd. Själva vektorn, alltså talserien, är alltid endimensionell (en rät linje). Därför är det skillnad mellan en vektor och en array: en array kan vara flerdimensionell, men det kan inte en vektor. – Se också tensor;
om nätverk: schematisk beskrivning av hur enheterna i ett datornätverk är sammankopplade. – En topologi beskriver med enkla geometriska modeller hur datorer och annan utrustning är anslutna till varandra. Man renodlar strukturen genom att tänka sig att alla böjda och tilltrasslade kablar rätas ut. Vanliga topologier är stjärnformad, hierarkisk, ringformad och mesh (spindelnät). – Ordet: Topologi är den gren av matematiken som handlar om beständiga egenskaper hos föremål som kan böjas, vridas och deformeras, som rep, tygstycken och elastiska föremål – ”geometri utan mått”. Att avgöra om en knut kan lösas upp är en topologisk uppgift. – Topos är grekiska för plats. – På engelska: topology.
(
