Hoppa till huvudinnehållet

DD2350 Algoritmer, datastrukturer och komplexitet 9,5 hp

Kurs-PM HT 2020-51571

Version 2 – 2020-12-10 11:35:17

Kursomgång

HT 2020-1 (Startdatum 2020-08-24, Svenska)

Undervisningsspråk

Svenska

Kursen ges av

EECS/Datavetenskap

Kurs-PM HT 2020

Presentation av kursen

Denna kurs ger en introduktion till teoretisk datalogi som är ett starkt forskningsområde på KTH. Du kommer att stöta på några av våra forskningsresultat i kursen.

Du får lära dig mer om algoritmkonstruktion och får se några ganska komplicerade, men mycket användbara, algoritmer. Komplexitetsdelen av kursen handlar om hur man undersöker vilka problem som kan lösas (i rimlig tid) med datorns hjälp, vilka som tar orimligt lång tid och vilka som inte kan lösas med en dator över huvud taget.

Problem som är för svåra för att lösa exakt kan ibland lösas approximativt. Du kommer att få se exempel på några approximationsalgoritmer och några problem som är så svåra att dom inte ens kan approximeras i rimlig tid.

Rubriker markerade med en asterisk ( * ) kommer från kursplan version HT 2020

Innehåll och lärandemål

Kursinnehåll

Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering, lokal och total sökning. Algoritmanalys. Approximationsalgoritmer och heuristiker. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri. Implementation av algoritmer.

Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd, bloomfilter. Användning och implementation av datastrukturer. Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid). NP-fullständiga problem, oavgörbara problem. Hur man kan hantera problem med hög komplexitet.Ämnesterminologin på svenska och engelska.

Lärandemål

Efter fullgjord kurs ska studenten kunna:

  • utveckla och implementera algoritmer med datastrukturer och analysera dem med avseende på korrekthet och effektivitet,
  • jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet,
  • definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet,
  • jämföra problem med hänsyn till komplexitet med hjälp av reduktioner,
  • hantera problem med hög komplexitet

i syfte att

  • självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne,
  • i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

Läraktiviteter

Kursen består av 33 föreläsningar och 14 ö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 ett tillfälle 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. 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å videor ska ses och uppgifter ska göras före dessa föreläsningar.

Detaljplanering

  • 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

  • Ö1 28 augusti
    Algoritmanalys.
  • Ö5 24 september
    Grafalgoritmer och undre gränser.
  • Labb 2 25 september
    Rättstavning, redovisning.

Sammanfattning av alla algoritmer hittills i kursen.

  • Ö7 7 oktober
    Probabilistiska algoritmer. Reduktioner.
  • Mästarprov 1, senast onsdag 7 oktober klockan 19!
    Uppgiftslydelsen läggs upp i Canvas 23 september.

    Algoritmer. Muntliga redovisningar sker 12-16 oktober.

Period 2

  • F23 27 oktober
    [SN] Oavgörbarhet. (Sup: 49-73)
    <inspelning saknas>
  • Ö8 29 oktober (endast grupp 2-4, den lite enklare gruppen är inställd)
    Genomgång av lösning till mästarprov 1. Oavgörbarhet.
  • Labb 3 30 oktober
    Flöden och matchningar, redovisning.
  • Labb 4 13 november
    NP-fullständighetsreduktioner, redovisning.
  • Mästarprov 2, senast 3 december klockan 15!
    Uppgiftslydelsen läggs upp i Canvas 19 november.

    Komplexitet. Muntliga redovisningar sker 7-11 december.

  • Ö12 2 december (endast grupp 2-4, den lite enklare gruppen är inställd)
    Komplexitetsklasser och repetition.
  • Labb 5 4 december
    Heuristik för rollbesättningsproblemet, redovisning. Bokningslistor publiceras i Canvas 3 december.
  • Extra labbredovisningstillfälle 11 december för alla labbar, inklusive högrebetygslabben. Bokningslistor publiceras i Canvas 9 december.
  • Teoritenta 15 december klockan 9-12. Skrivtid 9:00-10:30 i Canvas. Obligatorisk rättningssession kl 11:00-12:00 i Zoom.
  • Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 15 december och redovisas skriftligt 4 januari och muntligt veckan 7-11 januari 2021.
  • Frivillig munta för högre mästarprovsbetyg, 13 och 15 januari 2021. Muntan genomförs på KTH. Anmälan görs under perioden 31 december 2020 till 6 januari 2021. 
  • Redovisning av högrebetygslabben Heuristik för rollbesättningsproblemet (inga andra labbar kan redovisas), 12 januari 2021 kl 9-12. Bokningslistor publiceras i Canvas 31 december.

