Differences

This shows you the differences between two versions of the page.

--- tematy_prac_inzynierskich [2019/07/01 00:55]
pszwed [6. Optymalizacja na GPU]
+++ tematy_prac_inzynierskich [2020/06/28 02:57]
pszwed [2020]
@@ Line 1: / Line 1: @@
+===== Struktura pracy =====
+  *[[struktura_pracy_inz|Struktura pracy]]
+  *[[prace_inz_uwagi|Uwagi]]
+  *[[proces_dyplomowania|Proces dyplomowania]]
 ====== Tematy prac inżynierskich ======
+===== 2020 =====
+  *Map matching
+  *Algorytmy optymalizacji
+  *Grupowanie grawitacyjne
+  *Generacja i testy Negatywnych Baz Danych
+==== 1. Map matching ====
+Zarezerwowane jako implementacja w Pythonie? :?:
+(a) Implementacja (znanego) algorytmu rzutowania sekwencji odczytów GPS na mapę w postaci procedur składowanych dla PostgreSQL/PostGIS, na podsatwie [[https://www.researchgate.net/publication/263855222_SLIDES_An_Incremental_Map-Matching_Algorithm_Based_on_Hidden_Markov_Model]]
+Procedury mogą być zaimplementowane w
+  - [[https://www.postgresql.org/docs/9.2/plpgsql.html]] preferowane, łatwe w konfiguracji i wydajne
+  - Java lub Pythonie (trudniejsze w konfiguracji i dyskusyjne wydajnościowo)
+(b) Alternatywnie, dla mapy przechowywanej w pamięci w językach Java lub Python, ale konieczna implementacja funkcjonalności, które są w PostGIS zaimplementowane (indeksy przestrzene, obliczanie odleglości) oraz wstępne prztewarzanie danych mapy.
+Zakres:
+  - załaduj mapę oryginalną
+  - podziel drogę na segmenty (od skrzyżowania do skrzyżowania)
+  - dodaj tabele/struktury danych do przechowywania ścieżek GPS
+  - dodaj tabele/struktury danych na graf przypisujący odczyty do punktów na odcinkach dróg
+  - napisz procedurę, która dla nowego punktu:
+    - rozszerza graf o nowe możliwe wierzchołki //expansion//
+    - usuwa z grafu wierchołki, z których nie można kontynuować //contraction//
+  - podprocedury powinny mieć warianty lub być sterowane parametrami
+  - Testy:
+    - jakościowe - czy ścieżki są odwzorowane poprawnie
+    - wydajnościowe - ile zapytań można przetwarzać w jednostce czasu, ewentualnie grupowanie punktów jednej ściezki
+==== 2. Algorytmy optymalizacji ciagłej z użyciem numpy ====
+To jest temat, który można rozszerzyć na kilka algorytmów. Wspólną cechą ma być:
+  * wykorzystanie operacji biblioteki numpy. Mimo, że są funkcjami Pythona, sa zaimplementowane w C i działają wydajnie
+  * Zamiast wykonywac operacje na pojedynczych osobnikach (wektorach w R^n), maja być przeprowadzane operacje na całych macierzach (w których wiersz odpowiada osobnikowi)
+  * uzycie do testów funkcji z konferencji CEC [[http://www.tflsgo.org/special_sessions/cec2019]]. Konieczna jest ich reimplementacja. Funkcje CEC wykorzystują kilkanascie funkcji bazowych, które następnie są zniekształcane przez przesuniecia i rotacje. W przypadku kilku prac można zestw funkcji opracować wspólnie.
+  * Z reguły algorytmy mają jakieś parametry. Dla danej funkcji  należy przeprowadzić dobór parametrów przez losowe lub systematyczne przeszukanie przestrzeni parametrów.
+  * Wybór macierzowej reprezentacji może powodować pewne niewielkie odstepstwa od bazowego algorytmu mające na celu przyspieszenie obliczeń
+  * Działanie algorytmu należy przetestować, np. wyznaczajac najlepszą wartośc funkcji 10 razy, podać wartości srednie, odchylenia standardowe, itp
+=== 2.a PSO ===
+Implementacja algorytmu Particle Swarm Optimization. Należy zaimplementować rózne topologie:
+  * globalną
+  * sąsiedzi
+  * losowowanie grafu
+=== 2.b Algorytm mrówkowy ===
+Implementacja algorytmu mrówkowego, np. wykorzytsujac idee z [[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4037618/]]
+=== 2.c Algorytm pszczeli ===
+Istnieje kilka wersji...
+=== 2.d ===
+Inne do przedyskutowania..., np [[https://troja.uksw.edu.pl/zasoby/SL2014-ZhangSanderson2009.pdf]]
+==== 3. Grupowanie grawitacyjne ====
+Grupowanie (klasteryzacja) to proces łączenia danych w grupy. Przez dane rozumiane są tu wektory w R^n. Zazwyczaj oczekuje się, że grupy będą od siebie oddalone, natomiast dane należące do jednej grupy położone blisko siebie. Przy grupowaniu grawitacyjnym wykorzystuje się model sił grawitacji - blisko położone punkty przyciągają się mocniej i skupiają w grupy.
+Celem pracy jest implementacja kilku znanych wersji algorytmu grupowania grawitacyjnego i przetestowanie ich działania.  Testy mają obejmować  [[https://scikit-learn.org/stable/modules/clustering.html|typowe przykłady 2D]] oraz kilkanaście zbiorów danych z repozytorium UCI.
+Język implementacji Python.
 ===== 2019 =====
+Obecnie zarezerwowanych jest 12/12
+:!: ** Nie podejmuję się prowadzenia kolejnych prac ze wzgledu na osiągnięcie limitu** :!:
 ==== 1. Wizualizacja danych geograficznych ====
 :!: Rezerwacja
@@ Line 9: / Line 87: @@
 ==== 2. Narzędzia WebScraping ====
+:!: Rezerwacja
 Przegląd i porównanie narzędzi WebScraping dla kilku przykładowych zadań, np. zbieranie danych z serwisu nieruchomości lub samochodów, zbieranie publikacji prasowych na popularnych portalach, produktów z Allegro, itp. Zakres zadań do uzgodnienia.
 ==== 3. Map matching ====
-(a) Implementacja (znanego) algorytmu rzutowania sekwencji odczytów GPS na mapę w postaci procedur składowanych dla PostgreSQL/PostGIS.
+(a) Implementacja (znanego) algorytmu rzutowania sekwencji odczytów GPS na mapę w postaci procedur składowanych dla PostgreSQL/PostGIS, na podsatwie [[https://www.researchgate.net/publication/263855222_SLIDES_An_Incremental_Map-Matching_Algorithm_Based_on_Hidden_Markov_Model]]
-(b) Alternatywnie, dla mapy przecowywanej w pamięci w językach Java lub Python, ale konieczna implementacja funkcjonalności, które są w PostGIS zaimplementowane (indeksy przestrzene, obliczanie odleglości) oraz wstępne prztewarzanie danych mapy.
+Procedury mogą być zaimplementowane w
+  - [[https://www.postgresql.org/docs/9.2/plpgsql.html]] preferowane, łatwe w konfiguracji i wydajne
+  - Java lub Pythonie (trudniejsze w konfiguracji i dyskusyjne wydajnościowo)
+(b) Alternatywnie, dla mapy przechowywanej w pamięci w językach Java lub Python, ale konieczna implementacja funkcjonalności, które są w PostGIS zaimplementowane (indeksy przestrzene, obliczanie odleglości) oraz wstępne prztewarzanie danych mapy.
+Zakres:
+  - załaduj mapę oryginalną
+  - podziel drogę na segmenty (od skrzyżowania do skrzyżowania)
+  - dodaj tabele/struktury danych do przechowywania ścieżek GPS
+  - dodaj tabele/struktury danych na graf przypisujący odczyty do punktów na odcinkach dróg
+  - napisz procedurę, która dla nowego punktu:
+    - rozszerza graf o nowe możliwe wierzchołki //expansion//
+    - usuwa z grafu wierchołki, z których nie można kontynuować //contraction//
+  - podprocedury powinny mieć warianty lub być sterowane parametrami
+  - Testy:
+    - jakościowe - czy ścieżki są odwzorowane poprawnie
+    - wydajnościowe - ile zapytań można przetwarzać w jednostce czasu, ewentualnie grupowanie punktów jednej ściezki
 ==== 4. Wykorzystannie reguł rozmytych do rekomendacji produktów ====
 :!: Rezerwacja
@@ Line 22: / Line 119: @@
 ==== 5. Aplikacja webowa do edycji dokumentacji projektowej ====
+:!: Rezerwacja
 Projekt w stylu [[http://home.agh.edu.pl/~pszwed/wiki/doku.php?id=amo:projekt]]
 Konfigurowalna struktura dokumentu: [[http://home.agh.edu.pl/~pszwed/wiki/doku.php?id=amo:rup_tailored]]
@@ Line 27: / Line 126: @@
 ==== 6. Optymalizacja na GPU ====
 Implementacja popularnych algorytmów optymalizacji ciągłej na GPU: CUDA lub OpenCL. //Takich prac może być wiecej...//
@@ Line 48: / Line 148: @@
   - WebAssembly
   - Rekomendacja/ocena utworów muzycznych
-  - Przepisy
+  - Przepisy (zamienione na web crawling + walidację)
+  - Smart Mirror