Till KTH:s startsida Till KTH:s startsida

Kurs-PM för DD1352 adk16

Lärare

Kursledare och föreläsare är Viggo Kann, viggo@csc.kth.se och Stefan Nilsson snilsson@csc.kth.se

Det står var och en fritt att välja övningsgrupp eller byta grupp under kursens gång. Övningsassistenter är:

  1. Emma Nimstad, normalsvår grupp
  2. Marcus Dicander, lite svårare grupp
  3. Susanna De Rezende, lite enklare grupp på engelska

Vid teoriredovisning 1 och 2 vid övning 2 och 4 finns det en fjärde övningsgrupp för att alla ska få plats.

Det finns också ett antal ytterligare personer som är labbhandledare och tar emot mästarprovsredovisningar.

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar och övningar täcker endast en del av kursmaterialet. Två kursböcker:

Dessa kan köpas i ett inplastat bokpaket på kårbokhandeln för 670 kronor. Supplementet kan även köpas löst för 120 kronor.

Funktionsnedsättning

Om du har en funktionsnedsättning kan du få stöd via Funka:
https://www.kth.se/student/studentliv/funktionsnedsattning
Informera dessutom kursledaren om du har särskilda behov. Visa då upp intyg från Funka.

Kursens pedagogiska upplägg

  • Studera på det sätt som är effektivast för dej! Allt föreläsnings- och övningsmaterial finns tillgängligt i förväg.
  • Koncentrerade entimmesföreläsningar med läsanvisningar. Kom förberedd och var vaken för bästa resultat! Avsnittet dynamisk programmering görs som omvänt klassrum.
  • Övningsuppgifter med fullständiga lösningar. Övningsgrupper med svårighetsgradering.
  • Momenten i kursen tränar verkliga arbetssituationer för bättre autenticitet.
  • Aktiverande färgfrågor på föreläsningarna och kontinuerlig examination med labbteoriuppgiftredovisning inför varje datorlabb gör att du automatiskt hänger med i kursen.
  • Undervisning byggd på pedagogisk forskning - en hel doktorsavhandling om ADK las fram 2014!
  • Målrelaterade betygskriterier; välj själv betyg!
  • Gott om tid för labbar och mästarprov, ingen stressad tentasituation.

Kursen består av 33 föreläsningar och 12 övningar. Alla föreläsningar efter första veckans tre föreläsningar är egentligen entimmesföreläsningar (men av schematekniska skäl har vid fem tillfällen två entimmesföreläsningar kommit att hamna direkt efter varandra). Viggo Kann [VK] och Stefan Nilsson [SN] delar på föreläsningarna. Följande 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.

Undervisning, redovisningar och läsanvisningar

  • KT=Kleinberg-Tardos,
  • 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

  • F1 31 augusti (2 timmar)

    [SN+VK] Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad. (KT: 29-56)

  • F2 1 september(2 timmar)

    [SN] Repetition av sortering (animering 1, animering 2). (KTorig: 209-221/KTnie: 115-127)
    Effektiv kodning och avlusning. Se även Diverse länkar i kurswebbens vänstermeny.

  • Ö1 2 september

    Algoritmanalys.

  • F5 6 september

    [VK] Datastrukturer: bloomfilter. Tillämpning: rättstavning.

  • F6 8 september

    [SN] Korrekthetsbevis.

  • Ö2 9 september

    Datastrukturer och grafer. Teoriredovisning för labb 1.

  • F7 13 september kl 13

    [SN] Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KTorig: 115-136, 183-188/KTnie: 157-179, 225-230)

  • F8 13 september kl 14

    [SN] Algoritmkonstruktion: dekomposition. (KTorig: 221-234, 242-246/KTnie: 127-140, 148-152)

  • F9 14 september

    [VK] Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-260)
    Visualiseringar: Fibonaccitalen.

  • Ö3 15 september

    Dekomposition och dynamisk programmering.

  • Labb 1 16 september

    Konkordans, redovisning.

  • F10 19 september kl 10

    [VK] Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 261-290)

  • F11 19 september kl 11

    [VK] Exempel på motivering av korrekthet: dynamisk programmering. (KT: 290-301, 307-311)

  • Ö4 20 september

    Dynamisk programmering. Teoriredovisning för labb 2.

  • F14 26 september

    [VK] Undre gränser. (Sup: 17-29)

  • Ö5 29 september

    Grafalgoritmer och undre gränser.

  • Labb 2 30 september

    Rättstavning, redovisning.

  • F18 5 oktober

    [SN] Algoritmkonstruktion: polynomberäkningar och FFT. (KTorig: 234-242/KTnie: 140-148)

  • Ö6 7 oktober

    Algoritmkonstruktion. Teoriredovisning för labb 3.

Sammanfattning av alla algoritmer hittills i kursen.

  • F19 10 oktober

    [SN] Probabilistiska algoritmer. (KTorig: 707-734, 769-776/KTnie: 661-688, 723-730)

  • Mästarprov 1, senast måndag 10 oktober klockan 15.15!
    Uppgiftslydelsen läggs upp på mästarprovssidan på kurswebben 26 september.

    Algoritmer. Muntliga redovisningar sker 14-20 oktober.

  • F20 11 oktober

    [SN] Reduktioner. (KT: 451-459)

  • Ö7 11 oktober

    Probabilistiska algoritmer. Reduktioner.

  • F21 13 oktober

    [SN] Introduktion till komplexitet, motivering. (KT: 463-466 hela sidan)

Period 2

  • F23 1 november

    [SN] Oavgörbarhet. (Sup: 49-73)

  • Ö8 3 november

    Genomgång av lösning till mästarprov 1. Oavgörbarhet.

  • Labb 3 4 november

    Flöden och matchningar, redovisning.

  • F24 8 november

    [VK] Cooks sats.

  • F25 9 november kl 8
    [VK] NP-fullständighetsbevis. (KT: 466-495)

  • F26 9 november kl 9

    [VK] NP-reduktionsvisualisering med Alvie (instruktioner).
    I Alvie finns reduktioner för delmängdssumma (Subset Sum) och hörntäckning (Vertex Cover) visualiserade och bevisade.
    Alvie är utvecklat av Pierluigi Crescenzi. Om du inte vill ladda ner Alvie själv kan du titta på reduktionsvisualiseringarna som filmer.

  • Ö9 10 november

    NP-fullständighetsbevis. Teoriredovisning för labb 4.

  • F27 15 november

    [SN] NP-fullständighetsreduktioner. (KT: 459-463)

  • F28 16 november

    [VK] Mer NP-fullständighetsreduktioner. (KT: 497-505)

  • Ö10 16 november

    NP-fullständiga problem.

  • Labb 4 18 november

    NP-fullständighetsreduktioner, redovisning.

  • F29 22 november

    [VK] Approximationsalgoritmer. (KT: 599-630)

  • F30 23 november

    [VK] Mer approximationsalgoritmer. (webbsida om Christofides algoritm)

  • Ö11 24 november

    Approximationsalgoritmer

  • F32 30 november

    [VK] Komplexitetsklasser. (KT: 495-497, 531-547)

  • Mästarprov 2, senast 6 december klockan 12.15!
    Uppgiftslydelsen läggs upp på mästarprovssidan på kurswebben senast 22 november.

    Komplexitet. Muntliga redovisningar sker 9-15 december.

  • F33 6 december

    [SN+VK] Repetition. Kursens betygssystem.

  • Ö12 8 december

    Komplexitetsklasser och repetition.

  • Extra labbredovisningstillfälle 13 december kl 13-15.
  • Teoritenta 19 december klockan 9-12 i sal D1 och F2.
  • Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt och muntligt i omtentaveckan i januari.
  • Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, i Spel- och Sporthallen 10 januari 2017 kl 14-17. I mån av tid kan också övriga labbar redovisas då. Ingen anmälan.
  • Frivillig munta för högre betyg, 10-12 januari 2017. Anmälan ska göras senast 6 januari 2017 på kurswebben.

Examination

Fyra labbar, två mästarprov och teoritenta krävs för godkänt. Betygsättningen är målrelaterad, se betygskriterierna på nästa sida. Alla resultat rapporteras i Rapp. För mer information om examinationen, se kurswebbens examinationssida.