TEMATY PRAC DYPLOMOWYCH  INŻYNIERSKICH 2017

 

1.

Tytuł w j. polskim

Algorytmy grafowej i sieciowej optymalizacji dyskretnej w ramach biblioteki KOALA.

Tytuł w j. angielskim

Graph-theoretic discrete optimizations algorithm for KOALA library.

Opiekun pracy

prof. dr hab. inż. Krzysztof Giaro

Konsultant pracy

 

Cel pracy

Biblioteka KOALA obejmuje rozległy zbiór wielomianowych algorytmów rozwiązujących rozmaite zagadnienia z zakresu grafowej i sieciowej optymalizacji dyskretnej, zaimplementowanych jako szablony C++. Celem pracy jest jej wzbogacenie o dalsze nietrywialnie procedury (szczegółowy zakres do uzgodnienia, wstępne propozycje: wyszukiwanie ważonych skojarzeń, nieklasyczne modele kolorowania, rozbudowa/modyfikacja istniejących generycznych klas struktur danych).

Zadania do wykonania

  1. Zapoznanie się z szablonami i metaprogramowaniem w C++

  2. Zapoznanie się z biblioteką KOALA.

  3. Implementacja wybranych algorytmów na potrzeby biblioteki.

Literatura

  1. M. Sysło, N. Deo, J. Kowalik, Algorytmy optymalizacji dyskretnej, PWN.

  2. Schrijver, A Course in Combinatorial Optimization, National research institute for mathematics and computer science in the Netherlands & Department of Mathematics University of Amsterdam, 2006. http://homepages.cwi.nl/~lex/files/dict.pdf

  3. D. Vandervoorde, N. Josuttis "C++ Szablony, Vademecum profesjonalisty", Helion S.A 2003.

  4. N. Josuttis "C++ Biblioteka Standardowa, podręcznik programisty", Wydawnictwo HELION 2003.

  5. Dokumentacja KOALI: http://kaims.pl/koala/

Liczba wykonawców

1 – 2

Uwagi

Wymagana bardzo dobra znajomość C++.

 

2.

Tytuł w j. polskim

Aplikacja wspomagająca zarządzanie czasem przez studentów

Tytuł w j. angielskim

Time management application for students

Opiekun pracy

dr inż. Krzysztof M. Ocetkiewicz

Konsultant pracy

 

Cel pracy

Celem pracy jest implementacja aplikacji wspomagającej zarządzanie czasem. Aplikacja powinna mieć postać aplikacji internetowej uzupełnionej o aplikację mobilną. Aplikacja powinna umożliwiać publikację planu zajęć, dodatkowych materiałów, ogłoszeń itp. oraz informować użytkowników o ważnych wydarzeniach w najbliższym czasie.

Zadania do wykonania

1. Przegląd istniejących rozwiązań;

2. Projekt systemu.

3. Implementacja;

4. Testy wydajnościowe;

5. Dokumentacja;

Literatura

1. https://www.w3.org/TR/html5/;

2. F. Ableson, R. Sen “Android w akcji";

3. https://docs.angularjs.org/api;

4. https://ionicframework.com/docs/;

5. www.w3schools.com/jsref/;

Liczba wykonawców

 

Uwagi

 

 

3.

Tytuł w j. polskim

Sprawdzanie zgodności strony WWW z przeglądarkami.

Tytuł w j. angielskim

Checking WWW page for browser compatibility.
 

Opiekun pracy

dr inż. Krzysztof M. Ocetkiewicz

Konsultant pracy

 

Cel pracy

Celem pracy jest implementacja narzędzia, które przegląda źródła strony WWW (HTML, CSS, JavaScript) i na ich podstawie określa minimalne wersje popularnych przeglądarek (np. Firefox, Chrome, Opera, IE, Edge) które poprawnie obsługują stronę. Przydatnym elementem byłoby wskazanie elementów, których usunięcie poprawiłoby zgodność.

Zadania do wykonania

1. Przegląd istniejących rozwiązań.

2. Implementacja analizatorów JavaScript, HTML, CSS.

3. Przygotowanie bazy danych zgodności elementów języków z wersjami przeglądarek.

4. Implementacja narzędzia.

4. Testy.

5. Dokumentacja.

Literatura

1. https://www.w3.org/TR/html5/;

2. www.w3schools.com/jsref/;

3. caniuse.com

4. https://www.w3.org/Style/CSS/

Liczba wykonawców

 

Uwagi

 

 

4.

Tytuł w j. polskim

