Kursöversikt

Viggo Kann [VK] och Douglas Wikström [DW] delar på föreläsningarna. Stefan Nilsson [SN] och Tomas Ekholm [TE] håller gästföreläsningar. Både föreläsningar och övningar ges i sal på campus. Nedanstående tabell visar vad som kommer att behandlas under föreläsningarna och övningarna. För varje föreläsning anges vilket material i kurslitteraturen som behandlas. Du bör ha skummat det innan du kommer till föreläsningen för att ha riktig glädje av föreläsningen. I tabellen nedan finns länkar till föreläsningsbilder, övningsuppgifter och annat material.

Föreläsning 9-11 om dynamisk programmering samt föreläsning 20 och 21 om reduktioner och introduktion till komplexitet har omvänd undervisning, så det finns förberedande videor och uppgifter till dessa föreläsningar. Första timmen på dessa föreläsningar är avsatt för att du ska kunna göra förberedelserna. Ta i så fall med egen dator. Om du gör förberedelserna i förväg räcker det att du kommer till andra timmen på dessa föreläsningar.

Undervisning, redovisningar och läsanvisningar

  • KT=Kleinberg-Tardos, oavsett om det är KTorig eller KTnie
  • KTorig=Kleinberg-Tardos International Edition (2006) eller motsvarande amerikanska utgåva
  • KTnie=Kleinberg-Tardos New International Edition (2014), när denna skiljer sig från den tidigare utgåvan (kapitel 5 Divide and Conquer kommer före kapitel 4 Greedy Algorithms och kapitel 13 Randomized Algorithms kommer före kapitel 12 Local Search)
  • Sup=supplementet Algorithms and Complexity

Period 1

  • Övningsmästarprovsövning 1 25 september
    Redovisning av övningsmästarprov 1 som förberedelse till mästarprov 1, som publiceras kl 8:00 den 26 september.
    Grupp 3 genomför övningsmästarprovet i Zoom: https://kth-se.zoom.us/j/62214207240 (Du laddar då upp din lösning i Canvas under övningen.)
    Övriga grupper är i sal (grupp 1 i U31, grupp 2 i U41 och grupp 4 i U51). Det går bra att gå till vilken av grupperna som helst.
  • Labb 2 26 september
    Rättstavning, redovisning.
  • F14 26 september
    [VK] Undre gränser. (Sup: 17-29)
    Genomgång av lydelsen till uppgift 1 och 3 på mästarprov 1.

Sammanfattning av alla algoritmer hittills i kursen.

  • F20 8 oktober (OBS, omvänd föreläsning: förberedelse krävs!)
    [DW] Reduktioner. (KT: 451-459)
    Första timmen: tid för att göra förberedelserna.
    Andra timmen: frågestund och arbete med uppgifter i grupp.
  • Ö7 8 oktober
    Probabilistiska algoritmer. Reduktioner.
  • F21 10 oktober (OBS, omvänd föreläsning, förberedelse krävs!)
    [DW] Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)
    Första timmen: tid för att göra förberedelserna.
    Andra timmen: frågestund och arbete med uppgifter i grupp.
  • Mästarprov 1 (Algoritmkonstruktion) senast tisdag 15 oktober klockan 19:00.
    Uppgiftslydelsen publiceras i Canvas 26 september.
    Muntliga redovisningar sker 21-25 oktober (tentaveckan).

