Algorytmika przestrzeni metrycznych

fakultatywne

Algorytmy i struktury danych 1000-213bASD

Algorytmika 1000-2N00ALG

Wykład ma na celu zaznajomienie studentów z problemami optymalizacyjnymi związanymi z przestrzeniami metrycznymi. Szczególny nacisk położony będzie na algorytmy aproksymacyjne.

1. Algorytmy aproksymacyjne w grafach planarnych.

2. Programowanie liniowe. Problem Facility Location.

3. Zanurzenia metryczne. Algorytm FRT dla zanurzania w metryki drzewiaste.

4. Klastrowanie. Algorytm k-means++

5. Metryki euklidesowe. Coreset dla problemu k-means.

6. Redukcja wymiaru. Lemat Johnsona-Lindenstraussa

7. Algorytm Arory dla problemu komiwojażera w metryce euklidesowej.

8. Algorytmy w przestrzeniach z ograniczonym doubling dimension

9. Zanurzenia grafów w metrykę L1. Problem Sparsest Cut

1. The Design of Approximation Algorithms, D. P. Williamson, D. B. Shmoys, Cambridge University Press 2012

2. Foundations of Data Science, A. Blum, J. Hopcroft, R. Kannan, Cambridge University Press 2020

Wiedza

1. Rodzaje przestrzeni metrycznych i ich własności (K_W04)

2. Teoria zanurzeń metrycznych (K_W04)

3. Algorytmy aproksymacyjne dla problemu komiwojażera w różnych rodzajach

metryk (K_W01, K_W05)

4. Algorytmy aproksymacyjne dla problemów klastrowania (K_W01, K_W05)

5. Algorytmy preprocessingu dla problemów klastrowania (K_W01, K_W05)

Umiejętności

1. Student potrafi sformalizować zagadnienia optymalizacyjne takie jak

klastrowanie (K_U01, K_U03)

2. Student potrafi projektować algorytmy w oparciu o programowanie liniowe,

programowanie dynamiczne, zanurzenia metryczne i inne techniki (K_U05)

3. Student potrafi analizować współczynniki aproksymacji algorytmów (K_U03)

Kompetencje

1. Student jest gotowy do twórczego i innowacyjnego podejścia do

rozwiązywania problemów z zakresu algorytmów klastrowania w

przestrzeniach metrycznych (K_K03).

Trzy serie prac domowych, których wynikiem jest modyfikator z przedziału [-1, 1.5] do egzaminu ustnego. Egzamin ustny.