Dr Byrka bada losowe rozwiązania :: Artykuły / Polski Serwis Naukowy

Polecamy również:

Michael Hanlon: "10 pytań, na które nauka nie znalazła (jeszcze) odpowiedzi" - recenzja

"Myślenie na głos" pomaga rozwiązywać zadania z matematyki

"Primus Inter Pares" - konkurs na najlepszego studenta

Zastosowanie procedury "Niebieskie Karty" dla policji

"AIDS: ryzyko znasz- reszta zależy od ciebie"

Niebieska Karta - wyjaśnienie terminu; procedura "Niebieskie Karty"

Usprawnienia w sieciach telekomunikacyjnych, umiejscowienie elementów na układach scalonych, przygotowanie drzew ilustrujących historię ewolucji - to tylko niektóre praktyczne zastosowania algorytmów, nad którymi pracuje dr Jarosław Byrka, tegoroczny laureat Nagrody im. Witolda Lipskiego dla młodych informatyków.

Niektóre problemy w informatyce nie mają jednej dobrej odpowiedzi. Prawidłowych wyników może być tak wiele, że znalezienie jednego, najlepszego, poprzez przeszukanie wszystkich możliwych jest zbyt kosztowne. W takich sytuacjach często wystarczają wyniki zbliżone do optymalnego.

Do rozwiązania tych problemów Jarosław Byrka używa tzw. zrandomizowanych algorytmów aproksymacyjnych. Dzięki nim możliwe odpowiedzi są przeszukiwane w sposób losowy i dość szybko można znaleźć zadowalający, choć niekoniecznie najlepszy wynik. Laureatowi Nagrody im. Lipskiego udało się udoskonalić niektóre sposoby losowego przeszukiwania odpowiedzi i poprawić jakość uzyskiwanych wyników.

Jednym z zagadnień, którego rozwiązania udoskonalił młody badacz jest problem tzw. drzewa Steinera. "Mamy dany graf i koszt jego krawędzi. Problem polega na tym, żeby połączyć wybrane wierzchołki najtaniej jak się da. Jedną z trudności jest jednak to, że kupno jednej krawędzi może skutkować zmianą przydatności innych krawędzi" - objaśnia nagrodzony.

Na przykład mamy serwery i sieć połączeń między nimi. Wykorzystanie każdego z połączeń związane jest z jakimś kosztem, a użycie konkretnego połączenia wpływa na koszt optymalnego uzupełnienia sieci pozostałymi połączeniami.

Rozwiązanie tego problemu może znaleźć zastosowanie przemysłowe. "To ważny problem z punktu widzenia działania sieci telekomunikacyjnych. Jeśli chcemy zapewnić sobie możliwość łączenia lokalizacji w internecie, konieczne jest rezerwowanie przepustowości na łączach, co jest usługą płatną. Dlatego ważna jest minimalizacja kosztu rezerwacji. Zależy nam, żeby pewne protokoły podejmowały decyzje szybko, bo czas działania, a nie optymalność rozwiązania jest tutaj kluczowa" - podkreśla informatyk.

Innym zagadnieniem, nad którym pracuje Byrka jest problem lokalizacji. "Mamy pewien zbiór klientów, którym chcemy zapewnić świadczenie (np. dostarczyć prąd) konstruując pewne obiekty (np. elektrownie). Dysponujemy zbiorem lokalizacji (miejsc, w których możemy zbudować elektrownie) wraz z ich kosztem (ceną za wybudowania ich właśnie w tych miejscach). Chodzi o to, żeby wybrać podzbiór lokalizacji i przypisać każdego z klientów do poszczególnych obiektów tak, żeby zminimalizować łączny koszt tego działania" - wyjaśnia Byrka.

Informatyk obrazuje problem: "Dwa banki miały jakąś liczbę biur i iluś klientów. W pewnej chwili postanowiły połączyć się w jeden bank. Nowy bank po połączeniu ma tyle samo klientów co dwa banki, ale prawdopodobnie może mieć o połowę mniej biur. Musi wybrać, które z nich można zlikwidować. Usuwanie niepotrzebnych biur powinno przebiegać tak, żeby klienci nie mieli zbyt daleko do banku. Chcielibyśmy zminimalizować społeczny koszt tego rozwiązania."

"Podobne algorytmy znajdują zastosowanie przy produkcji elementów elektronicznych, gdzie na układzie scalonym umieszcza się pewne części, które muszą być ze sobą połączone. Czasem elementów jest tak dużo, że próba znalezienia najlepszego rozwiązania skazana byłaby na porażkę. I wtedy właśnie przydają się algorytmy aproksymacyjne" - dodaje naukowiec.

"Istotą algorytmów aproksymacyjnych jest to, że działają szybko, ale są niedokładne" - zaznacza informatyk. Ale jemu udało się zmniejszyć niedokładność tych rozwiązań i zbliżyć je do optimum. Na razie jeszcze nikomu nie udało się poprawić jego wyniku.

Laureat nagrody im. Witolda Lipskiego zaznacza, że bada tylko najprostsze wersje problemów. "Ich rozwiązania nie są bezpośrednio stosowane, ale prowadzą do głębszego zrozumienia problemu i do konstrukcji odpowiednich narzędzi przemysłowych" - wyjaśnia.

Innym problemem, nad którym pracuje Byrka, jest stworzenie programu do ilustrowania historii ewolucji gatunków. Złożone dane, np. genetyczne, mogłyby być zobrazowane za pomocą drzewa. W budowie tego drzewa znalazłyby odbicie zależności ewolucyjne między poszczególnymi organizmami. Młody naukowiec interesuje się też teorią gier i tym, jak mogą się zmieniać strategie graczy. Problem ten jest ważny z punktu widzenia ekonomii.

PAP - Nauka w Polsce, Ludwika Tomala

agt/

komentuj publikację

Czy wiesz że...?

wersja BETA

Poradnictwo obywatelskie polega na informowaniu ludzi (w formie indywidualnej lub grupowej) o przysługujących im prawach oraz spoczywających na nich obowiązkach, w zakresie istotnym dla rozwiązania jego problemu oraz pomoc w wyborze optymalnego rozwiązania. pełny tekst

Twierdzenie o dualności rezultat przedstawiający cztery możliwości dotyczące istnienia rozwiązań optymalnych i dopuszczalnych problemu programowania liniowego w postaci standardowej. pełny tekst

Własność optymalnej podstruktury jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. pełny tekst

Moduł "Czy wiesz że...?" (wersja testowa, beta): definicje/pojęcia wygenerowane w obrębie tego modułu pochodzą z Wikipedii i udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Dostęp do pełnej wersji każdego hasła (oraz dokładnch informacji na temat licencji, autora oraz edycji) możliwy jest po kliknięciu w odnośnik opisany jako "pełny tekst".