DM839: Randomiserede algoritmer (10 ECTS)

STADS: 15014701

Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 3. +4. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Kendskab til algoritmer, datastrukturer, kompleksitet og elementær diskret sandsynlighedsteori, svarende til f.eks stoffet fra DM507, DM508 og DM538.

Kursusintroduktion
Probabilistisk analyse af algoritmer, randomiserede algoritmer, samt probabilistiske kombinatoriske konstruktioner er blevet fundamentale redskaber i datalogi og anvendt matematik. Formålet med kurset er at give et solidt fundament for anvendelsen af diskret sandsynlighed som et redskab til
såvel analyse samt design af algoritmer. Dette inkluderer at illustrere anvendelsen af den probabilistiske metode til, at udlede randomiserede algoritmer. I kurset indgår både teoretiske og praktiske (eksperimentelle) elementer og der lægges lige vægt på anvendelse og teori.

Kompetencer
De studerende vil opnå detaljeret indsigt i anvendelser af randomisering og elementær sandsynlighedsteori til design og analyse af algoritmer og skal kunne anvende den opnåede viden i relevante sammenhænge til

• at analysere den forventede køretid af visse deterministiske algoritmer
• at udvikle nye randomiserede algoritmer for problemer der i natur minder om dem der er studeret i kurset.
• at anvende randomisering som et hjælpeværktøj til udvikling af deterministiske algoritmer via derandomiseringsteknikker.
• at vurdere den forventede køretid af Las Vegas algoritmer
• at vurdere sandsynligheden for et korrekt svar fra en Monte Carlo algoritme.
• at bruge den probabilistiske metode på problemer der i natur ligner dem der er studeret i kurset.
• at bruge randomisering som et værktøj til udvikling af protokoller for f.eks kommunikations problemer.

Forventet læringsudbytte


Emneoversigt
udvikling af randomiserede algoritmer (eksempel min cut i grafer), forventet køretid af algoritmer, fejlsandsynlighed for algoritmer, den probabilistiske metode, Chernoff bounds, Hashing, derandomisering, kugler i kasser og tilfældige grafer, experimentel test af (randomiserede) algoritmer, mm.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen med udgangspunkt i projekt og opgaver. Ekstern censur, bedømmes efter 7-trins skalaen (10 ECTS). Der stilles en eller flere opgaver, samt et projekt i løbet af kurset. Disse kan løses i grupper og danner udgangspunkt for den mundtlige eksamen. Alle dele bedømmes og karakteren gives ud fra det samlede indtryk (ikke gennemsnit af delprøver).

(STADS: 15014702)

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 40 timer
Træningsfase: 20 timer, heraf:
 - Eksaminatorie: 20 timer

Aktiviteter i studiefasen Studiefase: 60 timer

Sprog
Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. feb 2014.