02249 Beregningsmæssigt hårde problemer

2024/2025

Kursusinformation
Computationally Hard Problems
Engelsk
7,5
Kandidat
Generel retningskompetence (MSc), Computer Science and Engineering
Retningsspecifikt kursus (MSc), Computer Science and Engineering
Retningsspecifikt kursus (MSc), Mathematical Modelling and Computation
Teknologisk specialisering (MSc), Computer Science and Engineering
Teknologisk specialisering (MSc), Mathematical Modelling and Computation
E3A (tirs 8-12)
Campus Lyngby
Forelæsninger og opgaver (hvoraf nogle er obligatoriske).
13-uger
E3A
Skriftlig eksamen og bedømmelse af opgave(r)
Skriftlig eksamen og bedømmelse af opgave(r). Gruppeprojekter skal individualiseres. Karakteren fremkommer ved en helhedsvurdering.
Skriftlig eksamen: 4 timer
Alle hjælpemidler - uden adgang til internettet
7-trins skala , ekstern censur
02110. 02141. 02402/02403/02405 , Kendskab af algoritmer og grundlæggende emner fra formelle sprog og statistik/​sandsynlighedsregning.
Carsten Witt , Tlf. (+45) 4525 3722 , cawi@dtu.dk
01 Institut for Matematik og Computer Science
I studieplanlæggeren
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