DM551: Algoritmer og sandsynlighed (10 ECTS)

STADS: 15015901

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.

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 Matematisk redskaber i datalogi eller DM535 Diskrete metoder i datalogi skal være kendt.
Kurset kan ikke følges hvis DM538 er bestået, eller hvis DM538 indgår obligatorisk i din studieordning.

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. De studerende lærer at bruge ovennævnte principper til at udvikle og analysere (randomiserede) algoritmer, samt til at anvende randomisering til design af simple algoritmer til fx sammenhæng i grafer. Kurset indeholder også en introduktion til endelige automater, samt disses anvendelse i forbindelse med søgning i tekststrenge.

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, bl.a. på centrale diskrete sandsynlighedsfordelinger.
• løse lineære rekursionsligninger.
• udvikle og analysere basale randomiserede algoritmer under brug af redskaber fra kombinatorik og diskret sandsynlighedsteori.
• beskrive disse handlinger i et præcist matematisk sprog og argumentere for de enkelte skridt i udregningerne.
• opskrive en endelig automat som svarer til tekstsøgningsproblemet for et givet tekstmønster P.
• anvende algoritmer til at finde forekomster af en given tekststreng i en tekst.
• Anvende teknikker fra universel hashing til udvælgelse af hash funktioner med god forventet opførsel.

Emneoversigt
Kombinatorik, tælleteknikker for permutationer og kombinationer, binomialkoefficienter, inklusion/eksklusion-princippet, diskret sandsynlighedsteori, standard diskrete sandsynlighedsfordelinger, rekursionsligninger, randomiserede algoritmer, universel hashing, streng søgning, endelige automater.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
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 mundtlig eksamen ved afslutningen af kurset, der bedømmes med karakter efter 7-skalaen og ekstern censur. 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. (15015902)

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: 40 timer
Træningsfase: 30 timer, heraf:
 - Eksaminatorie: 30 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. september 2014 til 31. august 2016.