Overordnede kursusmål
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.
Litteraturhenvisninger
Forelæsningsnoter vil være tilgængelige på DTU Learn.
Sidst opdateret
02. maj, 2024