Efter period 2 är kursen slut. Den som har labbar kvar att redovisa kan göra det antingen i labbveckan i juni eller på labbpassen i systerkursen DD2352 Algoritmer och komplexitet. Säg till den du redovisar för att du ska ha labben rapporterad på adk20.

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äg till den du redovisar att du ska ha mästarprovet rapporterat på adk20.

Den som har tentan kvar kan gå upp på omtentan 9 april 2021 kl 14:00-17:00 eller nästa ordinarietenta i december 2021.

Kursens pedagogiska upplägg

  • Studera på det sätt som är effektivast för dig! 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! I vissa avsnitt av kursen används omvänd undervisning (flipped classroom).
  • Övningsuppgifter med fullständiga lösningar. Övningsgrupper med svårighetsgradering. Ett urval av uppgifterna löses på övningarna, resten lämnas för egen övning.
  • Momenten i kursen tränar verkliga arbetssituationer för bättre autenticitet.
  • Aktiverande färgfrågor på föreläsningarna och kontinuerlig examination med labbteoriuppgiftsredovisning inför varje datorlabb gör att du automatiskt hänger med i kursen.
  • Du förbereds väl för mästarproven med övningsmästarprov, bedömningskriterier och autentiska exempel på tidigare studentinlämningar med kommentarer.
  • 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.

Nyckelbegrepp

Svensk-engelsk ADK-ordlista

Här är 50 facktermer i ADK-kursen som inte har en uppenbar direktöversättning.

algoritm algorithm
approximationskvot approximation ratio
approximerbarhet approximability
beräkningsbarhet computability
beräkningsmodell computational model
beslutsproblem decision problem
bitkostnad bit cost
datastruktur data structure
dekomposition divide and conquer
delmängdssumma subset sum
dynamisk programmering dynamic programming
enhetskostnad unit cost
förberäknad (funktion) precomputed (function)
girig algoritm greedy algorithm
grafgenomgång graph traversal
grannlista adjacency list
grannmatris adjacency matrix
heuristik heuristics
hörn vertex
ickedeterministisk non-deterministic
kant edge
kantmatris incidence matrix
komplexitet complexity
konjunktiv normalform conjunctive normal form
konstruktionsproblem construction problem
källa source
latmanshashning lazy hashing (ingen standardterm)
målfunktion objective function
mängdpartitionering partition problem
mästarsatsen Master theorem
NP-fullständig NP-complete
oavgörbar undecidable
oberoende mängd independent set
optimeringsproblem optimization problem
polynomisk reduktion polynomial reduction
polynomisk tid polynomial time
prioritetskö priority queue
probleminstans problem instance
rekursivt uppräknelig recursively enumerable
restkapacitet residual capacity
rimlig tid feasible time
räknesortering counting sort
satisfierbar satisfiable
simulerad härdning simulated annealing
slumpeliminering derandomization
spännande träd spanning tree
totalsökning exhaustive search
tuff motståndare adversary
undre gräns lower bound
utlopp sink
verifierbar verifiable
övre gräns upper bound

Förberedelser inför kursstart

Rekommenderade förkunskaper

För vissa av kursens labbar måste ett snabbare programspråk än Python användas, varför kunskaper i Java eller C/C++ rekommenderas.

Den som bara läst diskret matematik i SF1671 behöver läsa kursen SF1688 parallellt med DD2350. Diskretmattekursen DD1610 räknas som ekvivalent med SF1662 i behörighetshänseende.

Sannolikhetsteori och statistik motsvarande SF1901 rekommenderas. Logik motsvarande DD1350/DD1351 rekommenderas men är inte nödvändigt.

Kurslitteratur

  • Algorithm Design av Kleinberg-Tardos, Pearson, 2014, ISBN 978-1292023946.

  • Det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126. Säljs bara på kårbokhandeln.

Examination och slutförande

Betygsskala

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

