EP3360 Algoritmer för nätverk - Komplexitet och approximationer 8,0 hp

Algorithms for Networks - Complexity and Approximations

Kursen behandlar grunderna i komplexitetsteori och algoritmdesign med tillämpningar inom nätverkssystemoptimering och sekventiell beslutsfattande. Kursen är avsedd för doktorander som forskar inom IT-området, och det förbereder studenterna att använda rigorösa metoder för att bevisa komplexitet av optimeringsproblem och för att konstruera approximationsalgoritmer med bevisbara prestanda gränser för beräkningsmässigt svårlösta problem.

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Information för forskarstuderande om när kursen ges

Kursen ges i vartannat år, i P2.

Lärandemål

Efter kursen ska studenten kunna:

-       definiera klassen av beräkningskomplexitet i ett korrekt sätt och analysera komplexa algoritmer;

-       diskutera grundläggande problem inom områdena av grafteori, mängd och partitioner, lagring och schemaläggning;

-       formulera nätverkskonstruktionsproblem som beslut- eller diskreta optimeringsproblem;

-       presentera förfaranden för att bevisa NP-fullständighet och NP-hårdhet, och kunna bevisa några grundläggande exempel;

-       använda approximationsalgoritmer att hantera NP-svåra problem. 

Kursens huvudsakliga innehåll

1.      Problem, algoritmer och komplexitet, polynomtid, NP-fullständiga och NP-svåra problem

2.      Exempel på polynomisk tid problem på grafer, giriga algoritmer, användning för nätverk design. 

3.      Kända NP-fullständiga problem, bevis på NP fullständighet, problem utanför NP

4.      Polynomtids-reducering, NP-svåra problem, användning för nätverk design

5.      Approximationsmetoder och algoritmer - giriga strategi, begränsning, partition

6.      Approximationsmetoder och algoritmer – relaxation, primal-dual schema och local ratio

7.     Bevis på komplexitet och algoritmdesign för nätverksproblem baserad på ny litteratur 

Kursupplägg

8 föreläsningar, 2 seminarier med studentpresentationer , 3 hemuppgifter, tentamen. 

Behörighet

PhD student

Litteratur

-        J. Kleinberg, É. Tardos, “Algorithm Design” Pearson Education, 2014

-        Ding-Zhu. Du Ker-I Ko; Xiaodong Hu, “Design and Analysis of Approximation Algorithms”, Springer Optimization and Its Applications vol 62

-        Utdrag av M.R. Garey and D.S.Johnson, “Computers and Intractability,” W. H. Freeman, 1979

-        Relevanta tidskriftsartiklar med nätverksapplikationer, angivna före kursstart. 

Examination

  • EXA1 - Tentamen, 8,0, betygsskala: P, F

Krav för slutbetyg

-        Aktivt deltagande på föreläsningarna

-        30 min muntliga presentation på ett av seminarierna

-        80% på hemuppgifter

-        80% på tentamen

Ges av

EECS/Nätverk och systemteknik

Examinator

Viktoria Fodor <vjfodor@kth.se>

Versionsinformation

Kursplan gäller från och med HT2016.
Examinationsinformation gäller från och med VT2019.