Kursens innehåll varierar från kursomgång till kursomgång. Exempel på ämnen är approximationsalgoritmer, databrytning, kryptografi, parallella beräkningar och probabilistiska algoritmer.
DD2542 Seminariekurs i teoretisk datalogi, algoritmer och komplexitet 7,5 hp
Kursomgången 2024 kommer handla om approximerbarhet av NP-svåra optimeringsproblem. Detta är samma ämne som 2020, men troligen kommer vissa justeringar göras, delvis i samråd med kursdeltagarna.
Om ett optimeringsproblem är NP-svårt så innebär det, under antagandet att NP inte är lika med P, att det inte går att lösa exakt i polynomiell tid. Man studerar därför effektiva approximationsalgoritmer som är garanterade att hitta en lösning inom en given faktor av optimalt. Kursen kommer diskutera två typer av resultat.
Algoritmiska resultat där vi designar en algoritm för ett givet problem och visar att den har eftertraktade egenskaper. Typiskt att den går i polynomiell tid och hittar en lösning som är optimal inom en given faktor. Generella metoder baserade på linjärprogrammering och semi-definit programmering kommer att studeras. Vi kommer studera grundläggande problem som maximal skärning, största oberoende mängd och villkors satifiering.
Vi kommer även studera svårighetsresultat. Detta innebära att visa att för vissa problem så förblir det NP-svårt att hitta även en approximativ lösning av god kvalité. Många resultat av denna typ bygger på PCP-satsen som visar att varje problem i NP har ett kort bevis som kan verifieras av en probabilistisk verifierare som bara läser att konstant antal bitar. Vi kommer studera beviset av PCP-satsen samt ge flera exempel på hur man använder detta för att visa svårighetsresultat.
Information per kursomgång
Information för HT 2024 semteo24 programstuderande
- Studielokalisering
KTH Campus
- Varaktighet
- 2024-08-26 - 2024-10-27
- Perioder
- P1 (7,5 hp)
- Studietakt
50%
- Anmälningskod
50547
- Undervisningsform
Normal Dagtid
- Undervisningsspråk
Engelska
- Kurs-PM
- Kurs-PM är inte publicerat
- Antal platser
Min: 10
- Målgrupp
Valbar för studenter antagna till masterprogram.
- Planerade schemamoduler
- [object Object]
- Schema
Kontakt
Johan Håstad (johanh@kth.se)
Kursplan som PDF
Notera: all information från kursplanen visas i tillgängligt format på denna sida.
Kursplan DD2542 (HT 2021–)Rubriker med innehåll från kursplan DD2542 (HT 2021–) är markerade med en asterisk ( )
Innehåll och lärandemål
Kursinnehåll
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.
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
Kursrum i Canvas
Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.
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.