Znak Politechniki Warszawskiej

Absolwentka Wydziału MiNI z nagrodą VCLA International Student Awards 2020

Laureatka nagrody VCLA International Student Awards, Karolina Okrasa oraz dr inż. Paweł Rzążewski, promotor pracy.

Karolina Okrasa otrzymała wyróżnienie za pracę magisterską pt. Złożoność wariantów problemu homomorfizmu w wybranych klasach grafów w kategorii Outstanding Master Thesis Award. Praca została napisana pod kierunkiem dr. inż. Pawła Rzążewskiego. W tym roku w konkursie wyłonionych zostało dwóch laureatów. Karolina, obecnie doktorantka na Wydziale Matematyki i Nauk Informacyjnych, działa na pograniczu dwóch dyscyplin naukowych: matematyki i informatyki teoretycznej.

W nagrodzonej pracy poruszona została teoria złożoności obliczeniowej algorytmów rozwiązujących problemy zdefiniowane na grafach. Uwaga skupiła się szczególnie na dość szerokiej rodzinie takich problemów, znanych jako homomorfizmy grafów.

Dodatkowe założenia mogą pomóc

Istnieje wiele ważnych problemów grafowych, dla których na przestrzeni lat znaleziono szybko działające algorytmy. Z drugiej strony, istnieją problemy "trudne", które łatwo jest sformułować, ale nie potrafimy napisać szybkiego algorytmu, który znajdzie rozwiązanie. Przykładem takiego zagadnienia może być słynny problem komiwojażera. – mówi Karolina.

Doktorantka przyznaje, że do wspomnianych „trudnych” problemów zalicza się wiele problemów homomorfizmów grafów.

Do takich problemów można „naiwnie” podchodzić, sprawdzając po kolei wszystkie możliwości, w nadziei, że trafimy na rozwiązanie. W pesymistycznym przypadku jednak może to trwać bardzo długo. Zależy nam więc, żeby dowiedzieć się, kiedy można takie podejście ulepszyć. – dodaje.

Według autorki pracy, jednym z kierunków badań nad wspomnianym ulepszaniem jest ograniczenie się do pewnej klasy grafów. W wielu sytuacjach nie jest wymagane, abyśmy umieli rozwiązywać problem dla dowolnego grafu, ale tylko dla grafów z pewną określoną własnością. Wówczas może okazać się, że potrafimy zaprojektować algorytm, który będzie działał szybciej, ponieważ skorzysta z własności grafu, na których będziemy pracować. Jeśli zaś, mimo dodatkowych założeń, nie potrafimy znaleźć lepszego algorytmu, to może się zdarzyć, że potrafimy formalnie pokazać, że taka własność nie może znacząco wpłynąć na szybkość rozwiązywania problemu.

W swojej pracy badałam grafy o tzw. ograniczonej szerokości drzewowej. Szerokość drzewowa to funkcja, która dla każdego grafu, mówi nam (w bardzo dużym uproszczeniu) jak skomplikowana jest jego struktura. – wyjaśnia laureatka nagrody VCLA International Student Awards 2020.

Wielkie odkrycie

Jednym z tzw. „momentów przełomowych” projektu było wspólne dotarcie – studentki oraz promotora – do dwóch zapomnianych artykułów naukowych sprzed prawie 20 lat. Opublikowane w 2001 i 2002 roku prace zawierały szereg ciekawych twierdzeń z teorii grafów, lecz wszystko wskazywało na to, że nikt jeszcze nie skorzystał z nich w swoich badaniach. Okazało się, że część tych wyników była dokładnie tym, czego w swojej pracy potrzebowała Karolina. Przyznaje ona, że była to też swoista „lekcja” i jak sama mówi – wielokrotnie zdarza się, że matematyczne twierdzenia dowodzi się nie mając na uwadze konkretnych zastosowań. Takie teorie rozwijane są przez kolejnych naukowców, bądź wykorzystywane jako narzędzia w pokrewnych dziedzinach. Tak też było w tym przypadku, choć na zastosowanie udowodnionych twierdzeń trzeba było poczekać prawie 20 lat.

Informacja o wygranej Karoliny Okrasy znajduje się na stronie konkursu >>