Superkomputer KDM: Zastosowania

Projekt dotyczy trzech zagadnień z dziedziny języków formalnych oraz optymalizacji działania bezprzewodowych sieci sensorowych. Pierwszym rozważanym problemem jest problem dekompozycji języków skończonych. Na podstawie dotychczasowych prac kierownika i wykonawców projektu opracowany zostanie nowy, równoległy algorytm dekompozycji języków skończonych oparty na wektorowej reprezentacji potencjalnych zbiorów dekompozycji. Po opracowaniu i implementacji algorytmu przeprowadzona będzie seria obliczeń umożliwiających ocenę jakości otrzymanego zrównoleglenia, a także porównania go z dotychczasowymi rozwiązaniami realizatorów projektu. Drugim problemem będzie indukcja niedeterministycznych automatów skończonych na podstawie podanej próbki przykładów pozytywnych i negatywnych. W ramach prowadzonych prac opracowany zostanie nowy model problemu, który zostanie następnie poddany zrównolegleniu w celu skrócenia czasu potrzebnego do uzyskania poszukiwanego automatu minimalnego. Jako trzeci będzie rozwiązywany problem maksymalnego czasu pokrycia w bezprzewodowych sieciach sensorowych.
Sieci takie składają się z węzłów będących sensorami (czujnikami), które komunikują się w sposób bezprzewodowy. Zadaniem sensorów jest monitorowanie określonego obszaru przez pomiar wartości, takich
jak np. temperatura, promieniowanie elektromagnetyczne, jakość powietrza, etc. Każdy sensor określa swoją pozycję, korzystając z systemu nawigacji satelitarnej lub na podstawie położenia
względem pozostałych węzłów. Sensory zasilane są z baterii, przez co czas ich pracy jest ograniczony. Ustalenie odpowiedniego harmonogramu aktywności poszczególnych sensorów umożliwia wydłużenie czasu pracy całej sieci. Stąd wynika potrzeba opracowania algorytmów wyznaczenia harmonogramu maksymalizującego
czas pracy sieci składającej się z dużej liczby sensorów. Wykazano, że problem ten jest trudny obliczeniowo i należy do klasy NP.

Celami projektu są zatem:
- opracowanie nowych algorytmów równoległych i sekwencyjnych dla wymienionych wyżej problemów,
- implementacja opracowanych algorytmów,
- ocena opracowanych rozwiązań w kontekście miar jakości zrównoleglenia problemu oraz czasu działania.

Duża złożoność obliczeniowa rozważanych problemów stanowi uzasadnienie do skorzystania z superkomputera. Przewidywana implementacja algorytmów zostanie zaprojektowana w języku C/C++ z użyciem interfejsu MPI (Message Passing Interface). Stosowany będzie także język Python.