Numb3rs

Det, Charlie og co. virkelig bidrog med idag, var at genskabe det billede, der var forvansket, fordi det var taget dels gennem ruden på en bus og dels reflekteret i en termokop (eller noget i den retning).

Anamorfose
Forvanskning af billeder. I Numb3rs var billedet forvansket i spejlingen, men det omvendte har været kendt langt tilbage i tiden: Lav en tegning, som er forvansket, men som ser rigtig ud, hvis man f.eks. stiller en spejlende cylinder midt på (spejl anamorfose), hvis man kommer gående hen imod tegningen (perspektivanamorfose)- eller hvad man nu kan forestille sig. Da Vinci brugte teknikken med perspektiv – det er f.eks. smart, når man maler lofter.

Istvan Orosz: Anamorphosis with Column. Man kan se, hvor forvansket, det ser ud, inden spejling i cylinderen. Matematikken bag er ikke så vanskelig. Tegn det billede, man vil have frem på cylinderen i et sædvanligt rektangulært koordinatsystem (se øverst til venstre i tegningen nedenfor.) Billedplanen, hvor man skal tegne det deformerede billede, skal have det tilsvarende polære koordinatsystem: De lodrette linier fra før bliver til radier i en cirkel (linjer ud fra centrum), og de vandrette bliver til cirkelbuer med samme centrum (koncentriske). Billedet overføres nu et lille rektangel af gangen.

(Billede af Istvan Orosz, fra Wikipedia)

Kender man forvanskningen, kan man finde det oprindelige billede ved at “regne tilbage” – i.e., at løse det inverse problem.

Det er indbygget i f.eks. Photoshop, når det drejer sig om velkendte forvanskninger i kameraets objektiver. Men Larry og Amita (og til sidst også Charlie)  må skræddersy deres “afforvanskning”.

De genskaber situationen med bussen og kruset, anbringer Charlie som chauffør og finder ud af, hvordan han ser ud spejlet i kruset. Og så regner de tilbage, en lille firkant ad gangen. Larry nævner noget om splines: Når man regner på en firkant ad gangen, skal man sørge for, at det ser fornuftigt ud, hvor firkanterne mødes. Tænker man f.eks. på bare en dimension og laver sig en funktion, der skal være f(x)=x^2 for positive x og f(x)=x for negative x, så mødes de fint i x=0 (funktionen er kontinuert), men grafen knækker. Vil man undgå et knæk, skal man forlange noget mere om de funktioner, man tillader.

Forvanskningen kan afhænge af bølgelængden af lyset, og så må man afforvanske rød, grøn og blå hver for sig.

Fra Wikipedia: http://en.wikipedia.org/wiki/File:Uniformity.jpg

Her er et flot eksempel på forskellig forvanskning i to glas.

I en “afforvanskning” drejer det sig om funktioner, der tager to variable ind og giver to variable ud
(u,v) sendes i (x(u,v),y(u,v)).
(u,v) er koordinaterne i det forvanskede billede og (x(u,v),y(u,v)) skulle gerne være det rigtige billede. Kender man nu funktionen for at komme den anden vej – fra (x,y) til (u,v), altså forvanske, så kan man (måske) finde den, der “afforvansker”.

Charlie kommer til sidst med en diffeomorfi, der vrider det delvist afforvanskede billede på plads. En diffeomorfi er en differentiabel afbildning – som kan gøre noget forskelligt i forskellige områder af billedet – se nedenfor -man skal forestille sig, at de blå linjer har været koordinatsystemet, som nu er blevet vredet, men ikke værre end at linierne ikke har fået knæk – de er bare blevet buet.

Jeg ved ikke, hvordan Charlie gennemskuede, at det var den deformation, han skulle bruge, men ifølge igen Wikipedia, havde Interpol i 2007 en sag, hvor en pædofil havde taget billeder af sig selv, men fordrejet ansigtet ved en diffeomorfi – et “swirl” – Interpol gennemskuede, hvilken diffeomorfi, det var, og deformerede tilbage igen.

Der er fantastisk flotte eksempler på fortovsmalerier med perspektivisk anamorfose på Julian Beever’s hjemmeside. Bemærk, at billedrne kun har 3D effekt, hvis man ser dem fra den rigtige side. Se f.eks. globussen i det rigtige og det forkerte perspektiv.

Numb3rs køre på sæson 6 i USA, og nu er det besluttet kun at lave 16 i stedet for de planlagte 22 episoder.
Man kan skrive under på en protest på
http://www.petitiononline.com/numb3rs/petition.html
Jeg har skrevet under.
Man kan følge sagen på Numb3rs fangruppen på Facebook
Hilsen
Lisbeth

Charlie brugte matematik til at finde ud af, hvor folk sad i baren, før de allesammen blev skudt. Jeg hørte det som aggregerede modeller. Amita nævnte en anvendelse af grafteori for at matche nyrepatienter med donorer. Charlie havde udregnet decimaler i Euler-Mascheroni-konstanten, og han snakkede om Goldbach-formodningen. Til sidst brugte de “Hidden Markov Models” til at analysere skjulte mønstre på DVD’en
Jeg tilstår, at jeg denne gang skriver om den matematik, der blev nævnt i forbifarten, for jeg ved simpelthen ikke, hvordan det med siddepladserne hænger sammen med noget. Hidden Markov Models har jeg skrevet om før på bloggen – jeg kaldte dem skjulte Markov processer.

