Numb3rs

Onsdag klokken 20 konkurrerer DR igen med Kanal 5 om at tiltrække de mange, der vil se TV med matematik i…

Så sæt DVD-optageren til, mens du ser Numb3rs, for DR2 viser Proof med Gwyneth Paltrow, Jake Gyllenhaal og Anthony Hopkins.

Som med alle film om matematikere, er jeg lidt ambivalent overfor Proof. Problemet her er, at matematiske evner igen kædes sammen med sindssygdom, og det er altså lidt trættende. Omvendt er det dejligt at se en kvindelig matematiker, Gwyneth Paltrow.

Filmen handler jo ifølge titlen om et bevis, men man ser faktisk ikke meget rigtig matematik. Det handler mere om, hvordan livet som matematiker kan være, og det er ind imellem ret godt beskrevet, og ind imellem karikeret. Det er, som med f.eks. Good Will Hunting, problematisk, at matematik ser ud til at handle udelukkende om genialitet og ikke så meget om hårdt arbejde og om at være omhyggelig. Faktisk handler det i høj grad om hårdt arbejde. Der er simpelthen en lang vej til at forstå en gren af matematikken godt nok til at kunne få gode ideer om netop den del af matematikken. I Proof har Paltrow jo i hvert fald været ved at læse matematik, så det giver mening, at hun overhovedet kan forstå sin fars arbejde og selv lave ny matematik.

Der er en herlig scene med en fest, hvor Gyllenhaals band spiller (altså Hal’s band – den matematiker, Gyllenhaal spiller i filmen) Jo, matematikere kan godt holde fest!

Proof var oprindelig et teaterstykke, og spillede mere end 900 forestillinger på Broadway – ret godt gået.

Se selv filmen. Det er en god film, selvom matematikken og matematikerne måske ikke er helt troværdige hele tiden. Men matematikere er også meget forskellige, så dem, der forekommer heri, findes der også kopier af i virkeligheden.

Forholdet mellem Paltrow, hendes far og hendes søster, er rigtig godt beskrevet. Så alene af den grund er det en god film.

Idag klokken 12 blev det offentliggjort på Abelprisens hjemmeside, at prisen i år går til to af bagmændene bag moderne gruppeteori. Nemlig John Griggs Thompson og Jaques Tits. På Abelprisens hjemmeside kan man læse meget mere om de to prismodtagere og hvorfor, de har fået prisen. Det er matematikkens størstepris, så det er en meget stor ære at få den.

Gruppeteori er basalt set teorien om symmetri. Man kan tænke på symmetri som operationer: Spejlingssymmetri betyder, at man ikke kan se forskel på objektet før og efter, man har spejlet det. I gruppeteori betragter man operationerne som sådan. Spejling i en bestemt linje, rotation med 90 grader etc. Og det er karakteristisk, at
man kan sammensætte operationerne,
man kan gøre dem om, i.e. rotere tilbage igen eller spejle tilbage.
Og der er en neutral operation: Gør ingenting.

Hvis et objekt er bevaret under rotation med 90 grader og ved spejling i x-aksen, så er det også bevaret ved den sammensatte operation. Så symmetrierne af et objekt kan beskrives som den mængde af operationer, der fastholder det. Og sådan en mængde er en gruppe, fordi operationerne opfører sig som ovenfor.

Visse grupper er i virkeligheden kombinationer af andre:
En 15-kant er symmetrisk under rotation med 1/15 af en omgang, men symmetrierne kan sammensættes af rotation 2/5 og derefter tilbage 1/3. Altså er symmetrierne af femtenkanten en kombination af symmetrierne af femkanten og trekanten.

Grupper, der ikke kan sammensættes fra mindre stykker, kaldes simple, og ligesom primtal er interessante som byggeblokke for tallene, er de simple grupper interessante.

I et enormt projekt har man nu klassificeret alle simple grupper, og Abelprisen til Thompson er en anerkendelse af hans fundamentale bidrag til dette kæmpe projekt.

Hvis man nu har en gruppe, altså nogen operationer, f,g,h og regler om, at f*f*f*f er den trivielle flytning etc., sså kan man spørge, om der er en geometrisk figur med netop disse symmetrier.

Tits har bidraget med resultater i den retning – fra gruppe til geometri. hvor de geometriske objekter f.eks. kan være noget i retning af den 4-dimensionale kube, hyperkuben, som jeg har fortalt om før.

I får måske mere en anden dag, men lige nu må I kigge videre på abelprisens hjemmeside, hvis I vil vide mere.

Igen et glimrende afsnit af Numb3rs – men vi holder os jo til matematikken her, så ikke et ord om alt det andet!

Der var jo faktisk masser af matematik og lignende.

I starten eksperimenterede Larry og Charlie med en af de mystiske maskiner, man kan finde opskrift på rundt omkring på nettet. Mythbusters har haft den med for et halvt års tid siden (Episode 68, Antigravity device). Påstanden var, at man kunne slukke for tyngdekraften med den fikse trekantede konstruktion, men det kunne man ikke…

