MM851: Algoritmer og sandsynlighed

NYT kursus E19

Kurset samlæses med DM551.

Kurset kan ikke følges af studerende, der har bestået DM538 eller DM528.

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.

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: strømning i netværk, 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.

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.
• Opstille en strømningsmodel for problemer som ligner dem der dækkes i kurset

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
• Strømning i netværk

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

• Introfase (forelæsning, holdtimer) - Antal timer: 40
  
• træningsfase: Antal timer: 30

Aktiviter 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