Grafteori og nyrepatienter
Når en pårørende tilbyder at give sin ene nyre til en syg bror, søster, datter, søn,… sker det desværre ofte, at de ikke matcher hinanden. Hvis der er tale om venner, er det sikkert endnu mere sandsynligt.
Og donoren vil nok ikke ofre en nyre til hvem som helst.
Men hvis der nu er to donor og patient par (A,a) og (B,b), hvor A vil donere til a, B vil donere til b. Ingen af dem matcher, men A og b matcher og B og a matcher. Så giver A og B implicit en nyre til deres familiemedlemmer, eller i hvert fald giver de hver en nyre, og a og b får hver en nyre. Mere generelt skal der måske flere (donor, patient) par til at få det til at gå op.

Opgaven er nu at finde den slags mere parringer. Ofte med bibetingelser om, at nyrer ikke skal transporteres for langt, at meget syge patienter går forud, at visse match er bedre end andre. Og det hører hjemme i branchen grafteori.
En matematiker ved US Naval Academy, Sommer Gentry, har set på dette problem, og det bruges tilsyneladende på bl.a. Johns Hopkins universitetshospital. De ser, så vidt jeg kan se, kun på den simple version, hvor et par matcher et andet par. Der er en gennemgang her.

Det gælder om at optimere. En patient med blodtype 0 kan kun bruge en donor med blodtype 0, mens en donor med blodtype 0 kan bruges til mange patienter (der står, at det er alle, men så simpelt er det nu nok ikke). Så man skal helst ikke “spilde” en god donor på en “nemt parret” patient.

Her er et eksempel:

Alle knuderne (cirklerne) er donor-patient par, og kanterne er match. Hvis man nu starter med at matche par nummer 4 og nummer 17, har man dummet sig, for bagefter er det kun

meget få match tilbage.

Man ønsker altså at finde den bedste parring/matching. En parring er et udvalg af kanter, som ikke har nogen fælles knuder (man kan ikke genbruge donorer/patienter). Og man vil have så mange kanter (og dermed knuder) med som muligt.

Lidt simplere eksempler:

(Fra Wikipedia under Creative Commons – se her.)

De øverste tre er maksimale parringer – man kan ikke tilføje nogen kanter-  men de er ikke optimale, for man kan sætte flere kanter ind, hvis man begynder bedre. (Bortset fra den sidste). Wikipedia kalder de optimale parringer for maximum parringer.

I b) er der en perfekt parring, idet alle knuder er med i en rød kant. Så man kan spørge: Findes der en perfekt parring? Hvilke klasser af grafer har perfekt parring? Og mere praktisk: Hvordan finder man en maksimum parring? Det sidste er besvaret. Edmonds algoritmen finder en maksimum parring i polynomiel tid. Den kaldes også stier, træer og blomster algoritmen (siger Wikipedia).

Man bygger en parring lidt ad gangen. Tilføj kanter, som ikke deler et hjørne, indtil der ikke kan tilføjes flere – man har en maksimal parring. Hvis alle hjørner er med, er den maksimum og vi er færdige. Hvis et hjørne ikke er med, kan den ikke blive bedre. Hvis mere end to hjørner ikke er med er der to muligheder:

1)Der er en udvidende sti, som er en sti, hvis kanter skiftevis er fra matchingen og ikke er det, og om starter og slutter i en knude, som ikke er parret endnu (en uparret knude).- se figuren, hvor de sorte kanter er i parringen, de lyseblå er kanter i grafen, men ikke med i matchingen.

(Fra Wikipedia-public domain)

Man laver en ny parring, hvor de kanter, der er i den udvidende sti og er sorte (er i parringen) bliver lyseblå (fjernes fra parringen). Og de kanter, der var lyseblå bliver sorte (tilføjes til parringen). Nu har vi en kant mere end før i parringen og dermed to knuder mere med.

2) Hvis der ikke er en udvidende sti, kan man ikke lave en større parring end den, man har. (Det kræver et bevis).

Algoritmen skal altså finde udvidende stier. Udvidende stier findes ved at “opdyrke en skov”. Start med alle uparrede hjørner. De er rod i hver sit træ. Tilføj alle kanter fra disse hjørner, (de er ikke i parringen, for hjørnerne var uparrede), nu er træerne 1 kant høje (eller 0, hvis der ingen kanter var). Hvis en af de nye kanter ender i et parret hjørne, tilføjes den tilhørende kant fra parringen (det gør man for alle de nye kanter.) Træerne er nu 0, 1 eller 2 kanter høje.  Og man bliver ved. Hvis der opstår forbindelser på tværs mellem træer er der mulighed for, at der er en udvidet sti: Løb fra roden op i det ene træ og ned i det andet til den anden rod. Det er mere indviklet, og mere smart fundet på – man skal “trække blomster sammen”. Læs mere på Wikipedia.
Her er en skov (der vender på hovedet – det er en uvane blandt grafteoretikere og dataloger). Der er en udvidet sti fra knuden til venstre via den skrå stiplede lyseblå til knuden til højre. Hvis man skifter lyseblå kanter om til sorte og omvendt langs denne sti, har det konsekvenser for andre kanter i parringen, så man skal lave sin algoritme smart nok

