Forelæsninger og opgaver (hvoraf nogle er obligatoriske). Der er krav om aflevering af mindst 6 skriftlige besvarelser af obligatoriske opgaver i løbet af undervisningen for at kunne gå til eksamen.
For mange problemer i den virkelige verden kender man ingen metoder til effektivt at finde den optimale løsning. Vi kalder denne type problemer for beregningsmæssigt hårde problemer. For denne type problemer er det kun muligt at finde approksimative løsninger indenfor rimelig tid. Kursets formål er at sætte de studerende i stand til at identificere et problem som beregningsmæssigt hårdt og udstyre dem med algoritmiske metoder til at finde approksimative løsninger.
Læringsmål:
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
designe en inputbeskrivelse for et givet problem
definere de forskellige niveauer af hårdhed af problemer
definere hvornår et problem er hårdt
identificere den tilgrundliggende abstrakte struktur af et virkeligt problem
afgøre om et givet problem er beregningsmæssigt hårdt
analysere et givet problem med hensyn til dets kompleksitet
analysere randomiserede algoritmer med hensyn til brug af ressourcer
analysere randomiserede algoritmer med hensyn til kvaliteten af den løsning de frembringer
genkende muligheden for anvendelsen af randomiserede algoritmer til at løse et givet hårdt problem
designe randomiserede algoritmer for specifikke problemer
sammenligne og vurdere forskellige løsningsmetoder for et givet problem og vælge den mest lovende
Kursusindhold:
Der findes mange vigtige problemer indenfor daalogi og andre områder, som kan løses optimalt, men hvor den tid det kræver er så lang, at det gør det praktisk umuligt. Eksempler på sådanne problemer er: optimal tildeling af opgaver til processorer, finde den optimale rute for en varebil, pakke en kuffert optimalt, optimere læsset af et rumfartøj eller at finde den optimale sammensætning af et aktiedepot.
I kurset vil vi først præcisere hvad vi mener med "beregningsmæssigt hårde" problemer. Derefter vil der blive givet eksempler på denne type problemer og præsenteret metoder til at bevise at et givet problem er hårdt. For at kunne analysere et problem fra den virkelige verden er det nødvendigt først at identificere den tilgrundliggende matematiske struktur af problemet. Derefter kan det konverteres til en abstrakt matematisk model som det er muligt at analysere.
Vi vil derefter betragte randomiserede algoritmer og vise hvordan disse kan bruges til at give approksimative løsninger til hårde problemer. Disse algoritmer er hurtige algoritmer der "slår plat eller krone" undervejs, dvs. bruger en tilfældighedsgenerator. Derfor kan man få forskellige løsninger når man kører en sådan algoritme på det samme input gentagne gange. Vi vil vise, at der er hårde problemer, som kan løses og "næsten optimalt" med randomiserede algoritmer. Dvs. at algoritmen med stor sandsynlighed finder en "god" løsning.
Litteratur:
Forelæsningsnoter vil være tilgængelige på Campusnet.
Mulighed for GRØN DYST deltagelse:
Kontakt underviseren for information om hvorvidt dette kursus giver den studerende mulighed for at lave eller forberede et projekt som kan deltage i DTUs studenterkonference om bæredygtighed, klimateknologi og miljø (GRØN DYST). Se mere på http://www.groendyst.dtu.dk/kursustilmelding.aspx