Examination

  • LAB1 - Laborationsuppgifter, 4,0 hp, Betygsskala: A, B, C, D, E, FX, F
  • MAS1 - Individuellt mästarprov, 1,5 hp, Betygsskala: A, B, C, D, E, FX, F
  • MAS2 - Individuellt mästarprov, 1,5 hp, Betygsskala: A, B, C, D, E, FX, F
  • TEN1 - Teoritentamen, 2,5 hp, Betygsskala: P, F

Examinator beslutar, baserat på rekommendation från KTH:s samordnare för funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Avsnittet nedan kommer inte från kursplanen:

Kursens examination bygger helt på kursens målrelaterade betygskriterier.

Kursen har fyra obligatoriska moment i Ladok:

  • LAB1, datorlaborationer, 4 hp, graderat betyg A-F
  • MAS1, mästarprov 1, 1,5 hp, graderat betyg A-F
  • MAS2, mästarprov 2, 1,5 hp, graderat betyg A-F
  • TEN1, tenta, 2,5 hp, ograderat betyg P/F

Nedan finns detaljerad information om dessa moment.

Identitetskontroll

Vid både labbredovisningar och mästarprovsredovisningar kommer vi att be dig visa legitimation så att vi är säkra på vem som examineras.

Laborationer

Fem obligatoriska datorlabbar ingår i kursen. Dessa utgör momentet LAB1. Labbarna ska göras i tvåpersonsgrupper, men enpersonsgrupper kan godkännas av kursledaren i undantagsfall. Den betygshöjande delen på labb 5 måste dock göras individuellt. Varje labb som redovisas och godkänns senast det labbtillfälle som finns angivet på labben ger en så kallad labbleveranspoäng. Den som fått 4-5 labbleveranspoäng (dvs har levererat minst fyra av labbarna i tid) får betyg C på momentet LAB1. Den som får 2-3 labbleveranspoäng får betyg D. Betyg C kan höjas till betyg A eller B med den betygshöjande extralabben som är en påbyggnad på labb 5, som ska göras och redovisas individuellt vid ett speciellt labbredovisningstillfälle i januari.

På varje labb finns dessutom ett antal frivilliga teoriuppgifter. Teoriuppgifterna redovisas skriftligt och muntligt på övningstillfällen (ingen annan möjlighet till redovisning ges) och ger en teoripoäng var, som ger bonus på tentorna under närmaste läsåret.

Det finns schemalagda labbtillfällen under hela kursen. Det kommer att finnas handledare tillgängliga på dessa labbpass. Börja att göra labbarna i god tid och fråga handledarna om du får problem. Du kan i princip redovisa alla labbarna vid alla labbtillfällen, men under det sista labbtillfället för varje labb, som är fyra timmar långt, prioriteras redovisningar av den labben.

Under Uppgifter i Canvaskursrummet ligger labbinstruktionerna.  Labbarna genomförs i år på distans, se instruktionerna till första labben.

Individuella uppgifter: mästarprov

Två obligatoriska individuella uppgifter, mästarprov, kommer att ges. Dessa ska lösas individuellt och redovisas både skriftligt och muntligt. Skriftliga lösningar till dessa uppgifter ska lämnas in i Canvas senast den tid som anges på uppgiftslydelsen. Den muntliga redovisningen kommer att ske några dagar senare för någon av assistenterna på en tid som ska bokas i förväg i Canvas.

Varje mästarprov består av tre uppgifter av olika svårighetsgrad som testar betygskriterierna för E, C respektive A.

Inför varje mästarprov ges ett frivilligt övningsmästarprov som kan lösas i grupp och som redovisas vid speciella mästarprovsövningar, se detaljschemat. Godkänd redovisning av ett övningsmästarprov ger en teoripoäng. Totalt kan alltså två teoripoäng fås från mästarprovsövningar.

Den som inte godkänts på ett mästarprov får möjlighet att göra ett nytt i slutet av kursen, men kan då bara få betyg E på mästarprovet. Dessa ommästarprov läggs upp i Canvas i samband med ordinarie teoritentan och ska redovisas både skriftligt och muntligt i omtentaveckan i januari.

Du kan se dina resultat på redovisade uppgifter i kursen under Omdömen i Canvas.

Teoritenta

Ordinarietentan går den 15 december klockan 9-12. Skrivtid 9:00-10:30. Obligatorisk rättningssession kl 11:00-12:00. Första omtentatillfälle är i påskperioden. 

