DM891: Algoritmer under stokastisk usikkerhed

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N340124102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Kandidat

STADS ID (UVA): N340124101
ECTS-point: 5

Godkendelsesdato: 07-10-2022


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM891 udbydes efter følgende plan, når kurset udbydes: Forår (kursusstart februar): ordinær eksamen (juni), første reeksamen (august) og anden reeksamen i (januar).

Indgangskrav

Ingen

Faglige forudsætninger

Der forudsættes kendskab til algoritmer og datastrukturer og analyse af disse, herunder algoritmedesignteknikker som grådige tilgange og dynamisk programmering, grundlæggende algoritmer for grafer, tids- og pladsanalyse, herunder asymptotisk notation, samt et basalt kendskab til sandsynlighedsteori. Forudsætningerne kan erhverves gennem algoritmekurser og kurser i diskret matematik på en bacheloruddannelse i datalogi.

Formål

Formålet med kurset er at introducere algoritmiske problemer, der involverer stokastisk usikkerhed, og at studere algoritmiske teknikker til dem samt deres beregningskompleksitet. De problemer i den virkelige verden, der kan modelleres med de pågældende problemer, omfatter ansættelsesprocesser, salg af varer til kunder, beslutningstagning under informationsomkostninger og klassificering af en patients risiko. Tilgængeligheden af stokastiske oplysninger kan begrundes med tilgængeligheden af store datamængder.

Kurset bygger oven på den viden, der er erhvervet i kurserne DM549 Diskrete Metoder til Datalogi eller MM537 Introduktion til Matematiske Metoder, DM551 Algoritmer og Sandsynlighed eller MM541 Kombinatorisk Matematik, DM507 Algoritmer og Datastrukturer, og DM553 Kompleksitet og Beregnelighed. Kurset giver et fagligt grundlag for at lave et speciale indenfor algoritmer under stokastisk usikkerhed.

I forhold til uddannelsens kompetenceprofil har kurset fokus på
- at give kompetence til at forstå komplekse problemer,
- at give ekspertviden baseret på nyere international forskning på højt niveau,
- at give kompetence til at arbejde med komplekse opgaver hen imod en løsning,
- at give kompetence til at formidle videnskabelige problemer og løsninger gennem skriftlige opgaver.

Målbeskrivelse

Kursets læringsmål er, at den studerende demonstrerer evnen til at
- definere og sammenligne de problemer, der studeres i kurset.
- identificere problemer fra den virkelige verden, der kan modelleres med de abstrakte problemer, der studeres i kurset.
- beskrive og udføre de algoritmer, der studeres i kurset.
- gennemføre de algoritmeanalyser, der studeres i kurset.
- bevise øvre og nedre grænser for garanteret ydeevne for algoritmer for problemer relateret til dem, der studeres i kurset.
- designe og analysere nye algoritmer for problemer, der ligner dem, der studeres i kurset.

Indhold

Følgende hovedproblemer behandles i kurset:
- sekretærproblemet, varianter og udvidelser,
- profet-ulighed-problemet, varianter og udvidelser,
- problemer med Markov-kæder og Markov-beslutningsprocesser,
- Pandoras æskeproblemet og udvidelser,
- stokastiske sonderingsproblemer,
- problemer med evaluering af stokastiske funktioner.

Hvis det pågældende aspekt er gennemførligt for det pågældende problem, vil eksakte algoritmer, algoritmer med beviselige ydelsesgarantier, beregningskompleksitet og tilpasningsgab blive drøftet.

Litteratur

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Juni

Udprøvninger

Mundtlig

EKA

N340124102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

30 minutter

Hjælpemidler

Oplyses på kurset

ECTS-point

5

Uddybende information

Mundtlig eksamen samt et antal opgavesæt afleveret i løbet af kurset. Karakteren baseres på et samlet indtryk af elementerne som indgår i evalueringen.
Opgavebesvarelserne danner, sammen med udvalgte emner fra kurset, grundlag for den mundtlige eksamen.

Vejledende antal undervisningstimer

36 timer per semester

Undervisningsform

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen, dvs. intro, trænings- og studiefasen.
- Introfase: 22 timer.
- Træningsfase: 14 timer.

Aktiviteter i studiefasen
- løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne,
- løsning af eksamensopgaverne,
- selvstudium af visse emner fra lærebogen,
- selvstændig opsamling på intro og træningsfasen.

Ansvarlig underviser

Navn E-mail Institut
Kevin Schewior kevs@sdu.dk Institut for Matematik og Datalogi, IMADA

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil Uddannelse Semester Udbuds periode

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.
Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.