Differences

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

--- tematy_prac_inzynierskich [2020/01/05 00:59]
pszwed
+++ tematy_prac_inzynierskich [2020/06/28 03:01]
pszwed [3. Grupowanie grawitacyjne]
@@ Line 1: / Line 1: @@
+===== Struktura pracy =====
+  *[[struktura_pracy_inz|Struktura pracy]]
-===== Proces dyplomowania ======
+  *[[prace_inz_uwagi|Uwagi]]
-  - Dyplomatka/Dyplomant przesyła mailem Promotorowi pracę do poprawy
+  *[[proces_dyplomowania|Proces dyplomowania]]
-  - Promotor nanosi poprawki. Ten cykl może się powtarzać...
-  - Kiedy nie ma uwag, przygotowywana jest wersja finalna w PDF i przekazywana przez Dyplomantkę/Dyplomanta do Wirtualnej Uczelni. //Proszę zwrócić uwagę, czy poprawnie podano informacje na stronie tytułowej, np. tytuł w j. angielskim, kierunek, katedrę itp.// Od tego czasu nie można wprowadzać zmian, ponieważ system przetwarza sumy kontrolne wygenerowane z PDF. Jest to także dobry moment na przesłanie kodu pracy, zbiorów danych, itp.
-  - Praca automatycznie trafia do systemu antyplagiatowego i po jakimś czasie (liczonym na ogół w godzinach) pojawia się raport
-  - Promotor potwierdza, że praca nie jest plagiatem, pisze opinię w systemie Baza Prac EAIiIB i wgrywa opinię do systemu Wirtualna Uczelnia. Wystawia też ocenę.
-  - Często w tym momencie następuje wybór Recenzenta (o ile nie jest narzucony wcześniej)
-  - Następnie praca zmienia status na //zatwierdzona// i recenzent jest powiadamiany, że może pobrać PDF i przystąpić do recenzji. Czasem recenzent nie jest wprowadzony do systemu i musi to zrobić manualnie pracownik Dziekanatu (oczywiście w dzień roboczy).
-  - Recenzent przygotowuej recenzję w systemie Baza Prac  EAIiIB i wgrywa ją do Wirtualnej Uczelni, wystawia też ocenę. Zazwyczaj nie trwa to długo (2-3 dni), ale system zakłada 5 dni na recenzję. Czasem Recenzent może chcieć uzyskać wgląd do kodu pracy.
-  - Recenzent i promotor drukują opinie (są to osobne kartki), podpisują je i najczęściej zostawiają na półeczce na korespondencję w sekretariacie Katedry C2 406, czynne od 9.00-15.00
-  - Zadaniem Dyplomantki/Dyplomanta jest zebranie popdpisanych recenzji, wydrukowanie pracy i innych niezbędnych dokumentów oraz złożenie w Dziekanacie
-W przypadku pomyłek, błędów, niestandardowych systuacji wszelkie interwencje dokonywane są manualnie przez administratora systemu, co zajmuje sporo czasu. Więc proszę dokładnie sprawdzać dokuemnty przed przesłaniem.
-:!: Kluczowe jest zapisanie się na jakiś (realny) termin obrony. Dla prac nieukończonych, w trakcie poprawek - raczej sugerowałbym dalsze terminu.
+====== Tematy prac inżynierskich ======
-===== Struktura pracy ======
+===== 2020 =====
-[[struktura_pracy_inz|Struktura pracy]]
+  *Map matching
+  *Algorytmy optymalizacji
+  *Grupowanie grawitacyjne
+  *Generacja i testy Negatywnych Baz Danych
+==== 1. Map matching ====
+Zarezerwowane jako implementacja w Pythonie? :?:
-=====Uwagi=====
+(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]]
-  * W tekście pracy nie używamy czasu przyszłego (opisujemy to, co jest/istnieje lub to, co zostało zrobione)
+Procedury mogą być zaimplementowane w
-  * Nie piszemy, że //chcemy przybliżyć// lub //ułatwić zrozumienie//. Czytelnikiem jest osoba oceniająca pracę, więc nie można sugerować, że czegoś może nie rozumieć ;-)
+  - [[https://www.postgresql.org/docs/9.2/plpgsql.html]] preferowane, łatwe w konfiguracji i wydajne
-  * W miarę mozliwosci ilustrujemy tekst rysunkami. Nawet prostymi, typu przepływ danych od A do D poprzez B i C: A -> B -> C -> D.
+  - Java lub Pythonie (trudniejsze w konfiguracji i dyskusyjne wydajnościowo)
-  * Podczas obrony przewidziana jest trwająca około 7 min prezentacja, podczas której pokazuje się 8-12 slajdów. Prezentacja jest oceniana (25% oceny z obrony). Rysunki wybrane z pracy są tu dobrymi kandydatami na treść slajdów.
-  * Prezentacja powinna obejmować:
+(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.
-      - Slad tytułowy
-      - Cel pracy
+Zakres:
-      - Przedstawiennie problemu, motywacje
+  - załaduj mapę oryginalną
-      - Może zawierać elementu przegladu literatury (ale krótko)
+  - podziel drogę na segmenty (od skrzyżowania do skrzyżowania)
-      - Opis prac własnych (zaprojektowano, zaimplementowano, przetestowano, rezultaty). Raczej rysunki, diagramy, niewielkie tabele, mało tekstu.
+  - dodaj tabele/struktury danych do przechowywania ścieżek GPS
-      - Podsumowanie
+  - dodaj tabele/struktury danych na graf przypisujący odczyty do punktów na odcinkach dróg
-  * Zła prezentacja:
+  - napisz procedurę, która dla nowego punktu:
-     * Ma 20 slajdów
+    - rozszerza graf o nowe możliwe wierzchołki //expansion//
-     * W tym 12+ to przegląd literatury i przytoczenie znanych faktów/definicji/rozwiązań/technologii, a 3 slady na prace własne
+    - usuwa z grafu wierchołki, z których nie można kontynuować //contraction//
-     * Dyplomant skupia się na szczegółach
+  - podprocedury powinny mieć warianty lub być sterowane parametrami
-     * Około 14 slajdu przewodniczący komisji przerywa i prosi o przejście do podsumowania (przed slajdami z pracami własnymi)
+  - Testy:
-====== Tematy prac inżynierskich ======
+    - 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.
+==== 4. Generacja i testy Negatywnych Baz Danych ====
+Negatywne Bazy Danych (NDB) przechowują w jawnej postaci negatywną informację. Można to przeanalizować na przykładzie łańcucha bitów 101. Negatywna reprezentacja to oczywiście wyliczenie innych wariacji: 001,010, itd. Stosując symbole wieloznaczne może to być również 1*0, 0**, itp. Te dwie ostatnie specyfikacje są równoważne formule logicznej b0&&!b2 || !b0. Znalezienie ciągu zdań (bitów) to zagadnienie SAT [[https://pl.wikipedia.org/wiki/Problem_spe%C5%82nialno%C5%9Bci]], które jest problemem o złożoności NP. Celem pracy jest implementacja algorytmów generacji NDB oraz przeprowadzenie testów, czy możliwe jest złamanie wygenerowanych NDB z użyciem solwerów SAT (np. [[http://minisat.se/|Mini SAT]] i  [[https://www.princeton.edu/~chaff/zchaff.html|zChaff]]).
 ===== 2019 =====