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.
Välj termin och kursomgång
Välj termin och kursomgång för att se aktuell information och mer om kursen, såsom kursplan, studieperiod och anmälningsinformation.
Kursval
Gäller för kursomgång
HT 2024 semteo24 programstuderande
Anmälningskod
50547
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.
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
Kurslitteratur
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
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
Möjlighet till plussning
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
Ges av
Huvudområde
Utbildningsnivå
Påbyggnad
Kontaktperson
Övrig information
Kursen ges normalt vartannat år (jämna år) i period 1. Undervisningsspråket är engelska.
Kursen har ersatt DD2442.