Tematy mgr | Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej

Finite automata algorithms in 2-dimensional space

dr hab. inż. Dariusz Dereniowski

1.

Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc: Building a Nest by an Automaton. ESA 2019: 35:1-35:14

2.

Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann: Forming Tile Shapes with Simple Robots. DNA 2018: 122-138

3.

Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler: Shape Recognition by a Finite Automaton Robot. MFCS 2018: 52:1-52:15

dr hab. inż. Robert Janczewski

1. Zapoznanie się ze współczesnymi atakami na aplikacje internetowe.

2. Analiza metod zapewniających bezpieczeństwo aplikacji.

3. Stworzenie aplikacji internetowej z zastosowaniem wybranych zabezpieczeń.

4. Weryfikacja bezpieczeństwa aplikacji i ocena skuteczności zaimplementowanych rozwiązań.

Analiza systemów kwantowej wymiany klucza

Analysis of quantum key distribution systems

dr inż. Piotr Mironowicz

Celem pracy jest przegląd, analiza, udoskonalenie i implementacja protokołów kwantowej wymiany klucza wykorzystywanych w praktycznych zastosowaniach, w wymianie informacji przy użyciu istniejących urządzeń oraz teoretycznych koncepcji.

Nicolas Gisin, Grégoire Ribordy, Wolfgang Tittel, and Hugo Zbinden, Quantum Cryoptography, Rev. Mod. Phys. 74, 145, (2002).

Lluis Masanes, Stefano Pironio, Antonio Acin, Secure device-independent quantum key distribution with causally independent measurement devices, Nat. Commun. 2, 238 (2011).

Analiza własności skojarzeniowych metryk filogenetycznych na drzewach losowych.

Analysis of matching phylogenetic metrics on random trees

prof. dr hab. inż. Krzysztof Giaro

Metryki filogenetyczne pozwalają na porównywanie drzew filogenetycznych, będących alternatywnymi hipotezami odnośnie historii ewolucji grupy badanych gatunków. Metryki skojarzeniowe (matching metrics) stanowią nowy, ogólny wzorzec definicji takich miar, wprowadzają w zbiorze drzew strukturę przestrzeni metrycznej odwołując się do zagadnienia najlżejszego skojarzenia w grafie dwudzielnym. Celem pracy jest statystyczna analiza własności wybranych miar tego rodzaju oraz weryfikacja wybranych hipotez badawczych na małych lub losowych filogenezach.

1.

Zapoznanie się z wybranymi tematami filogenetyki komputerowej, w szczególności analizą porównawczą filogenez.

2.

Zapoznanie się z wzorcem metryk skojarzeniowych oraz ich własnościami.

3.

Implementacja generatorów drzew filogenetycznych w modelach losowania równomiernego, Yule'a, a-model oraz sporządzenie pełnego katalogu małych drzew.

4.

Efektywna implementacja algorytmów wyznaczania wybranych metryk skojarzeniowych.

5.

Wyznaczenie i analiza rozkładów wartości metryk dla szerokiego zakresu liczebności gatunków w różnych modelach losowania.

6.

Weryfikacja wybranych hipotez badawczych odnośnie zależności między metrykami.

1.

Bryant, Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis. University of Canterbury 1997.

2.

Semple, Steel, Phylogenetics. Oxford University Press, 2003.

3.

Bogdanowicz, Giaro, Matching split distance for unrooted binary phylogenetic trees, IEEE/ACM Trans. on Comp. Biol. and Bioinformatics, 9 (2012).

4.

Bogdanowicz, Giaro, Comparing phylogenetic trees by matching nodes using the transfer distance between partitions, J. Comp. Biol., Vol. 24, No. 5 (2017).

5.

Materiały własne opiekuna.

Dobrowolne udostępnianie zasobów w internetowej aplikacji open-source

Volunteer resource sharing in open-source web application

dr inż. Krzysztof Manuszewski