Grundlæggende handlede det om “Load Flow analysis” og andre metoder til at se på kraftværker i netværk. Charlie analyserede, hvilket kraftværk, man skulle tage ud, for med størst sandsynlighed at forårsage hele netværket til at lukke ned via en dominoeffekt; og der var en ingeniør (Lyle Donohue), der havde brugt Dantzig Wolfe dekomposition til at forudsige effekten af at sabotere forskellige dele af nettet.

Dominoeffekt eller Cascading failure: Problemet er, at man er nødt til at reagere hurtigt, hvis et kraftværk går ned. Vi så det på Sjælland og i det sydlige Sverige for et par år siden: Et kraftværk gik ned, et andet blev overbelastet og lukkede, hvorved endnu flere blev overbelastede etc. – man har relæer, der lukker ned, hvis der løber for meget strøm – ligesom vi har HFI relæ i private hjem. Så hvordan forebygger man den effekt? Man kan isolere hvert kraftværk og dets brugere, så der ikke er back up hvis et værk går ned. Det vil begrænse skaden, men er ikke ideelt der, hvor andre kraftværker kunne have leveret strømmen og dermed have holdt alle brugere forsynet. Desuden ønsker man at fordele belastningen, så man f.eks. kan få strømmen fra den billigste leverandør – måske er det billigere at køre med middelstor belastning på flere kraftværker end med høj belastning et sted og lav andre steder.

Man har altså et stort overordnet problem: Sørg for strøm til alle på nettet billigst muligt eller rettere med mest mulig profit. Problemet og diverse beslutninger (luk ned eller bliv på – skru op eller ned for forsyning fra et sted – sæt endnu en enhed i drift – luk et relæ…) skal distribueres til mindre enheder – de lokale kraftværker – som ikke har overblik over hele nettet, men kun kan se data fra dele af nettet. Man kan formentlig ikke nå at regne overordnet på hele nettet, hvis der er risiko for blackout. Hver enkelt enhed skal reagere hurtigt. Og beregningerne vil involvere rigtig mange variable.

Et andet problem er, at når et kraftværk aller bare en ledning falder ud, ser netværket pludselig helt anderledes ud – man mangler alle de forbindelser, der gik via det kraftværk eller den ledning. Derfor ser beregningerne pludselig fundamentalt anderledes ud. Det er ikke bare en konstant, der er blevet lidt større eller mindre, men nogen helt andre ligninger.

Se mere om netværk tidligere på bloggen. Der drejede det sig om sociale netværk, men man kan også tænke på det som kraftværker og ledninger. Man må så forestille sig, at ledningerne har forskellige kapacitet.

Kan man sørge for, at den samlede beslutning bliver optimal ved at fordele beslutningerne og informationerne rigtigt? Og kan man undgå, at systemet, som skal optimere profitten, vil give mørklægning af store områder.

Der findes tidsskrifter (IEEE Transactions on Power systems), som udelukkende beskæftiger sig med den slags problemer, så det vil være for omfattende at gå ind i detaljerne, men metoderne er ofte

Distribuerede beregninger, lineær programmering og Dantzig Wolfe:

At distribuere større beregninger er vanskeligt men væsentligt. Og med moderne parallelle processorer sker det hele tiden med større eller mindre held. Den algoritme, Charlie henviser til, Dantzig Wolfe, er fra 1960. George Dantzig, 1914-2005, var ophavsmand til simplex metoden i lineær programmering, som nok er et af de væsentligste bidrag til moderne beregningsmetoder – den er fra midt i 40’erne:
Et lineært programmeringsproblem er et problem af typen:
Find maksimum for funktionen f(x,y,z)=7x+3y+z under bibetingelserne x+y <=7, 3y<= 2 , x+z <= 7og både x,y og z positive. Der er altså et begrænset område, hvorfra vi må vælge x,y,z, og i et lineært programmeringsproblem er det afgrænset af planer, hvis vi har tre variable. Har vi kun to variable, er det afgrænset af linier.
Den slags problemer findes mange steder: En virksomhed har begrænsninger på leverancer, arbejdskraft i forskellige afdelinger, lånemuligheder etc. Eller som her: Der er begrænset kapacitet forskelige steder i nettet – i kraftværkerne eller i ledningsnettet.
Eftersom niveaumængderne for f(x,y,z) (de punkter hvor f(x,y,z)=2, er et eksempel på en niveaumængde) er planer, er der et hjørnepunkt, hvor funktionen er maksimal. (Der kan være flere løsninger, hvis funktionen er konstant på en af siderne/kanterne)
I simplexmetoden starter man i et hjørne. Så går man langs en kant til det nabohjørne, hvor funktionen f har højest værdi, og højere end der, hvor vi står. Og så fremdeles, indtil der ikke er sådan et hjørne. I så fald har vi nået et maksimum.

Det smarte ved metoden er, at man kan algoritmisere den, i.e., få en computer til at regne det ud, og den gør det effektivt i rigtig mange tilfælde. Man kan også finde worst cases, hvor det tager meget lang tid.

