De siste ukene har jeg fulgt et onlinekurs i grunnleggende IT-greier, nemlig algoritmer og datastrukturer. Jeg har lært en hel masse kule ting som jeg irriterer meg over at jeg ikke har hørt om tidligere (skjønt, kanskje jeg ikke var klar til å sette pris på disse tingene før nå?), men først, onlinekurs? srsly?

Jeg merker at jeg har en iboende skepsis mot onlinekurs, uten at jeg vet helt hvorfor, men jeg er i ferd med å bryte den ned. Og det hjelper naturligvis at kurset har videoforelesninger av en professor fra Stanford, som attpåtil har publisert mye forskning på grunnleggende algoritmer og datastrukturer. I tillegg er enkle programmeringsoppgaver relativt godt egnet for nettundervisning siden det er en smal sak å sette opp en server der man kan laste opp hjemmeleksene og få dem automatisk kontrollert. Dette er jo faktisk en ting som benyttes i den ordinære undervisningen ved data på NTNU, skjønt neppe som eneste vurderingsform.

Selv har jeg ikke levert noen av oppgavene, siden jeg har vært litt opptatt med andre ting, men jeg har fulgt forelesningene. De kommer i hendige stykker på rundt ti til tjue minutter, og er utmerket tilbehør til frokosten, for eksempel. Det at jeg ikke har levert øvingene betyr forøvrig at jeg ikke får et fint diplom når jeg er ferdig, men det er egentlig greit nok. Skepsisen min er fortsatt sterk nok til at jeg ikke føler behovet for å ha et diplom fra et nettkurs.

Uansett, algoritmer og datastrukturer. Det viser seg at IT-folk har tenkt ut utrolig mye smart. Sortering, for eksempel. Sortering er jo et klassisk problem som det sikkert har vært skrevet flere dusin hyllemeter faglitteratur om, og som jeg inntil relativt nylig ikke har tenkt så mye på, utover å registrere at python har en innebygget sorteringsfunksjon som du stort sett kan få til å gjøre hva du vil ved å definere __lt__() på en passende måte når du lager egne klasser.

Jeg ble imidlertid nødt til å dykke litt dypere i materien her i sommer, da jeg hadde behov for å sortere noen tall i fortran, og fortran har naturligvis ikke noe slikt innebygget. Jeg er naturligvis ikke den første som trenger å sortere noe i fortran, men jeg bestemte meg for å ta det som en utfordring, og skrev min egen mergesort ved hjelp av rekursive funksjoner. Hvorfor akkurat mergesort? Hovedsaklig fordi det var den det tok meg kortest tid å forstå når jeg slo opp sorteringsalgoritmer på wikipedia. Nå vet jeg forøvrig at mergesort faktisk var et godt valg, ettersom minne ikke var viktig for meg.

Men jo. Etterhvert gikk kurset forbi ting som bare er av akademisk interesse for IT-folk, og begynte å snakke om ting som er av akademisk interesse for fysikere. For eksempel den frekke datastrukturen «heap», og dens anvendelser innen prioritetskøer, og igjen disses anvendelser innen hendelsesdrevne simuleringer.

Poenget med denne artikkelen, som jeg snart skal komme til, er hendelsesdrevne simuleringer, og ikke datastrukturer, men jeg vil likevel kjapt nevne at en prioritetskø er en ting som lar deg legge elementer i kø, og som så alltid gir tilbake det minste (i en eller annen forstand) elementet. Naivt skulle man kanskje tro at dette ville kreve voldsomt mye regning hver gang. For eksempel, hvis man har N elementer, og skal legge et nytt element på plass i køen, ville man kanskje regne med å måtte flytte N/2 elementer for å frigjøre en plass på riktig sted. Ved hjelp av en heap greier man imidlertid å gjøre dette på bare log(N) operasjoner. Meget frekt, og jeg anbefaler å se nærmere på disse tingene om man er interessert.

Men jo. Poenget var altså at jeg så en forelesning om hendelsesdrevne simuleringer. Eksempelet, som jeg antar er et klassisk eksempel, var harde kuler som kolliderer. For å gjøre en tidsdrevet simulering av et slikt system ville man typisk simulere et lite tidssteg ved å flytte alle kulene litt, sjekke om noen av dem kolliderer, regne ut ny posisjon og hastighet for de aktuelle kulene, og gjenta prosessen. Problemet med dette er for det første at du må ha veldig god tidsoppløsning for å være sånn passe sikker på å få med deg alle hendelser, og at det å sjekke etter kollisjoner krever N² operasjoner.

I en hendelsesdrevet simulering, derimot, regner man ut når første kollisjon kommer til å skje, flytter systemet så langt frem i tid, regner ut nye hastigheter for de kolliderende partiklene, regner ut når neste kollisjon kommer til å skje, etc. Og det er her denne prioritetskøen kommer inn i bildet. Det er nemlig den som har i oppgave å holde på alle mulige fremtidige kollisjoner, og alltid levere ut den neste. På denne måten kan man gjøre en slik simulering på N log(N) operasjoner pr steg, i stedet for N², og det er en ganske vesentlig forskjell.

Så, for å komme til det egentlige poenget. Jeg gikk på fredagskollokviet i forrige uke, og der var det en fyr som snakket om nettopp hendelsesdrevne simuleringer av harde kuler som kolliderer. Det var et ganske kult foredrag, og ikke minst, en kul diskusjon etterpå, der det kom frem et par ting som hadde vært interessant å undersøke. Inspirert av onlineforelesningen jeg hadde sett tenkte jeg at dette virker som noe man kan programmere på en helg, og dermed gikk jeg hjem på fredag og begynte å hacke.

Det tok ganske nøyaktig to dager å få til et system som kan simulere et par tusen partikler innen rimelig tid, og jeg har fortsatt et stykke igjen, ettersom han som holdt foredraget på fredag simulerte 250000 partikler. Jeg tror ikke jeg har tid til å se så mye mer på det med det første, men det var i allefall et kult problem som produserer kule videoer, og det er jo greit å ha et forhold til hva hendelsesdrevne simuleringer går ut på.