MM810: Grafteori I (5 ECTS)

STADS: 13004201

Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus

Undervisningsperiode
Kurset udbydes efter behov.

Ansvarlige undervisere
Email: qin@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen.

Faglige forudsætninger:
Studerende, der følger kurset, forventes at have kendskab til Lineær Algebra, stoffet fra MM510, Ringe og Talteori, og MM512, Grupper og Vektorrum eller tilsvarende.

Formål
Kurset har til formål at sætte den studerende i stand til at gengive definitioner og resultater fra grafteori inden for kursets pensum, hvilket er vigtigt i forhold til identificere matematiske strukturer fra grafteori i konkrete eksempler.

Kurset bygger oven på den viden, der er erhvervet i kurserne MM510 og MM515, og giver et fagligt grundlag for at studere videregående emner med henblik på et speciale i diskret matematik.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

• Give kompetencer til at planlægge og udføre videnskabelige projekter på højt fagligt niveau herunder styre arbejds- og udviklingssituationer, der er komplekse, uforudsigelige og forudsætter nye løsningsmodeller
• Give færdigheder til at sætte sig ind i, analysere, modellere og løse givne problemstillinger på et højt abstraktionsniveau ud fra logiske og strukturerede ræsonnementer
• Give viden om avancerede modeller og metoder i grafteori

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

• gengive definitioner og resultater fra grafteori inden for kursets pensum
• anvende teorien til at løse konkrete opgaver med udgangspunkt i kursets pensum
• argumentere for skridtene i opgaveløsningen
• gennemføre stringente og fuldstændige beviser for påstande med udgangspunkt i kursets pensum (tælleargumenter, induktion, indirekte beviser, algoritmiske beviser)
• forklare sammenhænge mellem begreber og resultater i grafteori
• benytte matematisk terminologi og symboler fra mængdelære, funktionsteori og logik
• identificere matematiske strukturer inden for kursets pensum i konkrete eksempler

Indhold
Kurset indeholder følgende faglige hovedområder: Grafer, delgrafer, sammenhængende grafer, trær, ikke separable grafer, træ-søge-algoritmer, kompleksitet af algoritmer, sammenhæng, uafhængige mængder og kliker, pardannelse, Hamilton kredse.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Rapport og mundtlig eksamen. Rapporten evalueres som del af den mundtlige eksamen. Tilladte hjælpemidler: Bøger og noter er tilladt i forberedelsen inden eksamen.Karakter efter 7-trinsskalaen og ekstern censur.

Reeksamen ifølge reglerne vedtaget i studienævnet.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 22 timer
Træningsfase: 20 timer, heraf:
 - Eksaminatorie: 20 timer

Aktiviteter i studiefasen

Undervisningsform
Aktiviteter i studiefasen: At studere kursusmaterialet og forberede de ugentlige øvelser, individuelt eller gennem gruppearbejde.

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.

Denne kursusbeskrivelse var gyldig fra 1. september 2016 til 31. august 2018.