Aplikacja wspomagająca tworzenie testów egzaminacyjnych z języka C++

Tytuł w j. angielskim

Application supporting construction of examination tests for C++ language

Opiekun pracy

dr hab. inż. Dariusz Dereniowski

Konsultant pracy

dr hab. inż. Dariusz Dereniowski

Cel pracy

Celem pracy jest utworzenie aplikacji w języku Java, która wspomaga tworzenie testów egzaminacyjnych. Aplikacja umożliwia automatyczne generowanie testów przy maksymalnym wykrywaniu ewentualnych błędów popełnianych przez osobę tworzącą arkusz egzaminacyjny (automatyczna kompilacja, tworzenie miejsc na odpowiedź itp.). Osoba układająca test dostarcza kod w języku C++ dla każdego z pytań oraz opracowuje kod w sposób określony przez program, natomiast zadaniem aplikacji jest wygenerowanie testu egzaminacyjnego oraz wygenerowanie szablonu z poprawnymi odpowiedziami do testu.

Zadania do wykonania

1. określenie wymagań;

2. utworzenie projektu systemu;

3. implementacja systemu;

4. przeprowadzenie testów

Literatura

materiały dydaktyczne z przedmiotu "Podstawy Programowania" (kier. Informatyka)

Liczba wykonawców

Temat jest przeznaczony do realizacji dla 4 osób.

 

Uwagi

Dostępny jest prototyp aplikacji, którego fragmenty można wykorzystać w toku prac.

 

5.

Tytuł w j. polskim

Program wspomagający obliczenia symboliczne

Tytuł w j. angielskim

A program that supports symbolic computations
 

Opiekun pracy

dr hab. inż. Robert Janczewski

Konsultant pracy

 

Cel pracy

Stworzenie programu realizującego wybrane obliczenia symboliczne w zbiorze liczb rzeczywistych.

Zadania do wykonania

1. Opracowanie struktur danych umożliwiających obliczenia symboliczne.

2. Implementacja kalkulatora symbolicznego – programu realizującego wybrane obliczenia symboliczne.

Literatura

1. Joel S. Cohen „Computer Algebra and Symbolic Computation”

Liczba wykonawców

 

Uwagi

 

 

6.

Tytuł w j. polskim

Program realizujący rozgrywkę brydżową

Tytuł w j. angielskim

A program that plays bridge

Opiekun pracy

dr hab. inż. Robert Janczewski

Konsultant pracy

 

Cel pracy

Stworzenie programu realizującego drugi etap gry w brydża, tj. rozgrywkę.

Zadania do wykonania

1. Zapoznanie się z zasadami gry.

2. Implementacja programu do gry w brydża z wykorzystaniem elementów sztucznej inteligencji.

Literatura

https://en.wikipedia.org/wiki/Contract_bridge

Liczba wykonawców

 

Uwagi

 

 

7.

Tytuł w j. polskim

Realistyczny symulator bilarda

Tytuł w j. angielskim

Realistic pool billiards simulator

Opiekun pracy

dr hab. inż. Robert Janczewski

Konsultant pracy

 

Cel pracy

Stworzenie programu do gry w bilarda działającego w oparciu o realistyczne modele matematyczne tej gry.

Zadania do wykonania

1. Zapoznanie się z zasadami gry i jej modelem matematycznym.

2. Implementacja programu.

Literatura

Burkhard Alpers „Modelling and Problem Solving in Billiards using DGS and Billiards Machine”

Liczba wykonawców

 

Uwagi

 

 

8.

Tytuł w j. polskim

Program rozpoznający i optymalnie kolorujący grafy-kaktusy

Tytuł w j. angielskim

A program that recognizes and colors cacti graphs
 

Opiekun pracy

dr hab. inż. Robert Janczewski

Konsultant pracy

 

Cel pracy

Implementacja wybranych algorytmów rozpoznawania i kolorowania kaktusów.
 

Zadania do wykonania

1. Zapoznanie się z kaktusami i algorytmami dekompozycji kaktusów.

2. Implementacja wybranych algorytmów dekompozycji, a następnie rozpoznawania i kolorowania kaktusów.

Literatura

R. J. Wilson „Wprowadzenie do teorii grafów”

Liczba wykonawców

 

Uwagi

 

 

9.

Tytuł w j. polskim

System plików oparty o znaczniki

Tytuł w j. angielskim

File system based on tags

Opiekun pracy

dr hab. inż. Robert Janczewski

Konsultant pracy

 

Cel pracy