I Dantzig Wolfe metoden har man et meget stort problem af typen ovenfor. Man har rigtig mange variable, men der er visse dele, der er uafhængige af hinanden – begrænsninger der kun involverer få variable. Disse delproblemer foreslår nu løsninger til det oprindelige problem. For eksempel er de to bibetingelser x+y<= 7, y <= 2 uden z, så man kan optimere 7x+3y under de betingelser og finder x=7 og y=0 . Med det som input er det overordnede problem nu at maksimere f(7,0,z)=49+z under bibetingelsen 7+z<= 7, hvor man ser, at z=0. Det er mere indviklet – man skal bruge information om, hvor godt man udnytter sit råderum, i.e., om man har lighedstegn i ulighederne, eller man er tæt på, og det skal sammenlignes med den funktion, vi vil optimere- hvor meget den vokser i forskellige retninger.

I praksis bruges metoden også i virksomheder, hvor underafdelinger skal træffe beslutninger og hovedafdelingen skal koordinere dem.

For en dansk introduktion til lineær programmering og simplexmetoden kan man f.eks. se matnatverdensklasse

Optimeringsproblemer er selvsagt væsentlige i anvendelser. Fra gymnasiet kender man dem fra funktionsundersøgelser, hvor man differentierer for at finde kandidater til maksimum og minimum, og der er et utal af metoder. Ikke-lineære problemer (hvor afgrænsningerne ikke er (højere dimensionale) planer, og/eller niveaumængderne er mere indviklede, er meget vanskeligere end de lineære. Man kan så forsøge med at tilnærme problemet med et, der er lineært eller man kan bruge andre metoder a la den fra gymnasiet, hvor man skal differentiere, eller man kan bruge variationsregningsmetoder eller andet. Løsningsmetoden afhænger af, om man skal have en præcis løsning, et hurtigt svar eller en passende kombination.

OBS. Dette handler om afsnittet i aften, men lægges på nu, fordi jeg vil have påskeferie… Så læs det ikke, før du har set aftenens program!

Pari mutuel betting, som bruges i dette afsnit er et system, hvor dem, der vædder, deler puljen efter visse regler. Der er ikke forudbestemte odds – de sættes efter, hvor mange der spiller på hvilke heste. Det er det system, man bruger ved totalisatorspil i Danmark.

Eksempel:

Lad os sige, der er tre heste i et løb (der er normalt flere) og der væddes

10000 kr på Helhesten

15000 kr på Halhesten

20000 kr på Hulhesten

Ialt 45000 kr. Så tager totalisatoren afgifter og der betales skat. f.eks. 5000 kr. Det er normalt en vis procentdel af de samlede indsatser, og desuden er der indtægter fra afrunding – af oddsene til tiendedele og/eller af udbetalingerne.

Nu er der 40000 til fordeling til dem, hvis hest vinder.

Hvis Hulhesten vinder, får de indsatsen dobbelt igen. Men hvis derimod Helhesten vinder, er der 4 gange indsatsen igen.

I nogen løb er der også penge til dem, der har satset på nummer 2, efter et system, som er mere indviklet.

Man offentliggør oddsene løbende efterhånden som der sættes penge på de forskellige heste.

Man kan læse lidt om historien bag i dette interview fra 1939 med Totalisatorforstanderen. En totalisator var oprindelig en slags regnemaskine, der kunne regne oddsene ud udfra det, der var blevet væddet.

I Longshot afsnittet (Longshot er navnet på en hest her, men det er også betegnelsen for en hest, hvis chancer er vurderet til at være små, ), har den dræbte vundet 30 gange ved at spille på hvem der blev nummer to. Det påstås, at han har et system, der gør, at han vinder. Og det er først, da systemet ikke virker, han får mistanke om, at der er nogen, der fusker med løbene.

Jeg må sige, jeg tvivler stærkt på, at man alene med matematiske formler kan vinde 30 gange – og vel at mærke aldrig tabe. Hvis man holder øje med oddsene op til løbet og man ved noget om hestene, er der naturligvis mere eller mindre smarte måder at satse på, men at han skulle ramme rigtigt så mange gange lyder meget mystisk.

Men der er skam skrevet en del artikler om matematikken i at spille på hunde og heste. At spille på heste kan sammenlignes med at handle med futures og andre finansielle produkter, hvor prisen afhænger af, hvor mange, der vil købe, og hvor man risikerer at miste alle sine penge. Derfor kan man studere investeringsstrategier ved at studere, hvordan der “investeres” i hestevæddeløb. Man har også studeret “effektivitet af markedet”, som groft sagt betyder, at prisen/odds er “rigtige” i den forstand, at de afspejler den offentligt tilgængelige information. Altså at spillerne agerer fornuftigt i forhold til den tilgængelige information. Se f.eks. “An examination of Market efficiency in British racetrack betting”, P.E. Gabriel og J.Marsden, Journal of Political Economy, Vol 98 og “Market efficiency in racetrack betting”, P. Asch, B.G.Malkiel og R.E.Quandt, Journal of Business, vol 57.

I Gambling and Rationality, R.N. Rosett, Journal of Political Economy, Vol. 73, 1965, bruges pari mutuel betting som model for et marked. Økonomer bruger ofte en model, der siger, at forbrugere i gennemsnit træffer rationelle beslutninger baseret på tidligere erfaringer og på oplysninger om markedet (personligt tror jeg ikke helt den holder, når jeg står i Føtex og skal investere i mad til næste uge, og da slet ikke, når jeg står i en boghandel…).

Hvordan, spillerne opfører sig, afhænger af, om de er villige til at løbe en stor risiko for at tabe, hvor gevinsten, hvis de vinder, så er høj, eller de omvendt foretrækker lav risiko, lav gevinst strategi. Hans forudsætninger er, at en spiller, der investerer (og dermed risikerer) 1 krone vil 1) Foretrække den hest med størst odds, hvis sandsynligheden for, de vinder, er den samme 2) Foretrække den med størst sandsynlighed, hvis oddsene er ens 3) Foretrække en hest, hvis odds OG vindersandsynlighed er større end de andre.
Han forudsætter, at man sammensætter strategier, der dækker flere løb. Det viser sig, at der er færre, der satser på en “long shot”, altså en hest med lav vindersandsynlighed og høje odds, end man ville forvente, men at opførslen falder indenfor det, man kan forvente af rationelle beslutninger.