fra Wikipedia – ingen betingelser for brug.

Euler Mascheroni konstanten
Euler-Mascheroni-konstanten eller bare Euler konstanten er defineret som en grænseværdi.
Lad x_n= (1+1/2+1/3+1/4+…+1/n)-ln(n)
Euler- konstanten er det tal, som x_n nærmer sig, når n bliver større og større. Man skal overveje, at der er en sådan grænseværdi. Men når man har vist det, er dette en fin definition af et tal.

Vi ved ikke, om Eulerkonstanten er rational (altså kan skrives som en brøk p/q, hvor p og q er heler tal). Vi ved heller ikke, om den er transcendent (om den er rod i et heltalspolynomium, altså løsning til en ligning a_n x^n+a_(n-1) x^(n-1)+…+a_1x -a_0=0, hvor alle a_k er hele tal).
Eksempelvis er kvadratroden af 2 irrational, men ikke transcendent, da det er rod i x^2-1.
Men pi er irrational og også transcendent, og det er grundtallet for den naturlige logaritme , e, også.

Hvis Eulertallet er rationelt, altså skrives p/q. Så ved man, at q må have mere end 242000 cifre.

Man kender de første 2 milliarder cifre i Eulerkonstanten (!!).
den optræder i mange sammenhænge – integraler, i forbindelse med Riemanns zeta funktion og mange andre steder. Se for eksempel Math World.

Leonhard Euler, som man kan se på billedet, (Public domain, da copyright på det oprindelig maleri er udløbet. Se Wikipedia) var en utroligt produktiv matematiker – en af de største, vi har haft. Lorenzo Mascheroni havde jeg ikke hørt om før, men han var italiener og har bl.a. bevist en sætning, som også danskeren Georg Mohr viste (og Mohr var først) – Mohr kendes måske af læserne fra Georg Mohr konkurrencen for gymnasieelever.

I går var jeg til lanceringsfest for bogen Nærmest Lykkelig i Nørdland – kommer på Gyldendal Business 12. november.
Nærmest Lykkelig i Nørdland er et større projekt, som har til formål at få flere kvinder ind i “nørdfagene”, og der er mange elementer i projektet bl.a. en test på facebook og en filmkonkurrence.
Man kan vinde op til 25000 kr. ved at lave en video – se mere om betingelserne.

Og køb bogen. den er god – og jeg er med i den 🙂 Det er en blanding af fakta-afsnit og interviews med 12 “rollemodeller” – herunder yours truly…

Der var afledning/decoy i flere betydninger. Charlie omtalte “decoy effect” eller asymmetrisk dominans fra marketing, og Nikki var lokkedue/decoy.

Programmet Spider, som overvågede ATM-maskinerne var et distribueret neuralt netværk. Der var “scheduling algoritmer” og Larry nævnte Hall effekten.

ATM-maskiner

ATM står for “automated teller machine”. Og ATM-maskiner er pengeautomater. Der er meget matematik i pengeautomater: Transaktioner skal krypteres, så man ikke kan opsnappe data fra mit dankort, når de sendes fra pengemaskinen til en central enhed. De signaler, der sendes rundt er kodede, hvilket ikke er det samme som kryptering. Kodningen sikrer, at man kan læse beskeden, når den når frem, selvom der måske er sket små fejl undervejs.

I dette afsnit havde forbryderne adgang til et program, Spider, der overvågede transaktionerne mellem et stort net af ATM-maskiner. De forsøgte at gennemskue, hvordan informationen blev sendt rundt, ved at få de kidnappede kvinder til at hæve “skæve” beløb i automaterne. Ideen skulle være, at man kunne genkende den datastrøm, der svarede til 437$, hvis man havde gjort det mange gange. hvis nu, man brugte samme kryptering af data, hver gang, kunne det jo give mening, men det gør man forhåbentlig ikke.

Pointen var, at de ville gennemskue, hvornår en pengeautomat skulle fyldes op – det var en af de ting, overvågningssystemet Spider holdt styr på.

Brydningen af tyskernes Enigma kryptering under 2. Verdenskrig byggede faktisk på, at man vidste, at en bestemt sætning blev gentaget hver dag. Det gav noget ekstra information om krypteringen, som man kunne bruge til at gætte (og her mener jeg ræsonnere sig frem til) dagens indstilling af Enigmamaskinen og dermed dagens kryptering. Det var her væsentligt, at man også havde Enigma maskinen – smuglet ud af en polsk matematiker via Paris lige før krigen. Så måske er der noget om, at man ved at hæve 437$ tilstrækkeligt tit kunne gennemskue noget om nettet i Spider.

