Utskrift från Malmö högskolas webbplats www.mah.se

Effektiva algoritmer och approximationsheuristiker för kombinatoriska och geometriska problem

Kontaktperson: Bengt J. Nilsson
Ansvarig: Andrzej Lingas / Datavetenskapliga institutionen Lunds Universitet
Medarbetare: Mia Persson
Samarbetspartner: Lunds Universitet
Finansiär: Vetenskapsrådet
Tidsram: 2012-01-01 -- 2014-12-31
Fakultet/institution: Fakulteten för teknik och samhälle, Institutionen för datavetenskap
Ämne: Naturvetenskap

Studiet av kombinatoriska och geometriska problem innehåller två aspekter av problemlösning. Dels att förstå problemets inneboende egenskaper --- ofta genom att formulera det matematiskt --- och dels att faktiskt lösa det, dvs. att konstruera resurssnåla metoder som numera normalt körs på dator. Ett tidigt exempel är ´´radixsorteringsalgoritmen´´ som under förra seklet användes i speciella hålkortssorteringsmaskiner, alltså långt före förekomsten av elektroniska datorer. Även Euklides algoritm för att beräkna största gemensamma delare till två tal uppfyller alla krav som ställs på en lösning till ett kombinatoriskt problem. Även om beräkningsproblem har fascinerat människan alltsedan de gamla grekerna så är det först under detta sekel som beräkningsteori fått sitt stora genombrott, främst av två orsaker. Den första är att datorer blivit tillgängliga inom alla delar av samhället. Den andra orsaken är de extremt stora datamängder som utnyttjas i all vetenskaplig forskning. Ett exempel på att beräkningsmässiga problem dyker upp inom andra vetenskaper är analys av DNA-sekvenser inom biologi. Det är endast genom utvecklingen av moderna algoritmiska metoder som sådan analys är möjlig, och det är långt viktigare än de tekniska resurser som står till buds. En fråga som är grundstenen i modern beräkningsteori är vad kännetecknar en resurssnål beräkning. Detta är en av de mest grundläggande vetenskapliga frågor som någonsin ställts, både från ett teknologiskt och ett filosofiskt perspektiv. Ämnet studeras vid alla institutioner för datavetenskap i hela världen och forskningsbasen är internationellt sett mycket bred, med forskare i alla världsdelar. Vår projektgrupp har en utomordentligt stark ställning inom området resurssnåla beräkningar, mer specifikt inom design och analys av effektiva algoritmer, approximationsheuristiker och datastrukturer för kombinatoriska och geometriska problem. Inom några områden såsom approximationsalgoritmer för geometriska nätverk och beräkningsgeometri är gruppen världsledande. Vi planerar att fortsätta vår framgångsrika forskning om konstruktion och analys av effektiva algoritmer, approximationsheuristiker och datastrukturer för grundläggande kombinatoriska och geometriska problem inom fyra sammankopplade områden: grafalgoritmer, kommunikationsnätverk, beräkningsgeometri och beräkningsbiologi. Ett exempel på ett problem som vi arbetar med är, givet två strukturer, att avgöra om den ena ingår som en del av den andra. Det finns olika varianter av detta problem, och de är kända under namn som delgrafisomorfi, delgrafhomeomorfi och kombinatorisk mönstermatchning. Detta problem förekommer inom kemi, biologi, igenkänning av mönster i texter eller i bilder osv. Ett annat exempel på ett problem vi studerar är beräkning av bästa resvägen. Målet är att bygga en databas som inte tar alltför stort datorminne, så att om en användare anger två platser A och B på en karta skall algoritmen mycket snabbt kunna svara på frågan t.ex. hur lång är kortaste resvägen fån A till B, och sedan ange fler detaljer om resan, enligt användarens önskemål. I stället för korstaste resvägen kan man bygga in andra mått i databasen på vad är bästa resvägen, genom att t.ex. ta hänsyn till resans kostnad och tidsåtgång.

Senast uppdaterad av Magnus Jando