Zanurzenia metryczne

Prowadzący

Marcin Kotowski


marcin.kotowski1@gmail.com

Opis


Wyobraźmy sobie, że mamy mapę Warszawy wyposażoną w czasy dojazdu. Chcemy narysować te mapę uwzględniając owe czasy (krótszy dojazd = krótsza odległość na mapie). Czy da się to zrobić bez zniekształceń, skoro odległość "czas dojazdu" jest zazwyczaj różna od fizycznej odległości dwóch punktów?

Powyższy problem stanowi przykład problemu z teorii zanurzeń metrycznych. Mamy abstrakcyjny zbiór, w którym mierzymy odległości w jakiś sposób (możemy np. myśleć o grafie z odległością równą najkrótszej ścieżce między wierzchołkami), i chcemy narysować go w przestrzeni euklidesowej tak, by zachować odległości. Czy zawsze da się to zrobić? A jeśli nie, to jakie są przykłady "trudnych" grafów o bardzo "nieeuklidesowej" geometrii?

Teoria zanurzeń metrycznych posiada wiele zastosowań algorytmicznych. Zanurzenie grafu w "ładniejszą" przestrzeń często pozwala projektować wydajne algorytmy - aby rozwiązać problem grafowy, zanurzamy go w przestrzeń, której struktura pozwala na dobry algorytym, dbając o to, by odległości nie uległy zbytniemu zniekształceniu.

Zanurzenia metryczne stanowią bogaty dział z przecięcia matematyki i informatyki teoretycznej (zahaczający o teorię grup, grafy losowe, spektralną teorię grafów, …). Na zajęciach postaram się zaprezentować wstęp do podstawowych zagadnień i konstrukcji, zostawiająć jak najwięcej pracy do wykonania Wam. 1. dzień poświęcimy na wstęp i proste zadanie, 2. na dowodzenie twierdzeń w małych grupach, 3. na tzw. "desery".

Program zajęć

(ulegnie jeszcze uzupełnieniu)
Poniżej zamieszczam zrzut tematów wokół których będą się obracać zajęcia - materiał omówiony na zajęciach będzie stanowił ścisły podzbiór poniższego:

Wymagania

Ww. elementy zostaną wprowadzone i przetestowane w zadaniach kwalifikacyjnych.

Zadania kwalifikacyjne

Dostępne tutaj: Zadania kwalifikacyjne W razie pytań etc., śmiało piszcie na maila!

Uwaga: zadanie 6. okazało się trudne, zastąpiłem je zadaniem 7.