Przejdź do treści Wyszukiwarka

Charakterystyka sieci (grafów) spotykanych w dzisiejszym świecie sprawia, że nawet najbardziej podstawowe zadania przetwarzania grafów (takie jak obliczanie spójnych składowych lub najkrótszych ścieżek) stanowią spore wyzwanie.

Sieci te bywają bardzo duże: ich rozmiar może z łatwością przekroczyć pojemność pamięci głównej pojedynczego komputera. Nawet jeśli sieć mieści się w pamięci głównej komputera, może się zdarzyć, że użycie dobrze znanych i sprawdzonych optymalnych algorytmów (takich jak przeszukiwanie wszerz) nie gwarantuje, że obliczenia zostaną wykonane wystarczająco szybko. Podczas gdy częstotliwości taktowania procesorów konsumenckich przestały wzrastać, systematycznie rośnie liczba rdzeni typowego procesora. W związku z tym, uzasadnionym jest poszukiwanie wydajnych algorytmów równoległych zarówno w klasycznych modelach pamięci współdzielonej (PRAM), jak i bardziej współczesnych modelach obliczeń masowo równoległych (takich jak MapReduce) z danymi wejściowymi rozproszonymi pomiędzy wiele maszyn.

Kolejnym wyzwaniem, przed którym stoimy, jest to, że spotykane obecnie sieci zmieniają się w czasie. W typowym scenariuszu sieć podlega bardzo częstym, niewielkim aktualizacjom. Aktualizacje są na tyle małe, że ponowne obliczanie wymaganych informacji od zera po każdej zmianie wydaje się nierozsądne. Ta myśl dała początek bardzo bogatemu obszarowi dynamicznych algorytmów grafowych, w którym poszukuje się wydajnych struktur danych utrzymujących żądane informacje o własnościach dynamicznych grafów. Większość dotychczasowych prac w tym obszarze ma charakter czysto teoretyczny. Praktyczna ewaluacja dynamicznych algorytmów grafów jest wciąż w powijakach.

Celem badań naszego zespołu jest projektowanie i ewaluacja nowych równoległych i dynamicznych algorytmów dla podstawowych problemów przetwarzania grafów. Po pierwsze, prowadzimy teoretyczne badania nad tym, jakie równoległe kompromisy pomiędzy głębokością a pracą algorytmu mogą być osiągnięte i w jakim stopniu te rozwiązania mogą być skuteczne w dynamicznych sytuacjach. Po drugie, opracowujemy implementacje i przeprowadzamy eksperymentalne oceny dynamicznych i równoległych algorytmów grafowych dla problemów w kręgu zainteresowań praktyków.

Badania zespołu są częściowo skoordynowane z celami grantu NCN 2022/47/D/ST6/02184 ,,Równoległe i dokładne algorytmy dla problemów ścieżkowych w grafach skierowanych’’ realizowanego przez IDEAS NCBR.

Lider zespołu badawczego


Adam Karczmarz

Adam Karczmarz jest badaczem w IDEAS NCBR i na Uniwersytecie Warszawskim, gdzie uzyskał stopień doktora w 2019 roku. Interesuje się teoretycznymi i praktycznymi aspektami projektowania algorytmów i struktur danych. Jego dotychczasowe badania koncentrowały się głównie na klasycznych problemach przetwarzania grafów, takich jak osiągalność i obliczanie najkrótszych ścieżek, zwłaszcza w modelach: dynamicznym, odpornym na awarie i równoległym, w których stawia się czoła niektórym z najpoważniejszych wyzwań współczesnych dużych sieci. Ostatnio bada również powiązania między klasycznym projektowaniem algorytmów a uczeniem maszynowym.

Stypendium MEiN dla wybitnych młodych naukowców (2022)

Stypendium FNP START (2020)

Stypendium NCN Etiuda (2017)

 

 

Grant NCN Sonata (2023)

Grant NCN Preludium (2019)

 

Inne grupy i zespoły badawcze

  • Uczenie w sterowaniu, grafach i sieciach Zespół badawczy rozwija sieci neuronowe generujące grafy. Rozwiązania te są zorientowane na automatyczne projektowanie struktur naturalnie reprezentowanych przez grafy, takich jak molekuły czy sieci energetyczne.
    Paweł Wawrzyński
  • Leśnictwo precyzyjne Zastosowanie danych teledetekcyjnych w pozyskiwaniu informacji o lasach ma swoją długą, już około 100-letnią, historię.
    Krzysztof Stereńczak
  • Uczenie maszynowe zero-waste w wizji komputerowej Zarówno nauka, jak i przemysł chętnie sięgają po rozwiązania wykorzystujące modele uczenia maszynowego, głównie głębokie sieci neuronowe.
    Tomasz Trzciński