DM892: Approksimationsalgoritmer

Studerende, der følger kurset, forventes at kunne

• designe og analysere algoritmer

Stoffet fra DM507/DM578/DS814 forudsættes kendt.
Det er en fordel at kende stoffet fra DM553 Kompleksitet og beregnelighed og at have basalt kendskab til lineær programmering.

Mange opgaver som planlægning og skedulering kan formuleres som diskrete optimeringsproblemer, men ofte kan de ikke løses optimalt inden for en rimelig tid. Her spiller approksimations-algoritmer en væsentlig rolle.

En approksimationsalgoritme er en optimerings-algoritme med en garanteret køretid og løsningskvalitet. F.eks. gennemgås i kurset en simpel og hurtig algoritme, som garanterer at finde en TSP-rute, som er højst en halv gang længere end den optimale.

Vi vil også se på online-algoritmer. Her er begrænsningen ikke, at der ikke findes polynomielle algoritmer til at løse problemet optimalt, men derimod begrænset viden om problem-instansen. Når man kører et program, ved man f.eks. ikke altid, hvilke hukommelses-sider, det vil være en fordel at bevare i den hurtige, men forholdsvis lille, del af hukommelsen.  

Kurset bygger oven på den viden, der er erhvervet i kurset DM507/DM578/DS804 Algoritmer og datastrukturer. Referencer til begreber fra DM553 Kompleksitet og beregnelighed eller DM545/DM871 Lineær og heltalsprogrammering kan også finde sted i kursusforløbet.

Kurset giver et fagligt grundlag for at lave et speciale indenfor approksimations- og/eller online-algoritmer.
I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

• Give færdigheder i at beskrive, analysere og løse avancerede datalogiske problemstillinger ved hjælp af de lærte modeller
• Give færdigheder i at analysere fordele og ulemper ved forskellige algoritmer, specielt med hensyn til ressourceforbrug
• Give færdigheder i at udvikle nye varianter af de lærte metoder, hvor det konkrete problem kræver det
• Kunne forstå og på et videnskabeligt grundlag reflektere over principper og grundlæggende egenskaber omkring approksimations- og online-algoritmer
• Give ekspertviden om approksimations- og online-algoritmer
• Give viden om et udvalg af specialiserede modeller og metoder udviklet inden for approksimations- og online-algoritmer fra den internationale forskningsfront

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evne til at:            

• Beskrive problemerne behandlet i kurset kort og præcist.
• Beskrive algoritmerne gennemgået i kurset, både konkrete algoritmer og algoritme-paradigmer.
• Analysere kendte og nye algoritmer, især mht approksimations-faktor men også mht køretid og pladsforbrug.
• Vurdere hvilke metoder, der er hensigtsmæssige at anvende i sammenhængen.
• Tilpasse kendte algoritmer til specialtilfælde af kendte problemer og til nye problemer.
• Designe og analysere nye algoritmer til at løse problemer, som i natur minder om problemer fra kurset.

Kurset indeholder følgende faglige hovedområder: 

• Approksimations-faktor og competitive ratio.
• Køretid og pladsforbrug
• Kombinatoriske algoritmer, LP-baserede algoritmer, grådige algoritmer
• Deterministiske og randomiserede algoritmer
• Konkrete optimerings-problemer så som TSP, scheduling, knapsack, bin packing og caching.

• Introfase (forelæsning): 36 timer 
• Træningsfase 36 timer

Aktiviteter i studiefasen:

• Løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne
• Selvstudium af visse emner fra lærebogen
• Selvstændig opsamling på intro og træningsfasen