Numb3rs

Jeres blogmeister/moster har påskeferie, så det bliver en kort udgave denne gang.
Der blev nævnt en hel del matematik: Marshall Penfield skulle undervise i spektralteori for ikke-hermiteske matricer. Der var brug for hans “Deep current set theory”. Kodeskriften på muren var en Vigenere kode. Spilteori om en duel med tre personer. Der var uden tvivl matematik i algoritmen til at klone mobiltelefoner. Der var masser af data mining.
Identifikation af mobiltelefoner
Når mobilopkald skal sendes og modtages, er der brug for, at telefonen “identificerer sig” på nettet. I de amerikanske system sker det ved, at hver telefon har et ESN-nummer (Electronic Security Number) og en MIN (Mobile Identification Number). I Europa – på GSM-nettet – er der et IMEI nummer (International Mobile Equipment Identification), som står i telefonen bag batteriet. Det bruges, som navnet indikerer, til at identificere telefonen (så man f.eks. kan finde stjålne telefoner) og ikke brugeren. Brugeren har et nummer knyttet til SIM-kortet, et IMSI (International Mobile Subscriber Identification). Disse tal har et checkciffer – et ekstra ciffer-, som dels sikrer, at man ikke kan opfinde nye numre selv – man skal kende checksumreglerne – og dels,at man kan finde fejl, hvis et ciffer er sendt med en fejl (en primitiv kodningsalgoritme – der er meget bedre fejlkorrigerende algoritmer, men ikke mere om det nu).

For IMEI er reglerne:

IMEI-nummeret har 15 cifre (det ene er checkciffer). De valideres ved Luhn algoritmen, som er som følger: Start helt fra højre i tallet – checkcifret er længst til højre. Tag hvert andet ciffer og gang det med 2. Læg cifrene i disse fordoblede tal sammen med de oprindelige cifre. Nu skal resultatet være deleligt med 10 – ende på 0.

Eksempel:

 Tallet er 49927398716 (ikke et IMEI, men det er princippet, det gælder)

Nu fordobles hvert andet: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18

Og vi lægger sammen: 6 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 4 = 70

Det ender på 0, så tallet er ok.

Man kan ikke bruge algoritmen til at rekonstruere et tal, man har lavet en enkelt fejl i, da man gør det samme ved hvert andet ciffer. Mere avancerede checksum algoritmer findes. Se tidligere på bloggen om fejlkorrigerende koder. Og om CPR-numre.

Det bruger ofte at regne “modulo et helt tal”. Altså at lave division med rest, og gemme resten. Det er rigtig smart. En gammel anvendelse er, at hvis 9 går op i summen af cifrene i et tal, så går 9 op i tallet selv. (Det er en god opgave at finde ud af, hvorfor det virker – og husk, det er i ti-talssystemet).

Man kan faktisk godt klone mobiltelefoner, som de gør i serien. Det er meget nemt at google sig til info om den slags, men det får I ikke opskrifter på her – der skal også bruges noget ekstra kode, så vidt jeg kan se. Så hold øje med mystiske opkald fra din telefon.

Jeg glemte Ada Lovelace dag i går. Det er dagen, hvor bloggere peger på et kvindeligt forbillede i de teknisk-naturvidenskabelige fag. Se Finding Ada. Jeg har rigtig mange forbilleder – heldigvis. For eksempel alle dem, jeg møder til European Women in Math konferencerne. Se videoer med interviews fra konferencen i Novi Sad i august 2009: Video 1
Video 2
Video 3
Der kan man bl.a. høre Ingrid Daubechies, som er kvinden bag wavelets. Et matematisk område, vi alle bruger dagligt, når f.eks. vi ser billeder på nettet, tager billeder med mobilen.

Ada Lovelace har jeg skrevet om tidligere på bloggen – det klipper jeg ind her:
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.
Hun døde som 36 årig af kræft og åreladning. Åreladning er i øvrigt et eksempel på en behandling, som slog rigtig mange patienter ihjel, før man fik lavet en ordentlig statistisk analyse af, om det hjalp eller ej. Det gjorde det mildt sagt ikke…

Glimrende afsnit – og en konspirationsteoretiker, som havde lidt ret…
Jeg så matematik i noget om videorekonstruktion og nogle pingviner. I massespektroskopi til analyse af kemiske rester i et fingeraftryk. Og Simpsons paradoks.
Desuden var der et eksempel på en af de berømte/berygtede “pranks”, som både Caltech og MIT er stolte af. Denne var omskrivning af Hollywood skiltet, ved at klistre sort plastik op strategisk, så der stod Calsci. Det har Caltech studerende gjort i 2003: Her er det beskrevet i Time. Med billede. Overskriften er “Nerd humor meets California Landmark.”

Forensics Videoreconstruction

Man kan gennemsøge mange overvågningsvideoer samtidig for at finde f.eks. den samme bil flere steder og dermed følge dens rute. Ideen bag er at kombinere computerkraft og mennesker: Compteren søger og kommer med forslag, som mennesket ved skærmen godkender efterhånden, hvorefter computeren ved, at den er på ret spor. Det går, ifølge artiklen her, meget hurtigere, end hvis computeren skal søge færdigt selv. Systemet hedder VideoFerret. Matematikken bag er bl.a. afstandsmål (metrikker). Brugeren kan bestemme, hvordan man måler afstanden mellem to billeder (udsnit af billeder er det nu), altså hvad det betyder, at to billeder ligner hinanden. Et billede af en bil og et andet af den samme bil set fra en lidt anden vinkel kan være langt fra hinanden, hvis man tæller, hvor mange pixels, der afviger, og det samme gælder, hvis man har ændret belysningen en smule. Derfor er der afstandsmål, der svarer til den mindste variation af billede 1, man kan nøjes med for at få billede 2. Et eksempel er Earth Mover’s Distance, som er lidt mere indviklet…

Simpsons paradoks.
Basalt set skyldes Simpsons paradoks følgende brøkregningsresultat:
Der findes tal, a,b,c,d,A,B,C,D, så
* a/b < A/B
* c/d < C/D
og
* (a+c)/(b+d)>(A+C)/(B+D)
Eksempelvis:
* 1/5 < 2/8
* 6/8 < 4/5
* 7/13 > 6/13.
Det ser jo ret uskyldigt ud, men det har overraskende konsekvenser i sandsynlighedsteori/statistik. Her kommer en historie med disse brøker 🙂
En medicinsk behandling testes og man ser på bedring med den nye og den gamle behandling.
Ud af 13 mænd bliver 5 behandlet med den nye og 1 får det bedre. 8 får den gamle behandling og 2 får det bedre.
Ud af 13 kvinder bliver 8 behandlet med den nye og 6 får det bedre. 5 bliver behandlet med den gamle og 4 får det bedre.

Blandt mænd er der sandsynlighed 1/5 for at få det bedre med den nye behandlig, 2/8 med den gamle.

Blandt kvinder er sandsynligheden 6/8 for at få det bedre med den nye behandling. 4/5 med den gamle.
Som i brøkregningen ovenfor ses, at sandsynligheden samlet for at få det bedre med den nye behandlig er 7/13 og med den gamle er den 6/13. Så glemmer man køn, skal der behandles med den nye, men mænd for sig og kvinder for sig skal bruge den gamle ??? Det ser jo mystisk ud. Kigger vi nærmere på tallene, er det klart, at mænd i det hele taget har ringere chance for at få det bedre (3/13) end kvinder (10/13). Så en mulig forklaring kan være, at mændene i denne test er mere syge end kvinderne, og det ser også ud til, at man ikke giver så mange af dem den nye behandlig- måske fordi de er mere syge. Altså at der er en eller flere underliggende variable, vi ikke har med. Og at det er dem, der forklarer forskellene.

Betingede sandsynligheder:
Brøkerne ovenfor er betingede sandsynligheder: Sandsynligheder for at få det bedre med ny/gammel behandling givet køn. Med formler, hvor A er “få det bedre”, B er “ny behandling”, C er “er kvinde”. og ~B er “ikke B”, altså gammel behandling. ~C er “ikke kvinde”, altså mand 🙂
P(A/B) > P(A/~B) (sandsynligheden for at få det bedre med ny behandling er større end med den gamle)

P(A/B & C) < P(A/~B & C) (sandsynligheden for at få det bedre givet “ny behandling OG kvinde” er mindre end med “gammel behandling OG kvinde”)

