(TR) 2023/24-L Programowanie współbieżne i rozproszone EF/I-DU>PWiR

1. Napisać program równoległy do obliczania wyznacznika macierzy kwadratowej. [5 pkt.]
2. Napisać program równoległy do obliczania wartości całki oznaczonej metodą Monte Carlo. Dla uproszczenia można założyć, że funkcja jest monotoniczna i ciągła w przedziale całkowania. [5 pkt.]
3. Selekcja. Dany jest zbiór liczb A = \{a_1, a_2,\ldots, a_n\}. Znaleźć k-ty najmniejszy element zbioru A, czyli taki element x \in A, że podzbiór A' = {a'\in A: a'<x} ma moc k-1 (|A'| = k-1). [10 pkt.]
4. Przeszukiwanie. Dany jest posortowany niemalejąco ciąg liczb A = \left\langle a_1, a_2,\ldots, a_n\right\rangle (\forall_{i=2..n} a_{i-1} \leq a_i). Znaleźć indeks elementu x, czyli taki numer i w ciągu A, że a_i = x. Gdy brak jest elementu x w ciągu A, powinno być zwrócone 0. [10 pkt.]
5. Łączenie. Dane są dwa posortowane niemalejąco ciągi liczb A = \left\langle a_1, a_2,\ldots, a_n\right\rangle (\forall_{i=2..n} a_{i-1}\leq a_i) oraz B = \left\langle b_1, b_2,\ldots, b_m\right\rangle (\forall_{i=2..m} b_{i-1}\leq b_i). Utworzyć taki posortowany niemalejąco ciąg C = \left\langle c_1, c_2,\ldots, c_{m+n}\right\rangle, że \forall_{i=1..m+n} c_i\in A\cup B oraz \forall_{i=2..m+n} c_{i-1}\leq c_i. [10 pkt.]
6. Znajdowanie podciągu. Dane są dwa ciągi znaków A = \left\langle a_1, a_2, \ldots, a_n\right\rangle oraz B = \left\langle b_1, b_2,\ldots, b_m\right\rangle (m\leq n). Znaleźć wszystkie wystąpienia ciągu B w ciągu A, czyli wypełnić odpowiednimi wartościami logicznymi tablicę M w następujący sposób: M[i] = true \Leftrightarrow \forall_{j = 0..m-1} a_{i+j} = b_{1+j} (1 \leq i \leq n-m+1). [10 pkt.]
7. Sortowanie. Dany jest zbiór liczb A = \{a_1, a_2,\ldots, a_n\}. Posortować niemalejąco zbiór A, czyli wygenerować taki ciąg \left\langle b_1, b_2,\ldots, b_n\right\rangle, że \forall_{i=1..n} b_i \in A oraz \forall_{i=2..n} b_{i-1}\leq b_i. [10 pkt.]
8. Znajdowanie sumy prefiksu. Dany jest ciąg liczb A = \left\langle a_1, a_2,\ldots, a_n\right\rangle. Wygenerować taki ciąg B = \left\langle b_1, b_2, ..., b_n\right\rangle, że \forall_{i=1..n} b_i = \sum_{k=1..i} a_k. [10 pkt.]

http://skinderowicz.pl/static/pw2/MPI-tutorial.html

Zadana dodatkowe na wyższą ocenę z użyciem OpenMP:
- wykazać różne komunikacje: blokujące, nieblokujące, point-topoint, grupowe
- sortowanie równoległe 
- schemat rozsyłania w pierścieniu 
- obliczanie liczby PI z wykorzystaniem funkcji komunkacji zbiorowej 
- obliczanie wyznacznika macierzy kwadratowej 
- łączenie – dwa posortowane niemalejąco ciągi, z nich utworzyć kolejny nieposortowany 
- przeszukiwanie – przeszukać ciąg w poszukiwaniu i i zwrócić x 
- program zwracający max lub/i min
- przeszukiwanie listy np. liczb w celu znalezienia szukanych wartości
- sprawdzanie wydajności MPI
- mnożenie macierzy i wektora
- inne propozycje własne