Tentan (momentet TEN1) är en teoritenta som görs på distans i ett speciellt examinationsrum i Canvas (som kommer att vara tillgängligt för alla anmälda till tentan) och lämnas in i Peergrade. Alla hjälpmedel (som publicerats eller skrivits innan tentan börjar) är tillåtna. Under skrivtiden får tentanden inte kommunicera om tentan med någon annan än en lärare på kursen.

Tentans uppgifter är alla på E-nivå, dvs det går inte att få mer än godkänt på tentan. För godkänt krävs minst 13 av 14 poäng inklusive poäng på uppgifter som visar uppfyllelse av lärandemålet definiera och översätta centrala begrepp. Den som får 11 eller 12 poäng eller som får minst 13 poäng men har missat måluppfyllelsen får möjlighet att komplettera till godkänt. Teoripoängen som samlats genom labbteoriredovisningar (upp till 5 teoripoäng) och övningsmästarprov (upp till 2 teoripoäng) läggs till poängen på teoritentan på alla tentor inom ett år från kursstart.

Teoritentans uppgifter testar följande betygskriterier på nivå E:

  • analysera algoritmer med avseende på effektivitet: förklara principerna, analysera enklare algoritmer
  • jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet
  • definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet
  • jämföra problem med hänsyn till komplexitet med hjälp av reduktioner: förklara principerna
  • förklara hur man kan hantera problem med hög komplexitet: förklara principerna

Vi rekommenderar alla att titta på senaste årens extentor för att bättre förstå hur uppgifterna kan se ut. Lösningsförslag finns bara till ordinarietentorna. Notera att på tentorna för kurskoden DD1352 är det bara E-uppgifterna som motsvarar uppgifter på teoritentan för DD2350. Det finns ett övningsquiz på begrepp och definitioner inför teoritentan.

Skrivtiden är 90 minuter. Direkt efter tentan vidtar en obligatorisk genomgång, i Zoom, av lösningarna till tentan och kamraträttning. Rättningen kontrolleras sedan av lärarna och resultatet kungörs förhoppningsvis samma dag. Klagomål på rättning av tentan görs till kursledaren. Kursledaren avgör hur och när kompletteringsuppgifter ska redovisas.

Tentaanmälan ska göras som vanligt.

Varför kamraträttning?

  • Det är bra för lärandet att få återkoppling i direkt anslutning till examinationen.

  • Att sätta sig in i någon annans lösningar och tankesätt är lärorikt.

  • Du får insikt i hur bedömning av tentor går till och vilka överväganden rättande lärare behöver göra.

  • Betygsättningen snabbas upp. Resultatet är klart samma dag!

Att tänka på vid kamraträttningen

  • Rättningssessionen är en obligatorisk del av tentan och närvaron kontrolleras i Zoom.

  • Du bedömer en annan students arbete. Var och en förtjänar en korrekt bedömning. Följ därför rättningsmallen och rättningsanvisningarna så gott du kan.

  • Om du är osäker på bedömningen av en uppgift går det bra att fråga. Om du fortfarande är osäker efter frågestunden skriver du ett frågetecken efter eller istället för din bedömning av uppgiften.

  • Var saklig och professionell. Gör inte narr av en lösning och skratta inte åt en lösning eller någon annans fråga under kamraträttningssessionen.

Muntlig tenta och slutbetyg

Den som fått godkänt på labbarna, båda mästarproven och teoritentan får godkänt på kursen. Slutbetyget bestäms som ett oviktat genomsnitt av betygen på samtliga tre betygsatta moment (MAS1, MAS2, LAB1), eventuellt kompletterat med en muntlig tenta och/eller en högrebetygslabb, se betygskriterierna

Exempel: 

betyg på MAS1, MAS2, LAB1 ger slutbetyg
E, E, C D
E, C, B C
C, A, A B

Den som är godkänd på båda mästarproven och har fått minst betyg C på det ena (eller har klarat E- och A-uppgifterna på mästarprov 2) har möjlighet att gå upp på en muntlig tenta för att få högre betyg på mästarproven. Den muntliga tentan kan efter teoritentan bokas in (i Canvas) på tider i tentaveckan i januari 2020. Vid den muntliga tentan kommer läraren att kontrollera att du uppfyller betygskriterierna för det betyg du aspirerar på. Kursböckerna (men inga kompendier eller anteckningar) är tillåtna hjälpmedel.

Möjlighet till komplettering

Betyget Fx kan kompletteras till E/godkänt för momenten MAS1, MAS2 och TEN1. Enskilda laborationer kan tillgodoräknas senare kursomgångar så länge laborationsuppgiften är oförändrad.