Sprawdzenie możliwości skalowania aplikacji non-profit poprzez udostępnianie mocy obliczeniowej przez dobrowolnych użytkowników. Rozwiązanie analogiczne do często stosowanego mirroringu zasobów statycznych stosowanego w repozytoriach pakietów dystrybucji Linuksowych dla dynamicznych danych.

1. Opracowanie oraz implementacja aplikacji opartej o skalowalne API

2. Umożliwienie dobrowolnego podłączania dodatkowych serwerów API przez użytkowników zewnętrznych

3. Wykonanie badań pozwalających na oszacowanie wpływu takiej architektury na wydajność aplikacji

4. Analiza uzyskanych danych, opracowanie wniosków i dokumentacji testowanego projektu

1. https://restfulapi.net/

2. https://cloud.google.com/solutions/scalable-and-resilient-apps

3. https://en.wikipedia.org/wiki/Mirror_site

Krawędziowe kolorowanie grafów ze znakiem

Edge coloring of signed graphs

dr hab. inż. Robert Janczewski

Implementacja i analiza istniejących oraz opracowanie nowych algorytmów kolorujących krawędziowo grafy ze znakiem.

1. Zapoznanie się z tematyką krawędziowego kolorowania grafów ze znakiem.

2. Implementacja i analiza wybranych algorytmów krawędziowego kolorowania grafów ze znakiem.

3. Opracowanie nowych, efektywnych algorytmów kolorujących optymalnie wybrane klasy grafów ze znakiem.

Richard Behr: "Edge coloring signed graphs", Discrete Mathematics 343 (2020),

Metody abstrakcyjnej sumaryzacji tekstu

Abstractive text summarization

dr inż. Krzysztof Manuszewski

1. Przegląd znanych w literaturze podejść do abstrakcyjnej sumaryzacji tekstu. 

2. Identyfikacja problemu(ów) do wykonania teoretycznej lub eksperymentalnej analizy. 

3. Przeprowadzenie wybranych doświadczeń. 

4. Opcjonalne zaproponowanie własnej metody podejścia do problemu.

1. I.Goodfellow, Y.Bengio, A.Courville: Deep Learning, MIT Press 

2. B.Steven: Natural Language Processing with Python, O'Reilly Media, Inc 2009

Modele kolorowania a grafy po wybranych przekształceniach

Graph coloring models and their behaviours after chosen transformations

dr Marcin Jurkiewicz

1) Wyznaczenie wartości liczby chromatycznej (różnych wariantów) dla zadanych grafów po wybranych przekształceniach

2) Oszacowanie (doświadczalne lub teoretyczne) wskaźnika Witsenhausena dla wybranych źródeł.

1) Przegląd modeli kolorowania dla grafów, które powstały po zastosowaniu określonych operacji

2) Zaimplementowanie algorytmu szacującego wskaźnik Witsenhausena dla wybranych źródeł

3) Zaimplementowanie wybranych modeli w systemie Gurobi

Kubale M. "Optymalizacja dyskretna", WNT 2002

Jurkiewicz M. "Szacowanie kanałowej przepustowości Shannona metodami teoriografowymi", Praca doktorska 2019

Witsenhausen H. "The zero-error side information problem and chromatic numbers" IEEE Transactions on information theory Vol. 22, 5 (1976)

Modele rzeczywistych sieci złożonych

Models of real complex networks

dr Marcin Jurkiewicz

1) Napisanie przeglądu zawierającego sposoby modelowania wielkich rozszerzających się sieci złożonych (modele wskazane przez opiekuna).

2) Zaimplementowanie i porównanie wspomnianych modeli.

1) Implementacja oraz przetestowanie niektórych modeli rzeczywistych sieci złożonych w językach C/C++ i Python.

2) Implementacja oraz przetestowanie niektórych parametrów rzeczywistych sieci złożonych w językach C/C++ i Python.

3) Opis zachowania oraz porównanie kluczowych parametrów powiększających się sieci złożonych

Newman, Mark. Networks. Oxford university press, 2018.

Dehmer, Matthias, ed. Structural analysis of complex networks. Springer Science & Business Media, 2010.

