DD2350 Algoritmer, datastrukturer och komplexitet 9,5 hp

Algorithms, Data Structures and Complexity

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.

Visa kursinformation utifrån vald termin och kursomgång:

Kursomgång och genomförande

Ingen kursomgång är vald

Välj termin och kursomgång ovan för att få information från rätt kursplan och kursomgång.

Kursinformation

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.

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet *

Programmering och datalogi motsvarande DD1338/DD1320/DD1321/DD1325/DD1327/DD1339/ID1020.

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. Diskret matematik motsvarande SF1671 och SF1688 eller någon av SF1630, SF1662, SF1679 (kan läsas parallellt). Sannolikhetsteori och statistik motsvarande SF1901. Logik motsvarande DD1350/DD1351 rekommenderas men är inte nödvändigt.

Utrustning

Ingen information tillagd

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.


Meddelas senast 10 veckor före kursstart på kurswebben.

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.

Om särskilda skäl finns kan annan examinationsform användas.
I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex

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.

Examinator

Viggo Kann

Ytterligare information

Kurswebb

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

Kurswebb DD2350

Ges av

EECS/Datavetenskap

Huvudområde *

Datalogi och datateknik

Utbildningsnivå *

Avancerad nivå

Påbyggnad

DD2440 Avancerade algoritmer, DD2442 Seminariekurs i teoretisk datalogi, DD2445 Komplexitetsteori, DD2448 Kryptografins grunder, DD2458 Problemlösning och programmering under press.

Kontaktperson

Viggo Kann (viggo@kth.se)

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.

Övrig information

Betygskriterier meddelas vid kursstart.

Kursen har ersatt DD1352. DD2350 kan inte kombineras med DD1352, DD2352 eller DD2354.

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