Dansk

MM541: Kombinatorisk matematik (5 ECTS)

STADS: 13012101

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere

Email: yeo@imada.sdu.dk

Skemaoplysninger

Hold	Type	Dag	Tidsrum	Lokale	Uger
Fælles	I	Mandag	12-14	U56	6-12
Fælles	I	Onsdag	14-16	U56	5
Fælles	I	Torsdag	14-16	U24	5-6
Fælles	I	Torsdag	14-16	U43	8-9,11
H16	TE	Tirsdag	10-12	U56	6-12
H16	TE	Torsdag	14-16	U24	7
H16	TE	Torsdag	14-16	T9	10
H16	TE	Torsdag	14-16	U154	12
H16	TE	Fredag	08-10	U10	5
H17	TE	Onsdag	14-16	U56	6-9,11-12
H17	TE	Torsdag	08-10	U30A	10
H17	TE	Fredag	13-15	U24	5
H17	TE	Fredag	13-15	U142	7
H17	TE	Fredag	13-15	U14	10
H17	TE	Fredag	13-15	T9	12

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 emnerne fra MM537 (Introduktion til Matematiske Metoder).

Formål

Kurset har til formål at sætte den studerende i stand til at anvende metoder fra kombinatorisk matematik, (algoritmisk) grafteori samt (primært kombinatoriske anvendelser af) lineær programmeringsteori.

Disse færdigheder er vigtige både når der skal udvikles nye algoritmer til et givet problem og når man skal optimere en profit eller minimere udgifter i mange praktiske problemer. Det er også vigtig i forståelsen af de anvendte algoritmer og metoder.

Kurset bygger videre på den viden i logik og grundlæggende matematisk bevisførelse, der undervises i i MM537. Det forudsættes at den studerende på baggrund af dette er i stand til at formulere enkle matematiske beviser.

Hvis kurset suppleres med andre kurser i lignende emner kan det danne baggrund for et Bachelor-projekt i diskret matematik.

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

Give viden om udvalgte matematiske emner så som lineær programmering og tælle metoder.
Give viden om hvordan man foretager matematiske analyser ved brug af diskrete metoder, samt at forholde sig kritisk til de benyttede matematiske teorier og modeller
Give kompetencer og færdigheder i brugen af ovenstående.

Målbeskrivelse

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

Tælle antallet af elementer i en mængde.
Formulere tælleproblemer ud fra en beskrivelse i ord
Løse lineære rekursionsligninger.
Løse grafteoretiske problemer som i natur minder om dem i kurset.
Formulere lineære programmer og anvende dualitetssætningen for lineær programmering.

Indhold

Kurset indeholder følgende faglige hovedområder:

Kombinatorik.
Tælleteknikker for permutationer og kombinationer.
Binomialkoefficienter.
Inklusion/eksklusionsprincippet.
Lineære rekursions ligninger.
Grafteori (basale definitioner, ruteproblemer, udspændende træer og pardannelser).
Grådige algoritmer.
Lineær programmering og dualitet.
Algoritmiske beviser.
Gode karakterisationer.

Litteratur
Der er i øjeblikket ikke angivet nogle materialer for kurset.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:

Mundtlig eksamen delvist baseret på skriftlige opgavesæt. Ekstern censur, 7-trinsskala (5 ECTS). (13012102).

I løbet af kurset stilles to opgavesæt, hvoraf det ene skal løses selvstændigt, medens det andet må løses i grupper af op til 3 personer. Disse besvarelser danner, sammen med udvalgte emner fra kurset, grundlag for en individuel mundtlig eksamen ved afslutningen af kurset.

Karakteren baseres på et samlet indtryk af de tre elementer som indgår i evalueringen. Censor vil have mulighed for at se besvarelserne på de to opgavesæt.

Reeksamen i samme eksamenstermin. 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.
Introfase: 26 timer
Træningsfase: 22 timer, heraf:
- Eksaminatorie: 22 timer

Aktiviteter i studiefasen Studiefase: 30 timer

Selvstudium af lærebogen og andet undervisningsmateriale.
Løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne.
Skriftlige hjemmeopgaver som en del af eksamen.
Selvstændig opsamling på intro- og træningsfasen.
Repetition op til eksamen.

Undervisningsform
Kurset består af forelæsninger og eksaminatorier. I løbet af kurset stilles desuden to opgavesæt, hvoraf det ene skal løses selvstændigt, medens det andet må løses i grupper af op til 3 personer.

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. februar 2017 til 31. januar 2018.