Omvendt kan man måske også bruge nogen af investeringsstrategierne fra de finansielle markeder til at lægge strategier for at spille på heste. Hvis man analyserer data fra tidligere afviklede løb: Hvad var odds ved åbning, hvordan varierede de, hvad var de forskellige hestes tidligere resultater – plejer helhesten at vinde over halhesten -, hvordan vurderede professionelle de enkelte heste (det er også afspejlet i odds ved åbning),…. – altså en lang stribe forklarende variable. Og hvad var så udfaldet: Hvilken hest vandt. Og hvilken model ville bedst forudsige alle disse forskellige løbs udfald, udfra de forklarende variable.

På Charlies tavler stod der noget med logit- funktionen. logit(p) er logaritmen til p/(1-p)
Det er den brøk, der optræder, når man laver logistisk regression. Se All’s Fair om logistisk regression. Mon ikke Charlie tænker på, hvordan man estimerer hestenes sandsynlighed for at vinde givet en stribe forklarende variable. I en logistisk model regner man med, at logit(p) er en lineær funktion af de forklarende variable, altså

[tex]logit(p)= b_0+ b_1 x_1+b_2 x_2 + cdots b_n x_n[/tex]

hvor x’erne er forklarende variable, og b’erne er koefficienter, man skal finde. Med en forklarende variabel skal man finde bedste rette linie. Med to er det bedste plan etc. Her kunne p være sandsynligheden for at en given hest vinder i et bestemt løb.

Den bedste model kan man så bruge til at forudsige senere løb og altså sætte penge på “den rigtige” hest. Specielt kan man lade være med at spille, hvis ikke det er ret klart, hvad man bør spille på. Man kan med andre ord lave bedre strategier.

Charlie snakkede også om arbitrage. En artikel “Arbitrage strategies for cross track betting on Major Horse tracks”, Journal of Business vol 63, D.B.Hausch og W.Ziemba ser på, hvordan man kan udnytte, at man kan spille forskellige steder på det samme løb. Puljen og dermed oddsene et sted kan være forskellige fra de andre steder, og man skal altså satse både efter, hvilken hest, man tror vinder, og hvor den giver gode odds. (Arbitrage går ud på at udnytte prisforskelle på samme produkt ved at købe og videresælge).

Her er en rapport om at vinde på hundevæddeløb. Strategien er at satse på de hunde, man ikke tror vinder, i sidste øjeblik. Og så stiger oddsene på den, der vinder, og som man også selv har en del penge på. Men det virker vel ikke, hvis man faktisk deler puljen som ovenfor. Så der er et eller andet mere indviklet bag, skulle man tro.

En, der kom galt afsted med formler for hestevæddeløb, var Ada Lovelace (1815-1852).

Verdens første datalog – eller programmør. Hun arbejdede sammen med Babbage, som lavede en “differensmaskine”, en forløber for computeren. Ada Lovelace skrev en artikel “Observations on Mr. Babbages analytical engine”, hvor hun beskrev, hvordan man, hvis engang sådan en “analytical engine” blev lavet, skulle oversætte kommandoer til tal – altså lave et programmeringssprog. Hun beskrev procedurer, løkker og mange andre dele af programmering. Men hun brugte også differensmaskinen til at lave udregninger, som hun skulle bruge til at spille på heste, og det gik grueligt galt. Hun tabte rigtig mange penge og måtte pantsætte familiens smykker.

Hun var en imponerende dame. Det var bestemt ikke hverdagskost, at kvinder beskæftigede sig med matematik og lignende. Læs mere om hende på St Andrews hvor man finder mange matematikerbiografier – på engelsk.

