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.

Eksamensdato
Den ordinære eksamen finder sted den 20. januar 2009
Reeksamen finder sted den 30. juni 2009

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.