Nauka

W skrócie

Działania badawcze i praca naukowa pracowników Instytutu Informatyki skupiają się na następujących dziedzinach:

• Teoria złożoności
• Lingwistyka matematyczna
• Sztuczna inteligencja
• Sztuczne systemy immunologiczne i ich zastosowania
• Kombinatoryka, algorytmy kombinatoryczne
• Teoria grafów
• Geometria obliczeniowa
• Semantyka, specyfikacja i weryfikacja algorytmów generycznych
• Sieci Bayesowskie
• Współbieżność, sieci Petriego

Tematyka badawcza

Dokładniejszy opis badań prowadzonych przez naszych pracowników w ostatnich latach dostępny jest poniżej. Informacje pochodzą z danych zbieranych do potrzeb parametryzacji i ocen PKA w latach 2020-2022. Niektórzy badacze dołączyli do swoich opisów obszerniejsze wyjaśnienia. Kolejność przypadkowa.

Janusz Dybizbański

• Teoria grafów: Zorientowane kolorowanie, zorientowana liczba chromatyczna wybranych klas grafów, zorientowane kliki. Homomorfizmy w turnieje (oriented coloring) oraz w grafy 2-pokolorowane (2-edge-colored coloring).
• Odporność na błędy (fault tolerance) hipersześcianów.
• Cykle i ścieżki Hamiltona w hipersześcianach. Liczby Ramseya dla Hipergrafów i on-line.

Mateusz Miotk

• Problem dominowania z certyfikatami w grafach oraz ich zastosowania. Mówimy, że zbiór D jest dominujący w grafie G, kiedy każdy wierzchołek spoza tego zbioru ma sąsiada w zbiorze D. Interesuje nas najmniejszy taki zbiór, co ma swoje zastosowanie na przykład w sieciach radiowych. Zbiór dominujący D jest zbiorem dominującym z certyfikatami, wtedy i tylko wtedy, gdy każdy wierzchołek z tego zbioru nie jest sąsiedni tylko z jednym z wierzchołków spoza tego zbioru. Dominowanie to jest poniekąd odwrotną definicją zbiorów 2-dominujących i ma swoje zastosowanie w sieciach społecznościowych, gdzie chcemy uniknąć sytuacji, gdy wierzchołek jest „obserwowany” tylko przez jednego sąsiada. Tutaj również interesuje nas przypadek najmniejszego zbioru dominującego z certyfikatami.
• Nowe operacje tworzenia grafów dwudzielnych. Graf dwudzielny, to taki graf, który można pokolorować legalnie dwoma kolorami. Pojęcie legalnego pokolorowania, oznacza, że jeśli wierzchołek dostaje kolor, powiedzmy czerwony, to żaden jego sąsiad nie może otrzymać takiego samego koloru. Tutaj zdefiniowaliśmy operacje tworzenia grafu dwudzielnego z dowolnego innego grafu, opierając się na funkcji z wszystkich występujących w tym grafie podgrafów pełnych do liczb naturalnych. Operacje tę nazwaliśmy Bipartyzacją Grafu w oparciu o funkcję. Interesują nas właściwości tej operacji w kontekście powstawania znanych grafów dwudzielnych (na przykład drzew), oraz powiązania różnych otrzymywanych zbiorów (na przykład najmniejszych zbiorów dominujących), które można scharakteryzować w języku tej operacji.

Łukasz Mielewczyk