Der var et gennemgående tema idag, nemlig tilfældighed. Og hvordan det generelt misforstås. Charlie havde to billeder med prikker og spurgte sine studerende, hvilket der mon stammede fra regndråber, der falder tilfældigt. Man har tendens til at tro, at det er det, hvor punkterne er spredt nogenlunde jævnt ud og man ikke har nogen der ligger tæt på hinanden; men faktisk er det jo ret usandsynligt, at der ikke er nogen, der falder meget tæt på hinanden. Hvis altså det er tilfældigt, hvor regndråber falder i forhold til hinanden… Et eksempel på tilfældighed, som opfattes ikke tilfældigt, var shufflefunktionen i en MP3 afspiller, hvor mange tror, at deres MP3 foretrækker bestemte numre, siden de tit kommer først.

Et andet emne var trafikovervågningen i Los Angeles. Man har konstant overvågning af trafikken – se LARTMC, Los Angeles Regional Transportation Management Center. Der kan man f.eks. finde et kort over hele freewaysystemet og hvor galt det ser ud med trafikken på de enkelte vejstrækninger. I Danmark har vi TRIM der overvåger trafikken i Københavns området, og vi kan skam også se trafikken i Aalborg.
Er der nu matematik i det? Faktisk er der masser af matematik i trafikplanlægning. En model for trafik og for trafikregulering bruger typisk mange forskellige slags matematik og kombinerer det i et computerprogram , der kan simulere løsning til alle disse underliggende ligninger. Man kan meget sjældent løse den slags eksakt.
Opbygning og afvikling af køer er, som man kan se hver dag på de danske veje, en indviklet proces. Et synspunkt er, at man har en periode, hvor kapaciteten på vejen er for lille til de biler, der skal igennem. Det giver anledning til opbygning af en kø. Når så kapaciteten igen er høj nok – man har fjernet en havareret bil el. lign. – tager det tid at afvikle køen igen. Det kan f.eks. studeres som køteori og hører til i statistik eller operationsanalyse, og bruges mange steder. Design af “samlebånd”, hvor man har en vis kapacitet forskellige steder, design af computernetværk – modellering af trafk på internettet osv.

Desuden er det vigtigt med gode modeller, hvis man vil lave automatisering af trafikken eller af trafikreguleringen. En meget lille del af et intelligent reguleringssystem kan være regulering af trafikken ind på motorvejene. Hvis man kan se, at der er ved at opstå kø, bliver der rødt lys for tilkørslerne. Se f.eks. “Ramp metering” projektet her fra Lancaster. På Contram finder man et program, der modellerer trafik; det bruges bl.a. i Stockholm og mange andre steder i Sverige og Norge. I Danmark har Lyngby Tårbæk kommune en licens, men det må vel være en anden kommune nu… Man kan lægge sit eget vejnet ind og give data for, hvor mange, der vil køre fra A til B og hvornår. Det er selvfølgelig meget væsentligt at man kan lave den slags modellering, inden man bygger nye veje, broer og tunneler. Andre modeller medtager muligheden for at sende nogen med tog, på cykel osv. Desuden, kan man lave beregninger af omkostninger – miljømæssigt, transporttid,… Systemerne kan også bruges til at give bilisterne informationer, som så kan få dem til at ændre rute, et Advanced Traveller Information System.
Charlie siger, at man modellerer trafik på motorvejsnettet på samme måde som væskestrømning i rør, der er forbundet. Han omtaler partielle differentialligninger. Jeg har fundet en artikel, eller rettere noget undervisningsmateriale fra NYU om netop den model. Her kommer en forhåbentlig ikke alt for teknisk forklaring – for mere teknik, se linket ovenfor.
Vi ser på en lang vejstrækning – ikke et helt netværk med sideveje etc.

x måler, hvor langt henne ad vejen, vi er, t er tiden. lad Q(x,t) være antallet af biler, der passerer x-kilometermærket i tidsrummet mellem t og t+1 sekunder (eller noget lignende) (Q er flux i fysiksprog) Vi har et mål for tæthed, [tex]rho(x,t)[/tex] er antal biler mellem x og x+ 1 meter til tiden t. U(x,t) betegner gennemsnitshastigheden for de biler, der er mellem x og x+1 meter til tiden t.
Der er en sammenhæng, Q=[tex]rho[/tex]U
som følger af en betragtning om, at de biler, der passerer x med hastighed u i tidsintervallet t til t+1, er dem, der befinder sig tæt nok på til at nå der hen. Hvis alle biler har samme hastighed U m/s og tætheden er konstant [tex]rho[/tex] biler/m, må antallet af biler, der passerer x i løbet af et sekund, være [tex]rho[/tex]U.
Er tæthed og hastigheder ikke konstant, skal man overveje det lidt nøjere – det kan man læse via linket ovenfor.
Biler fordamper ikke, så der er en sammenhæng mellem ændringer i [tex]rho[/tex] og ændringer i Q. Det giver en partiel differentialligning (partiel, fordi vi ser på to variable, nemlig x og t).
Hvis man tilføjer, at gennemsnitshastigheden afhænger af tætheden – heldigvis kører vi ikke så hurtigt, når der er meget tæt trafik – får man en anden sammenhæng mellem [tex]rho[/tex] og Q via en funktion Q([tex]rho[/tex]), som er 0 for [tex]rho[/tex]=0, så vokser den til et maksimum, aftager og bliver igen 0, når [tex]rho[/tex] er så stor, at trafikken går i stå.
Man kan f.eks. sætte Q([tex]rho[/tex])=[tex]rho[/tex](1-[tex]rho[/tex])

