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¡± ¨C 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.