Scheduling algoritmer

Når flere computere/processer vil have adgang til samme ressource, en database eller lignende, er der en “scheduling algoritme”, der bestemmer i hvilken rækkefølge, de får adgang. Jeg deler lige nu en større computer med andre, og der er en algoritme, der bestemmer, hvordan vi deler. (Og dette indlæg er forsinket, fordi schedulingen har været, at ingen kunne noget som helst de seneste dage – det er jo også en slags prioritering omend lidt uhensigtsmæssig).

Meget simpelt kunne man give hver proces adgang i 1 millisekund ad gangen, så jeg får et millisekund, så min kollega, så den næste kollega og så mig igen, hvis vi kun er tre. Hvis der ikke er andre på, har jeg den hele tiden. Man kan også prioritere. For eksempel kan jeg erklære et tungt program for en baggrundsproces, så de andre får fortrin, og min store beregning kun bruger tid på computeren, når ingen andre har brug for den. Eller man kan bestemme fra “højere sted”, at nogle kolleger er mere værd end andre og dermed får fortrinsret. Man kan have et kommunikationsnetværk, hvor visse typer data får fortrinsret. Eksempelvis har telefonsamtaler fortrinsret for SMS’er (så vidt jeg ved). Man kan ikke have “huller” i samtalerne, men man kan godt vente lidt på en SMS.

Scheduling og deadlocks.

Det sagde Charlie ikke noget om, men det er nu interessant og fin matematik…

I en database er der grænser for hvor mange, man giver adgang af gangen: Man kan ikke tillade flere at hæve penge fra samme konto samtidig – hvis der står 100 kroner, flere med adgang til kontoen læser det og derefter hæver hver 100 kroner, så er kunderne glade og banken knap så glad.

Figure her forestiller to processer, T1 og T2, som begge vil have adgang til ressourcerne A og B. Det gør det ved et Lås ressourcen, så andre ikke kan få adgang (og hæve pengene), gør noget med ressourcen og frigiv den så. Lås A hedder PA, frigiv A hedder VA.

T1 vil gøre PA, PB, VB, VA – i den rækkefølge

T2 ønsker PB, PA, VA, VB

En udførsel af programmet svarer til en “sti” (en kurve) fra (0,0) til (1,1), som hele tiden bevæger sig opad og mod højre, da både T1 og T2 skal gå fremad.

På tegningen kan man se, hvad der sker, hvis T1 har låst A (udført PA) og T2 har udført PB. Så er systemet låst fast. – man er i området “unsafe”. De vil have hinandens ressourcer, og det sker ikke, for T1 frigiver ikke A, før den har haft B – og omvendt.

Der er en deadlock. En smart scheduler ville have forhindret det – altså have forudset, at når T1 har fået A, skal T2 ikke have B, før A er færdig.

At studere den slags problemer fra et geometrisk synspunkt er meget effektivt – eksemplet her kan man godt overskue uden, men de kan jo være meget mere indviklede – 100 processer, 50 fælles ressourcer…

En anden nyttig information fra billedet er, at der er et område, unreachable, hvor man aldrig vil komme, hvis man starter i (0,0). Den information er nyttig, hvis nu der er ubehagelige konsekvenser af at være i det område – a la nedbrud af systemer.

Det er faktisk mit forskningsområde; datalogiske problemer angribes med geometrisk (topologiske) metoder.

Asymmetrisk dominans

En forhandler har to MP3 afspillere

A koster 400 kr og har 30 GB

B koster 300 kr og har 15 GB

Skal man købe en MP3 og interesserer sig for pris og hukommelse – billgst muligt, mest mulig hukommelse, kan man ikke umiddelbart bestemme sig for, om man skal købe A eller B – B er billigere, men den har også mindre. Decoy effekten er som følger:

Hvis der er en tredje afspiller

C: koster 450 kr og har 25 GB

Så er A klart bedre end C (billigere og mere hukommelse), C er stadig ikke klart bedre eller dårlige end B – der er assymmetrisk dominans. Marketingfolk har vist, at hvis C er med i udbuddet, så vil langt flere købe A fremfor B, end hvis C ikke er der. Man synes A er et godt tilbud, fordi det er bedre end C (som marketingfolkene måske bare har sat til salg for at få folk til at købe den dyre A…)

Vil man have solgt flere af B, skal man i stedet for C udbyde

D: koster350 kr og har 10 GB

Nu er B klart bedre end D (billigere og mere hukommelse), A er dyrere end D, men har mere hukommelse, så der er ikke en klar præference – assymetrisk dominans. Forbrugerne synes nu, B er et bedre tilbud end A, fordi B slår C.

Fra matematikerens synspunkt er det jo noget med psykologi, men jeg kan da påpege, at der her er tale om en partiel orden. En MP3 er givet ved to tal, (p,h)=(pris, hukommelse). Og (p1,h1) er større end eller lig med (p2,h2), hvis p1 er mindre end eller lig p2 og h1 er større end eller lig h2. Tegner man det i et sædvanligt koordinat system, er alt, hvad der ligge “ovenfor og til venstre” et punkt (p,q) større end (p,q).

