DM829: Effektive graf-algoritmer (5 ECTS)

STADS: 15011401

Niveau
Kandidatkursus

Undervisningsperiode

Udbydes efter behov.

Ansvarlige undervisere
Email: cwn@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 3. kvartal

Indgangskrav:
Ingen

Faglige forudsætninger:
Grundlæggende kendskab til algoritmer og sandsynlighedsregning som f.eks. opnået gennem DM507 Algoritmer og datastrukturer, DM508 Algoritmer og kompleksitet og DM528 Kombinatorik, sandsynlighed og randomiserede algoritmer.

Kursusintroduktion
Formålet med kurset er at opnå indgående kendskab til graf-algoritmer med lav tidskompleksitet og/eller lavt pladsforbrug samt kompakte grafrepræsentationer, der relaterer til minimering af længde, med primært fokus på korteste veje. Klassiske algoritmer som Dijkstra er for langsomme i mange sammenhænge som f.eks. GPS og kommunikationsnetværk, og disse algoritmer kræver, at hele grafen er gemt i hukommelsen. I praksis er det ofte tilstrækkeligt med approksimative korteste vej- afstande, og her muliggør nye preprocesseringsteknikker og grafrepræsentationer besvarelse af afstandsforespørgsler langt hurtigere og med mindre pladsforbrug.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

• beskrive effektive algoritmer og graf-repræsentationer for de grafproblemer, der behandles i kurset,
• identificere de overordnede metoder og algoritmiske ideer fra kurset,
• anvende metoder og algoritmiske ideer fra kurset i nye problemsammenhænge, der i natur ligner de i kurset behandlede emner.

Emneoversigt
Korteste veje, afstands-orakler, spannere, multiplikative og additive approksimationer af korteste vej-afstande, minimalt udspændende træer.

Litteratur

Meddeles ved kursets start.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
a) Kursets evaluering består af obligatoriske opgaver, en mundtlig fremlæggelse af en artikel og en projektopgave. Bedømmes samlet, bestået/ikke bestået, intern censur ved underviser. (15011402)

Reeksamen følger reglerne vedtaget i studienævnet.
Reeksamen kan have en anden form end den ordinære eksamen.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger: 24 timer
Eksaminatorietimer/opgaveregning: 14 timer
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. feb 2012.