Nad skrótami i przybliżeniami w obliczeniach, które mogą przyczynić się do postępu w informatyce pracuje Michał Włodarczyk z Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego. Badacz został wyróżniony przez Fundację na rzecz Nauki Polskiej w programie stypendialnym START.

Trudne problemy można dokładnie rozwiązać tylko w jeden sposób. Trzeba wygenerować wszystkie potencjalne rozwiązania i wybrać najlepsze z nich. Brzmi prosto, jednak okazuje się, że w miarę, jak dodajemy elementy, czas działania takich programów, czyli matematycznych algorytmów, rośnie wykładniczo. Potrzeba więc całych klastrów komputerowych i długich lat na obliczenia. Każdy nowy element musi być przecież połączony ze wszystkimi innymi w każdym możliwym wariancie rozwiązania.

Michał Włodarczyk wyjaśnia na poziomie matematycznym, co łączy ze sobą różne trudne problemy. Zastanawia się, czy da się je rozwiązać w przybliżony sposób, rezygnując z dokładności na rzecz skrócenia czasu działania algorytmu. Analizowane przez niego zagadnienia optymalizacyjne należą do kanonu informatyki teoretycznej i ich różne aspekty są badane od kilkudziesięciu lat. Jednym z przykładów jest rozmieszczenie fabryk.

„Naszym celem jest otwarcie sieci fabryk. Znamy położenie potencjalnych odbiorców towarów oraz listę miejsc, w których można wybudować fabrykę wraz z kosztami takiego przedsięwzięcia. Gdzie powinniśmy postawić fabryki, aby zminimalizować koszty budowy fabryk oraz transportu towarów?” - opisuje problem stypendysta FNP.

Drugi przykład nazywa się Drzewem Steinera i dotyczy komunikacji. „Dana jest pewna sieć połączeń np. telekomunikacyjnych. Zależy nam na wykupieniu najtańszego podzbioru połączeń, który zapewni łączność pomiędzy zbiorem interesujących nas terminali. Przy pomocy tego problemu można modelować także zagadnienia z projektowania układów scalonych oraz z biologii obliczeniowej” - mówi badacz.

Kolejny problem to szeregowanie zadań. Do dyspozycji jest zbiór maszyn i trzeba tak zaplanować wykonanie wielu zadań, aby zminimalizować czas pracy. Każda maszyna może wykonywać tylko jedno zadanie naraz. Zadania mogą różnić się poziomem trudności i wzajemnymi zależnościami.

I jeszcze projektowanie aukcji. Powiedzmy, że chcemy sprzedać kolekcję towarów, trzymając się ustalonych reguł. Raz złożonej oferty nie możemy wycofać. Dysponujemy częściowymi informacjami o tym, którzy klienci są zainteresowani naszymi towarami i ile są w stanie za nie zapłacić. Jak należy zaprojektować aukcję, aby jak najwięcej na niej zarobić?

„Dla wielu istotnych zagadnień optymalizacyjnych nie są znane żadne efektywne algorytmy rozwiązujące problem dokładnie. Jednym z wyjść z takiej sytuacji jest stosowanie algorytmów aproksymacyjnych, czyli znajdujących rozwiązanie różniące się od optymalnego maksymalnie o pewien ustalony czynnik” - tłumaczy badacz.

Trudnością w zastosowaniach praktycznych jest potrzeba modelowania informacji o nieznanych danych. Przykładem jest planowanie inwestycji, kiedy dysponuje się jedynie uproszczonymi przewidywaniami zachowań klientów. Za inny przykład może posłużyć zarządzanie portalem internetowym, który musi być gotowy na obsłużenie możliwych zapytań internautów w rozsądnym czasie, jednak mając dostęp do statystyk opisujących ruch internetowy.

Naukowcy pracują nad uogólnieniem znanych wyników z teorii algorytmów aproksymacyjnych, tak aby można było je wykorzystywać, kiedy część danych wejściowych do programu jest opisana jedynie rozkładem prawdopodobieństwa.

„Pewne interesujące nas problemy zostały już zbadane w modelach probabilistycznych, jednak przy silnych założeniach np. co do niezależności występujących zdarzeń. Chcielibyśmy pozbyć się takich założeń i rozwinąć teorię działającą w możliwie prostym modelu na dowolnych rozkładach prawdopodobieństwa” - wyjaśnia Włodarczyk.

Poza konstruowaniem algorytmów, naukowcy chcą zrozumieć, jak zmienia się struktura problemu w obliczu niepewności danych. Ustalają m.in. jakie własności posiadają rozwiązania optymalne. Wszystko to ma sprawić, że teoria algorytmów będzie bliższa praktyce.

PAP – Nauka w Polsce, Karolina Duszczyk

kol/ ekr/