Det er en partiel orden, fordi der er punkter, sum ikke er hverken større end eller mindre end hinanden.

Selv med Charlie lidt indisponeret kunne der komme matematik med – Amita og Larry kan godt selv… Jeg så noget om squish squash algoritmer og noisy edge i analysen af radarsignalet – hvor de endte med at finde flyet. Charlie havde anden ordens sædvanlige differentialligninger på sin tavle, da han regnede på, hvilken satellit, der blev brugt. Amita nævnte “Opti krystallografisk analyse” i forbindelse med diamanten og klassifikation af, hvor den kom fra (det brugte de nu ikke). Der var en del topografiske kort – bl.a. fra National Geospatial Intelligence Agency NGIA (vistnok også kaldet NGA) – det var det, der var hemmeligt, men som Charlie (eller måske Ian Edgerton) havde adgang til. Jeg vil tro, det drejer sig om de nyeste billeder fra satellitovervågning.

Krystallografisk analyse og diamanter
Handel med diamanter kan, som man så i dette afsnit, være en blodig affære. Indtægterne kan finansiere krige, og man vil gerne identificere, hvor diamanter kommer fra, for at kunne undgå dem fra Sierra Leone, DR Congo, Liberia og Angola, som menes at være mest “blodige”. Se
Gems of war: scientists struggle to identify conflict diamonds Science News, August 2002. Åbenbart var det blandt Bill Clintons sidste bedrifter som præsident, at han gav penge til forskning i “fingeraftryk” for damanter.
Det er et aktivt forskningsområde, og flere metoder forsøges. Her Hope Diamond’s Fiery Red Phosphorescence Key To Fingerprinting ScienceDaily (Jan. 7, 2008) kan man se Hope diamanten lyse rødt, når man lyser på den med et bestemt lys.
Visse faste stoffer har krystalstruktor: Atomerne er ordnet i et regelmæssigt gitter. Klassifikation af den slags gitre er fra matematikeres synspunkt i branchen gruppeteori; det handler om symmetrier. der er flere synspunkter – Bravais lattice er et; jeg vil beskrive punktgruppe synsvinklen:

En punktgruppe er en mængde af symmetrier (rotationer og spejlinger), der holder et punkt fast. For et krystal holder man et atom fast og ser på, hvilke rotationer, der bringer alle andre atomer over i et atom af samme type. F.eks er natrium klorid NaCl (kogesalt) et gitter med skiftevis natrium og klor atomer. Holder man et kloratom fast (en af de grønne nedenfor), kan man bringe naboatomerne over i hinanden ved f.eks. at rotere 90 grader omkring tre forskellige akser eller spejle i passende planer. Symmetrierne udgør en gruppe, da man
1) kan sammensætte to (rotere først om en og så en anden akse) og få en ny symmetri
2) Kan komme tilbage igen (rotere den anden vej eller spejle igen)
3) har en symmetri, der ikke gør noget.

(Fra Wikipedia under Creative Commons, se copyright
Man kan klassificere de grupper, der kan optræde som symmetrigrupper for krystaller. I et krystal forlanger man, at der er translationssymmetri, altså at man kan skubbe alle atomer et skridt i samme retning og derefter ikke kan se forskel på krystallet før og efter. Hvis symmetrierne, der holder et atom fast, skal passe sammen med translationer, kan man vise, at det ikke er alle symmetrier, der kan optræde.

Man studerer krystallerne struktur ved at sende polariseret lys igennem og (som jeg har forstået det) se, hvordan det absorberes. Og hvordan absorptionen afhænger af, hvordan man vender krystallet. Måske sender man upolariseret lys in, og så bliver det polariseret af at gå igennem krystallet.

Diamanter har også krystalstruktur – kulstofatomerne sidder i et gitter med en bestemt struktur. Tænk ikke på måden, der er slebet på – det er en helt anden historie, men den struktur, de har, når man finder dem. Strukturen er i princippet den samme for alle diamanter

Billede fra Wikipedia under Creative Commons. Se her om Copyright.
a) er diamant, b) grafit, c) Lonsdalit d), e) og f) er Fullerenes (kulstof 60, 540 og 70) – også kaldet buckyballs g) er amorf kul – det, vi normalt vil kalde kul e) er et kulstof nanorør.

Diamanter er altså i princippet ens – de har struktur som ovenfor. Klassifikation/fingeraftryk er en kortlægning af urenheder i diamanterne – enkelte andre atomer end kul: Hvilke andre, og hvordan sidder de i strukturen. Jeg har ikke kunnet se referencer til, at det skulle være lykkedes at klassificere diamanter på den måde, men der arbejdes på sagen.

Symmetrier og virus

Reidun Twarock og hendes gruppe i York arbejder med klassifikation af virus via symmetrier. Virus indkapsler sig i en “capsid”, hvis symmetrier afslører meget om, hvordan virus agerer. Se et interview i Plus Magazine
Squish squash
Jeg har skrevet om squish squash tidligere. Se Noisy Edge

