Differences

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

--- tematy_prac_inzynierskich [2019/07/11 02:29]
pszwed [2019]
+++ tematy_prac_inzynierskich [2023/07/13 00:59] (current)
pszwed [5. Zapytania w języku naturalnym do bazy danych (geograficznych)]
@@ Line 1: / Line 1: @@
+===== Struktura pracy =====
+  *[[struktura_pracy_inz|Struktura pracy]]
+  *[[prace_inz_uwagi|Uwagi]]
+  *[[proces_dyplomowania|Proces dyplomowania]]
 ====== Tematy prac inżynierskich ======
+===== 2023 =====
+Możliwe jest zgłaszanie propozycji własnych tematów. Ważnym dla mnie problemem jest wypełnienie rozwijanej aplikacji danymi tak, aby możliwe było przetestowanie wydajności. Raczej oczekiwane jest użycie 10000+ rekordów, a nie np. 20.
+==== 1. Aplikacja do analizy sieci społecznościowej pracowników AGH ====
+Zarezerwowane [M.D.]
+Zakres pracy:
+  - webscraping danych o publikacjach pracowników AGH (być może z pewnymi ograniczeniami)
+  - zapis do bazy danych
+  - budowa grafów powiązań pomiędzy pracownikami (wspólne publikacje, takie same słowa kluczowe publikacji)
+  - wizualizacja i przeglądanie danych
+==== 2. Uczenie ze wzmocnieniem na platformie Ray ====
+Opracowanie jednego lub kilku przykładów ucznia ze wzmocnieniem korzystającego z modułów platformy [[https://www.ray.io/|Ray]]
+Typowe zastosowanie - gra, której stan jest obserwowany i w zależności od stanu należy wydać odpowiednie polecenie.
+Przy wsparciu biblioteki proces uczenia rozdzielony pomiędzy współbieżne zadania lub agentów. Należy zbierać dane dotyczące wydajności systemu (w tym czasów wykonania).
+==== 3. Optymalizacja rozmieszczenia pojazdów w Car Sharing ====
+[D.K. - rezerwacja wersji z Gurobi]
+Celem jest rozwiązanie następującego zagadnienia:
+  * mamy k lokalizacji (na przykład dzielnic) oraz pewną liczbę n pojazdów
+  * w danym czasie t pojazdy są  rozmieszczone w lokalizacjach lub są w ruchu
+  * Znane jest prawdopodobieństwo P(i,j,t) przejazdu z lokalizacji i do j rozpoczynającego się w czasie t. Czasy możemy zdyskretyzować , np. do 15 min.
+  * Znany jest czas tego przejazdu T(i,j,t)
+  * Jeżeli rozważymy pewien horyzont czasowy, np. 24h to możemy zasymulować zachowanie systemu i obliczyć E[T] - wartość oczekiwaną sumarycznego czasu ruchu samochodów w ciągu doby. W ten sposób wyznaczamy wartość funkcji celu.
+  * W celu optymalizacji podejmujemy decyzję dotyczącą transferu pojazdu z lokalizacji i do j rozpoczętego w czasie t x_{ijt} = 0/1. Staramy przenieść samochody z lokalizacji o małym popycie do lokalizacji bardziej atrakcyjnych, niekoniecznie w danym momencie ale za kilka godzin.
+  * Liczba przemieszczanych w danym momencie samochodów jest ograniczona (np. m=10 to liczba pracowników zajmujących się przemieszczaniem)
+  * Do rozważenia - platforma gurobi,  [[https://www.gurobi.com/jupyter_models/vehicle-rental-optimization/]]
+  * lub opracowanie i implementacja własnago algorytmu heurystycznego
+[W zasadzie może to być kilka prac,  gurobi vs. własna implementacja, różne algorytmy, implemetacja na GPU - CUDA lub OpenCL, itd.]
+==== 4. Propagacja informacji w dużym grafie (= grafie sieci drogowej) ====
+[Zarezerwowane P.G. 02.07.2023]
+Celem pracy jest implementacja i testy oprogramowania implementującego 2-3 algorytmy propagacji informacji w grafie. Załóżmy, że utworzymy graf sieci drogowej Krakowa wydzielając kilkudziesięciometrowe odcinki dróg. Aktywacja jednego z odcinków (np. zmiana gęstości ruchu lub innego parametru) powinna być rozpropagowana w jego sąsiedztwie. Możliwe algorytmy to przesyłanie komunikatów do sąsiadów, rozwiązania wzorowane na automatach komórkowych lub losowe błądzenie po grafie (z ograniczeniem liczby kroków).
+Oczekiwana jest wizualizacja wyników (np. pogrubione/pokolorowane odcinki dróg). Możliwa implementacja na GPU (CUDA lub OpenCL).
+==== 5. Zapytania w języku naturalnym do bazy danych (geograficznych) ====
+[Zarezerwowane A.M.]
+Interesuje nas zbiór danych przechowywanych w bazie OSM (https://www.openstreetmap.org/) dla Polski.
+Zakładamy pewną skończoną liczbę typów zapytań dotyczących różnych obiektów (około 20-30) , np.:
+  * "miejscowość poniżej 10000 mieszkańców położone w pobliżu jeziora"
+  * "parkingi w Krakowie w dzielnicy Krowodrza"
+takie zapytania należy rozpoznać i zamienić na kwerendy do BD, a następnie wyświetlić wyniki w aplikacji webowej
+  * Do przetwarzania tekstu i rozpoznawania typów zapytań i ich argumentów należy użyć biblioteki spaCy [[https://spacy.io/]] a zwłąszcza [[https://spacy.io/api/matcher]]
+  * Aplikację można zaprojektować w architekturze backend - frontend, albo w postaci monolitycznej.
+  * Językiem spaCy jest Python, więc
+       * albo usługa będzie dostępna poprzez mikroserwis,
+       * albo backend będzie napisany w Pythonie (np. Flask, FastAPI)
+       * albo cała aplikacja będzie napisana w Pythonie (np. Django lub dash)
+==== 6. Gra połączona z agentową symulacją świata ====
+[Rezerwacja J.G]
+===== 2021 =====
+**Wyczerpałem limit prac inżynierskich**
+Możliwe jest zgłaszanie własnych tematów. Jednak, nie chcę prowadzić prac polegających na implementacji aplikacji webowej/mobilnej
+z użyciem typowego stosu technologicznego, do której dorobiona jest specyfikacja w stylu [[http://home.agh.edu.pl/~pszwed/wiki/doku.php?id=amo:projekt_tematy|Analizy i Modelowania Oprogramowania]]. Na ogół bardzo trudno taką aplikację wypełnić danymi i później porządnie przetestować.
+=== 1. Optymalizacja ciągła: PyTorch + algorytm pszczeli===
+[zajęte, MW]
+=== 2. Optymalizacja ciągła - algorytm mrówkowy===
+Obejmuje opracowanie algorytmu (specyficzna implementacja). Platforma TensorFlow lub PyTorch lub CUDA
+Testy z użyciem funkcji testowych z konferencji CEC
+[zajęte MS]
+=== 3. Inne algorytmy optymalizacji ciągłej ===
+Do ustalenia.  [jeszcze jeden temat zarezerwowany ... AZ]
+=== 4. Baza wiedzy z rozmytymi relacjami===
+Na przykładzie rekomendacji dietetycznych dla różnych typów schorzeń.
+Obejmuje: bazę, interfejs dostępu REST do odczytu i zapisu, aplikację webową. Należy wypełnić bazę przykładowymi danymi, np dla 2-3 schorzeń i produktów spozywczych.  [zajęte MK]
+=== 5. Repozytorium danych tekstowych na potrzeby NLP ===
+Obejmuje projekt i implementację bazy danych + web scraping artykułów z wybranych 2-3 źródeł (np. PubMed), indeksowanie według wybranych terminów. [zarezerwowane PM]
+=== 6. Rozpoznawanie aktywności użytkownika na podstawie odczytów czujników urządzenia mobilnego ===
+Aplikacja mobilna zbierająca i interpretująca dane. Należy zarejestrować przykłady odczytów (bieg, chód,  jazda samochodem, rowerem). Następnie przeprowadzić ekstrakcję cech (widmo częstotliwości, zero-crossing rate, itp) i przeprowadzić klasyfikację.  [zarezerwowane]
+=== 7. Predykcja szeregów czasowych z użyciem Rozmytych Map Kognitywnych ===
+Implementacja na platformie TensorFlow lub PyTorch. Najchętniej na (części) danych typu PEMS https://dot.ca.gov/programs/traffic-operations/mpr/pems-source
+=== 8. Projekt i implementacja wybranych algorytmów grupowania dla PostgreSQL===
+Przykładowe algorytmy to k-means, db-scan, ward.  Implementacja w języku PL/pgSQL. Projekt obejmuje generację danych syntetycznych różnych rozmiarów i testy algorytmów. [zarezerwowane HM]
+=== 9. Rozpoznawanie emocji w głosie===
+W ramach pracy należy zdefiniować kilka kategorii emocji (spokojna rozmowa, uprzejma rozmowa z klientem, kłótnia, program informacyjny, itp.) Dla każdej kategorii należy wyekstrahować około 100 kilkunastosekundowych przykładów z różnych źródeł (filmy, podcasty). Następnie korzystając z biblioteki librosa wyekstrahować cechy i przeprowadzić klasyfikację. Patrz [[http://home.agh.edu.pl/~pszwed/wiki/doku.php?id=med:start]]
+[zajęte MW]
+=== 10. Generacja informacji o ruchu w grafie ===
+Graf sieci drogowej na podstawie mapy OSM. Rozmiar - co najmniej aglomeracja. W sieci porusza się duża liczba obiektów, dla każdego obiektu losowany jest punkt startowy i końcowy i wyznaczana droga (np. algorytmem A-star). Oprogramowanie ma zbierać informacje o koncentracji obiektów w danym miejscu i przedziale czasu (natężeniu ruchu).    [zarezerwowane SK]
+=== 11. Grupowanie obiektów na mapie===
+Implementacja algorytmu, który będzie łączył w grupy blisko położone obiekty. Odległość musi uwzględniać rzeczywistą odległość w sieci drogowej (długość drogi wyznaczonej np. algorytmem A-star). [zarezerwowane KR]
+=== 12. Wirtualny wyścig ===
+[Zajęte AK]
+=== 13. Animacja awatara ===
+[zarezerwowane AG]
+<!--
+**Na razie nie mam propozycji tematów **
+Generalnie, nie chcę prowadzić tematów polegających na implementacji aplikacji webowej/mobilnej z użyciem typowego stosu technologicznego, do której dorobiona jest specyfikacja w stylu [[http://home.agh.edu.pl/~pszwed/wiki/doku.php?id=amo:projekt_tematy|Analizy i Modelowania Oprogramowania]]. Na ogół bardzo trudno taką aplikację wypełnić danymi i później porządnie przetestować.
+Typowy zakres prac
+  * eksploracji danych/uczenie maszynowego - tu można wybrać kilka obszarów - obrazy, muzyka, NLP, szeregi czasowe, np. dane o natężeniu ruchu drogowego, notowania giełdowe
+  * algorytmy optymalizacji ciagłej (ale na platformie typu TensorFlow lub PyTorch)
+  * może to być implementacja systemu, który będzie miał jakiś inteligentny komponent albo będzie przydatne w tej dziedzinie - jak narzędzie do etykietowania
+-->
+===== 2020 =====
+  -Map matching :!: Zajęte
+  -Algorytmy optymalizacji (możliwych jest kilka tematów) :!: Jeden temat zajęty
+  -Grupowanie grawitacyjne :!: Zajęte
+  -Generacja i testy Negatywnych Baz Danych :!: Zajęte
+  -Analiza antyplagiatowa kodu :!: Zajęte
+==== 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** lub **tensorflow**. 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 (CUDA)====
+:!: Zajete
+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.
+Platforma implementacji CUDA (NVidia). Ewentulnie porównanie z czystym C.
+==== 4. Generacja i testy Negatywnych Baz Danych ====
+:!: Zajete
+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ż
+<code>1*0, 0**</code>
+Te dwie ostatnie specyfikacje są równoważne formule logicznej
+$f=b_0\wedge \neg b_2 \lor \neg b_0$.
+Znalezienie ciągu zdań (bitów), dla których formuła jest prawdziwa to zagadnienie  [[https://pl.wikipedia.org/wiki/Problem_spe%C5%82nialno%C5%9Bci|SAT]], które jest problemem o złożoności NP. Jest to problem łatwy, dla 1-20 bitów (zastosowanie brute force), ale dla  64 trudny. Celem pracy jest implementacja algorytmów generacji NDB oraz przeprowadzenie testów, czy możliwe jest złamanie wygenerowanych NDB z użyciem wybranych solwerów SAT (np. [[http://minisat.se/|Mini SAT]] i  [[https://www.princeton.edu/~chaff/zchaff.html|zChaff]]).
+==== 5. Analiza antyplagiatowa kodu ====
+:!: Zarezerwowany
+Celem pracy jest implementacja systemu, który będzie umożliwiał przesłanie plików źródłowych w wybranym języku programowania przez zalogowanych użytkowników, a następnie określał stopień podobieństwa kodu. Podstawowym narzędziem do wykorzystania jest znany algorytm określania najdłuższego wspólnego podciągu. Można zajrzeć tu [[http://home.agh.edu.pl/~pszwed/wiki/lib/exe/fetch.php?media=07-imperatywne-jezyk-c-lancuchy-znakow.pdf|str 27]]. Podobieństwo powinno być określane: na poziomie znaków oraz na poziomie symboli. Szczególnie interesująca jest modyfikacja algorytmu tak, aby uwzględnić substytucję symboli, tzn. jeżeli napotkany zostanie identyfikator x12 oraz odpowiadający mu identyfikator y10, wówczas obliczony zostanie także stopień dopasowania po zamianie x12 na y10.
 ===== 2019 =====
-Obecnie zarezerwowanych jest 11/12
+Obecnie zarezerwowanych jest 12/12
+:!: ** Nie podejmuję się prowadzenia kolejnych prac ze wzgledu na osiągnięcie limitu** :!:
 ==== 1. Wizualizacja danych geograficznych ====
 :!: Rezerwacja