Eftersom trafikken bevæger sig hurtigt ved lave tætheder, vil områder med lav tæthed “indhente” dem med højere tæthed og dermed skabe endnu højere tæthed foran sig og lavere tæthed bag sig, og der bygges op til meget høj tæthed. Man får altså områder med meget lav tæthed og områder med meget høj tæthed og tilsvarende hastigheder. Det kaldes chokbølger og vi kender det fra motorvejen, hvor man pludselig, efter at have kørt med god fart, indhenter et område med lav fart, uden man umiddelbart kan se, hvad problemet er.

Der er en fin illustration her fra Utrecht af trafikken i sådan en model.

I Danmark har vi også trafikmodeller. Se f.eks. DTUs Modelcenter.

Jeg spottede igen en del matematik i dette afsnit: Analyse af et trafikuheld brugte cykloidekurver til at beskrive positionen af trafikofferets hæl ved almindelig gang. Der var billeder med skjulte beskeder (matematikken var desværre ikke rigtig med, for man skulle bare kigge nøje på en forstørrelse – og vups havde kvindens hår skjulte bankkontonumre og navnet på to vidner, der var blevet myrdet… Vi har tidligere haft en mere avanceret brug af billeder, nemlig steganografi, oppe i bloggen, men det var ikke det, Charlie brugte idag.)
Charlie og Larry spillede med en rubiksagtig dims til sidst. den vil jeg gerne høre om, hvis nogen ved, hvad det var.

Der var også omtale af kombinatorisk optimering – det skulle Amita være særlig god til. Det skulle bruges til at finde næste mødested for muldvarpen og repræsentanten for den kinesiske efterretningstjeneste.

Den matematik, I får mere om idag, er det, der blev brugt til at søge billederne fra sikkerhedkameraerne igennem, nemlig Eigenfaces, eller egenansigter må det danske ord være.

Et digitalt billede består af pixelværdier. Lad os sige, der er 255 gråtoner, så vil hver pixel have en værdi mellem 0 og 255. Et billede med 100 x 100 pixels har altså 10000 tal mellem 0 og 255, en vektor med 10000 koordinater. Det giver i princippet [tex]256^10000[/tex], et tal med 24000 cifre, mulige billeder. Hvis vi på forhand ved, at billederne forestiller ansigter, så er der rigtig mange af mulighederne, som ikke vil optræde, og det kan man udnytte. Ideen er, at ansigterne, som jo i første omgang er i et 10000 dimensionalt rum (10000 koordinater pr. ansigt), faktisk ikke skal bruge så mange koordinater. Hvis vi ved, vi befinder os på jorden, kan vi give position ved længde og breddegrad, selvom vi jo i pricippet er i et (mindst) tre dimensionalt rum.

Hvis nu vi havde to koordinater til at beskrive billeder, ville ideen være, at de ligger cirka på en linje. Man finder altså bedste rette linje igennem. Derefter kan alle billeder beskrives ved en parameter, som giver, hvor langt ude af linjen, de ligger. I den teknik, jeg beskriver nedenfor, vil man
1) finde det midterste punkt (xM,yM), som middelværdien af x-koordinaterne, og middelværdien af y-koordinaterne.
2) Så beregner man for alle punkter differensen mellem deres koordinat og middelpunktet.
3) Man finder en vektor, der repræsenterer den retning, hvor afvigelsen fra middelpunktet er størst, svarende til en retningsvektor for den linje, de ligger på. Det er det, der nedenfor er egenvektoren med størst egenværdi.

Først samler man en masse billeder af ansigter sammen. Hvert billede giver en vektor med 10000 koordinater. Lad os sige, vi har 500.
Man udregner “middelfjæset” ved at lægge alle vektorerne sammen og dividere med antallet.
Nu repræsenteres hvert ansigt istedet ved afvigelsen fra middelfjæset – man trækker middelfjæsvektoren fra alle de andre. Og så bliver det lidt avanceret: Lad A være den 500 x 10000 matrix, der har afvigelses vektorerne som rækkevektorer. Matricen [tex]C=A^TA[/tex] kaldes kovariansmatricen. Den er nu 10000 x 10000 og den er symmetrisk. En vektor v, som opfylde [tex]Cv=lambda v[/tex] kaldes en egenvektor for C, og de billeder, der svarer til disse vektorer kaldes egenansigter/eigenfaces. Man vil nu beskrive andre ansigter som vægtede summer af egenansigterne. En høj værdi af [tex]lambda[/tex] (en høj egenværdi) svarer til, at billedet er væsentligt til karakterisation af andre ansigter (indgår med høj vægt), og det viser, sig, at man kan nøjes med meget få egenansigter – man udelader dem med meget lav [tex]lambda[/tex].
Lad os sige, der er 10 egenansigter med høje egenværdier. Så kan vi nu beskrive alle andre ansigter med 10 koordinater i stedet for 10000.