Stworzenie programu symulującego system plików oparty o znaczniki.

Zadania do wykonania

1. Zapoznanie się z metodami automatycznej klasyfikacji zawartości plików.

2. Stworzenie programu symulującego system plików oparty o znaczniki.

Literatura

https://en.wikipedia.org/wiki/Semantic_file_system

Liczba wykonawców

 

 

10.

Tytuł w j. polskim

Tworzenie wieloplatformowych aplikacji ze wspólną logiką biznesową rozwijaną techniką TDD

Tytuł w j. angielskim

Application of TDD for development .Net Core and Xamarin cross-platform solutions with shared business logic
 

Opiekun pracy

dr inż. Krzysztof Manuszewski

Konsultant pracy

dr inż. Krzysztof Manuszewski

Cel pracy

Technologie pochodzące od firmy Microsoft .NET Core i Xamarin są stosunkowo nowe na rynku. Ich podstawową zaletą jest wieloplatformowość - programista pisze logikę biznesową tylko raz, a aplikacja dostępna jest na wielu platformach. W pisaniu logiki biznesowej pracę natomiast wspomaga technika TDD. Połączenie TDD z możliwościami wieloplatformowych bibliotek pozwala na ograniczenie czasu pracy oraz zapewnia redukcję błędów do minimum. Celem pracy jest stworzenie wieloplatformowej aplikacji z pomocą techniki TDD i technologiami platformy .NET, a także identyfikacja zalet i wad tego rozwiązania w stosunku do podejść w pełni natywnych.

Zadania do wykonania

1.  Zapoznanie się z techniką TDD, ASP.NET Core i Xamarin

2.  Identyfikacja wad i zalet podejścia wieloplatformowych bibliotek

3.  Zastosowanie odpowiedniego podziału warstw w celu optymalnego wykorzystania współdzielonego kodu

4.  Projekt i implementacja przykładowej aplikacji z wykorzystaniem podejścia TDD na wieloplatformowych bibliotekach

5.  Opracowanie sprawozdania z wykonanej pracy wraz z odpowiednimi wnioskami

Literatura

 

Liczba wykonawców

Temat jest przeznaczony do realizacji dla 2-4 osób.

Uwagi

 

11.

Tytuł w j. polskim

Sztuczna inteligencja dla nieklasycznej gry o umiarkowanej komplikacji zasad

Tytuł w j. angielskim

AI for modern game with moderate rules complexity

Opiekun pracy

dr inż. Krzysztof Manuszewski

Konsultant pracy

dr inż. Krzysztof Manuszewski

Cel pracy

Celem projektu jest stworzenie aplikacji umożliwiającej rozgrywkę w nowoczesną grę planszową lub karcianą o umiarkowanej komplikacji zasad i potencjalnie niepełnej informacji. Dobrym przykładem może być np. Gra Splendor lub Carcasonne. Rozwiązanie powinno obejmować platformę do rozgrywek testowych/trenowania SI i implementację samego algorytmu SI grającego zamiast człowieka.

Platforma może mieć uproszczony charakter. Głównym celem jest realizacja algorytmu grającego. Być może uda się zrealizować więcej niż jedno podejście do realizacji logiki gry np. np. klasyczny minimax z prostą funkcją oceniającą, funkcje oceniające wykorzystujące sieci neuronowe i/lub heurystyki ogólne.

Zadania do wykonania

  1. Wybór gry

  2. Projekt i realizacja silnika reguł i platformy do rozgrywek

3.  Projekt i realizacja algorytmu/ów grających

4.  Ocena jakości uzyskanych rozwiązań.

Literatura

 

Liczba wykonawców

Temat jest przeznaczony do realizacji dla 2-4 osób.

Uwagi

 

12.

Tytuł w j. polskim

Środowisko dla programu grającego w gry Tetris/Super Hexaggon.

Tytuł w j. angielskim

Environment for program playing Tetris/Super Hexaggon.

Opiekun pracy

dr inż. Krzysztof Manuszewski

Konsultant pracy

dr inż. Krzysztof Manuszewski

Cel pracy

Temat użycia sztucznej inteligencji w grach komputerowych ma wiele praktycznych zastosowań, np. w robotyce lub prace nad autonomicznym samochodem.  Od strony teoretycznej do budowy takich systemów używa się 'Reinforced learning', czyli dziedziny uczenia maszynowego związanego ze sterowaniem i podejmowaniem decyzji.

 