P(A/B & ~C) < P(~B & ~C). (sandsynligheden for at få det bedre givet “ny behandling OG mand” er mindre end med “gammel behandling OG mand”)

Faktisk kan man, hvis datamængden er stor nok (eller der er tale om kontinuerte variable), finde et C (en opdeling af data i to andre grupper – C og ikke C), så uligheden P(A/B) > P(A/~B) vendes om, når man betinger med C og med “ikke C” som ovenfor.

Et eksempel fra det virkelige liv
Her er data om dødsstraf i drabssager i Florida i perioden 1973-1978. Opdelt efter den dømtes race:

Dømt Dødsstraf Anden straf.
Sort    59       2547
Hvid    72       2185

Der er altså 3,2 % af de hvide mordere, der får dødsstraf og 2,3 % af de sorte.
Hvis nu vi medtager offerets race, giver det et noget andet billede:

Offer Morder Dødsstraf Anden straf
Sort    Sort         11     2309
Sort    Hvid        0         111
Hvid    Sort        48       238
Hvid    Hvid       72       2074

Der er sandsynlighed 0,45% for at få dødsstraf, hvis offeret var sort. Og 5,2% hvis offeret var hvid. (Man bør naturligvis regne efter, om disse tal er signifikante –  chi^2 test eller lignende). Man skal altså tænke sig om, før man drager konklusioner. Bemærk, at ingen hvide har fået dødsstraf for at slå en sort ihjel. De første tal var altså misvisende, fordi sorte mest slås ihjel af andre sorte og tilsvarende for hvide ofre – morderen er oftest hvid.

Det var lidt småt med matematikken her, men noget var der da. Bremselængde for tog, der vejer 12000 tons i stedet for 10000 tons. Søgealgoritmer og lederudvælgelse for swarmbots’ene. Progressive Collapse Analysis – af risikoen for, om togvognen ville kollapse. Der blev brugt varmekameraer, og det er der selvfølgelig matematik i.
Bremselængde
Et tog, der kører med hastighed v har en kinetisk energi på 1/2 mv^2, hvor m er massen (vægten). lad os sige, toget kører lige ud, så der ikke er en ændring i højden og dermed den potentielle energi (et tog kan standses ved at køre stejlt opad). Hvis decellerationen (acceleration med negativt fortegn) er -a, så kan er der følgende sammenhæng:
m*a*S=1/2 mv^2
hvor S er standselængden. Og nu ser det ud til, at vægten kan forkorte ud, men så har vi glemt, at decellerationen afhænger af massen.

Jeg fandt noget om togbremser på engelsk her . Der er faktisk også en særlig side om North American Freight Train brakes. Tog bremser med trykluft, som fordeler bremsekraft ud til ale vogne. Bremseklodser presses mod hjulene og friktion mellem klodser og hjul og mellem hjul og skinner indgår i nedbremsningen. Når man bremser et tog, skal der bremses jævnt på alle vogne/hjul. Hvis men bremser lokomoivet, vil vognene “indhente det” og køre af sporet. Trykluft sendes ned gennem toget til alle vogne, og ifølge denne artikel er gnidningskoefficienten mellem stål og stål den samme som mellem gummi og is – altså bremser et tog som en bil på is… Et tog vil normalt ikke skride på skinnerne – det ruller til stop, og det gør, som jeg forstår det, at vægten har stor indflydelse, da den maksimale bremsekraft (ma) er nogenlunde konstant. Derfor er bremselængden proportional med vægten. Hmmm… det er ikke århundredets forklaring; skriv endelig, hvis du har bedre info om tog og bremselængde.