• Praca (zakończone) nad projektem badawczym: „Problem lasu prostokątnych gałęzi Steinera” (ang. „The rectilinear Steiner forest arborescence problem”).
• Praca nad projektem badawczym związanym z Interaktywnym dowodzeniem twierdzeń związanych z algorytmami, teorią grafów, geometrią obliczeniową. Poprzez interaktywne dowodzenie twierdzeń mamy na myśli pewien układ, w którym znajduje się maszyna (np. komputer) i użytkownik (człowiek) współpracują ze sobą interaktywnie, aby stworzyć formalny dowód. Przykładowym narzędziem, które umożliwia interaktywne dowodzenie twierdzeń i które mam zamiar wykorzystać jest Mizar (https://mizar.uwb.edu.pl/). Język Mizar został zaprojektowany tak, aby był jak najbardziej zbliżony do języka używanego w pracach matematycznych,a jednocześnie był automatycznie weryfikowalny. Te dwa cele osiąga się, wybierając zestaw angielskich słów i zwrotów, które najczęściej występują w matematyce nieformalnej. W szczególności język zawiera standardowy zbiór logiki pierwszego rzędu i kwantyfikatorów do tworzenia formuł oraz daje możliwość do wykorzystania (łączenia) zmiennych wolnych logiki drugiego rzędu do tworzenia schematów twierdzeń. Pozostałe konstrukcje składniowe Mizara są używane do pisania dowodów i definiowania nowych obiektów matematycznych.

Hanna Furmańczyk

• wybrane modele kolorowania grafów
• wybrane modele szeregowania zadań
• złożoność obliczeniowa problemów teorii grafowych

Maciej Dziemiańczuk

• Kombinatoryka (zliczanie ścieżek kratowych)
• Automaty komórkowe (dyskretne odwracalne automaty komórkowe zachowujące sumę stanów)

Joanna Czarnowska

• Modelowanie zdarzeń ekstremalnych z wykorzystaniem procesów max-stabilnych. W szczególności wykorzystanie do analizy maksymalnych prędkości wiatrów w Polsce.
• Teoria zdarzeń ekstremalnych w modelowaniu wysokich kwantyli rozkładów probabilistycznych.
• Tworzenie i walidacja modelu do prognozy poziomów zwrotów dla dziennych opadów w Niemczech
• (Obecnie) Kopuły w modelowaniu rozkładów wielowymiarowych. Zastosowanie struktur C-Vine i D-Vine do korekty prognoz w działających numerycznych modelach meteorologicznych.

Mikołaj Czechlewski

• Informatyka kwantowa: kwantowe generatory liczb losowych, nierówności Bella, kodowanie kwantowe, kwantowy internet.

Radosław Ziemann

• Problem b-kolorowania grafów (b-coloring) – szukanie lepszych oszacowań dla grafów d-regularnych
• Problem zbioru geodezyjnego (geodetic set) – konstrukcja algorytmu liniowego dla grafów zewnętrznie planarnych, badanie złożoności algorytmicznej
• Problem wypukłego zbioru dominującego (convex dominating set) – konstrukcja algorytmu liniowego dla grafów zewnętrznie planarnych, badanie złożoności algorytmicznej

Anna Nenca

• Automaty komórkowe
• Zorientowane kolorowanie grafów
• Oznakowane kolorowanie grafów (signed coloring)

Paweł Pączkowski

• Teoria współbieżności
• Bisymulacja dla procesów bezkontekstowych z przekazywaniem wartości.
• Teoretyczne podstawy programowania współbieżnego
• Modelowanie i dowodzenie własności procesów współbieżnych.

Karol Horodecki

• Badania prowadzone w Centrum Teorii Technologii Kwantowych Uniwersytetu Gdańskiego. Badania te dotyczą kwantowej informatyki - dziedziny wykorzystującej prawa mechaniki kwantowej do osiągania celów informatycznych. Jedne z pierwszych prac, których byłem współautorem, dotyczyły protokołów otrzymywania bezpiecznego klucza kryptograficznego za pośrednictwem zaszumionych stanów kwantowych i kanałów komunikacyjnych.
• W ramach habilitacji wykazałem analogiczne cechy kilku zasobów kwantowych, takich jak nielokalność typu Bella, kontekstualność, bezpieczny klucz kryptograficzny i kwantowe splątanie.
• W ostatnim czasie, w ramach grantu Narodowego Centrum Nauki, jako lider wróciłem wraz z zespołem do tematu komunikacji zabezpieczanej kwantowo przed podsłuchem. Do głównych wyników z tego okresu oprócz artykułów dotyczących kwantowych pieniędzy czy sposobu zabezpieczenia kwantowych sieci przed atakami, należy seria prac prezentujących ograniczenia związane z otrzymywaniem bezpiecznego klucza kryptograficznego.
• Obecnie kontynuuję badania dotyczące różnych zasobów kwantowych jak również interesuję się dziedziną kwantowego uczenia maszynowego.

Viktoria Onyshchenko

• Teoria gier, zbiory rozmyte, systemy informacyjne, równania różniczkowo-różnicowe, teoria sterowania, procesy konfliktowo sterowane, modulacja fraktalna, dynamika ułamkowa, układy dyskretno-ciągłe, sztuczna inteligencja, uczenie maszynowe, Big Data
• Udoskonaliłam modele układów dynamicznych o ułamkowej dynamice i wpływie impulsowym, które w przeciwieństwie do istniejących wykorzystują równania różniczkowo-różnicowe z pochodnymi ułamkowymi, co pozwala na dokładniejsze scharakteryzowanie wskaźników jakości sieci informacyjnej
• Zaproponowałam model ruchu sieciowego, oparty na ułamkowym ruchu Browna. Za pomocą opracowanego modelu przeanalizowano dane o ruchu w rzeczywistej sieci informacyjnej dotyczące właściwości fraktalnych oraz opracowano algorytm odtwarzania ruchu na podstawie jego samopodobieństwa.
• Opracowałam metody, pozwalające na uzyskanie gwarantowanych wskaźników przepływu informacji w sieci komputerowej.
• Zaproponowałam algorytm steganograficzny, generujący dyskretny sygnał szumu o zadanym wymiarze fraktalnym, który pozwala na zwiększenie poufności przesyłanych informacji.

Joanna Jędrzejowicz

• Zajmuję się problemami w dziedzinie eksploracji danych, w szczególności klasyfikacją danych. Algorytmy klasyfikacji danych niezrównoważonych (ang.: imbalanced data classification) gdzie w zbiorze danych jedna klasa jest dominująca, stanowią szczególny przypadek i zainteresowanie gdyż takie dane występują bardzo często w praktyce.
• Tematyka moich prac skupia się na badaniu różnych metod hybrydowych dla klasyfikacji niezrównoważonej wykorzystujących takie narzędzia jak algorytmy genetyczne w połączeniu z programowaniem genetycznym (ang.: gene expression programming),
• Sieci neuronowe
• Algorytmy klasteryzacji

Paweł Żyliński

• Geometria obliczeniowa (pokrywanie wielokątów)
• Teoria grafów (dominowanie, kolorowanie, pokrywanie, skojarzenia)
• Optymalizacja kombinatoryczna (algorytmy aproksymacyjne)