Algorytmika przestrzeni metrycznych 1000-2M25APM
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
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Założenia (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
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).
Kryteria oceniania
Trzy serie prac domowych, których wynikiem jest modyfikator z przedziału [-1, 1.5] do egzaminu ustnego. Egzamin ustny.
Literatura
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
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: