Menu

Dec. 20, 2017, 12:38 p.m.

Nasz absolwent, mgr Bartłomiej Dudek, za swoją pracę magisterską pt. Edit Distance between Unrooted Trees in Cubic Time (promotor: dr Paweł Gawrychowski) otrzymał główną nagrodę w XXXIV Ogólnopolskim Konkursie Polskiego Towarzystwa Informatycznego na najlepsze prace magisterskie z informatyki, zorganizowanego w 2017 roku.

Pozostałe miejsca na podium zajęli absolwenci Uniwersytetu Warszawskiego: Małgorzata Gałązka i Jarosław Piórkowski.

Streszczenie pracy Bartłomieja Dudka:

Odległość edycyjna pomiędzy drzewami jest naturalnym uogólnieniem klasycznego problemu odległości edycyjnej pomiędzy słowami. Znajduje ona zastosowanie przede wszystkim w biologii obliczeniowej, a dokładniej w porównywaniu struktur RNA, a także w innych dziedzinach, na przykład w przetwarzaniu obrazu. Efektywne obliczanie odległości edycyjnej pomiędzy słowami jest prostym ćwiczeniem z algorytmów, ale dla drzew staje się to dużo trudniejsze. Demaine et al. [ACM Trans. on Algorithms, 6(1), 2009] skonstruowali algorytm znajdujący odległość edycyjną pomiędzy ukorzenionymi drzewami na n wierzchołkach w czasie O(n^3). Uogólnienie ich podejścia dla drzew nieukorzenionych wydaje się jednak dość problematyczne, i najlepszym znanym rozwiązaniem dla tej wersji pozostaje dużo wcześniejszy algorytm Kleina [ESA 1998] o wyższej złożoności O(n^3 log(n)). Jako że drzewa nieukorzenione wydają się dużo bardziej skomplikowane niż ukorzenione, można by podejrzewać, że złożoność problemu dla tych pierwszych po prostu musi być większa. W tej pracy pokazujemy, że wcale tak nie jest, bowiem odległość edycyjna pomiędzy drzewami nieukorzenionymi na n wierzchołkach może być wyliczona w czasie O(n^3). Bringmann et al. [arXiv:1703.08940, 2017] pokazali, że istnienie algorytmu o złożoności O(n^(3-eps)) dla drzew ukorzenionych nie jest możliwe zakładając jedną z popularnych hipotez używanych do pokazywania tego typu stwierdzeń. Ich wynik łatwo przenieść na drzewa nieukorzenione, więc istnienie algorytmu istotnie szybszego niż O(n^3) jest mało prawdopodobne.

Uzyskanie złożoności O(n^3) wymaga wielu nowych pomysłów w porównaniu do poprzedniego algorytmu działającego w takim czasie dla drzew ukorzenionych. Podobnie jak Demaine et al., zaczynamy od podziału obu drzew na ciężkie i lekkie ścieżki, jednak przedstawiamy ich podejście w inny, łatwiejszy do uogólnienia sposób. Początkowo, jedno z drzew dzielimy na górną i dolną część i każdą z nich przetwarzamy w inny sposób, przy czym dla każdej ścieżki w górnej części stosujemy nową technikę dziel i zwyciężaj. Uważna analiza tych pomysłów już wystarcza do rozwiązania o złożoności O(n^3 loglog(n)). Aby je usprawnić, uzależniamy podział drzewa na części od rozważanej ciężkiej ścieżki w drugim z drzew, a także zmieniamy podejście dziel i zwyciężaj, by brało pod uwagę rozmiary poddrzew przyczepionych do rozważanej ścieżki, a nie tylko jej długość. Na koniec trzeba dokładnie przeanalizować sumaryczny czas działania całego algorytmu.

Pokazujemy także jak zmodyfikować nasz algorytm tak, aby działał w czasie O(nm^2(1+log(n/m))) dla dwóch drzew nieukorzenionych o rozmiarach m i n. Demaine et el. udowodnili, że taka złożoność jest optymalna dla drzew ukorzenionych jeśli ograniczymy się do dość ogólnej klasy algorytmów dekompozycji. Dodatkowo pokazujemy, że cały algorytm można zaimplementować w pamięci O(nm).