Period 2

  • F27 och Manuskript 12 november
    [DW] NP-fullständighetsreduktioner. (KT: 459-463)
  • F28 och Manuskript 13 november
    [DW] Mer NP-fullständighetsreduktioner. (KT: 497-505)
  • Dags att börja titta på övningsmästarprov 2!
  • Två relevanta länkar från kursens länksamling för den som vill fördjupa sin förståelse av oavgörbarhet och reduktioner:
    - Math has a fatal flaw - en film om ofullständighet och oavgörbarhet
    - Reducing reductions to intuition     - Douglas Wikström beskriver och definierar dom olika typerna av reduktioner som ingår i ADK.
  • Labb 4 14 november
    NP-fullständighetsreduktioner, redovisning.
  • Ö10 15 november
    NP-fullständiga problem.
  • F29 19 november
    [DW] Heuristiska algoritmer. Simulated annealing. (KTorig: 661-670/KTnie: 749-758)
  • Övningsmästarprovsövning 2 20 november
    Redovisning av övningsmästarprov 2 och genomgång av fler exempel på NP-fullständighetsproblem som förberedelse till mästarprov 2, som publiceras denna dag.
    Grupp 3 genomför övningsmästarprovet i Zoom https://kth-se.zoom.us/j/62214207240 (Du laddar då upp din lösning i Canvas under övningen.).
    Övriga grupper är i sal. Det går bra att gå till vilken av grupperna som helst.
  • F30 21 november
    [VK] Approximationsalgoritmer. (KT: 599-630)
    Föreläsningen inleds med en genomgång av lydelsen till uppgift 1 på mästarprov 2.
    På begäran sänds genomgången av uppgift 1 på mästarprov 2 i Zoom https://kth-se.zoom.us/j/64935712966 (om tekniken tillåter - vi gör ett försök)
  • F31 25 november
    [VK] Mer approximationsalgoritmer. (webbsida om Christofides algoritm, Viggos lista med approximationsresultat för NP-svåra optimeringsproblem)
    Genomgång av lydelsen till uppgift 2 och 3 på mästarprov 2.
  • Ö11 26 november
    Approximationsalgoritmer. Teoriredovisning till labb 5.
  • F32 27 november
    [VK] Komplexitetsklasser. (KT: 495-497, 531-547)
    Genomgång av lydelsen till uppgift 3 på mästarprov 2.
  • F33 2 december
    [VK] Repetition. Kursens betygssystem. Om teoritentan, högrebetygslabben, muntan och omexamination.
  • Ö12 3 december
    Komplexitetsklasser och repetition.
  • Labb 5 4 december
    Heuristik för rollbesättningsproblemet, redovisning. 
  • Mästarprov 2 (komplexitet), senast 5 december klockan 19:00!
    Uppgiftslydelsen publiceras i Canvas 20 november klockan 17:00.
    Muntliga redovisningar sker 10-16 december.
  • Extra labbredovisningstillfälle 9 december för alla labbar, inklusive högrebetygslabben.
    Labbredovisningar prioriteras framför labbhjälp. Eftersom längden på redovisningarna varierar läggs inga bokningslistor upp, utan Stay-a-while används som kö. Redovisningar kommer att kunna genomföras både i Zoom och i datorsal Grå+Karmosin.
  • Teoritenta 19 december klockan 9-12. Skrivtid 9:00-10:30 i Canvas. Obligatorisk rättningssession kl 11:00-12:00 i Zoom. Sedvanlig tentaanmälan måste göras i förväg.
    Den som har 50% förlängd skrivtid tentar klockan 8:15-10:30.
  • Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt 3 januari och muntligt 7-8 januari 2025.
  • Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (övriga labbar kan inte redovisas) 7 januari 2025 kl 9-12. Bokningslistor publiceras i Canvas 31 december.
  • Labbkursreflektion bör lämnas in senast 8 januari 2024.
  • Frivillig munta för högre mästarprovsbetyg, 9 och 10 januari 2025. Anmälan görs under perioden 31 december 2024 till 7 januari 2025. Instruktioner om hur muntan genomförs. 

Efter period 2 är kursen slut. Den som har labbar kvar att redovisa kan göra det antingen i labbveckan i juni eller under våren på labbpassen i systerkursen DD2352 Algoritmer och komplexitet. Säg till den du redovisar för att du ska ha labben rapporterad på adk23. Labbkursreflektionen lämnar du in i kursrummet för adk24 när du är klar med alla labbarna.

Den som har mästarprov kvar kan göra dom i en senare kursomgång av antingen ADK (som går varje hösttermin) eller systerkursen DD2352 (som går varje vårtermin; du ska inte registrera dig på DD2352, men du behöver kontakta kursledaren för DD2352, Per Austrin, för att bli inlagd i kursrummet så att du kan lämna in mästarprovet).

Den som har teoritentan kvar kan anmäla sig till och gå upp på omtentan i april 2025 eller nästa ordinarietenta i december 2025.