MM541: Kombinatorisk matematik (5 ECTS)

STADS: 13012101

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere
Email: magnusgf@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Emnerne fra MM537 Introduktion til Matematiske Metoder forudsættes kendt.

Kursusintroduktion
Kurset vil give de studerende basale færdigheder til at arbejde med kombinatorisk matematik, (algoritmisk) grafteori samt (primært kombinatoriske anvendelser af) lineær programmeringsteori.

Kompetencer
De studerende vil opnå indsigt i teknikker til at tælle antallet af elementer i en mængde. De vil kende basale emner fra grafteori såvel som fundamentale grafproblemer. De vil kende den grundlæggende teori for lineær programmering herunder dualitetssætningen. Efter kurset vil de studerende være i stand til at bruge denne viden i relevante sammenhænge 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

Forventet læringsudbytte
Ved afslutningen af kurset forventes den studerende at kunne:

• Anvende tælleteknikker fra kurset til at finde kardinaliteten af en mængde
• opstille tælleproblemer ud fra en beskrivelse i ord
• Løse lineære rekursionsligninger
• Løse grafteori problemer der i natur minder om dem der er gennemgået i kurset
• Formulere lineære programmer for optimerings problemer der minder om dem fra kurset
• Beskrive disse handlinger i et præcist matematisk sprog og argumentere for korrektheden af de enkelte udregninger/skridt

Emneoversigt
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

Meddeles ved kursets start.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:

1. 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 første 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 eller i umiddelbar forlængelse heraf. Reeksamen er en mundtlig eksamen, der bedømmes med karakter efter 7-skalaen og ekstern censur.

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

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 2015 til 31. januar 2016.