Znamy laureatów VIII edycji konkursu o Nagrodę im. Witolda Lipskiego. To prestiżowy konkurs skierowany do młodych naukowców prowadzących badania w dziedzinie informatyki.

18 października odbyła się uroczysta gala wręczenia Nagrody, podczas której laureaci wygłosili referaty na temat swoich osiągnięć.

„Świetne prace, znakomite wyniki i wysokie oceny dobiegające z międzynarodowych środowisk naukowych podkreślają uzyskany przez tych młodych naukowców dorobek naukowy i obiecują ich dalszy szybki rozwój, a także wiele znakomitych osiągnięć w przyszłości” – tak prof. Andrzej Tarlecki przewodniczący Rady Nagrody, podsumował VIII edycję konkursu o Nagrodę im. Witolda Lipskiego.

W tegorocznej edycji konkursu wyłoniono dwóch laureatów głównej Nagrody. Najwyżej i równorzędnie oceniony został dorobek dr. Marka Cygana i dr. Marcina Pilipczuka z Uniwersytetu Warszawskiego. „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 przede wszystkim wiele wspólnych wyników opublikowanych w świetnych czasopismach i prezentowanych na prestiżowych konferencjach międzynarodowych” – mówi prof. Andrzej Tarlecki. Rada Nagrody przyznała również honorowe wyróżnienie dla dr. Artura Jeża z Uniwersytetu Wrocławskiego.

Prace Marka Cygana i Marcina Pilipczuka dotyczą aktualnych nurtów teorii algorytmów. Rada Nagrody uhonorowała ich obu między innymi za wspólnie zaproponowany algorytm wyznaczania szerokości grafów o najlepszej dotychczas znanej złożoności asymptotycznej i wynik złożoności problemów spójności grafów. „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.” – dodaje przewodniczący Rady Nagrody im. Lipskiego.

W konkursie wyróżnieniem został uhonorowany dr Artur Jeż z Uniwersytetu Wrocławskiego. Jego prace dotyczą teorii języków formalnych oraz ich związków z metodami kompresji tekstów. „Szczególnie ta ostatnia dziedzina i wyniki uzyskane przez dr. 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ń” – podsumowuje Andrzej Tarlecki.


Nagroda im. Witolda Lipskiego przyznawana jest już od 2005 roku. Konkurs 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 (polskim oddziałem ACM) i Polskim Towarzystwem Informatycznym.
Dzięki sponsorom, w tym firmie Sage, Rada Nagrody corocznie przyznaje młodym naukowców nagrodę pieniężną za dorobek naukowy w dziedzinie informatyki i jej zastosowań.
O Nagrodę im. Witolda Lipskiego mogą ubiegać się osoby, które nie przekroczyły 30 roku życia (lub 32 roku życia w przypadku kandydatów, którzy korzystali z urlopów wychowawczych) i są pracownikami, doktorantami lub studentami w krajowej szkole wyższej lub w instytucji, której jednym z celów statutowych jest prowadzenie badań naukowych w dziedzinie informatyki.

Zapraszamy również na stronę: http://nagrodalipskiego.mimuw.edu.pl.

 

***

Laureatami VIII edycji konkursu o Nagrodę im. Lipskiego zostali:

Dr Marek Adam Cygan - 28 lat - doktor nauk matematycznych w zakresie informatyki, adiunkt na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego. Odbywał staż naukowy na Uniwersytecie w Maryland oraz staż podoktorski w instytucie IDSIA na Uniwersytecie w Lugano.

Jego praca naukowa dotyczy najważniejszego problemu otwartego w informatyce - czy P jest równe NP? Powszechnie uważa się, że problemów trudnych obliczeniowo (NP-trudnych) nie da się rozwiązywać dokładnie za pomocą efektywnych algorytmów, za jakie uznaje się algorytmy wielomianowe. Z tego powodu różne poddziedziny algorytmiki podejmują problemy NP-trudne w różny sposób. Dwa nurty, które stanowią główną część jego pracy naukowej, 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, jednakże 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.

Dr Marcin Pilipczuk - 27 lat - doktor nauk matematycznych w zakresie informatyki, adiunkt na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Główny nurt jego badań dotyczy złożoności parametryzowanej i algorytmów umiarkowanie wykładniczych. Wiele problemów algorytmicznych, które napotyka w praktyce, okazuje się być bardzo trudnych do dokładnego rozwiązania. Naukowcy badają różne metody radzenia sobie z takimi problemami: czasem możliwa jest aproksymacja, czasem okazuje się, że różne heurystyczne rozwiązania radzą sobie w praktyce bardzo dobrze. Złożoność parametryzowana próbuje uzasadnić formalnie, dlaczego heurystyki są tak skuteczne, i, dzięki uzyskanym wnioskom, pozwolić na opracowanie lepszych i 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 próbuje zlokalizować, który dokładnie aspekt danych wejściowych jest odpowiedzialny za trudność danej instancji.

Wyróżnienie honorowe otrzymał:

Dr Artur Jeż – 30 lat - doktor nauk matematycznych w zakresie informatyki. W latach 2006 – 2010 – doktorant Instytutu Informatyki na Wydziale Matematyki i Informatyki Uniwersytetu Wrocławskiego. Obecnie przebywa na stażu podoktorskim w Max Planck Institute für Informatik w Saarbruecken. Ponadto jest adiunktem na Wydziale Matematyki i Informatyki Uniwersytetu Wrocławskiego (na urlopie naukowym w celu odbycia stażu).

Jego badania związane są z różnymi aspektami języków formalnych oraz ich powiązaniami z algorytmiką. W czasie doktoratu zajmował się głównie wyrażalnością gramatyk koniunkcyjnych, które są efektywnym sposobem zadawania składni zamkniętym na operacje boolowskie, oraz związanymi z nimi układami równań nad zbiorami liczb naturalnych. Obecnie zajmuje się związkami między kompresją danych równaniami w słowach, rozpoznawania słów przez automaty skończone oraz wyszukiwania wzorca. Ponadto zajmował się też problemem minimalizacji z błędami automatów skończonych.