Celem projektu będzie w pierwszym rzędzie stworzenie środowiska uruchomieniowego, w którym możliwe będzie testowanie algorytmów grających w gry komputerowe. W pierwszym etapie prace dotyczyć będą jednej gry. W toku rozwoju projektu podjęta zostanie decyzja czy dalsze prace dotyczyć będą uogólnienie platformy dla różnych gier czy doskonalony będzie sam algorytm grający.

 

Potencjalnym kierunkiem rozwoju projektu jest wykorzystanie do konstrukcji algorytmu grającego algorytmów sztucznej inteligencji np. sieci neuronowych

Zadania do wykonania

  1. Wybór gry

  2. Projekt i realizacja prototypu

  3. Rozwój platformy/algorytmu grającego

 

Literatura

1. Tensorflow: https://www.tensorflow.org/

2. Publikacje dotyczące tematu gier:

http://cs231n.stanford.edu/reports2016/121_Report.pdf

https://gym.openai.com/

http://karpathy.github.io/2016/05/31/rl/

http://cs231n.stanford.edu/reports2016/115_Report.pdf

https://www.studocu.com/en-au/document/stanford-university/convolutional-neural-networks-for-visual-recognition/other/playing-super-hexagon-with-convolutional-neural-networks-milestone/751843/

Liczba wykonawców

2-4

Uwagi

 

 

13.

Tytuł w j. polskim

Monitorowanie wykorzystania procesora w aplikacjach działających na maszynie wirtualnej Java

Tytuł w j. angielskim

Monitoring of cpu usage for applications running on JVM

Opiekun pracy

dr inż. Krzysztof Manuszewski

Konsultant pracy

dr inż. Damian Bogdanowicz, Dynatrace sp. z o.o. 

Cel pracy

Problemy związane z wydajnością są jednymi z trudniejszych wyzwań, które nierzadko pojawiają się podczas tworzenia rozbudowanych systemów informatycznych. Jako programiści mamy często podejrzenia, gdzie problem może występować, aby to potwierdzić i w efekcie zaproponować rozwiązanie, należy dane miejsce zbadać. Użycie wielkiego i „ciężkiego” profilera uniwersalnego nie zawsze jest najlepszym i najprostszym rozwiązaniem. Już samo skonfigurowanie takiego narzędzia może okazać się nietrywialnym zadaniem. Należy też pamiętać, że profilery wprowadzą dodatkowy narzut na czas działania aplikacji, którego obecność może istotnie utrudnić analizę.

 

Celem pracy/projektu jest stworzenie narzędzia o charakterze „mini-profilera” przygotowanego w postaci biblioteki, którą można łatwo dołączyć do aplikacji. Zasadniczym zadaniem jakie powinno spełniać rozważane narzędzie jest profilowanie częstotliwości odwiedzania danego miejsca w programie (np. metody) i związanego z tym wykorzystania mocy obliczeniowej procesora. Kontrolowanie działania „mini-profilera” powinno być możliwe bądź to wprost z kodu źródłowego, bądź z prostego interfejsu w przeglądarce internetowej.

Zadania do wykonania

Zapoznanie się z literaturą i narzędziami open source

Implementacja narzędzia oraz interfejsu użytkownika do zarządzania działaniem profilera.

Implementacja interfejsu do raportowania wyników (np. można wykorzystać podejście „flame graphs”)

Przygotowanie testowych aplikacji/scenariuszy prezentujących działanie narzędzia.

Literatura

“Java Performance: The Definitive Guide”, Scott Oaks, O'Reilly Media 2014,

“Evaluating the accuracy of Java profilers”, T. Mytkowicz i in., ACM SIGPLAN Notices - PLDI’10,

“Blazing Performance with Flame Graphs”, Brendan Gregg, LISA’13.

Liczba wykonawców

2-4

Uwagi

 

 

14.

Tytuł w j. polskim

Rozwiązanie integrujące informacje diagnostyczne w przykładowym systemie rozproszonym

Tytuł w j. angielskim

Solution for purpose of aggregation of diagnostic information in referential distributed system

Opiekun pracy

dr inż. Krzysztof Manuszewski

Konsultant pracy

dr inż. Krzysztof Manuszewski

Cel pracy