Barabási, Albert-László, Erzsébet Ravasz, and Tamas Vicsek. "Deterministic scale-free networks." Physica A: Statistical Mechanics and its Applications 299.3-4 (2001): 559-564.

Jiang, Wenchao, et al. "An Efficient Method of Generating Deterministic Small-World and Scale-Free Graphs for Simulating Real-World Networks." IEEE Access 6 (2018): 59833-59842.

Comellas, Francesc, and Michael Sampels. "Deterministic small-world networks." Physica A: Statistical Mechanics and its Applications 309.1-2 (2002): 231-235.

Lu, Zhe-Ming, Yu-Xin Su, and Shi-Ze Guo. "Deterministic scale-free small-world networks of arbitrary order." Physica A: Statistical Mechanics and its Applications 392.17 (2013): 3555-3562.

prof. dr hab. inż. Marek Kubale

mgr inż. Tytus Pikies

1. Przegląd literatury

2. Opracowanie własnych algorytmów

3. Implementacja wybranych algorytmów

1.On Minimizing the Makespan When Some Jobs

Cannot Be Assigned on the Same Machine, Syamantak Das and Andreas Wiese, 25th Annual European Symposium on Algorithms (ESA 2017)

2. An EPTAS for Machine Scheduling with Bag-Constraints, Kilian Grage, Klaus Jansen, Kim-Manuel Klein, SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures

 3. Scheduling Jobs Given in Cliques with Respect to

Total Completion Time, Klaus Jansen, Alexandra Lassota, Marten Maack, Tytus Pikies, sent to MFCS 2020

Opracowanie i implementacja algorytmów dokładnych, przybliżonych i heurystycznych dla wybranych podproblemów problemu szeregowania zadań w obecności konfliktów między zadaniami modelowalnych jako kliki.

Exact, approximate and heuristic algorithms for selected subproblems of the problem of scheduling on unrelated machines, under incompatibility constraints between jobs modeled by cliques.

prof. dr hab. inż. Marek Kubale

mgr inż. Tytus Pikies

Celem pracy jest opracowanie algorytmów dla wybranych problemów, jak również ich implementacja. W przypadku danych generowanych losowo implementacja i pomiary ma na celu określenie jak szybko algorytmy będą w zachowaniu zbliżać się do zachowania asymptotycznego - "dla dużych danych".

1. Przegląd literatury

2. Opracowanie własnych algorytmów

3. Implementacja wybranych algorytmów

1. On Minimizing the Makespan When Some Jobs

Cannot Be Assigned on the Same Machine, Syamantak Das and Andreas Wiese, 25th Annual European Symposium on Algorithms (ESA 2017)

2. Scheduling Jobs Given in Cliques with Respect to

Total Completion Time, Klaus Jansen, Alexandra Lassota, Marten Maack, Tytus Pikies, sent to MFCS 2020

3. Random Graphs, Second Edition, Béla Bollobás, Cambridge Studies in Advanced Mathematics 73, Cambridge University Press 2011

4. On-line bin packing — A restricted survey, Gábor Galambos & Gerhard J. Woeginger, Zeitschrift für Operations Research

Podziały grafów – algorytmy i zastosowania

Graph partitioning – algorithms and applications

dr hab. inż. Piotr Borowiecki

Celem pracy jest dokonanie przeglądu systematyzującego różne warianty problemu podziału grafów, opisanie ich zastosowań, np. w optymalizacji obliczeń wysokiej wydajności  (ang. High Performance Computing - HPC) i znanych algorytmów. Cennym uzupełnieniem będzie przedstawienie analizy znanych wyników eksperymentalnych oraz implementacja  wybranych algorytmów i ich eksperymentalne porównanie.

1. Zapoznanie się z literaturą przedmiotu.

2. Przegląd wariantów problemu i ich zastosowań

3. Przegląd znanych algorytmów

4. Eksperymentalne porównanie wybranych algorytmów.

1. Graph partition – http//wikipedia.org/wiki/Graph_partition

2. Christian Schulz, Graph Partitioning and Graph Clustering in Theory and Practice – Course Notes (2016)

