Igor Wojnicki's WIKI

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Tematy Projektów, ZTB ======

===== Warunki ogólne =====

Grupy projektowe maksymalnie 3 osobowe.

Ten sam temat może być realizowany przez więcej niż 1 grupę.

===== Opis tematów =====
 
==== 1. Przetwarzanie grafów ====

Poniższy przykład w Prologu
  * {{n_gs_e.pl}} - główny program do załadowania,
  * {{100_gs_e.pl}} - graf ok. 14 tys. elementów składowych,
  * {{slic.pl}} - predykaty realizujące przetwarzanie i wnioskowanie.
reprezentuje graf, którego struktura zbliżona jest do grafu: 

{{:pl:ztb:gas_station_gem-ca.png?600}}

Przedstawia on zależności w inteligentnej przestrzeni "obsługującej" stację benzynową.
Są to odpowiednio lampy (L), konfiguracje lamp (C), segmenty (S), obszary (A), oraz sensory (P,D,H,K).

Konkretne dane pochodzące od sensorów reprezentowane są jako etykiety (szczegóły na wykładzie/konsultacjach).

Celem projektu jest przetestowanie różnych technologii, umożliwiających przechowywanie i przetwarzanie w/w danych, pod kątem ich wydajności.
Jako rozwiązanie referencyjne przyjmuje się w/w kod w Prologu (ktorego dla większości poniższych projektów wcale nie trzba rozumieć ;-) )

Aby uruchomić referencyjne rozwiązanie w Prologu należy:
  - zainstalować [[http://www.swi-prolog.org/|SWI Prolog]],
  - pobrać w/w pliki (tj.{{n_gs_e.pl}}, {{100_gs_e.pl}}, {{slic.pl}}),
  - w katalogu z w/w plikami uruchomić SWI Prolog<code>
  swipl -s n_gs_e.pl -g ex -t halt</code>
  - najważniejszy jest czas realizacji testów podany w ostatniej linii.
Przykładowy rezultat uruchomienia w/w kodu powinien wyglądać następująco:
<code>
swipl -s n_gs_e.pl -g ex -t halt
Warning: /home/wojnicki/work/lighting/slic/slic.pl:22:
	Singleton variables: [X]
Warning: /home/wojnicki/work/lighting/slic/slic.pl:27:
	Singleton variables: [X]
%  slic compiled 0.00 sec, 2,176 bytes
%  100_gs_e.pl compiled 0.14 sec, 1,184,208 bytes
% /home/wojnicki/work/lighting/slic/n_gs_e.pl compiled 0.14 sec, 1,196,692 bytes
0
1
2
3
4
5
6
7
8
9
% 194,667 inferences, 4.471 CPU in 4.525 seconds (99% CPU, 43541 Lips)
</code>

Uruchmione jest 10 kroków transformacji grafowych realizujących 10 zdarzeń tj. odpowiedzi będących odpowiednimi etykietami na nadchodzące dane sensoryczne.

Rezultaty w/w ekspertymentów umieszczone są jako pliki tekstowe 0.txt, 1.txt,..., 9.txt w {{:pl:ztb:results0-9.tar.bz2}}, każdy przedstawia stan grafu z uwzglednieniem wierzchołków s oraz c po przeprowadzeniu danego ekspertymentu (0.txt po przeprowadzeniu ekspertymentu 0, 1.txt po przeprowadzeniu 1 itd.).

=== 1.1 Nierelacyjne ===

  - Wybierz 2 bazy nierelacyjne (nie grafowe!) na podstawie kryterium możliwości skutecznego przetwarzania grafów.
  - Zaimplementuj w/w graf i jego przetwarzanie w wybranych bazach.
  - Przetestuj wydajność. Podaj wyniki porównawcze programu w Prologu na używanej platformie.

=== 1.2 Grafowe ===

  - Wybierz 2 bazy grafowe.
  - Zaimplementuj w/w graf i jego przetwarzanie w wybranych bazach.
  - Przetestuj wydajność. Podaj wyniki porównawcze programu w Prologu na używanej platformie.

=== 1.3 Erlang/Mnesia ===

  - Zaimplementuj w/w graf i jego przetwarzanie korzystające z Erlang/OTP oraz np. Mnesia.
  - Przetestuj wydajność. Podaj wyniki porównawcze programu w Prologu na używanej platformie.


=== 1.4 Prolog/CLP ===

  - Zweryfikuj możliwość zaimplementowanie przetwarzania w/w grafu z wykorzystaniem CLP (Constraint Logic Programming).
  - Przetestuj wydajność. Podaj wyniki porównawcze programu w Prologu na używanej platformie.

=== 1.5 Relacyjne ===

  - Dla baz: PostgreSQL i MySQL zaimplementuj w/w graf i jego przetwarzanie.
  - Przetestuj wydajność. Podaj wyniki porównawcze programu w Prologu na używanej platformie.


==== 2. Mapy dynamiczne ====

[[Przykład użycia map dynamicznych]].

Baza danych {{rdnr_dump.sql|RDNR}}.

Baza danych {{https://www.dropbox.com/s/8pvmlaixvyuazol/krakow.sql.bz2|osmosis_db}}

=== 2.1 skrzyżowania ===

  - Należy napisać kod SQL dodający do mapy statycznej informacje o 15 skrzyżowaniach w Krakowie.
  - Dodać informacje o instancjach parametrów monitorowania (źródła danych sensorycznych) na w/w skrzyżowaniach tj.
    * długość kolejki przed skrzyżowaniem dla każdego pasa,
    * prędkość za skrzyżowaniem, wspólna dla wszystkich pasów. 
  - Uzupełnić dane sensoryczne: dla każdej instancji parametru monitorowania dodać 4 losowe wartości.

=== 2.2 wydajność ===

  - Wygenerować losowo informacje o skrzyżowaniach w mapie statycznej, ilość powinna być porównywalna z ilości skrzyżowań w Krakowie.
  - Do w/w skrzyżowań dodać losowo informacje o instancjach parametrów monitorowania
    * długość kolejki przed skrzyżowaniem dla każdego pasa,
    * prędkość za skrzyżowaniem, wspólna dla wszystkich pasów. 
  - Określić i przetestować scenariusze dostępu do tak wygenerowanych danych, biorąc pod uwagę rozdzielność Mapy Statycznej i Mapy Dynamicznej.

=== 2.3 wskazówki nawigacyjne ===

Dana jest mapa miasta (lub innego obszaru) zaimportowana z [[http://www.openstreetmap.org|OpenStreetMap]] (przy pomocy narzędzia [[http://wiki.openstreetmap.org/wiki/Osmosis|Osmosis]]). Na mapie tej wyznaczono trasę przejazdu w postaci sekwencji kolejno mijanych węzłów (''nodes''). 

Celem projektu jest:
  * określenie katalogu manewrów (które mogą być podawane jako wskazówki przez aplikację nawigacyjną), np. wzorując się na [[http://www.mapquestapi.com/directions/|API MapQuest]],
  * zaimplementowanie modułu (PostgreSQL + PostGIS + ew. wybrana technologia), który z opisanej powyżej sekwencji węzłów wygeneruje sekwencję kolejnych manewrów.

==== 3. Wyznaczanie trasy ====

=== 3.1 pgRouting ===
Celem projektu jest przeprowadzenie badań wydajności wyszukiwania trasy przy pomocy różnych algorytmów pakietu [[http://pgrouting.org|pgRouting]] w dużym grafie.

Zadania:
  * przygotowanie skryptu pobrania i importu wybranego fragmentu mapy do bazy PostgreSQL/PostGIS,
  * integracja bazy z pgRouting,
  * stworzenie prostej aplikacji do wyszukiwania trasy i prezentacji wyników,
  * przeprowadzenie testów wydajności dla różnych algorytmów i różnych funkcji heurystycznych, w tym ocena jakości rozwiązania przy heurystykach niedopuszczalnych.


=== 3.2 neo4j Routing ===
Celem projektu jest przeprowadzenie badań wydajności wyszukiwania trasy przy pomocy [[http://api.neo4j.org/current/org/neo4j/graphalgo/GraphAlgoFactory.html|różnych algorytmów]] bazy grafowej [[http://www.neo4j.org|Neo4j]] w dużym grafie.

Zadania:
  * przygotowanie skryptu pobrania i importu wybranego fragmentu mapy do bazy Neo4j,
  * stworzenie prostej aplikacji do wyszukiwania trasy i prezentacji wyników,
  * przeprowadzenie testów wydajności dla różnych algorytmów i różnych funkcji heurystycznych, w tym ocena jakości rozwiązania przy heurystykach niedopuszczalnych.
Igor Wojnicki's WIKI

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