Möjlighet till plussning

Det är tillåtet att plussa mästarprovsbetygen i en senare kursomgång. Det är också tillåtet att plussa labbetyget från C eller B med den betygshöjande labben i en senare kursomgång. Däremot går det inte att få nya labbleveranspoäng i en senare kursomgång.

Restmoment

Läs denna sida om du har uppgifter kvar att redovisa efter kursens slut.

Hederskodex

I denna kurs tillämpas EECS hederskodex, se: http://www.kth.se/eecs/utbildning/hederskodex

Arbetssituationer

Det är meningen att arbetet med momenten i kursen ska motsvara olika arbetssituationer i arbetslivet.

Labbarna tränar olika typer av programutvecklingsarbete:

  • I labb 1 ska du programmera efter en funktionsspecifikation.
  • I labb 2 ska du programmera om ett existerande program så att det fungerar likadant fast effektivare.
  • I labb 3 ska du programmera efter en detaljerad algoritmisk specifikation.
  • I labb 5 ska du attackera ett problem som inte kan lösas optimalt.

I alla labbar finns noggranna beskrivningar av format för indata och utdata. Alla labbar har givna effektivitetskrav och utförs som lagarbete (labbgrupper), precis som i arbetslivets agila parprogrammeringsprojekt. I labb 1 är parprogrammering obligatoriskt att använda.

Mästarproven tränar expertsituationen, alltså situationen som den som vet mest om något på en arbetsplats ställs inför när hen får ett problem: det finns ingen att fråga, så hen måste komma fram till svaret med egen tankekraft och genom att läsa litteratur. När problemet är löst ska experten förklara lösningen för chefen, både skriftligt och muntligt.

Tentan liknar tyvärr ingen verklig arbetssituation, men den följs av en kamraträttningssession som är mycket värdefull ur ett pedagogiskt perspektiv. Labb 4 har också en konstruerad arbetssituation; den är dock mycket värdefull för begreppsförståelsen.

Målrelaterade betygskriterier/bedömningskriterier

mål E D C B A
utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod för icketriviala problem givet ledtråd för icketriviala problem [A-kriteriet] givet ledtråd för svårare problem med den metod som passar bäst
examineras med labbar (för nivå E), mästarprov 1 och muntlig tenta
implementera algoritmer med datastrukturer efter funktionsspecifikation och efter detaljerad algoritmisk specifikation, med hänsyn taget till effektivitet med vissa krav på leveranstid med höga krav på leveranstid
examineras med labbar
analysera algoritmer med avseende på effektivitet förklara principerna, analysera enklare algoritmer analysera svårare algoritmer givet ledtråd analysera svårare algoritmer
examineras med labbar och teoritenta (för nivå E), mästarprov 1 och muntlig tenta
analysera algoritmer med avseende på korrekthet förklara principerna, förklara ett givet korrekthetsbevis framställa grundläggande idé för korrekthetsbevis framställa grundläggande idé och givet ledtråd genomföra fullständiga korrekthetsbevis [A-kriteriet] givet ledtråd genomföra fullständiga korrekthetsbevis med invarianter
examineras med mästarprov och muntlig tenta
jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet 
examineras med labbar, teoritenta och mästarprov 1
definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet 
examineras med teoritenta och mästarprov 2
jämföra problem med hänsyn till komplexitet med hjälp av reduktioner förklara principerna, utföra enklare reduktioner mellan givna problem [C-kriteriet] givet ledtråd visa NP-fullständighet eller oavgörbarhet [A-kriteriet] givet ledtråd utföra konstruktionsreduktioner
examineras med teoritenta och labb 4 (för nivå E), mästarprov 2 och muntlig tenta
förklara hur man kan hantera problem med hög komplexitet

förklara principerna,

konstruera enkla heuristiker

konstruera och analysera heuristiker konstruera och analysera mer avancerade heuristiker
examineras med teoritenta och labb 5 (för nivå E) och betygshöjande extralabb (för A och B)

Kursen har tre graderade Ladokmoment: MAS1 (individuellt mästarprov 1), MAS2 (individuellt mästarprov 2) och LAB1 (datorlabbar). TEN1 (teoritentan) har inte graderat betyg.

Slutbetyget är medelbetyget (oviktat) av de tre graderade betygen, avrundat till närmaste betyg.

