MM810: Grafteori I

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for MM810 udbydes efter følgende plan, når kurset udbydes: Efterår (kursusstart september): ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni eller august).

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

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Efterår

Udprøvninger

Rapport og mundtlig eksamen

EKA

N310001102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset

ECTS-point

Uddybende information

Rapporten evalueres som del af den mundtlige eksamen.

Vejledende antal undervisningstimer

42 timer per semester

Undervisningsform

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
For at sætte de studerende i stand til at nå læringsmålene for kurset tilrettelægges undervisningen således, at der er 42 forelæsningstimer, holdtimer etc. på et semester.

Disse undervisningsaktiviteter udmønter sig i en anslået vejledende fordeling af arbejdsindsatsen hos en gennemsnitsstuderende på følgende måde:

Introfase (forelæsning) - Antal timer: 22
Træningsfase: Antal timer: 20

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

Ansvarlig underviser

Navn	E-mail	Institut
Jing Qin	qin@imada.sdu.dk	Data Science

Skemaoplysninger

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (matematik)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode