DD2458 Problemlösning och programmering under press 9,0 hp

Problem Solving and Programming under Pressure

För att framgångsrikt lösa olika datalogiska problem krävs både gedigna teoretiska kunskaper och förmåga att tillämpa dessa kunskaper i praktiken.

Denna kurs fokuserar på förmågan att tillämpa teoretiska kunskaper om algoritmer, datastrukturer och komplexitet på givna problem. Att snabbt kunna analysera ett problem, göra bedömningar av föreslagna algoritmers komplexitet och kunna implementera en lösning snabbt och korrekt är användbara förmågor i arbetslivet. I denna kurs tränas problemlösningsförmåga dels med ett antal omgångar med hemuppgifter och dels med tidsbegränsade problemlösningssessioner.

Notera att detta är en ovanligt intensiv och arbetstung kurs.

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

    Datalogi och datateknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

VT19 popup19 för programstuderande

HT19 popuph19 för programstuderande

Lärandemål

Kursens övergripande syfte är att studenterna dels ska kunna användaprogrammering som ett verktyg för problemlösning, dels kunna tillämpa teoretiska kunskaper från andra datalogikurser på praktisk problemlösning. Kursen har ett stort fokus på att gå hela vägen från teori (i form av algoritmdesign) till praktik (i form av ett fungerande program).

Efter godkänd kurs ska studenten kunna 

  • använda algoritmkonstruktionsmetoder som giriga algoritmer,  dynamisk programmering, dekomposition och kombinatorisk sökning för  att konstruera algoritmer i syfte att lösa givna problem, 
  • använda grundläggande algoritmer inom områden som t.ex.~grafteori,  talteori, och geometri på givna problem samt anpassa dem till  problemspecifika omständigheter, 
  • analysera effektiviteten hos olika algoritmer för att  avgöra vilka som i ett givet sammanhang är tillräckligt effektiva, 
  • jämföra olika problem med avseende på svårighetsgrad, 
  • implementera algoritmer och datastrukturer givet  abstrakta specifikationer, 
  • identifiera buggar i andras lösningsförsök på problem, 
  • kommunicera med andra under problemlösning i grupp, 
  • presentera algoritmer, datastrukturer och problem muntligt på ett koncist och begripligt sätt. 

Målen uppnås dels genom att studenten under kursens gång löser ett stort antal hemuppgifter, implementerar ett antal algoritmer för att bygga upp ett mindre algoritmbibliotek, löser problem i små grupper under "problemsessioner", samt presenterar lösningar på hemuppgifter.

Kursens huvudsakliga innehåll

Algoritmer: beräkningsgeometri, grafalgoritmer, talteoretiska algoritmer, strängmatchning. Algoritmanalys och algoritmkonstruktion: dynamisk programmering, amorterad analys, rimlighetsbedömningar. Programmeringsfärdigheter, framför allt i C++ och Java.

Behörighet

Någon av kurserna DD1352 Algoritmer, Datastrukturer och Komplexitet, DD2352 Algoritmer och Komplexitet, eller motsvarande.

Rekommenderade förkunskaper

DD2440 Avancerade Algoritmer

Litteratur

Meddelas senast 4 veckor före kursstart på kursens hemsida.

Examination

  • LAB1 - Programmeringstävlingar, 4,5, betygsskala: A, B, C, D, E, FX, F
  • ÖVN1 - Skriftliga uppgifter, 4,5, betygsskala: A, B, C, D, E, FX, F

Betyget baseras på antalet lösta uppgifter av de olika sorterna, samt, i en viss utsträckning, på att presentationerna håller god kvalitet. Genom att uppgifterna har starkt varierande svårighetsgrad, kommer den som löser många uppgifter också, per automatik, lösa ett antal svårare uppgifter, vilket motiverar ett högre betyg. För betyg A behöver man dessutom lösa ett visst antal extra svåra uppgifter.

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Krav för slutbetyg

Examination kan endast ske i samband med pågående kursomgång.

Ges av

EECS/Datavetenskap

Kontaktperson

Per Austrin, e-post: popup-17@csc.kth.se

Examinator

Per Austrin <austrin@kth.se>

Övrig information

Deltagarantalet är begränsat till 25.

Kursen ges endast i mån av lärarresurser.

Påbyggnad

Diskuteras med kursledaren.

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.