Swarm bots
Charlies små robotter, som kunne samarbejde om at kortlægge den væltede togvogn, er et eksempel på et distribueret system og swarm bots var et projekt under EPFL i Lausanne, Schweiz.
En swarm bot, er en sværm af mindre og forholdsvis ukomplicerede robotter, som kommunikerer med hinanden – ofte kun lokalt, altså med de nærmeste – og dermed kan udføre større opgaver i en slags samarbejde. Ideerne kommer bl.a. fra studiet af myrekolonier.
Charlie demonstrerede, hvordan hans bots valgte en leder. Det er et gammelt basalt problem i distribueret beregning. Pointen er, at når der først er valgt en leder, har man mulighed for at lade den styre de andre og dermed få udført nogle jobs.
Der er mange ledervalgs algoritmer. De afhænger af, hvordan kommunikationen mellem de enkelte “agenter” (bots’ene) er. Hvor mange kommunikerer direkte med hinanden – kort sagt, hvad er det for et netværk, de danner. Med bots’ene kan netværket ændre sig, når de flytter sig rundt, og det komplicerer jo sagen.
En beskrivelse er, at man ser på netværket (en graf med knuder og kanter mellem dem; her går kanterne måske kun den ene vej svarende til at den ene bot kan sende til den anden, men ikke omvendt ) Så gælder det om at lave et udspændende træ, altså en knude er roden, der går grene ud fra den til visse knuder og grene til andre knuder fra disse knuder, men ikke tilbage igen, så altid op i træet. Lederen er roden. (Søg på spanning tree, hvis du vil se mere). det er der algoritmer til.
I distribueret beregning har man visse grundproblemer, som andre mere komplicerede problemer reduceres til. Så ved man, hvad betingelserne er for at løse de komplicerede problemer, når man har styr på de grundlæggende. Ledervalg er et af disse. Det er en ret almindelig tankegang: Visse problemer er ækvivalente – og det kan betyde, at det ene kan løses hvis og kun hvis det andet kan. At man har en effektiv algoritme for det ene hvis og kun hvis man har en for det andet. Etc.
Forskning i multi-agent systemer er et stort emne med bidrag fra både matematik, datalogi og ingeniørividenskab. Og der er masser af uløste opgaver.

Titlen er et citat fra Apocalypse Now og i øvrigt navnet på et Aalborgensisk band 🙂

Der var en del matematik: Analyse af havstrømme og bølger, (ud)foldning (deconvolution algorithms), strategier for sten, saks, papir (??), spectral sensing analysis (til at identificere marihuana planter), hyper spectral images.