Når man skal sammenligne ansigter, som de gør i serien, bliver det nu et meget mere beregningsmæssigt overkommeligt problem.

Man skal desuden have metoder til at finde ansigter i større billeder, så man kan fokusere på netop ansigterne. Både eigenface teknologien og dette er beskrevet i M. Turk og A. Pentland “Eigenfaces for Recognition” Journal of Cognitive Neoscience Vol 3 no.1, 1991.

Der er masser af Google hits på eigenfaces. Her er et par eksempler på eigenfaces hentet fra Eigenface group på Rice university http://www.owlnet.rice.edu/~elec301/Projects99/faces/index.html

Som flittige læsere nok ved, har Texas Instruments sponseret undervisningsmateriale om Numb3rs under overskriften We all use Math every Day. Det findes på websiden af sammen navn. Det er mest rettet mod folkeskole niveau eller lidt efter, men man kan faktisk også finde mere avancerede forløb, som efter min mening kan bruges i gymnasieskolen. På Cornell har de lavet denne side med materialer til stort set alle de udsendelser, der har været – og lidt til, for de er jo længere med serien i USA.
God fornøjelse, hvis I lader jer inspirere. Jeg vil i øvrigt meget gerne høre om, hvis nogen bruger disse eller andre forløb om Numb3rs.

Onsdag d. 5. marts kl. 20.00 på DR2 kommer der faktisk en amerikansk film om matematikere, nemlig Good Will Hunting fra 1997. Så sæt harddiskoptageren til – eller køb filmen på DVD for næsten ingen penge.

En af mine tidligere kolleger er meget glad for Good Will Hunting, da filmen minder hende om hendes søn, der dels tog en Ph.D. i matematik på MIT, hvor filmen foregår, dels ligner hovedrolleindehaver Matt Damon en del af udseende.

I modsætning til Numb3rs handler Good Will Hunting strengt taget ikke om matematik – det matematiske miljø er mest en undskyldning for at fortælle historien om en irrationel rod 🙂

Men der er masser af referencer til matematik i filmen, og derfor er den interessant for mig.

Jeg er ikke begejstret for filmens fremstilling af matematik og matematikere. Der er faktuelle brølere i filmen – specielt er det graverende at se, at Will Hunting bliver berømt ved at løse en “svær opgave om et avanceret Fourier-system”. På billedet ovenfor ser man ham i færd med at lave sin løsning, og et blik på tavlen afslører (for nogle af os), at der faktisk er tale om et problem fra et helt andet område af matematik, nemlig grafteori. I en anden scene ser man to matematikere “high-five” hinanden efter at have løst et andet, tilsyneladende svært problem – der, så vidt jeg kan se, også er et temmelig elementært problem i grafteori.

Jeg er også mindre begejstret for filmens noget fordomsfulde fremstilling af et matematisk forskermiljø, der fremstår som koldt og uvenligt. På den anden side er denne film det eneste stykke populær-fiktion, jeg kender ud over Numb3rs, der har omtalt Fields-medaljen.

På http://www.ams.org/mathmedia/archive/hunting-review.html kan man se en amerikansk lærers anmeldelse af Good Will Hunting. I PDF-udgaven af anmeldelsen kan man endvidere læse en kommentar fra matematikeren Daniel Kleitman,fra MIT, der var matematisk rådgiver på filmen. Man kan bl.a. se, at det oprindelig var hensigten, at Will Hunting skulle bevise, at [tex]P=NP[/tex]. Det er næsten ærgerligt, at han ikke gjorde det.

Problemet, Will Hunting løser, er et problem fra algebraisk grafteori. Bert Jaegers fra universitetet i Twente i Nederlandene har lavet en lille webside om dette problem og hvordan det kan løses i Maple.

Filmens instruktør, Gus van Sant, er øvrigt ikke nogen dårlig filminstruktør. Alle hans film ser ud til at handle om unge mænd i krise, og efterfølgeren, Finding Forrester, er næsten en gentagelse af Good Will Hunting, blot om en ung mand, der er et stort talent som skønlitterær forfatter. Men det er en helt anden snak.

(Og i aften, mandag d. 3. marts kl. 21.00, viser TV2 Film A Beautiful Mind om John Nash. En set fra et matematisk synspunkt lige så speget film som Good Will Hunting.)

Idag har vi en gæsteskribent på Bloggen: Kenneth Niemann Rasmussen er netop begyndt som PhD-studerende her ved Institut for Matematiske Fag i Aalborg, og han skal lave noget om Curvelets, som Charlie brugte idag. Her er hans forklaring til udsendelsen idag:

