Uhonorowane algorytmy

Znamy laureatów VIII Konkursu o Nagrodę im. Witolda Lipskiego, skierowanego do młodych polskich naukowców prowadzących badania w dziedzinie informatyki.

Uhonorowane algorytmy
Najwyżej oceniony został dorobek dr. Marka Cygana i dr. Marcina Pilipczuka. Obaj otrzymali równorzędne główne nagrody. Są doktorami nauk matematycznych w zakresie informatyki i adiunktami na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego. W 2007 r. opisywaliśmy ich - oraz Filipa Wolskiego - jako drużynę "Orłów Warszawy", która wygrała Akademickie Mistrzostwa Świata w Programowaniu Zespołowym ("International Collegiate Programming Contest") zorganizowane przez Association for Computing Machinery.

"Trudno było wyróżnić którąkolwiek z tych osób bez pomijania drugiej. Na uwagę zasługuje bogaty dorobek obu laureatów, który obejmuje wiele wspólnych wyników opublikowanych w świetnych czasopismach i prezentowanych na prestiżowych konferencjach międzynarodowych" - mówił podczas uroczystości wręczenia nagrody prof. Andrzej Tarlecki, przewodniczący Rady Nagrody im. Witolda Lipskiego. Rada przyznała też honorowe wyróżnienie dla Artura Jeża, doktora nauk matematycznych w zakresie informatyki. W latach 2006-2010 był doktorantem Instytutu Informatyki na Wydziale Matematyki i Informatyki Uniwersytetu Wrocławskiego. Obecnie przebywa na stażu w Max Planck Institute für Informatik w Saarbruecken. Jest adiunktem na Uniwersytecie Wrocławskim.

Prace Marka Cygana i Marcina Pilipczuka dotyczą aktualnych nurtów teorii algorytmów. Rada Nagrody uhonorowała ich za wspólnie zaproponowany algorytm "wyznaczania szerokości grafów o najlepszej dotychczas znanej złożoności asymptotycznej". "W pracach prezentujących te i inne wyniki ważne są nie tylko konkretne algorytmy i rezultaty dotyczące ich złożoności, ale także nowatorskie, ciekawe i niezwykle mocne nowe techniki algorytmiczne, często pozwalające na ich skuteczne stosowanie również w innych znanych i badanych problemach" - wyjaśnia prof. Andrzej Tarlecki.

Z kolei prace dr. Artura Jeża dotyczą teorii języków formalnych i ich związków z metodami kompresji tekstów. "Szczególnie ta ostatnia dziedzina i wyniki uzyskane przez dr. Artura Jeża, choćby dotyczące złożoności problemów wyszukiwania wzorców w skompresowanych tekstach, są niezwykle ważne dla praktycznych zastosowań" - mówi prof. Andrzej Tarlecki.

Algorytmy i języki formalne

Zagadnienia, które stanowią główną część pracy naukowej dr. Marka Cygana, to algorytmy aproksymacyjne oraz algorytmy parametryzowane. Celem algorytmów aproksymacyjnych jest uzyskanie szybkich metod rozwiązywania problemów kosztem ich optymalności. Uzyskane wyniki mogą się różnić od rozwiązań optymalnych. Algorytmy parametryzowane mają na celu uzyskanie dokładnego rozwiązania, ale przy dodatkowym założeniu o charakterystyce danych wejściowych problemu. "Można powiedzieć, że algorytmy parametryzowane i algorytmy aproksymacyjne są niejako komplementarne. Algorytmy aproksymacyjne pozwalają nam rozwiązywać dowolne instancje problemu w sposób przybliżony, a algorytmy parametryzowane uzyskują dokładne rozwiązania jedynie wybranej klasy instancji, o których strukturze możemy wnioskować na podstawie wielkości parametru instancji" - tłumaczą członkowie Rady Nagrody w uzasadnieniu werdyktu.

Dr Marcin Pilipczuk jako główny temat badań wybrał złożoność parametryzowaną i algorytmy umiarkowanie wykładnicze. Wiele problemów algorytmicznych, które napotykamy w praktyce, jest trudnych do dokładnego rozwiązania. Naukowcy badają różne metody radzenia sobie z nimi. Czasem możliwa jest aproksymacja, czasem okazuje się, że w praktyce dobrze radzą sobie różne heurystyczne rozwiązania. "Złożoność parametryzowana próbuje uzasadnić formalnie, dlaczego heurystyki są tak skuteczne i - dzięki uzyskanym wnioskom - pozwolić na opracowanie lepszych oraz szybszych algorytmów. Kluczową ideą złożoności parametryzowanej jest wprowadzenie nietypowej (tzw. wielowymiarowej) miary instancji problemu i analizę złożoności w oparciu o tę miarę. W swoich badaniach Marcin Pilipczuk próbuje zlokalizować, który dokładnie aspekt danych wejściowych jest odpowiedzialny za trudność danej instancji" - czytamy w uzasadnieniu.

Dla promocji polskich talentów

Konkurs o Nagrodę im. Witolda Lipskiego powstał z inicjatywy grupy polskich informatyków pracujących za granicą. W ideę włączyła się Fundacja Rozwoju Informatyki, przy współpracy z Polskim Stowarzyszeniem dla Maszyn Liczących i Polskim Towarzystwem Informatycznym. Patron nagrody, dr hab. Witold Lipski, był wybitnym polskim informatykiem, który odnosił sukcesy w światowej nauce. Zmarł w wieku 35 lat. Absolwent Studium Podstawowych Problemów Techniki przy Politechnice Warszawskiej stworzył w krótkim czasie imponujący dorobek naukowy obejmujący kombinatorykę, teorię wyszukiwania informacji oraz geometrię obliczeniową. W każdej z tych dziedzin osiągnął liczące się do dziś wyniki. Najbardziej znanym jego osiągnięciem naukowym była matematyczna teoria baz danych z niepełną informacją.

W celu komercyjnej reprodukcji treści Computerworld należy zakupić licencję. Skontaktuj się z naszym partnerem, YGS Group, pod adresem [email protected]

TOP 200