MM856: Grafteori
Det Naturvidenskabelige Studienævn
Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N310057102
Censur: Intern prøve, to eller flere bedømmere
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Kandidat
STADS ID (UVA): N310057101
ECTS-point: 10
Godkendelsesdato: 13-05-2020
Varighed: 1 semester
Version: Godkendt - aktiv
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
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 kurset MM541, 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 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
Efterår og januar
Udprøvninger
Portfolio og tests
EKA
N310057102
Censur
Intern prøve, to eller flere bedømmere
Bedømmelse
7-trinsskala
Identifikation
Fulde navn og SDU brugernavn
Sprog
Følger, som udgangspunkt, undervisningssprog
Varighed
3 timer
Hjælpemidler
Alle almindelige hjælpemidler er tilladte fx lærebøger, egne noter, computerprogrammer som ikke benytter internettet m.v.
Internet er ikke tilladt. Du må dog gå ind på kursets hjemmeside i itslearning i forbindelse med åbning af system "DE – Digital Eksamen". Noter fra kurset, som du ønsker at anvende som hjælpemidler, skal downloades til din computer senest dagen før eksamenen. Under eksamenen er det ikke sikkert at alt kursusmateriale er tilgængeligt for dig.
ECTS-point
10
Uddybende information
Portfolio eksamen bestående af: to dele:
- Obligatoriske opgaver - vægter 20 %
- Skriftlig eksamen (januar) - vægter 80 %
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.
Aktiviteter i studiefasen: At studere kursusmaterialet og forberede de ugentlige øvelser, individuelt eller gennem gruppearbejde.