Man kan købe Sæson 5 på region 1 DVD, altså den amerikanske standard. Den udkommer 20/10. Jeg handler hos Movie World, men der er sikkert mange andre muligheder. Den koster ca 400 kroner og indeholder 6 DVD’er (23 afsnit).

Sidste afsnit i sæson 4, så der var masser af “cliff hangers” til sæson 5. Men der var også en hel del matematik. Algebraisk statistik (det, der blev brugt i DNA-analysen, som blev sendt til Pakistan). Noget om at få data til at passe med forud bestemte konklusioner ved at se på data med bestemte briller(absolut forbudt i statistik). Noget i den branche af matematik, der kaldes teoretisk datalogi (!), nemlig Byzantinske fejl og fejltolerance. Og så var der den altoverskyggende problematik i afsnittet: hvad gør et internationalt fag som f.eks. matematik, i en verden, hvor det kan være ulovligt at fortælle om forskningsresultater til forskere fra bestemte lande?
Algebraisk Statistik
Det kan være mange ting, men jeg vil tro, der henvises til Bernd Sturmfels og brugen af algebraisk geometri i biologi. En ny gren af matematikken, Computer Algebra, er opstået i forbindelse med behovet for at “lave matematik på en computer” og her tænkes på matematik – ikke regnestykker. F.eks. har  stamfunktionsproblemer: find en funktion F(x) , hvis afledte er f(x), krævet rigtig smart ny matematik. Tænker man på, hvordan den slags gøres i hånden, er det klart, det er svært: Man skal se godt på funktionen, overveje, om det nu er delt integration eller substitution, der kan virke etc. Og de fleste funktioner f(x) har slet ikke en “pæn” stamfunktion. Sturmfels og co. bruger statistik kombineret med computer agebra i biologi – specielt i forbindelse med DNA sekvenser og lignende. Se f.eks. bogen Algebraic statistics for Computational Biology
Byzantinske fejl
I et computerprogram, der skal udføres i samarbejde mellem flere computere eller bare flere processorer i samme computer, skal man tage hensyn til en lang række problemer. Området Parallel (Concurrent) og distribueret (distributed) beregning er et overordentligt aktivt og væsentligt forskningsområde: Vi vil gerne tillade distribution (fordeling til flere processorer) af opgaverne, for det går hurtigere med flere processorer, men vi vil ikke have, der opstår fejl, som skyldes, at det nu er distribueret og ikke bare en processor, der går et skridt af gangen – samarbejdsproblemer… Jeg arbejder med matematik, der kan bruges til at ræsonnere om parallelle beregninger, og jeg har fået hjælp af min kollega Maurice Herlihy (Brown University) til dette svar. Maurice arbejder i området distribuerede systemer og er berømt for visse umulighedsresultater om netop fejltolerante programmer; resultaterne er vist ved brug af moderne matematik – fra området algebraisk topologi. Maurice’s foredrag, da han modtog Gödel prisen i 2004 , findes her.
Et eksempel på et distribueret system er “Free Flight”. Piloter, der skal over Atlanterhavet (f.eks.) skal måske fremover selv udveksle info med de andre fly og blive enige om, hvem der bruger hvilken korridor – i.e. – hvem flyver i laget i højde 10000m til 10500 m og hvem i laget 9500-10000m etc. De skulle helst kunne blive enige om en fælles fordeling af alle. Systemet er ikke indført, men er muligvis på vej.
Man kan finde mange flotte ppt præsentationer om distribueret beregning på Maurice’s hjemmeside.

I branchen fejltolerance er scenen som følger:

Man studerer

1) Forskellige typer fejl

2) Forskellige former for udveksling af information

3) Forskellige opgaver, der skal udføres i fællesskab.

Om 3): En typisk opgave, som mange distribuerede problemer kan koges ned til, er konsensus: Hver processor har en startværdi (ofte enten 0 eller 1) og alle processorer skal efter en række skridt enes om en af disse.

Om 2) Man kan udveksle synkront – alle udsender information samtidig. Eller asynkront – man sender, når man vil, og skal ikke vente til alle er klar. Man kan udveksle fra alle til alle eller man kan sende til  nærmeste naboer (passende defineret).

Om 1) En processor kan simpelthen dø – holde op med at sende. Den kan sende noget, der ikke overholder “reglerne”, den kan dø og senere live op igen. En Byzantinsk fejl repræsenterer det værste, man kan forstille sig : At en bevidst vildleder de andre. Det gør processorer jo ikke, men man bruger denne analogi for at kunne lave meget robuste systemer til f.eks. fly. Hvis man ikke kan vide, hvilken type fejl, der kan opstå, må man sikre sig mod det værst tænkelige.

Opgaven vil, når der er mulighed for fejlagtige processorer, være, at de ikke-fejlbehæftede enes om en af de værdier, de havde fra starten af.

Et typisk spørgsmål er: Hvor mange fejlagtige processorer kan man have, og stadig fuldføre?
Lad os sige, der er to værdier, 0 og 1, at vælge imellem. Og at der er tre processorer, A,B og C. I første runde skal de fortælle hinanden, hvilke værdier de har. Og i næste kommunikerer de, hvad de har modtaget fra hinanden. Vi sidder på B’s plads.

Første scenario:

A siger til B og C, “Min værdi er 0”

I næste runde siger C til B “A sagde, hun havde værdien 1”  (C er forræderen)

Andet scenario:

A siger til B: “Min værdi er 0” og til C: “Min værdi er 1” (A er forræder)

Så vil C i næste runde sig “A sagde, hun havde værdien 1” og C er ikke forræder.

Hvad skal B så konkludere? Det ser ens ud, men der er forskellige forræddere.

Man kan vise, at konsensus i denne opsætning kan løses, hvis der er højst t forrædere og mindst 3t+1 processer. Og at det ikke kan løses, hvis 1/3 af processorerne er fejlagtige/forræderiske.

Charlie påstod, at han brugte den type metoder til at finde forræderen. Det er tvivlsomt, for man kan godt have en løsning på konsensus, uden at have fundet ud af, hvem forræderen er. Bare man kan blive enig om en, der i hvert fald ikke er.

Et typisk bevis for umulighedsresultater er et modstridsbevis. I Herlihy (og i øvrigt Nir Shavit)’s resultater antager de, at de kan løse et bestemt konsensusproblem. Så bruger de nogen rigtig smarte argumenter til at oversætte til, at i så fald er der en bestemt funktion mellem to geometriske objekter. Fra algebraisk topologi ved vi, at den type funktion ikke findes. Voila en modstrid. Så antagelsen var forkert – man kan ikke løse dette konsensusproblem.

Matematik er international

Matematikkens infrastruktur er ganske kompliceret. Vi bruger Internettet (og har gjort det flere år før www): Vi emailer artikler frem og tilbage, mellem medforfattere. Vi lægger færdige artikler, som er klar til publicering – preprints- i ArXiv. Matematiske tidsskrifter er tilgængelige på nettet (nogen af dem er alt for dyre, men det er en anden historie). Der er to store databaser. MathReviews og Zentralblatt, hvori vi skriver korte reviews af allerede publicererede artikler. Så kan man søge og finde ud af, om det, man skal bruge, måske allerede er bevist i 1896 (!). Der er 2.500.000 reviews og altså lige så mange artikler. Matematik er et stort fagområde.
Vi rejser rundt i verden for at samarbejde. Vi har PhD-studerende og PostDocs (folk, der lige har fået deres PhD) fra mange lande, og danske PhD-studerende rejser ud. Vi deltager i konferencer, hvor vi præsenterer egen forskning, og, nok så vigtigt, lærer om andres forskning.
Vi skelner normalt ikke mellem, om kollegerne er fra den ene eller den anden del af verden.  Universiteternes rolle er at producere viden og give den væk til dem, der kan bruge den. Og for danske universiteter er det bl.a. at deltage i handlen med resultater: Jeg præsenterer mit arbejde og lærer om alle de andres. Den viden kan jeg så tage med hjem og måske gøre ingeniørkollegaer opmærksomme på noget nyt matematik, de ikke havde hørt om.
Omvendt skal man jo ikke være nyttig idiot og levere bombeopskrifter til galninge. Så det er en balance. I dette Numb3rs afsnit så det ud til, at FBI/CIA var så forhippede på, at pakistanerne var terrorister, at de så spøgelser i forskningsresultaterne.

Charlie og Larry analyserer musik for at se, om det har hit-potentiale. Der er noget med en “stringmetric”. Desuden bruger Larry og Charlie Kodningsteori for at gendanne tabt information i den computer, der bliver skadet, da en bil ryger i luften; Larry nævner Gröbner baser i den forbindelse Så der var rigtig meget matematik!

Matematik og hits
Der er flere firmaer, der analyserer musik for at forudse, om de bliver hits, og – vel mere nyttigt for pladeindustrien – siger noget om, hvordan man kan ændre et nummer for at give det mere hit-potentiale.

Firmaerne vil naturligvis ikke afsløre, hvad de helt præcist gør, men noget kan man finde ud af.

Platinum Blue (som nu hedder Music XRay), grundlagt af Mike McCready m.fl. omtales i The New Yorker i en artikel af Malcolm Gladwell (ham med “The tipping Point”). Et andet firma er uPlaya, hvis teknologi kaldes Hit Song Science.
Overordnet er pointen, at musik på digital form naturligvis kan analyseres med matematisk/statistiske/ datalogiske værktøjer. Feltet kalde Music Information Retrieval (MIR) og er beskrevet i Music Retrieval, A tutorial and Review.
Men hvad skal man kigge efter? Et digitaliseret musiknummer er en (meget lang) stribe 0’er og 1’er.
Firmaerne har studeret tidligere hits. Analyseret dem for tredive forskellige parametre (og det er nok hemmeligt hvilke) og derefter konstateret, at de samler sig i klumper i det 30-dimensionale rum. Og at numre, som ikke har været hits, typisk ikke ligger i disse klumper. Begge ovenstående firmaer hævder i øvrigt at have forudsagt, at Norah Jones ville få succes.

