12. april: Beregningsorientert matematikk og anvendelser

Kort om foredraget:

De første datamaskinene ble bygget for å gjøre matematiske beregninger i forbindelse med naturvitenskaplig forskning, og i dag er svært mye naturvitenskap utenkelig uten datamaskinberegninger. Men slike beregninger utgjør også mye av grunnlaget for teknologien vi møter hver dag som kompresjon av lyd og bilder, rangering av web-sider, GPS, medisinske avbildningsteknikker osv. I denne forelesningen skal vi se på noen slike eksempler, matematikken som ligger bak og hvordan de matematiske problemene løses ved hjelp av beregninger.

Oppsummering skrevet av Morten Dæhlen:

Om det å regne på hjertet

 Alle vet at hjertet er en muskel som pumper blod rundt i kroppen. Et hjerteslag starter med en elektrisk puls som beveger seg ut i hjerte  og får hjertet til å “slå”. Hjertet trekker seg sammen noe som kan beskrives som en mekanisk prosess som i sin tur presser blodet med friskt oksygen til kroppens funksjoner.

For å kunne regne på dette etableres et matematisk modell av disse prosessene i hjertet. Med utgangspunkt i den matematiske modellen lager man en såkalt numerisk modell eller sagt på en annen måte en modell som en datamaskin kan regne på. Deretter implementeres dette som programvare som må kjøres på kraftige parallelle datamaskiner. Grunnen til at man må kjøre dette på kraftige datamaskiner er at problemet er stort, dvs. at store ligningssystemer må løses for å få de svarene man ønsker. Til slutt kan resultatet presenteres, f.eks. gjennom grafisk visualisering og animasjoner.  Når dette er gjort kan også resultatene fra beregningene (simuleringene) sammmenlignes med målinger på fysiske hjerter for å se hvor god beregninger er. Disse sammenligningene kan benyttes til å forbedre den matematiske modellen som i sin tur bidrar til justeringer av den den numeriske modellen og programvaren som gjennomfører beregningene. Slik kan man fortsette til man er fornøyd med resultatet.

Denne forskningen brukes til å forstå bedre hvordan hjertet fungerer, bl.a.  ved å studere hvordan hjertet oppfører seg dersom man påfører modellen en skade (eller sagt på “hjertespråket” – et infarkt). Dette vil i sin tur kunne brukes til å gi bedre behandling. En annen anvendelse av denne teknologien er til behandling av hjerteflimmer. Mer om dette finner dere i en utmerket artikkel i Apollon.

Korteste vei for en handelsreisende!

“Travelling Salesman Problem” er et enkelt, men likevel uløst problem!

Fra skolematematikken lærte vi at dersom vi hadde en kurve (funksjon) kunne vi derivere denne og sette den deriverte lik “null”. Da fikk vi en ligning vi kunne løse og løsningen på denne ligningen var en optimal løsning. En løsning er optimal dersom den i en viss forstand er den beste av alle mulige løsninger. For “The Traveling Salsman Problem” (TSP) er det enkelt å beskrive hva som er den optimale løsning. En handlesreisende skal ut på veien og besøke N byer, og spørsmålet er; I hvilken rekkefølge skal han besøke disse N byene for at reisen skal bli kortest mulig? Utfordringen er at dette er mye vanskeligere enn det høres ut som!

Dersom man går frem “rett etter nesa” kan man sette opp alle mulige kombinasjoner av reiser, regne ut avstanden, og velge den reisen som er kortest. Problemet er imidlertid at når N vokser så vokser antall mulig reiseveier eksponensielt. Antall mulige turer er (N-1)!/2, f.eks. med N=5 byer får vi  12 forskjellige turer mens vi med N=12 byer får nesten 20 millioner valgmuligheter. Du kan jo selv regne ut hvor mange mulige reiseveier du må sjekke dersom du skal besøke N=20 byer?

Skal man løse dette, må man ved hjelp av matematiske metoder og programvare finne ut hvordan man avgrenser problemet, eller sagt på en annen måte hvordan man kan tenke seg å forkaste løsninger som man tidlig finner at ikke kan være en optimal løsning eller del av en optimal løsning. Ingen har i dag funnet en generell metode som løser dette problemet og det er utlyst en pris på 1 millioner dollar for den eller de som finner denne metoden. Verdensrekorden er på 89500!

3D i dataspillenes verden

Viktige elementer ved utvikling av dataspill er hvordan øke kvaliteten på bildene som vises, hvordan introdusere fysiske elementer som kollisjon, elastistitet, osv., og gjøre dette slik at oppførselen i den 3-dimensjonale verden blitt mest mulig realistisk. En nøkkel er bruk av grafikk-kort (GPU) og utnyttelse av kraften i disse spesialbygde enhetene gjennom parallell programmering.

Først og fremst må det bygges geometriske modeller av det vi ser. Disse er som regel bygget opp av trekanter der posisjonen til hver trekant er bestemt av tre punkter i rommet. En samling trekanter som henger sammen kalles en triangulering og alle objektene består av et antall trekanter som til sammen danner flater som vises på skjermen. Videre knyttes farger, materialegenskaper og teksturer (digitale bilder) til hver trekant. I tillegg til dette bruk lys for å skape liv. Et viktig poeng siden bildene skal vises i “sann-tid” er at man bruker så få trekanter som mulig, og Martin viste bl.a. frem en teknikk der man ved hjelp av grafikk-kortet kunne beregne glatte siluetter i “sann-tid” over en relativt grov triangulering. Uten denne metoden ville bildene på skjermen sett kantene ut.

Et annet viktig trekk med utviklingen, primært for å få større realisme inn i spillene, er å introdusere elastisitet i objektene. Dette betyr at objektene skal endre form når de kolliderer, slik f.eks en fotball gjør når foten treffer ballen eller ballen treffer en vegg. Dette betyr at det må knyttes fysiske egenskaper til trekantene som beskriver objektene, og trekantene må endre form som en funksjon av den kraften som påvirker objektet. Martin viste frem en film der elastiske kaniner bestående av ca. 2000 trekanter slippes ned på et plan. De endrer seg og spretter opp og ruller rundt. I tillegg til elastisiteten må systemet også finne ut når og hvor objektene kolliderer.

For å få alt dette til å gå fort nok, dvs kunne tegne mange bilder per sekund på en dataskjerm, er det viktig å utnytte kraften i grafikk-kortet som består av mange beregningskjerner som arbeider sammen (i parallell). Realistisk oppførsel i et dataspill krever god forståelse for den fysikken som skal modelleres, robuste matematiske modeller som beskriver den verden som skal vises frem, og sist men ikke minst avansert programvare som utnytter datamaskinens regnekraft.