• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Dr Byrka bada losowe rozwiązania

    19.10.2010. 00:35
    opublikowane przez: Redakcja Naukowy.pl

    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/

    Czy wiesz ĹĽe...? (beta)
    Teoria perturbacji (nazywana też rachunkiem zaburzeń) jest zbiorem metod matematycznych, które są używane do znalezienia przybliżonego rozwiązania problemu, który nie może być rozwiązany w sposób ścisły, dostarczając bezpośrednie rozwiązanie problemu. Teoria perturbacji może być zastosowana do rozwiązania problemu, gdy można go przedstawić jako część dającą bezpośrednie rozwiązanie i stosunkowo mały człon zaburzający. Problem otwarty – jest to zdefiniowany formalnie problem (zadanie), o którym wiadomo, że posiada rozwiązanie, jednak nie zostało ono jeszcze do tej pory odkryte. Niektóre spośród problemów otwartych matematyki, informatyki czy fizyki mają takie znaczenie praktyczne, że za ich rozwiązania zostały wyznaczone nagrody pieniężne. Heurystyka (gr. heuresis – odnaleźć, odkryć, heureka – znalazłem) - w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu niektórych zagrożeń komputerowych, takich jak wirusy lub robaki). Metody używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy przypadków, gdy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*).

    Problem NP-zupełny (NPC) czyli problem zupełny w klasie NP ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności). Algorytmy aproksymacyjne – algorytmy służące do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych. Stosuje się je zwykle do rozwiązywania problemów, dla których nie są znane szybkie algorytmy znajdujące rozwiązanie dokładne, na przykład dla problemów NP-zupełnych.

    Dziel i zwyciężaj (ang. divide and conquer) – jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania. 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.

    Programowanie zstępujące (projektowanie zstępujące) (ang. top-down design) - rozwiązanie programistyczne polegające na zdefiniowaniu problemu ogólnego poprzez podzielenie na podproblemy, które są dzielone na jeszcze mniejsze podproblemy aż do rozwiązań oczywistych, łatwych do zapisania. Następnie złożenie z rozwiązań podproblemów niższego rzędu rozwiązań problemów wyższego rzędu aż do całkowitego rozwiązania problemu. Serwer OPC – oprogramowanie, które udostępnia dane w standardzie OPC dowolnym klientom OPC. Najważniejszym zadaniem serwera jest dbanie, aby dane procesowe były aktualne oraz klienci mieli do nich swobodny dostęp. Serwery OPC oferują elastyczne rozwiązania dostarczające dane procesowe wtedy, kiedy są potrzebne i minimalizujące wykorzystanie szerokości pasma komunikacyjnego (np. algorytm optymalnego przesyłania, algorytm skanowania adaptacyjnego, wielokanałowa transmisja danych, redundancja). Niektóre serwery OPC oferują rozwiązania, w których - dzięki zdefiniowanemu uniwersalnemu interfejsowi - funkcjonalność związaną z realizacją wybranego protokołu można lokować w zewnętrznych, dynamicznie przyłączanych komponentach zwanych DataProvider.

    W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.

    Metaheurystyka - ogólny algorytm (heurystyka) do rozwiązywania problemów obliczeniowych. Algorytm metaheurystyczny można używać do rozwiązywania dowolnego problemu, który można opisać za pomocą pewnych definiowaych przez ten algorytm pojęć. Najczęściej wykorzystywany jest jednak do rozwiązywania problemów optymalizacyjnych. Określenie powstało z połączenia słowa "meta" ("nad", tutaj w znaczeniu "wyższego poziomu") oraz słowa "heurystyka" (gr. heuriskein - szukać), co wynika z faktu, że algorytmy tego typu nie rozwiązują bezpośrednio żadnego problemu, a jedynie podają sposób na utworzenie odpowiedniego algorytmu. Termin "metaheurystyka" po raz pierwszy został użyty przez Freda Glovera w 1986 roku.

    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. Simple assembly line balancing - podstawowy problem decyzyjny w planowaniu konfiguracji w swojej najbardziej podstawowej wersji. Spośród rodziny problemów Assembly Line Balancing jest on najlepiej znany i najlepiej zbadany. Mimo iż może on być zbyt uproszczony by oddać złożoność rzeczywistych problemów balansowania to uchwyca on główne aspekty. Wiele odmian bardziej ogólnych problemów są bezpośrednimi rozszerzeniami SALB lub przynajmniej wymagają rozwiązania problemu SALB w jakiejś postaci.

    Agens – w analizie transakcyjnej osoba, która rozpoczyna grę i ją podtrzymuje. Pozostałe osoby uczestniczące w grze są partnerami, którzy reagują na prowadzoną agensa grę w taki sposób, by mogła ona trwać dalej. Przykładowo w grze Dlaczego ty nie - tak ale agens przedstawia problem, którego nie może rozwiązać, a w przypadku, gdy inni próbują podawać rozwiązania sytuacji, agens znajduje dodatkowe problemy, które uniemożliwiają rozwiązanie tejże sytuacji. Gra trwa tak długo, jak długo partnerzy interakcji reagują na działania agensa. Rozwiązania Mie - dokładne rozwiązanie problemu rozpraszania światła na sferycznych cząstkach w postaci nieskończonego, ale zbieżnego szeregu. Rozwiązania Mie dają informacje o ilości promieniowania zaabsorbowanego lub rozproszonego przez cząstkę. Właściwości rozproszeniowe cząstki obliczone zgodnie z tym rozwiązaniem noszą kolokwialną (ale nieprawidłową) nazwę rozpraszanie Mie.

    Problem NP (niedeterministycznie wielomianowy, ang. nondeterministic polynomial) to problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.

    Dodano: 19.10.2010. 00:35  


    Najnowsze