Möjlighet till komplettering

Betyget Fx kan kompletteras till E/godkänt för momenten MAS1, MAS2 och TEN1. Enskilda laborationer kan tillgodoräknas senare kursomgångar så länge laborationsuppgiften är oförändrad.

Möjlighet till plussning

Plussning är tillåtet för MAS1 och MAS2. För LAB1 kan plussning endast göras från betyg B och C.

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare Information

Ändringar inför denna kursomgång

Alla föreslagna förändringar i senaste kursanalysen har genomförts. Majoriteten av förändringarna baseras på studentsynpunkter och studentförslag. Sedan föregående kursomgång, adk19, har följande ändrats:

  • Några specifika labbteoriuppgifter och oklarheter i lydelsen till labb 1 har förtydligats.
  • Testfallen och tidsgränsen för labb 2 har justerats så att det inte krävs mer än algoritmiska optimeringar för att klara tidsgränsen. Testfallen till labb 5 har korrigeras så att dom följer specifikationen exakt.
  • Alla assistenter har genomgått pedagogisk utbildning.
  • Övningarna kommer att ha fler studentaktiva moment.
  • Autentiska studentlösningar med olika betyg på tidigare mästarprov med kommenterade bedömningsprotokoll finns tillgängliga.
  • Övningsquiz i Canvas som övar på begrepp och definitioner inför teoritentan har utvecklats.
  • Före teoritentan kommer information att skickas ut som tydliggör att det är det nedskrivna som bedöms på tentan, och att det är viktigt att läsa tentauppgifterna noggrant.
  • Ytterligare två föreläsningar (reduktioner och introduktion till komplexitet) kommer att ha omvänd undervisning.
  • Alla föreläsningsbilder har digitaliserats.
  • Kursen ges med distansundervisning och distansexamination. Teoritentan genomförs inte som en traditionell övervakad skriftlig tenta utan som ett datorquiz med en efterföljande rättningssession i Zoom.

Kursvärdering och kursanalys

I början av kursen kommer två kursansvariga studenter att utses, som du kan ta kontakt med om du har synpunkter på kursen. Du kan också vända dig direkt till någon av lärarna med synpunkter.

Efter teoritentan kommer en kursenkät att skickas ut till kursdeltagarna.  Efter kursens slut kommer kursledarna, i samråd med kursansvariga studenterna, att göra en kursanalys som publiceras på kurswebben.

Kursanalys för adk19

Tidigare kursanalyser finns upplagda på sidan kursens utveckling och historik.

Zoomlänkar

Länk till Viggos föreläsningar: https://kth-se.zoom.us/j/66455760375

Länk till Stefans föreläsningar: https://kth-se.zoom.us/j/65855882630

Vilken föreläsning som har vilken föreläsare framgår av detaljplaneringen.

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

Övningsassistent Gruppens nivå Zoomlänk till övning Anmärkning
Douglas Wikström lite enklare grupp https://kth-se.zoom.us/j/62495765235 Denna grupp ställs in vid från och med  Ö8.
David Avellan-Hultman normalsvår grupp

https://kth-se.zoom.us/j/64904044709

 

Alice Heavey normalsvår grupp

https://kth-se.zoom.us/j/5724311699

 

Marcus Dicander lite svårare grupp  https://kth-se.zoom.us/j/62211833174  

Det finns också ett antal ytterligare personer som är labbhandledare och tar emot mästarprovsredovisningar: Anton Hampus, Christian Lidström, Herman Karlsson, Ilaria Carannante, Joakim Blikstad, Kilian Risse, Lisa Vällfors, Lukas Widén, Moa Andersson.

När du labbar skapar du ditt eget Zoomrum för din labbgrupp som ni arbetar i. Vid labbarna lägger ni in ert Zoomrums länk i kösystemet (alternativt redovisningsbokningssystemet) för att labbhandledaren ska hitta till ert rum. Mer information finns i labbinstruktionerna till labb 1.

Vid mästarprovsredovisningarna har varje assistent sitt eget Zoomrum som kommer att publiceras när bokningslistorna läggs upp.

Kursansvarig

Lärare

Examinator

Fakta om kursomgång

Startdatum

2020-08-24

Kursomgång

  • HT 2020-51571

Undervisningsspråk

Svenska

Kursen ges av

EECS/Datavetenskap

Kontakter

Kursansvarig

Lärare

Examinator