DM528: Kombinatorik, sandsynlighed og randomiserede algoritmer (5 ECTS)

STADS: 15004201

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
2. kvartal

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og datastrukturer og fra DM527 Matematiske redskaber i datalogi skal være kendt.

Kursusintroduktion
Kurset skal give de studerende færdigheder i at arbejde med kombinatorik og diskret sandsynlighed med henblik på anvendelser i datalogi. I den første del lærer de studerende teknikker til at tælle antallet af elementer i endelige mængder. I den anden del bruges disse teknikker til at arbejde med diskrete sandsynlighedsrum og -fordelinger. Derefter fortsættes med mere avancerede tælleteknikker og i den sidste del af kurset lærer de studerende at bruge ovennævnte principper til at udvikle og analysere randomiserede algoritmer.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

- anvende de i kurset gennemgåede tælleteknikker til at finde kardinaliteten af en mængde.
- anvende de i kurset gennemgåede begreber fra diskret sandsynlighedsteori, herunder kunne finde middelværdi og varians for centrale diskrete sandsynlighedsfordelinger.
- løse linære rekursionsligninger og at udføre en asymptotisk analyse af funktioners vækst givet ved ikke-lineære rekursionsligninger.
- udvikle og analysere basale randomiserede algoritmer under brug af redskaber fra kombinatorik og diskret sandsynlighedsteori.
- kunne beskrive disse handlinger i et præcist matematisk sprog og kunne argumentere for de enkelte skridt i udregningerne.

Emneoversigt
Kombinatorik, tælleteknikker for permutationer og kombinationer, binomialkoefficienter, inklusion/eksklusion-princippet, diskret sandsynlighedsteori, standard diskrete sandsynlighedsfordelinger, rekursionsligninger, generatorfunktioner, randomiserede algoritmer.

Litteratur

Meddeles ved kursets start

Pensum
Se pensumbeskrivelse.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Obligatoriske opgaver der bedømmes med B/IB og intern censur ved underviser.
(b) Skriftlig eksamen der bedømmes med karakter efter 7-skalaen og ekstern censur.

Reeksamen efter 4. kvartal. 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.

Forelæsninger: 22 timer
Eksaminatorietimer/opgaveregning: 20 timer.
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2008 til 31. august 2009.