Analyse af havstrømme og bølger
Vandbølger og strømme kan naturligvis modelleres matematisk. Hvor god en model, det er, afhænger af, hvor mange faktorer, man tager i betragtning, og omvendt bliver det numerisk uhåndterligt, hvis man tager for mange faktorer med – som altid i matematisk modellering.
En simpel (!) model er “shallow water wave equations”, som er koblede partielle differentialligninger. Det ser grafisk smukt ud: (jeg har bøvl med at sætte billeder ind, så det rager for langt ned, men der er mere tekst nedenfor 🙂

Modellen beskriver for hvert punkt (x,y,z) og tidspunkt t samspillet mellem

strømning i x-retningen u(x,y,z) og i y-retningen, v(x,y,z)

bundhøjden, b(x,y,z), bølgehøjden, h(x,y,z).

Nu skulle man jo tro, at man bare kunne løse ligningerne, men det kan man typisk ikke. Man må simplificere – linearisering og diskretisering er kodeordene. Man regner ikke på alle punkter, men paa et “net” – svarende til, at man f.eks. kun regner på x,y,z- koordinater …,-2, -3/2, -1, -1/2, 0, 1/2, 1, 3/2, 2,…. Så er løsningerne naturligvis ikke helt rigtige mere, og man må overveje, hvor galt det går. Og om man skal have et finere net – altså koordinater 1/4 også.
Numerisk analyse er den gren af matematikken, hvor man beskæftiger sig med, hvordan man håndterer den slags – både udfra hvor meget computerkraft, man har til rådighed og hvor store datamængder, man kan afstemme løsningerne efter. Charlie talte om en mere praktisk tilgang, og de var ude på Channel Islands og smide bøjer i havet. Det gør man systematisk:

Her er en oversigt over bøjer ud for Californien. Disse bøjer sender hele tiden information til “National data buoy center” . Her er f.eks. informationen fra Station 46025 (Santa Monica Basin) idag klokken 10.50:
Station 46025
NDBC
Location: 33.749N 119.053W
Conditions as of:
Thu, 11 Mar 2010 10:50:00 UTC
Winds: N (350°) at 9.7 kt gusting to 11.7 kt
Significant Wave Height: 3.9 ft
Dominant Wave Period: 6 sec
Mean Wave Direction: WNW (300°)
Atmospheric Pressure: 30.08 in and rising
Air Temperature: 54.3 F
Water Temperature: 56.1 F

man kan finde data tilbage fra 1982 fra denne bøje – imponerende.

I Danmark bruger man flere forskellige havmodeller. Man regner hver dag – fire gange om dagen på bølgemodellen DMI-WAM og giver prognoser for havbølger. I modellen og beregningerne indgår data fra andre modeller for f.eks. tryk og temperatur i luften – det er en enorm numerisk beregning. Det er en model for åbent hav og det er lidt mindre komliceret end kystnære bølger. Følger man linket ovenfor vil man bl.a se, at tidsskridtene er 20 sekunder og at der koordineres med modeller for Nordsøen-Østersøen, Nordatlante, Middelhavet og Rødehavet.
Hyperspektrale billeder
Charlie brugte luftfotos til at finde marihuana planter, men det var ikke almindelige fotos. De var hyperspektrale – man tager flere billeder af det samme, hvor hvert billede repræsenterer forskellige “farver” eller rettere dele af det elektromagnetiske bånd – altså også ikke-synlige dele.
En model for, hvad man ser på billedet er som følger (lineær model)
Hver pixel er et billede af det materiale, der findes indenfor denne pixel. Materialer reflekterer sollys forskelligt. Hvis x=(x1,…,xn) er mængden af materialerne 1,…n, vil man for denne pixel i energibånd nummer 1 se den samlede refleksion i dette bånd: p1=a11*x1+a12*x2+…+a1n*xn hvor koefficienterne a1k siger, hvor meget materiale nummer k reflekterer til bånd nummer 1. Tilsvarende for bånd nummer i
pi=ai1*x1+ai2*x2+…+ain*xn.
Nu kan man så (muligvis) regne tilbage og finde mængden af materiale – altså x1,…,xn ved at løse et antal lineære ligninger med n ubekendte. Antal ligninger = antal bånd. Mere indviklet bliver det, hvis terrænet ikke er fladt, så der måske reflekteres til nabopixels også. Så er det ikke lineært mere.
Her er en hyperspektral terning (fra Wikipedia om Hyperspectral imaging)

Jeg holdt foredrag i UNF Aalborg i går. Som altid herligt at komme hos UNF. Der er mange andre fine arrangementer – se UNF siderne. De holder til i både København, Århus, Odense og Aalborg med mindre afdelinger på Bornholm og i Herning. Og de holder foruden foredragsrækkerne diverse Sommerskoler – også om matematik.
Mine slides fra foredraget i går ligger her som pdf-fil.

Jeg faldt over When will I use Math siden – via den tyske matematiker forening DMV.
Der er f.eks. en fin illustration af nye periodiske “planetbaner”. Hos DMV har de haft en konkurrence om matematik tegneserier – man kan se vinderne her.
I Der Spiegel tør man godt skrive om matematik. Se her – der er mange artikler. Det er på tysk, men det havde I jo nok regnet ud.

Numb3rs holder juleferie på Kanal 5. I mellemtiden kan man skrive under på protesten mod, at sæson 6 er beskåret i USA.
http://www.petitiononline.com/numb3rs/petition.html
Og så er der jo masser af gode matematiksider på nettet.
For eksempel How Round is your circle (tak for tippet, Olav). Den knytter sig egentlig til en bog med samme titel, men man kan godt kigge på siden uden at have bogen. Titlen refererer til det, matematikerne kalder Reuleaux trekanter. Figurer, som har konstant bredde – og nej, det betyder ikke, det er en cirkel.
(Fra Wikipedia)
Ruller man den hen over et bord med en bog ovenpå, vil det være en fin glat bevægelse – bogen holder samme højde. Men den har ikke en konstant rotationsakse, så den er skidt som hjul på en bil…
Afstanden fra et hjørne til modsatte buestykke er konstant – det er altså en cirkelbue.
Reuleaux trekanten er den kurve med en given konstant bredde B, der har mindst areal. (Andre sådanne kurver er naturligvis cirklen med radius B/2 og Reuleaux-figurer med flere hjørner, men de har større areal).
Man kan bruge Reuleaux trekantformede bore bits til at bore (næsten ) kvadratiske huller – se her.

God juleferie.

Mvh
Lisbeth.

Charlie brugte blodstænksanalyse (blood spatter trigonometry) til at analysere blodet i kassen. Der var “reverse engineering”, design recovery og Occam’s razor.
Og så gæsteoptrådte Penn fra “Penn and Teller” i en rolle som sig selv. Benn and Teller er et TV-program, hvor forskellige “magiske” tricks pilles fra hinanden. og ikke bare tryllekunster, også tankelæsning og diverse okkulte fænomener.

Reverse engineering
Groft sagt går det ud på at tage en dims og finde ud af, hvordan den virker…
Amita nævner, at det bruges af dataloger – hun kalder det design recovery – og her er udgangspunktet, at man har et computerprogram – en lang stribe 0’er og 1’er. Kan man finde ud af, hvordan det virker.
Her er en bog om nogle teknikker, der bruges.

Målet er at kunne modificere dette software eller eventuelt reproducere det. For gamle store programmer bygget op over mange år – “legacy systems” – har man ofte mistet overblikket og har ikke nogen beskrivelse af, hvad hver enkelt programstump gør. Der kan en gang reverse engineering være nødvendig, hvis man f.eks. skal udbygge programmet, eller som ved årtusindskiftet skulle gennemskue, hvor man kunne få problemer med, at man ikke havde skrevet år 1985, men kun 85, eller især, hvis man har år 01 til at betyde både 1901 og 2001.

Man kan have ædle eller knap så ædle motiver – i bogen, jeg linker til ovenfor, står: “make modifications and hacks to get software that we do not have source code for to do things that it was not originally intended to do. ”
Matematikken kan være i analyse af data: Man giver sit software input og studerer output. Det gøres systematisk, og man kan f.eks. forsøge at opdage, hvornår der sker noget dramatisk med output. Kendskab til division med rest, som vi så det i sidste uge, kan være nyttigt, når man skal gennemskue kodning. Eller kryptering.

Reverse engineering i Computer Aided Design.
Ifølge Wikipedia er det reverse engineering, når man udfra kendte punkter på et geometrisk objekt (en kugleflade, en donut, en plan,…) genskaber det geometriske objekt.
Det er der meget matematik i: Punkterne skal forbindes, men ikke allesammen. Hvilke punkter skal forbindes og skal trekanten mellem punkterne a,b,c fyldes ud?
Det afhænger af, hvor tæt på hinanden, de ligger. Men man risikerer at “fylde hullet i donutten ud”.
lad os sige, vi regner med, det er en (over)flade.
En ide er, at man først vælger et tal, lad os sige 2, og forbinder alle punkter, hvis afstand til hinanden er mindre end 2. Man udfylder trekanter, hvis de tre punkter kan være i en cirkel med en fastsat radius osv. Så vælger man en ny startværdi. Jo større, jo flere punkter bliver forbundet. Er den for lille, bliver ingen punkter forbundet. Man må så vurdere, hvad der er “de rigtige” forbindelseslinjer og trekanter – hvor groft et net, man har.

Blodstænksanalyse
Analyse af blodstænk havde vi på bloggen i afsnittet Hot Shot
Blodet splatte ud i en ellipseform, og man analyserer længde og bredde for at se, hvor blodet er kommet fra – smuk rumgeometri, som man kan se i det tidligere indlæg. Hvis man gerne vil se blodige billeder med rigtige eksempler, er der en del, hvis man Googler bloodstain pattern analysis, men dem vil jeg ikke sætte ind her.
IABPA, International Association of Bloodstain Pattern Analysis, holder konferencer og udsender et nyhedsbrev.

Occams Razor
Princippet om, at man skal vælge en simpel model, hvis det er muligt. Det bruger Charlie til at gennemskue et princip i “akvariet”.

Så er Charlie tilbage på banen! Jeg så flere matematikholdige emner, men det var ikke oplagt for mig, hvad de blev brugt til. Fejlkorrigerende koder blev omtalt i starten. Geografiske netværk, “Supply Chain analysis” (for at finde noget fælles for de steder, der blev begået røverier imod.) Stregkoder og gendannelse af dem, hvis de er beskadiget (“Data recovery software”). Fraktal analyse (af lejligheden, hvor “the scan man” boede). I får noget om fejlkorrigerende koder – og lige en bemækning om “the scan man”. Det var vel tydeligt for enhver, at man havde lånt fra Dustin Hoffmans RainMan i filmen af samme navn. Jeg synes nu ikke, det, som Charlie antydede, vrimler med den slags folk i matematikmiljøerne, altså folk med “savant” egenskaber – at kunne tælle papirclips (eller tændstikker som i Rainman) er ikke nogen decideret fordel for en matematiker. Men andre karakteristika fra autismespektret findes i mere eller mindre udtalt grad. Og Asperger syndrom påstår man jo, at Einstein og Bill Gates (og en hel del skuespillere og komponister i øvrigt) har eller havde. Jo, det er dejligt at være i et rummeligt miljø!

Fejlkorrigerende koder
Jeg låner her fra min kollega Olav Geils glimrende noter – se flere eksempler på Olavs “populariseringshjemmeside”

Hvis man vil sende en besked og risikerer, der sker fejl undervejs, vil man gerne kunne finde den oprindelige besked igen.
Hvis det drejer sig om sædvanlig tekst, er vi allesammen gode til at gennemskue, at L3sb3th nok skal oversættes tilbage til Lisbeth. Vi ved, hvilke ord der er mulige/tilladt, og når vi ser et, der ikke er, leder vi efter noget, der ligner. Men hvad nu, hvis det er et signal – noget lyd eller måske en sum penge. Så giver alle beløb mening, men måske er 123 blevet til 193 undervejs.
I kodningsteori tilføjer man noget information, som gør, at der “bliver længere mellem” de mulige/tilladte strenge af tal, bogstaver eller hvordan man nu transmitterer.

Eksempel: Vi vil sende 123. Vi dobler beskeden op – sender det samme to gange: 123123. hvis modtageren ser 193123, ved de, der er noget galt med andet ciffer, men ikke, hvilket der er rigtigt – de kan ikke korrigere. Man må være lidt smartere.
her kommer et eksempel fra Olavs noter:
Binære Hammingkoder:
Vi vil sende beskeden (0,1,1,0) og koder den ved at tilføje tre binære tal e,f,g – vi vil sende (0,1,1,0,e,f,g). En besked, (a,b,c,d,e,f,g) skal opfylde, at a+b+c+e er lige, a+b+d+f er lige, og a+c+d+g er lige (giver 0 til rest ved division med 2…)
Vi skal have 0+1+1+e lige, så e=0.
0+1+0+f lige, så f=1
0+1+0+g lige, så g=1.
Vi sender altså (0,1,1,0,0,1,1)

Hvad hjælper det nu?
Lad os sige, du modtager (0,1,1,1,0,1,1). Det er klart, at der er noget galt, for a+b+d+f=3 – ulige og a+c+d+g=3, ulige (men a+b+c+e=2, lige). Hvad er der nu galt? Man går nu ud fra, at der kun er sket en enkelt fejl. Ved at skifte d fra 1 til 0 passer checksummerne og vi har en lovlig besked – et lovligt kodeord.

Denne kode er lineær: Tager man to lovlige kodeord, (a,b,c,d,e,f,g) og (A,B,C,D,E,F,G) og danner ordet (a+A,b+B,c+C,d+D,e+E,f+F,g+G), får man et nyt lovligt kodeord. Afstanden mellem to ord er antallet af pladser, hvor de er forskellige: Afstanden mellem de to lovlige ord (0,0,0,0,0,0,0) og (0,1,1,0,0,1,1) ovenfor er 4. Man kan vise, at afstanden mellem to lovlige ord er mindst 3. Denne minimumsafstand siger, hvor mange fejl, koden kan håndtere, i.e., korrigere ordet tilbage til det rigtige. Med en minimumsafstand på d, kan man korrigere (d-1)/2 fejl (rundet nedad, hvis d er lige). Her altså 1 fejl.
En god kode tilføjer få bogstaver og har stor minimumsafstand, og det er natuligvis en kunst at lave sådanne koder. Læs mere i Olavs noter. Følg linket ovenfor og se “kort foredrag, pdf-fil” eller “langt foredrag, pdf-fil”. Noget af matematikken i det er, at man i stedet for at se på rester ved division med 2 (lige/ulige), ser på rester ved division med andre tal. Den slags regning, modulo et helt tal, kender nogen maaske fra kryptering, men kodningsteori er en lige så aktiv og anvendt branche.