3. Inne pozycje literatury dostępne u opiekuna pracy

Projektowanie i implementacja skalowalnej aplikacji backendowej z wykorzystaniem podejścia chmurowego

Robust architectural design and implementation of scalable backend cloud-native application."

dr inż. Krzysztof Manuszewski

Celem pracy jest dokonanie przeglądu literatury i zebranie/wypracowanie wskazówek projektowych i implementacyjnych w zakresie realizacji aplikacji backendowych w kontekście technologii i rozwiązań chmurowych.

Ciekawe zagadnienia to np.:

Przegląd literatury z uwzględnienieniem podejścia DDD i mechanizmów chmurowych w kontekście realizacji aplikacji.

Eksperymenty implementacyjne w zakresie implementacji rozwiązań backendowych.

Teoretyczne opracowanie wyników.

Zebranie zaleceń dla projektowania oraz implementacji rozproszonych aplikacji backendowych przy uwzględnieniu specyfiki rozwiązań chmurowych.

Freeman, Pryce, Growing object-oriented software guided by tests, OReilly 2009

Newman S., Building Microservices OReilly 2015 i/lub Monolith to Microservices OReilly 2019

Nygard M., Release It! (sec ed.), Pragmatic Bookshelf 2018

Kleppmann, Designing Data intensive apps, OReilly 2017

Long J, Bastanni K., Cloud Native Java, OReilly 2017

Evans, Domain-driven Design, Addison-WesleyProfessional 2003

Rozbudowa serwisu Visual TreeCmp

Development of the Visual TreeCmp website

prof. dr hab. inż. Krzysztof Giaro

mgr inż. Tomasz Goluch                                

Serwis Visual TreeCmp dostępny jest pod adresem: https://eti.pg.edu.pl/treecmp/. Zaimplementowany jest w oparciu o platformę Spring. Pozwala na porównywanie i wizualizację drzew filogenetycznych wykorzystując bogaty zbiór metryk. Celem pracy jest rozszerzenie funkcjonalności o algorytmy wyznaczania nowych metryk lub ich wariantów, a także poprawa wydajności wyznaczania miar MAST i UMAST. Ponadto dla metryk matching’owych (MS, MC, MP, MT) należy wizualizować skojarzenie dopasowanych kladów.

Testowanie i ocena algorytmów uczenia ze wzmocnieniem.

Judging Reinforced Learning Algorithms System

dr inż. Krzysztof Manuszewski

Zbadanie możliwości realizacji systemu pozwalającego na konkursową ocenę algorytmów uczenia ze wzmocnieniem.

Możliwym rozwiązaniem jest system zbliżony do Kaggle, ale dla oceny tego rodzaju problemów nie wystarczy analiza danych statycznych. Wymagane jest przeprowadzenie cyklu symulacji (np gry).

Pot. system bedacy przedmiotem niniejszej pracy musiałby uwzględniać takie problemy jak

hostowanie środowiska symulacyjnego (zakładamy wykorzystanie gotowych rozwiązań kompatybilnych z openai gym) i

dostarczać webowego gui do zarzadzania kontestami/wynikami

nadzorować (pot rozproszone) srodowisko wykonawcze.

1. Analiza problemu i specyfikacja wymagań

2. Analiza dostępnych technologii izolacji procesów i rozmieszczania zadań.

3. Wybór technologii i projekt architektury systemu

4. Implementacja i testowanie systemu

5. Opracowanie dokumentacji projektu

Topologiczne indeksy grafowe

Topological Graph Indices

dr hab. inż. Piotr Borowiecki

Indeksy topologiczne mają istotne zastosowania m.in. w procesach selekcji i doboru w systemach wspomagających projektowanie związków chemicznych. Celem pracy jest dokonanie systematyzującego przeglądu topologicznych indeksów grafowych, które można wyznaczyć na podstawie grafu molekularnego danego związku chemicznego. W ramach przeglądu przewidywane jest opisanie własności wybranych indeksów topologicznych, ich powiązań z własnościami związków chemicznych i możliwości dyskryminacyjnych. Należy też przedstawić stan wiedzy dotyczącej złożoności obliczeniowej problemu wyznaczania poszczególnych indeksów,  a także algorytmów wyznaczania ich wartości lub oszacowań.

