<p>Den här magisteruppsatsen presenterar en metod för points-to analys som är avsedd för aktiviteter inom mjukvaruutveckling. Applikationer för mjukvaruutveckling som använder resultatet från en points-to analys är oftast intresserad av en liten del av det program som analyseras. För att göra metoden mer effektiv presenteras också ett antal approximationer som kommer att reducera storleken på analysen. En implementation av metoden och approximationerna gjordes för att kunna utvärdera metoden och approximationerna. Resultatet visar att approximationerna som gjordes på analysen inte påverkar precisionen avsevärt. Resultatet visar också att tiden för att göra en analys kortas ner mycket genom att göra approximationer på analysen.</p> / <p>This master’s thesis is presenting an approach to points-to analysis that is targeted to software engineering activities. Software engineering applications that use the result of points-to analysis are often only interested of a small amount of the classes in an application. In order to make the analysis more efficient, a couple of approximations are presented that will reduce the size of the analysis scope. An implementation was constructed to evaluate the approach and the approximations. The experimental result shows that the approximations made on the analysis are in the most cases not affecting the precision at all for the relevant parts of the application being analyzed. The experimental results also show that the analysis time is shortened considerable by using approximations.</p>

Den här magisteruppsatsen presenterar en metod för points-to analys som är avsedd för aktiviteter inom mjukvaruutveckling. Applikationer för mjukvaruutveckling som använder resultatet från en points-to analys är oftast intresserad av en liten del av det program som analyseras. För att göra metoden mer effektiv presenteras också ett antal approximationer som kommer att reducera storleken på analysen. En implementation av metoden och approximationerna gjordes för att kunna utvärdera metoden och approximationerna. Resultatet visar att approximationerna som gjordes på analysen inte påverkar precisionen avsevärt. Resultatet visar också att tiden för att göra en analys kortas ner mycket genom att göra approximationer på analysen. / This master’s thesis is presenting an approach to points-to analysis that is targeted to software engineering activities. Software engineering applications that use the result of points-to analysis are often only interested of a small amount of the classes in an application. In order to make the analysis more efficient, a couple of approximations are presented that will reduce the size of the analysis scope. An implementation was constructed to evaluate the approach and the approximations. The experimental result shows that the approximations made on the analysis are in the most cases not affecting the precision at all for the relevant parts of the application being analyzed. The experimental results also show that the analysis time is shortened considerable by using approximations.

Rörelseigenkänning (motion capture) med optiska mätsystem används i flera applikationer för översättning av positioner i det fysiska rummet till det virtuella. I det här arbetet approximeras den snittvolym som motsvarar vad två eller fler kameror ser i ett sådant optiskt mätsystem. Volymen approximeras med en octree-datastruktur som lagrar information om kvalitet för individuella delar i volymen. Datastrukturens associerade kvalitetsmått används i kombination med ett vinkelmått i ett senare delsteg för att optimera fram en kamerauppsättning med en genetisk algoritm. Volymapproximeringens konstruktion implementerades i C++ och den genetiska algoritmen använder specialiserad överkorsning och initiering. Genomet är utformat så att problemdomänen begränsas till det aktuella problemet. Resultatet av optimeringen visar att vidareutveckling är nödvändig och lösningarna som optimerats fram var inte tillräckliga. Potentiella framtida arbeten innefattar fortsatt utveckling av nuvarande kvalitetsmått, samt vidare jämförande studier av volymapproximeringen.

Garg and Könemann developed a framework for computing multi-commodity maximum flow in a graph, later called a multiplicative weight update framework. Madry used this framework and exchanged Dijkstra’s algorithm to a dynamic graph algorithm for approximating the shortest paths through the graph. With this approachhe developed the fastest algorithm to date for calculating the multi-commodity maximum flow, with a running time of Õ(mnϵ2). This project have implemented the algorithm and compared it with a slightly modified version of the former fastest algorithm by Fleischer with a time complexity of Õ(m2ϵ2). The results show that Madry’s algorithms is slower than Fleischer’s algorithm in practice for graph with less than 100 million edges. This project also computed the space needed for the dynamic algorithms used in Madry’s algorithm and can show a resulting space complexity of O(n(n+m)log2n), compared to the space complexity of Fleischer’s algorithm of O(n). For a graph with 100 million edges, 50 million Gb of space is needed to use Madry’s algorithm, which is more than our test computers had. We can therefore conclude that Madry’s algorithm is not usable in real life today, both in terms of memory usage and time consumption. / Garg and Könemann utvecklade ett framework för att beräkna multi-commodity maximum flöde i en graf sedan kallat ett multiplicative weight update framework. Madry använde detta framework och bytte ut Dijkstra’s algoritm mot en dynamisk grafalgoritm för att kunna approximera kortaste vägen i grafen. Med detta angeppssätt utvecklade han den idag snabbaste algoritmen för beräkning av multicommodity maximum flöde med en tids komplexitet på Õ(mnϵ2). Det här projektet har implementerat hans algoritm och jämfört den med den tidigare snabbaste algoritmen skapad av Fleischer med en tidskomplexitet på Õ(m2ϵ2). Resultatet visar att Madrys algoritm är långsammare än Fleischers algoritm i praktiken för grafer med färre än 100 miljoner kanter. Detta projekt beräknade också minnesåtgången för de dynamiska algoritmerna i Madrys algorithm och kan visa en resulterade minneskomplexitet på O(n(n+m)log2n), jämfört med Fleischers algoritm på O(n). För en graf med 100 miljoner kanter så behövs 50 miljoner Gb av minne för att kunna använda Madrys algoritm, vilket var mer än våra testdatorer hade. Vi kan därför konstatera att Madrys algoritm inte är användbar i praktiken idag, både när det kommer till minnesanvändning och till tidsåtgång.