Tematy projektów

• wykonanie projektu jest warunkiem uzyskania zaliczenia,
• termin oddania: Lab. nr 9 (30.iv-10.v.2024),
• architektura: liczba węzłów pracujących równolegle dopasowana do natury rozwiązywanego problemu i rozmiaru przetwarzanych danych,
• implementacja: praca w środowisku pracowni komputerowej WFiIS (MPICH, OpenMPI -- plus opcjonalnie dodatkowo wykorzystanie OpenMP, CUDA),
• postać: archiwum „nr_zespolu-nr_projektu-nazwisko-nazwisko.tar.gz” obejmujące podkatalog zawierający:
  • kod źródłowy programu,
  • plik z przykładowymi danymi wejściowymi,
  • plik z poprawnymi wynikami działania na w/w danych wejściowych,
  • plik z opisem budowy, działania i obsługi programu (zawierającym m. in. schemat blokowy) – w formacie PDF,
  • plik Makefile z regułami umożliwiającymi:

    - kompilację programu źródłowego do postaci wykonywalnej na komputerach pracowni,

    - uruchomienie programu z danymi przykładowymi,

    - przywrócenie zawartości podkatalogu do stanu wyjściowego.

• Archiwum projektu ma zostać zdeponowane poprzez witrynę kursu na Uczelnianej Platformie E-Learningowej.

• wykonanie projektu jest warunkiem uzyskania zaliczenia,
• termin oddania: Lab. nr 15 (17-19.vi.2024),
• architektura: dla wersji rozproszonej - wielowątkowy klient (zarządca) + minimum 2 odrębne serwery (wykonawcy);
  dla wersji PGAS - skalowalna liczba procesów/wątków,
• architektura: liczba węzłów pracujących równolegle dopasowana do natury rozwiązywanego problemu i rozmiaru przetwarzanych danych,
• implementacja: praca w środowisku pracowni komputerowej WFiIS (JDK, ORBacus, TAO, ... albo Berkeley UPC, UPC++, GASPI/GPI-2, XcalableMP, Parallel Computing in Java (PCJ) -- plus opcjonalnie dodatkowo wykorzystanie OpenMP, CUDA, OpenACC),
• pozostałe jak w pkt. 1.
• Archiwum projektu ma zostać zdeponowane poprzez witrynę kursu na Uczelnianej Platformie E-Learningowej.

1. Realizacja w/w dwóch projektów w trakcie semestru (maksymalnie 2 × 45 pkt = 90 pkt):
   • realizacja logiki aplikacji - 25 pkt,
   • realizacja interfejsu użytkownika - 5 pkt,
   • dokumentacja projektu (w tym kodu źródłowego) - 10 pkt,
   • prezentacja działania projektu - 5 pkt.
2. Terminowe zdeponowanie danego projektu - 5 pkt. (maksymalnie 2 × 5 pkt = 10 pkt).

Maksymalna liczba punktów: 100 pkt.

Końcowa tabela przeliczeniowa: punkty - ocena

Semestr letni 2023/2024

• Grupa lab. 3 (wtorek, godz. 11:30)
1. AG+MS: nr 12 - algorytm Bellmana-Forda
2. MR+EZ: nr 26 - równoległy algorytm genetyczny
3. ZS+WW: nr 18 - algorytm Floyda
4. JB+AS: nr  2 - MC rozkład temperatury 2-D
5. MC+NS: nr  7 - sortowanie PSRS
6. SM+KŻ: nr  1 - MC transport neutronów
• Grupa lab. 2 (środa, godz. 16:45)
1. JO+KT: nr 12 - algorytm Bellmana-Forda
2. ML+SN: nr  1 - MC transport neutronów
3. JS+DS: nr  6 - mnożenie macierzy alg. Cannona
4. DŁ+BW: nr  8 - szybka transformata Fouriera FFT
5. JS+KS: nr 24 - n-body problem (układ planetarny)
6. PS+KK: nr 21 - alg. Prima (drzewo rozpinające)
7. PK+ŁT: nr  9 - równanie Poissona (rozkład temp.)
• Grupa lab. 4 (środa, godz. 18:30)
1. ML+MP: nr 12 - algorytm Bellmana-Forda
2. KK+PP: nr 18 - algorytm Floyda
3. VK+MK: nr  8 - szybka transformata Fouriera FFT
4. TK+AJ: nr 22 - algorytm Dijkstry
5. MK+VT: nr 27 - problem komiwojażera (ant colony)
6. SK+IY: nr 26 - równoległy algorytm genetyczny
• Grupa lab. 1 (piątek, godz. 11:30)
1. MB+PS: nr 23 - alg. poszukiwań w głąb (8-puzzle)
2. MD+PG: nr 21 - alg. Prima (drzewo rozpinające)
3. MP+BS: nr 12 - algorytm Bellmana-Forda
4. SA+KG: nr 24 - n-body problem (układ planetarny)
5. MD+WG: nr 22 - algorytm Dijkstry
6. TS+JW: nr  8 - szybka transformata Fouriera FFT
7. WS: nr  7 - sortowanie PSRS

