Zaawansowane algorytmy i struktury danych/Ćwiczenia 13: Różnice pomiędzy wersjami
m Zastępowanie tekstu - "\ =\" na "=" |
m Zastępowanie tekstu – „ </math>” na „</math>” |
||
| Linia 29: | Linia 29: | ||
Uzasadnij, dlaczego algorytm $A_{k+1}$ liczenia minimum w tablicy n-elementowej działa w czasie O(1) używając <math> P_{k+1}(n))</math> | Uzasadnij, dlaczego algorytm $A_{k+1}$ liczenia minimum w tablicy n-elementowej działa w czasie O(1) używając <math> P_{k+1}(n))</math> | ||
procesorów, gdzie <math> P_k(n)= n^{1+\epsilon_k}, \epsilon_k= \frac{1}{2^{k}-1} | procesorów, gdzie <math> P_k(n)= n^{1+\epsilon_k}, \epsilon_k= \frac{1}{2^{k}-1} </math> | ||
Zakładamy, że dwa procesory nie mogą próbować wpisać jednocześnie dwóch różnych wartości w to samo miejsce | Zakładamy, że dwa procesory nie mogą próbować wpisać jednocześnie dwóch różnych wartości w to samo miejsce | ||
(ale mogą jednocześnie tę samą wartość). | (ale mogą jednocześnie tę samą wartość). | ||
| Linia 37: | Linia 37: | ||
<math> \max\{(\frac{n}{n^{\alpha}})^{1+\epsilon_k},\ \frac{n}{n^{\alpha}} | <math> \max\{(\frac{n}{n^{\alpha}})^{1+\epsilon_k},\ \frac{n}{n^{\alpha}} | ||
\times (n^{\alpha})^{1+\epsilon_k}\}= O(P_{k+1}(n)) </math> | \times (n^{\alpha})^{1+\epsilon_k}\}= O(P_{k+1}(n))</math> | ||
gdzie <math> \alpha=\frac{1}{2^{k}+1} </math> | gdzie <math> \alpha=\frac{1}{2^{k}+1}</math> | ||
</div> | </div> | ||
| Linia 53: | Linia 53: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Dzielimy tablicę na kawałki długości <math> \sqrt{n} </math>. Z otrzymanymi kawałkami robimy to samo, aż | Dzielimy tablicę na kawałki długości <math> \sqrt{n}</math>. Z otrzymanymi kawałkami robimy to samo, aż | ||
długość będzie pewną stałą. | długość będzie pewną stałą. | ||
</div> | </div> | ||
| Linia 78: | Linia 78: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
<math> O(n \log n) </math> | <math> O(n \log n)</math> | ||
</div> | </div> | ||
</div> | </div> | ||
| Linia 89: | Linia 89: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
<math> O(n ) </math> | <math> O(n )</math> | ||
</div> | </div> | ||
</div> | </div> | ||
Wersja z 11:04, 5 wrz 2023
Zadanie 1
Dany jest ciąg nawiasów otwierających i zamykających jednego rodzaju: ( lub ). Sprawdź, czy jest to ciąg poprawny nawiasowo w czasie log n z pracą liniową.
Zadanie 2
Dany jest ciąg nawiasów okrągłych lub kwadratowych "(" , ")", "[" , "]". Sprawdź, czy jest to ciąg poprawny nawiasowo w czasie log n z pracą liniową.
Zadanie 3
Uzasadnij, dlaczego algorytm $A_{k+1}$ liczenia minimum w tablicy n-elementowej działa w czasie O(1) używając procesorów, gdzie Zakładamy, że dwa procesory nie mogą próbować wpisać jednocześnie dwóch różnych wartości w to samo miejsce (ale mogą jednocześnie tę samą wartość).
Zadanie 4
Oblicz na CRCW PRAM minimum w tablicy n-elementowej w czasie O(log log n), używając O(n / log log n) procesorów. Zakładamy, że dwa procesory nie mogą próbować wpisać jednocześnie dwóch różnych wartości w to samo miejsce (ale mogą jednocześnie tę samą wartość).
Zadanie 5
Zmień algorytm ParallelMerger, tak aby scalał dwa ciągi w czasie logarytmicznym, używając tylko procesorów.
Zadanie 6
Jaka jest asymptotycznie liczba operacji w układzie arytmetycznym odpowiadającym algorytmowi PrefSums1?
Zadanie 7
Jaka jest asymptotycznie liczba operacji w układzie arytmetycznym odpowiadającym algorytmowi PrefSums2?
