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

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 

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. 

PhD student

-        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. 

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

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.

-        Aktivt deltagande på föreläsningarna

-        30 min muntliga presentation på ett av seminarierna

-        80% på hemuppgifter

-        80% på tentamen

Viktoria Fodor

• 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.