Celem projektu jest praktyczna realizacja działającego rozwiązania, które można zaklasyfikować jako częściowy zamiennik/uzupełnienie systemów klasy APM. W rozbudowanych systemach rozproszonych krytyczne staje się gromadzenie i przetwarzanie informacji diagnostycznych. Nawet proste stwierdzenie przyczyn awarii jednego z komponentów/serwisów może wymagać bardzo czasochłonnych analiz rozproszonych logów / informacji diagnostycznych. Przy braku możliwości skorelowania różnych wydarzeń diagnostyka taka często okazuje się wręcz niemożliwa. Rozwiązania spotykane w tym obszarze mogą się plasować pomiędzy prostą wizualizacją stanu zdrowia systemu (health page); zbieraniem, łączeniem i wizualizacją danych o obciążeniu i skomplikowanym przetwarzaniem strumieni zdarzeń z wykorzystaniem silników przeszukiwawczych i narzędzi analitycznych.

W ramach projektu powinno powstać działające rozwiązanie pozwalające na wspieranie diagnostyki w rozbudowanym systemie rozproszonym.  Przykładowy stos technologiczny to:

  • Logstash - do przetwarzania i integracji logów lypu logstash

  • ElasticSearch - Silnik wyszukiwawczy

  • Kibana – eksploracja i wizualizacja danych.

  • StatsD – serwer zbierający metryki systemów

  • Rieman – strumieniowy przetwornik danych o zdarzeniach

  • Graphite – graficzna wizualizacja wyników

Zadania do wykonania

  1. Zapoznanie się z problemami diagnostycznymi w systemach rozproszonych i specyfiką rozwiązań APM

  2. Zapoznanie się z dostępnymi narzędziami i technologiami, które mogłyby zostać wykorzystane do realizacji projektu

  3. Projekt i realizacja modelowego systemu rozproszonego

  4. Budowa systemu integrującego informacje diagnostyczne i jego integracja z rozwiązaniem modelowym

Literatura

  1. YouTube: Visualizing Logs Using ElasticSearch, Logstash and Kibana MSDN

  2. http://www.artofmonitoring.com/TheArtOfMonitoring_sample.pdf

  3. Dokumentacja poszczególnych narzędzi

Liczba wykonawców

2 – 4

Uwagi

 

 

15.

Tytuł w j. polskim

Monitorowanie alokacji pamięci w aplikacjach działających na maszynie wirtualnej Java

Tytuł w j. angielskim

Memory allocation monitoring for applications running JVM

Opiekun pracy

dr inż. Piotr Borowiecki

Konsultant pracy

 

Cel pracy

Jedną z cech przypisywanych językowi Java jest jego bezpieczeństwo, objawiające się m.in. brakiem potrzeby zwalniania przydzielonej pamięci. Usuwanie nieużywanych obiektów odbywa się automatycznie, za pomocą mechanizmu odświecania (garbage collection), w który wyposażona jest maszyna wirtualna. Nie oznacza to jednak, że programista może całkowicie zignorować kwestie związane z przydzielaniem pamięci. Warto pamiętać, że tzw. wycieki pamięci pojawiają się również w środowiskach wyposażonych w mechanizm garbage collection. Odszukanie miejsca wycieku nie zawsze jest łatwe. Jedno z podejść to tego zagadnienia polega na wykorzystaniu uniwersalnej aplikacji diagnostycznej tzw. „profilera”. Jednak może okazać się że, już samo skonfigurowanie takiego narzędzia będzie nietrywialnym zadaniem. Co więcej, odszukanie interesujących nas pomiarów w rozbudowanym interfejsie może znacząco wydłużyć czas rozwiązywania problemu.

 

Alternatywą  dla dla wspominanych narzędzi jest użycie „mini-profilera” przygotowanego w postaci biblioteki, którą można łatwo dołączyć do aplikacji i kontrolować jej działanie bądź to wprost z kodu źródłowego, bądź z prostego interfejsu w przeglądarce internetowej.

 

Celem pracy/projektu jest stworzenie narzędzia o charakterze wspomnianego „mini-profilera” dedykowanego do profilowanie alokacji pamięci w programie, pozwalającego na m. in. wygodną analizę ilości oraz miejsca zaalokowanej pamięci na obiekty tymczasowe i permanentne.

Zadania do wykonania

  1. Zapoznanie się z literaturą i narzędziami open source.

  2. Implementacja narzędzia oraz interfejsu użytkownika.

  3. Implementacja interfejsu do raportowania wyników (np. można rozważyć użycie podejścia „flame graphs”).

  4. Przygotowanie testowych aplikacji/scenariuszy prezentujących działanie narzędzia.

Literatura

  1. “Java Performance: The Definitive Guide”, Scott Oaks, O'Reilly Media 2014,

  2. Dokumentacja/źródła projektu java-allocation-instrumenter, https://github.com/google/allocation-instrumenter,

  3. “Blazing Performance with Flame Graphs”, Brendan Gregg, LISA’13.