1. Zapoznanie się z literatura przedmiotu.

2. Wybór indeksów topologicznych.

3. Opisanie wybranych indeksów, ich własności oraz powiązań z własnościami związków chemicznych (przykłady zastosowań).

4. Analiza złożoności obliczeniowej problemu wyznaczania wybranych indeksów – podanie algorytmów i znanych oszacowań.

5. Implementacja wybranych algorytmów, ich porównanie, oszacowanie efektywności i czasów działania.

1.Topological index – http//wikipedia.org/wiki/Topological_index

2. I.Gutman, Degree-Based Topological Indices,  Croat. Chem. Acta 86(4) (2013) 351-361.

3. K.Das, I.Gutman, B.Furtula, Survey on Geometric-Arithmetic Indices of Graphs, MATCH Commun. Math. Comput. Chem. 65 (2011) 595-644.

4. Inne pozycje literatury dostępne u opiekuna pracy

dr hab. inż. Robert Janczewski

Celem pracy jest analiza dostępnych rozwiązań pozwalających na zarządzanie stanem w aplikacjach wykorzystujących bibliotekę React.js. Należy przeanalizować wady oferowanego przez React.js mechanizmu setState() oraz zbadać dostępne alternatywy - między innymi Context API, czy zewnętrzne biblioteki takie jak MobX i Redux. Wynikiem pracy ma być aplikacja prezentująca możliwości każdego z wymienionych mechanizmów.

1. Analiza problemu zarządzania stanem w aplikacjach internetowych.

2. Przegląd rozwiązań oferowanych przez React.js - setState().

3. Analiza możliwości zarządzania stanem z wykorzystaniem Context API oraz React Hooks.

4. Przegląd zewnętrznych bibliotek: MobX, Redux (architektura Flux).

5. Implementacja aplikacji przedstawiającej omówione narzędzia.

1. Adam Boduch, Flux architecture, Packt Publishing 2016.

2. Alex Banks, Eve Porcello, Learning React: Functional Web. Development with React and Redux, O'Reilly Media 2017.

3. Pavan Podila, Michel Weststrate, MobX Quick Start Guide: Supercharge the client state in your React apps with MobX, Packt Publishing 2016.

4. Adam Freeman, Pro React 16, Apress 2019.

Zrównoleglanie wybranych algorytmów grafowych na GPU.

Parallelization of chosen graph algorithms on GPU.

dr Paweł Obszarski

Celem pracy jest zbadanie możliwości zrównoleglania algorytmów grafowych. Porównanie ich wydajności w kontekście wydajności teoretycznej oraz analogicznych algorytmów na CPU.

1. Zbadanie literatury.

2. Analiza teoretyczna i wybór algorytmów.

3. Implementacja wybranych algorytmów z umożliwieniem wykorzystania GPU.

4. Testy wydajnościowe i porównanie z rozwiązaniami operującymi na CPU.

1. R. Anderson, The Complexity of Parallel Algorithms

2. D. A. Bader, Parallel Graph Algorithms (Chapman & Hall/CRC Computational Science)

Do ustalenia z dyplomantem

1.

Zbadanie problematyki i porównanie renderowania odroczonego z tradycyjnym renderowaniem wprzód (ang. forward rendering).

2.

Opis i analiza renderowania sceny w przykładowej grze 3d używającej cieniowania odroczonego.

3.

Projekt i implementacja silnika graficznego.

4.

Wyrenderowanie i omówienie przykładowej sceny.

1.

Paweł Lapiński: Vulkan Cookbook, Packt Publishing 2017

2.

Matt Pharr, Randima Fernando: GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation, Addison-Wesley Professional 2005

3.

The Khronos Vulkan Working Group, Vulkan 1.2.144 - A Specification (with KHR extensions)