Hoppa till huvudinnehållet

DD2542 Seminariekurs i teoretisk datalogi, algoritmer och komplexitet 7,5 hp

Kursen 2022 kommer handla om vad som på engelska kallas "concrete complexity".  Vi kommer studera absoluta övre och under gränser för kostnaden att lösa vissa beräkningsproblem i olika beräkningsmodeller.  Det innebär gränser som inte är beroende av ett antagande som t.ex att NP är skilt från P.

En väsentlig del av kursen kommer handla om resultat inom kretskomplexitet.    En preliminär lista på resultat som kommer behandlas finns här.  Exakt innehåll kommer beslutas tillsammans med kursdeltagarna under den första delen av kursen.

Välj termin och kursomgång

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

Rubriker med innehåll från kursplan DD2542 (HT 2021–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehåll

Kursens innehåll varierar från kursomgång till kursomgång. Exempel på ämnen är approximationsalgoritmer, databrytning, kryptografi, parallella beräkningar och probabilistiska algoritmer.

Lärandemål

Efter godkänd kurs ska studenten kunna

  • diskutera avancerade begrepp inom kursens område
  • aktivt attackera problem inom kursens område, både genom eget arbete och genom sökning av relevant information
  • tillgodogöra sig och presentera det väsentliga innehållet i vetenskapliga artiklar inom kursens område.

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet

Slutförd kurs i algoritmer och komplexitet motsvarande DD2350/DD2352.

Aktivt deltagande i kursomgång vars slutexamination ännu inte är Ladokrapporterad jämställs med slutförd kurs.

Den som är registrerad anses vara aktivt deltagande. Med slutexamination avses både ordinarie examination och det första omexaminationstillfället.

Rekommenderade förkunskaper

Kursen är öppen för alla, men huvudmålgruppen är avancerade masterstudenter och doktorander i datalogi och matematik.

Även om de formella behörighetskraven är ganska begränsade kommer kursdeltagarna att behöva matematisk mognad och en vilja att lära sig nya saker. Notera att detta är en krävande kurs. (Men förhoppningsvis just därför ännu roligare!)

Utrustning

Ingen information tillagd

Kurslitteratur

Ingen information tillagd

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

  • ÖVN1 - Övningsuppgifter, 7,5 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med 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.

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

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

Kurswebb

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

Kurswebb DD2542

Ges av

Huvudområde

Datalogi och datateknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Ingen information tillagd

Kontaktperson

Johan Håstad (johanh@kth.se)

Övrig information

Kursen ges normalt vartannat år (jämna år) i period 1. Undervisningsspråket är engelska.

Kursen har ersatt DD2442.