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:
Kurset kan ikke følges af studerende, der har bestået DM538 eller DM528.

Faglige forudsætninger:
Studerende, der følger kurset, forventes at:

• Have kendskab til grundlæggende datastrukturer
• Have kendskab til basale algoritmer for manipulering af (repræsentationer af) talsæt og grafer, samt implementering af sådanne i et imperativt programmeringssprog
• Have kendskab til basal matematisk argumentation, herunder bevis ved induktion, bevis ved modstrid og logiske udtryk.
• Have kendskab til konvergens af potensrækker.

Formål
Kurset har til formål at sætte den studerende i stand til at anvende metoder fra kombinatorik og diskret sandsynlighed i forbindelse med design og analyse af algoritmer og datastrukturer. Disse færdigheder er vigtige både når der skal udvikles nye algoritmer til et givet problem og når man skal vurdere, hvilken blandt flere algoritmer, samt implementationer af disse vha. datastrukturer, der må forventes at være mest effektive til at løse problemet hurtigt.

Kurset bygger oven på den viden, der er erhvervet i kurserne DM507 Algoritmer og datastrukturer samt DM549 Diskrete metoder til datalogi.

Kurset giver et fagligt grundlag for at gennemføre et bachelorprojekt samt valgfrie kandidatkurser der indeholder et eller flere af følgende elementer: randomisering, tælleargumenter med henblik på analyse af kompleksiteten eller bevise korrektheden af en algoritme, samt probabilistiske beviser. Desuden giver kurset, suppleret med ovennævnte typer af kurser, et fagligt grundlag for at lave et speciale indenfor randomiserede algoritmer.

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

• Give kompetence til at kunne udvikle og analysere algoritmer ud fra metoder fra kombinatorik og diskret sandsynlighedsteori.
• Give færdigheder i at anvende kombinatoriske argumenter, samt diskret sandsynlighedsteori i forbindelse med udvikling og analyse af algoritmer og datastrukturer.
• Give viden om hvordan den probabilistiske metode anvendes
• Give viden om hvorledes kombinatorik og randomisering kan anvendes til udvikling og analyse af algoritmer der har en god forventet køretid/performance.
• Give viden om anvendelsen af randomisering af design af algoritmer, samt anvendelse af elementær sandsynlighedsteori til at analysere køretiden af algoritmer
• Give kompetencer til at udvikle nye varianter af centrale algoritmer og datastrukturer udviklet inden for datalogi

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

• Anvende de i kurset gennemgåede tælleteknikker til at bestemme kardinaliteten af en mængde.
• Anvende de i kurset gennemgåede begreber fra diskret sandsynlighedsteori, bl.a. på centrale diskrete sandsynlighedsfordelinger, samt til at vurdere forventede køretider af algoritmer.
• Løse lineære rekursionsligninger
• Udvikle og analysere basale randomiserede algoritmer under brug af kursets emner.
• Anvende teknikker fra universel hashing til udvælgelse af hash funktioner med god forventet opførsel.
• Anvende algoritmer fra kurset til at finde forekomster af en given tekststreng i en tekst.
• Opskrive en endelig automat som svarer til tekstsøgningsproblemet for et givet tekstmønster.

Indhold
Kurset indeholder følgende faglige hovedområder:

• Kombinatorik
• Tælleteknikker, herunder permutationer, kombinationer, binomialkoefficienter, fordeling af emner i kasser samt inklusion/eksklusions-princippet
• Lineære rekursionsligninger
• Diskret sandsynlighedsteori og diskrete sandsynlighedsfordelinger
• Randomiserede algoritmer
• Probabilistisk analyse af algoritmer
• Den probabilistiske metode
• Universel hashing
• Strengsøgning
• Endelige automater

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:

1. Mundtlig eksamen på baggrund af to opgavesæt afleveret i løbet af kurset. Ekstern censur, 7-trinsskala. Karakteren baseres på et samlet indtryk af de tre elementer som indgår i evalueringen. (10 ECTS). (15015902).

Det første opgavesæt skal løses selvstændigt, medens det andet må løses i grupper af op til 3 personer. Opgavebesvarelser danner, sammen med udvalgte emner fra kurset, grundlag for den mundtlige eksamen. 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: 40 timer
Træningsfase: 30 timer, heraf:
 - Eksaminatorie: 30 timer

Aktiviteter i studiefasen
Aktiviteter i studiefasen:

• 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

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 2016 til 31. august 2018.