I artiklen om MIR nævnes mange parametre, som kunne indgå i analyserne: Rytme, tempo, tonehøjde (pitch), volumen, “timbre” – det, der gør, at man kan høre, at en tone spilles på en saxofon og ikke en trompet, tonalitet (er det A-dur eller C-mol – for den slags musik, hvor det giver mening), orkestrering (hvilke instrumenter spiller hvad), melodi, harmonier, struktur på langs: gentagelser, pauser, hvordan temaer fletter ind i hinanden, skift i rytme, volumen og alle de andre parametre.

Det gælder så om at genkende alle disse egenskaber i musikken udfra de lange strenge af 0’er og 1’er.
Her kommer “stringmetrics” ind i billedet.

Strengmetrikker
Skal man sammenligne to strenge af 0’er og 1’er – binære strenge – kræver det et mål for, hvor forskellige de er.
Er de lige lange kan man f.eks. sige, at afstanden er antallet af pladser, hvor de er forskellige: Afstanden mellem 0001 og 0010 er 2, fordi de er forskellige på de to sidste pladser. Dette afstandsmål kaldes Hamming-afstand.
Der er et hav af strengmetrikker. Her er en lang liste. Man tænker generelt på strenge af ikke bare 0 og 1, men med andre “alfabeter” – som f.eks. ordene i en ordbog, hvor alfabetet er det sædvanlige. Når Google finder stavefjel og spørger “Mente du stavefejl”, er der en strengmetrik i spil.

Levenshtein-afstanden mellem to strenge er det mindste antal basale ændringer, man skal lave for at komme fra det ene ord til det andet. De basale ændringer er 1) Indsæt et bogstav 2) Fjern et bogstav 3) Erstat et bogstav med et andet.
Eksempel: fra mandag til tirsdag
Mandag -> Mansdag ->Tansdag ->Tinsdag->Tirsdag
Affstanden er altså 4, hvis man tror på der ikke er en smartere måde at gøre det på. Der er algoritmer, der finder Levenshtein-afstanden – se linket ovenfor eller Wikipedia.
Der er afstandsmål, der tager hensyn til almindelige stavefejl, til bogstaver, der udtales nogenlunde ens (så afstanden mellem d og t er kortere end mellem d og k) og mange andre variationer.

Et afstandsmål kan ikke være hvad som helst. Man har helt generelt afstand mellem elementer i en mængde M (som så kan være strenge, punkter i planen, andengradspolynomier, billeder,… alt efter den ønskede anvendelse.
Et afstandsmål (kaldes også en metrik) skal opfylde følgende simple regler, hvor d(x,y) betyder afstanden mellem x og y og d(x,y) altid er et reelt tal:
d(x,y)=0 hvis og kun hvis x=y (og d(x,y) er aldrig negativ)
d(x,y)=d(y,x) (Symmetri)
d(x,y) <= d(x,z)+d(z,y)

Den sidste kaldes trekantsuligheden og siger, at afstanden direkte fra x til y er mindre end eller lig med afstanden fra x til y via z. Man behøver faktisk ikke sige, at d(x,y) ikke er negativ, for 2d(x,y)=d(x,y)+d(y,x)>=d(x,x)=0 hvor vi bruger symmetri og trekantsuligheden.

Det er fantastisk effektivt at have et sådant generelt afstandsbegreb. Hver gang, man bruger de generelle egenskaber til at argumentere for, at noget gælder, så gælder det for alle de afstandsmål, man kan finde på.
En mængde med et afstandsmål kaldes et metrisk rum, og vi kan definere

• kontinuerte funktioner mellem to metriske rum
• Det metriske rum (M,d) er begrænset, hvis d(x,y)<=R for et fast R og for alle x,y i M
• En sti eller kurve i et metrisk rum er en kontinuert afbildning s:[0,1] ->M hvor [0,1] er intervallet med sædvanligt afstandsmål.
• Kuglen omkring m med radius r er alle de x i M, som opfylder d(x,m)<r (OBS: Kugler kan se meget mærkelige ud. Tænk på strengmetrikkerne ovenfor)

og meget mere.

Kodningsteori må I vente med til en anden gang.

men her er et klip med Bobby McFerrin, der illustrerer, hvordan vi har et fælles tonesprog i den pentatone skala:

I et tidligere afsnit, 2-23, brugte Charlie modeller for strømning langs kysten. Det står der noget om i New York Times. “Finding order in the apparent chaos of currents.” Det ser ud til at være den forskning, Charlie og co. hentyder til, da de smider bøjer i vandet og dermed får et billede af strømforholdene og hvor de lig, der driver i land, kommer fra.
Der er rigtig gode videnskabsartikler i New York Times.
Forskningen foregår bl.a. på Caltech – se f.eks. her for det generelle projekt og her for det, der foregår i Monterey bugten.