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
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
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
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
Skemaoplysninger
Administrationsenhed
Team hos Uddannelsesjura & Registratur
Udbudssteder
Anbefalede studieforløb
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.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.