MM856: Grafteori
Kommentar
Indgangskrav
MM856 samlæses med MM855, og man kan derfor kun tilmelde sig et af disse kurser.
Ellers Ingen yderligere indgangskrav.
Faglige forudsætninger
Studerende, der følger kurset, forventes at have basal kendskab til grafteori og diskret matematik svarende til stofffet i MM541 (Kombinatorisk Matematik).
Formål
- Give kompetencer til at planlægge og udføre komplicerede videnskabelige projekter på et højt fagligt niveau. Herunder at kunne løse komplekse problemer ved hjælp af grafteori.
- 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.
- forklare sammenhænge mellem begreber og resultater i grafteori
- benytte grafteori algoritmer til at løse komplekse problemer.
Indhold
Kurset indeholder følgende faglige hovedområder: Grafer, træer, afstande, pardannelser i generelle grafer, veje, kredse, farvning i grafer, Hamilton kredse, planar grafer, random grafer, NP-hårdhed og digrafer.
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Udprøvninger
Obligatoriske opgaver og skriftlig eksamen
EKA
Censur
Bedømmelse
Identifikation
Sprog
Varighed
Hjælpemidler
Tilladt(Dog uden internet), nærmere beskrivelse af eksamensreglerne vil blive offentliggjort under Course Information på kursets side i BlackBoard’.
ECTS-point
Uddybende information
Eksamen består af obligatoriske opgaver og en skriftlig eksamen, hvor karakteren baseres på en helhedsvurdering, hvor de obligatoriske opgaver vægter 20 % og den skriftlige eksamen vægter 80 %.
Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen.
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
- Introfase (forelæsninger, spørgetimer) 52 timer.
- Træningsfase (eksaminatorier) 38 timer.
- Total = 90 timer.
Aktiviteter i studiefasen: At studere kursusmaterialet og forberede de ugentlige øvelser, individuelt eller gennem gruppearbejde.