Digital maleri analyse er et område som næsten måtte komme på banen i forbindelse med det stjåle maleri i afsnittet “Provenance”. Charlie nævner både wavelets og curvelets i hans forklaring af hvordan han er kommet frem til at maleriet er en forfalskning og desuden kan man også bemærke at der står wavelets vs curvelets på tavlen tidligere i afsnittet, da Charlie og hans far skændes i garagen. Wavelets er tidligere beskrevet på bloggen, men her er endnu et forsøg.
Wavelets går ud på at man kan beskrive en vilkårlig funktion ved hjælp af linear kombinationer af flytninger og skaleringer af en enkelt funktion og selve teknikken med flere skalerede niveauer illustreres bedst med et lille taleksempel.
Antag at vi har følgende talrække på 16 tal vi vil beskrive

9 9 9 9 9 9 10 10 11 12 14 15 16 16 17 17. (a)

Vi tager nu gennemsnittet af tallene to og to og nedenunder gemmer vi desuden differencen mellem de to tal, vi har taget gennemsnit af

9 9 9 10 11,5 14,5 16 17 (b)

0 0 0 0 1 1 0 0. (c)

Dermed har vi nu en ny talrække på 8 tal som vi kan gentage metoden på,

9 9,5 13 16,5 (d)

0 1 3 1, (e)

så vi ender med en talrække på 4 tal og for den sags skyld kunne vi fortsætte indtil vi kun har et tal. Det ses nu at vi ved hjælp af (c), (d) og (e) kan rekonstruere (a). De indeholder tilsammen, ligesom (a), 16 tal, så man har ikke umiddelbart vundet noget. I stedet kan man se på hvilken betydning talrækkerne (e) og (c) med differencer har. I (e) står der først et nul det vil sige at de første fire tal i (a) er det samme og ud fra (d) ses at tallet er 9. Der er ikke flere nuller i (e) og de første to tal i (c) kan vi ses bortfra da de allerede er dækket af (e) derefter er der et nul i (c) så de næste to tal i (a) er også det samme og ud fra (b) kan vi se at de også er 9. Ved at fortsætte på denne måde kan vi nøjes med 9 tal til at beskrive (a).

Curvelets er i princippet wavelets som er specielt beregnet til billeder. Forstået på den måde at wavelets opløser et billede ved hjælp af kvadratter som flyttes og skaleres og curvelets har en mere fleksibel opløsning ved hjælp af rektangler som ud over at flyttes og skaleres, desuden roteres. Dette er vigtig i forbindelse med billeder idet kanter på et billede har meget større betydning end flader. Udover at det gør curvelets bedre til at komprimere billeder gør det også at curvelets giver en opløsning som siger mere om billedet og dermed bedre kan bruges til at analysere en malers penselstrøg.

Et eksempel på wavelets anvendt til at analysere Van Gogh malerier kan ses her http://www.pacm.princeton.edu/~ingrid/VG_swirling_movie/. At der er rigtig mange ting som spiller ind i forbindelse med afgørelsen af om et maleri er en forfalskning kan desuden ses i denne artikel om Van Goghs “Garden of the Asylum” http://www.cs.unimaas.nl/~postma/dpa/HendriksVanTilborgh2001.pdf .

Og Lisbeth Tilføjer: Se også links fra det tidligere indslag om curvelets.

I afsnittet “To døtre” bruger Charlie og Amita de amerikanske Social Security Numre og den måde, de laves på, til at lede efter det bortadopterede barn. Det danske CPR-nummersystem er ikke lavet efter samme princip, men lad mig alligevel skrive lidt om det. CPR-numre består, som vi vel alle ved, af fødselsdato og år på formen ddmmåå og derefter følger 4 cifre.Der er bindinger på disse fire tal:

• Det sidste ciffer er lige for kvinder og ulige for mænd.
• Første ciffer kan være 0,1,2 eller 3 for personer født i 1900-1999
• Det kan være 4 for personer født i 1937-2036
• Det kan være 5, 6, 7, 8 eller 9 for personer født i 2000 – 2036 eller 1858 – 1899.

Disse bindinger sikrer, at 010299-5xxx er en person fra 1899 og ikke 1999 etc.Men det er ikke det hele. For at opdage fejlindtastninger, er der endnu et check:

• De ti cifre i et CPR nummer abcdef-ghij skal opfylde, at 4a+3b+2c+7d+6e+5f+4g+3h+2i+j er et tal, som 11 går op i. Ideen er, at man har et check på, om en række tal faktisk er et CPR-nummer. Det fanger fejlindtastninger, og det gør det også sværere at opfinde CPR-numre, med mindre man kender reglen…

Begrænsningerne ovenfor gør, at der er færre CPR-numre til rådighed på en given dato, end man umiddelbart skulle tro udfra de 9999 muligheder for de fire sidste cifre, men man er endnu ikke løbet tør. Der er 270 lige og 270 ulige numre til fødselsdatoer i perioden 1937-2036. Læs mere her hos CPR. Den mest benyttede fødselsdato i registeret er 1 januar 1950 (141 kvinder og 237 mænd). Det skyldes formentlig, at man har tildelt SKAT nogen fiktive numre, som de kan bruge – eller måske er det noget med personer, der indvandrer, og som ikke kender deres fødselsdato – lidt mystisk er det da.