Liczba wykonawców

 

Uwagi

 

 

16.

Tytuł w j. polskim

Wieloosobowe gry planszowe na urządzenia mobilne

Tytuł w j. angielskim

Multiplayer board games for mobile devices

Opiekun pracy

dr inż. Piotr Borowiecki

Konsultant pracy

 

Cel pracy

Opracowanie zestawu wieloosobowych gier planszowych działających na urządzeniach przenośnych takich jak smartfon, tablet. Aplikacja powinna umożliwiać grę kilku graczom wykorzystującym równocześnie różne urządzenia.

Zadania do wykonania

  1. Wybór zestawu gier

  2. Wybór środowiska programistycznego

  3. Wykonanie projektu

  4. Implementacja i testowanie systemu

Literatura

  1. Robert Nystrom, Game programming patterns.

  2. James S. Cho, The begginer’s guide to Android game development.

Liczba wykonawców

 

Uwagi

 

 

17.

Tytuł w j. polskim

Optymalizacja półokreślona w wykrywaniu splątania kwantowego

Tytuł w j. angielskim

Semidefinite programming for entanglement detection

Opiekun pracy

dr inż. Piotr Mironowicz

Konsultant pracy

 

Cel pracy

Zapoznanie się z podstawami optymalizacji półokreślonej oraz problematyką separowalności macierzy gęstości (przydatna wiedza z algebry liniowej). Implementacja narzędzia do formułowania warunków separowalności macierzy dla środowiska OCTAVE z frameworkiem YALMIP.

Zadania do wykonania

1. Przegląd literatury.
2. Implementacja narzędzia w postaci skryptów w języku MATLAB.

3. Sporządzenie dokumentacji.

Literatura

1. L. Vandenberghe, S. Boyd, Semidefinite Programming, SIAM Review, 38(1): 49-95, March 1996 http://stanford.edu/~boyd/papers/sdp.html

2. A. Doherty, P. Parrilo, F. Spedalieri, Distinguishing separable and entangled states, Physical Review Letters, Vol. 88, No. 18, 187904, (2002) https://arxiv.org/abs/quant-ph/0112007

3. A. Doherty, P. Parrilo, F. Spedalieri, A complete family of separability criteria, Phys. Rev. A 69, 022308 (2004) https://arxiv.org/abs/quant-ph/0308032

Liczba wykonawców

 

Uwagi

Wskazane zainteresowanie teorią kwantów, w szczególności informatyką kwantową.

 

18.

Tytuł w j. polskim

Dwuwymiarowy RPG w klimacie fantazy

Tytuł w j. angielskim

Two dimensional fantasy RPG
 

Opiekun pracy

dr Piotr Mironowicz

Konsultant pracy

 

Cel pracy

Utworzenie dwuwymiarowej gry RPG w systemie i świecie zaproponowanym przed Dyplomanta z wykorzystaniem wybranego frameworka.

Zadania do wykonania

1. Opis systemu, świata i fabuły gry.

2. Opis wykorzystanego frameworka.

3. Implementacja gry.

Literatura

1.  https://www.slant.co/topics/341/~best-2d-game-engines

Liczba wykonawców

 

Uwagi

 

 

19.

Tytuł w j. polskim

Implementacja oparta na bibliotece Koala wybranych heurystycznych algorytmów ograniczonego kolorowanie grafów.

Tytuł w j. angielskim

Koala library based implementation of chosen heuristic algorithms for graph restricted coloring.

Opiekun pracy

dr Paweł Obszarski

Konsultant pracy

 

Cel pracy

Model ograniczonego kolorowania grafów stosowany jest w problemach szeregowania zadań. Jest on uogólnieniem klasycznego kolorowania grafów, w którym ograniczamy liczby wierzchołków w określonym kolorze. Celem pracy jest implementacja i przetestowanie wybranych algorytmów.

Zadania do wykonania

1. Przegląd literatury;
2. Implementacja algorytmów dokładnych dla wybranych klas grafów;
3. Opracowanie i implementacja algorytmów heurystycznych;
4. Testy i porównanie zaimplementowanych algorytmów.

Literatura

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, (2001), Introduction to Algorithms (2nd ed.).

2. Dokumentacja biblioteki Koala.

3. P. Obszarski, Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze, Automatyzacja procesów dyskretnych (2010).

4. Inne do konsultacji.

