Matematik leder till bättre algoritmer

Avhandlingen består av tre delar. I den första delen behandlas ett problem med överföring av data. Då man överför en mängd symboler händer det att några symboler på vägen blir fel på grund av brus.

För att det ursprungliga meddelandet ska kunna återskapas kodar man det med en så kallad felrättande kod, vilken bland annat ökar antalet symboler som överförs. En sådan kod är konstruerad så att när meddelandet avkodas framstår det ursprungliga meddelandet i korrekt skick, även om begränsade fel uppstått vid överföringen av meddelandet. Desto större fel man vill skydda sig mot, desto fler extra symboler krävs. Det finns teoretiska gränser för hur många extra symboler som krävs för att nå en viss felrättningskapacitet. Avhandlingens första del är avgränsad till fasmodulering, en speciell typ av dataöverföring. En tidigare presenterad övre gräns för prestanda för koder vid symmetrisk fasmodulering och normalfördelat (eller Gaussiskt) brus har generaliserats för att fungera även vid asymmetrisk fasmodulering, samt vid generaliserat Gaussiskt brus.

I den andra delen behandlas ett problem med kluster av datorer. Då många datorer gemensamt ska köra ett program, det vill säga en mängd processer, finns risk att någon dator kraschar. Under vissa förutsättningar kan processer som ursprungligen allokerats till en dator som kraschat flyttas till andra datorer i klustret. Man vill gärna att programmet körs snabbt i de fall då ingen dator kraschar, men man vill också att programmet körs snabbt i de fall då högst en dator kraschar (att flera datorer ska krascha betraktas som mycket osannolikt). Om man vill allokera processerna så att man kan garantera viss prestanda vid en datorkrasch, hur bra prestanda kan man då uppnå när ingen dator kraschar?

I den tredje delen behandlas ett problem med att avbilda GPS-mätningar till en färdväg på en karta. GPS-mätningar är sällan helt korrekta, de slår ofta fel på ett par meter och ibland på flera tiotal meter. För navigationshjälp vill man kunna avgöra den mest sannolika positionen, givet en serie mätningar. För en mängd andra tillämpningar, så som trafikanalys och elektroniska tullsystem vill man kunna avgöra vilken väg man mest sannolikt färdats, givet en serie mätningar. Det finns redan åtskilliga algoritmer för att lösa problemen, men ingen algoritm ger perfekta lösningar. I avhandlingen presenteras, utöver teoretiska diskussioner kring så kallade sannolikhetsbaserade algoritmer, en metod för att utnyttja att mätfelen vid konsekutiva mätningar beror på varandra. Det har inte gjorts förr, och kan leda till bättre precision hos kommande algoritmer.

INFORMATION & KONTAKT
Disputationen är öppen för allmänheten.
Dag: Torsdag 29 november
Tid: Kl 13:00
Plats: C216, C-huset, BTH, Campus Gräsvik, Karlskrona

För mer information, kontakta Efraim Laksman på telefon 0455- 38 56 84 eller via e-post: efraim.laksman@bth.se Se även www.bth.se