1. Monte Carlo - transport neutronów (Quinn, zad. 10.8)
2. Monte Carlo - rozkład temperatury w 2-D. (Quinn, zad. 10.9)
3. Monte Carlo - Model Isinga w 2-D. (Quinn, zad. 10.10)
4. Monte Carlo - Przydział pokoi metodą simulated annealing. (Quinn, zad. 10.11)
5. Monte Carlo - Ruch na rondzie. (Quinn, 10.13)
6. Mnożenie macierzy - algorytm Cannon'a. (Quinn, zad. 11.6)
7. Sortowanie PSRS (Parallel Sorting by Regular Sampling). (Quinn, zad. 14.8 a. )
8. Szybka transformata Fouriera FFT. (Quinn, zad. 15.5, Grama, Gupta, rozdz. 13)
9. Równania różniczkowe cząstkowe (PDE) - rozkład temperatury na płycie w stanie ustalonym - równanie Poissona. (Quinn, zad. 13.5)
10. Poszukiwanie minimum f(x̅) - Metoda sympleksu nieliniowego - algorytm Torczona. (Karbowski, rozdz. 8.3.2)
11. Poszukiwanie minimum f(x̅) - Dekompozycja zadań optymalizacji - algorytm Jacobiego. (Karbowski, rozdz. 8.4.1)
12. Routing w sieciach komputerowych - algorytm Bellmana-Forda. (Karbowski, rozdz. 9.1.3.1)
13. Poszukiwanie minimum f(x̅) - Optymalizacja bez ograniczeń metodą największego spadku. (Karbowski, rozdz. 9.1.2.3)
14. Algorytmy chaotyczne (asynchroniczne) - Układy równań liniowych. (Karbowski, rozdz. 9.1.2.1)
15. Układ równań liniowych - dekompozycja LU. (Ortega, 2.2)
16. Układ równań liniowych - redukcja ortogonalna QR - transformacje Householdera. (Ortega, 2.2)
17. Układ równań liniowych - dekompozycja Cholesky'ego. (Ortega, 2.2)
18. Algorytm Floyda - znajdowanie najkrótszej ścieżki w grafie zorientowanym z wagami. (Quinn, rozdz. 6.4).
19. Znajdowanie cieni za wzgórzami na bazie algorytmu Floyda. (Quinn, zad. 6.12 a.)
20. Generowanie zbioru Mandelbrota - program typu Manager - Workers (Quinn, zad. 9.9)
21. Minimalne drzewo rozpinające - algorytm Prim'a (Grama, Gupta, par. 10.2)
22. Drzewa wszystkich najkrótszych ścieżek - algorytm Dijkstra'y (Grama, Gupta, par. 10.3)
23. Algorytm poszukiwań w głąb (depth-first) - The 8-puzzle problem - (Grama, Gupta, par. 11.2)
24. Problem oddziaływań wielu ciał (The n-body problem) - Symulacja układu planetarnego (Quinn, par. 3.6)
25. Klasyfikowanie dokumentów - program typu Manager - Workers (Quinn, par. 9.2)
26. Równoległy algorytm genetyczny - np. projektowanie planu zajęć (A Parallel Genetic Algorithm for Solving the School Timetabling Problem , Parallelisation of Genetic Algorithms for Solving University Timetabling Problems , Parallelisation of Genetic Algorithms for Solving University Timetabling Problems )
27. Rozproszone rozwiązanie problemu komiwojażera (travelling salesman problem) - kolonia mrówek (ant colony) (distributed algorithm for the solution of TSPs by ant colonies , Algorytm mrówkowy jako metoda rozwiązania problemu komiwojażera , Optymalizacja kolonii mrówek , A Parallel Implementation of Ant Colony Optimisation ... applied to the TSP , Parallel Implementation of an Ant Colony Optimization ... with OpenMP )