Liczba wykonawców

 

Uwagi

 

 

20.

Tytuł w j. polskim

Algorytmy przeszukiwania hipergrafów

Tytuł w j. angielskim

Hypergraph search algorithms
 

Opiekun pracy

dr Paweł Obszarski

Konsultant pracy

 

Cel pracy

Celem pracy jest analiza, implementacja i testy wybranych algorytmów przeszukiwania hipergrafów w kontekście różnych sposobów przechowywania hipergrafów.

Zadania do wykonania

1.  Przegląd literatury;
2.  Wybór struktur przechowujących hipergrafy;
3.  Wybór algorytmów przeszukiwania hipergrafów;
4.  Implementacja wybranych rozwiązań;

5.  Porównanie implementacji i testy.

Literatura

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, (2001), Introduction to Algorithms (2nd ed.).

2. Dokumentacja biblioteki Koala.

3. Do ustalenia i konsultacji.

Liczba wykonawców

 

Uwagi

 

 

21.

Tytuł w j. polskim

Symulator do testowania algorytmów spotkania dla mobilnych agentów

Tytuł w j. angielskim

A tool for the simulation of rendezvous algorithms for mobile agents

Opiekun pracy

dr inż. Łukasz Kuszner

Konsultant pracy

 

Cel pracy

Stworzenie symulatora do testowania algorytmów

Zadania do wykonania

1. Projekt i implementacja aplikacji.

2. Implementacja wybranych algorytmów.

3. Testy porównawcze.

Literatura

- D. Dereniowski, R. Klasing, A. Kosowski, Ł. Kuszner, Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks, Theoretical Computer Science, vol. 608 (3), 2015, 219-230,

- Symulator maszyny PRAM: http://sourceforge.net/p/prammachine/home/Home/

Liczba wykonawców

 

Uwagi

 

 

22.

Tytuł w j. polskim

Symulator do testowania algorytmów samostabilizujących

Tytuł w j. angielskim

A tool for the simulation of self-stabilizing algorithms

Opiekun pracy

dr inż. Łukasz Kuszner

Konsultant pracy

 

Cel pracy

Stworzenie symulatora do testowania algorytmów samostabilizujących.

Zadania do wykonania

1. Projekt aplikacji.

2. Implementacja.

Literatura

Shlomi Dolev. Self-Stabilization, The MIT Press, 2000

Symulator maszyny PRAM: http://sourceforge.net/p/prammachine/home/Home/

Liczba wykonawców

 

Uwagi

 

 

23.

Tytuł w j. polskim

Rozproszona ewakuacja mobilnych agentów

Tytuł w j. angielskim

Distributed evacuation of mobile agents

Opiekun pracy

dr inż. Łukasz Kuszner

Konsultant pracy

 

Cel pracy

Symulacja wybranych algorytmów ewakuacji mobilnych agentów.

Zadania do wykonania

1. Implementacja wybranych algorytmów.

2. Przeprowadzenie testów i opracowanie wyników.

Literatura

Clifford Stein, Rivest Ronald L, Cormen Thomas H., Leiserson Charles E., Wprowadzenie do algorytmów, PWN 2013.

P. Borowiecki, S. Das, D. Dereniowski, Ł. Kuszner, Distributed Evacuation in Graphs with Multiple Exits, LNCS 9988, 2016.

Liczba wykonawców

 

Uwagi

 

24.

Tytuł w j. polskim

Algorytmy dokładne dla problemów bezpieczeństwa w gridach

Tytuł w j. angielskim

Exact algorithms for security problems in grids

Opiekun pracy

dr hab. inż. Michał Małafiejski

Konsultant pracy

mgr inż. Kacper Wereszko

Cel pracy

Celem pracy jest komputerowe zweryfikowanie parametrów wybranych grafowych dla problemów bezpieczeństwa: koalicji wierzchołkowych i krawędziowych, zbiorów defensywnych oraz bezpiecznych, dla grafów, które są iloczynami kartezjańskimi ścieżek i cykli (Pn x Pm, Pn x Cm, Cn x Cm).

Zadania do wykonania

1. Zapoznanie się z literaturą.
2. Implementacja algorytmów (zalecane zrównoleglenie na klastrze obliczeniowym) wyczerpującego przeglądu (branch-and-bound, algorytmy programowania dynamicznego).

3. Testy algorytmów dla krat (grids) z ograniczoną liczbą wierzchołków w jednym z wymiarów.

4. Stworzenie katalogu wzorców rozwiązań oraz wypracowanie stosownych hipotez teoretycznych.

5. Próba udowodnienia wybranych hipotez (we współpracy z promotorem i konsultantem).

Literatura

1. R.Lewoń, A.Małafiejska, M.Małafiejski, Global defensive sets in graphs, Discrete Mathematics 339 (2016), 1861–1870

2. R.Lewoń, A.Małafiejska, M.Małafiejski, K.Wereszko, R.Kozakiewicz, Global edge alliances, in preparation

Liczba wykonawców

1 - 3

Uwagi

Temat o potencjalnym charakterze badawczym, możliwy do kontynuowania w ramach pracy magisterskiej. Wymagane solidne podstawy matematyczne.

 

25.

Tytuł w j. polskim

Przeszukiwanie przestrzeni grafów z ograniczonym stopniem dla problemów końcówkowego kolorowania grafów

Tytuł w j. angielskim

Searching for graphs with bounded degree for the incidence coloring problems

Opiekun pracy

dr hab. inż. Michał Małafiejski

Konsultant pracy

dr inż. Anna Małafiejska

Cel pracy

Celem pracy jest implementacja wydajnych algorytmów (w architekturze równoległej (klastrowej, CUDA, etc)) wyznaczających liczby chromatyczne grafów z ograniczonym maksymalnym stopniem,stworzenie katalogu małych grafów dla problemów: końcówkowego kolorowania grafów, zwartego kolorowania grafów, kolorowania incydentorów grafów.

Zadania do wykonania

1. Zapoznanie się z literaturą.
2. Implementacja algorytmów.

3. Testy algorytmów dla grafów z ograniczonym stopniem.

4. Weryfikacja komputerowa wybranych hipotez: ICC dla grafów z  ze stopniem co najwyżej 4, hipoteza IICC dla grafów ze stopniem co najwyżej 4, własność dziedziczności dla grafów podkubicznych, IIR(1,1)-kolorowanie dla grafów ze stopniem co najwyżej 5.

Literatura

1. Janczewski R., Małafiejska A., Małafiejski M., Interval incidence coloring of bipartite graphs, Discrete Applied Mathematics 166 (2014), 131–140

2. Janczewski R., Małafiejska A., Małafiejski M., Interval incidence graph coloring, Discrete Applied Mathematics 182 (2015), 73–83

3. Maydanskiy M., The incidence coloring conjecture for graphs of  maximum degree 3, Discrete Mathematics 292 (2005), 131–141

Liczba wykonawców

Temat o potencjalnym charakterze badawczym, możliwy do kontynuowania w ramach pracy magisterskiej. Wymagane solidne podstawy matematyczne.

Uwagi

1 - 3

 

26.

Tytuł w j. polskim

Szeregowanie zadań wieloprocesorowych wykorzystujących dedykowane zasoby maszynowe

Tytuł w j. angielskim

Scheduling of mutiprocessor tasks using dedicated resources

Opiekun pracy

dr hab. inż. Michał Małafiejski

Konsultant pracy

mgr inż. Krzysztof Pastuszak, dr inż. Krzysztof Ocetkiewicz

Cel pracy

Celem pracy jest implementacja i przetestowanie opracowanych algorytmów opartych o metody programowania dynamicznego dla problemów szeregowania zadań jedno- i wieloprocesorowych wykorzystujących dedykowane zasoby (procesory).

Zadania do wykonania

1. Zapoznanie się z modelami szeregowania wieloprocesorowego.

2. Zapoznanie się z algorytmami programowania dynamicznego dla wybranych problemów szeregowania.

3. Implementacja algorytmów znajdowania ważonych skojarzeń.

4. Implementacja wybranych algorytmów szeregowania zadań.

5. Optymalizacja złożoności i wydajności wybranych algorytmów szeregowania zadań.

6. Opracowanie i implementacja wydajnych algorytmów heurystycznych.

Literatura

Małafiejski M., Ocetkiewicz K., Pastuszak K., Efficient algorithms for scheduling one- and multiprocessor tasks with dedicated processor resources, in preparation

Biblioteka Koala: http://koala.os.niwa.gda.pl/api/

Goemans-Williamson Algorithm for Minimum Weight Perfect Matching ( https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/teaching/adm2ss14/lectures/lecture.11.2014-05-23.pdf )

Liczba wykonawców

Temat o potencjalnym charakterze badawczym, możliwy do kontynuowania w ramach pracy magisterskiej. Wymagane solidne podstawy matematyczne.

Uwagi

1 - 3