Zaawansowane algorytmy i struktury danych/Ćwiczenia 13: Różnice pomiędzy wersjami
m Zastępowanie tekstu – „ </math>” na „</math>” |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
| Linia 28: | Linia 28: | ||
==Zadanie 3== | ==Zadanie 3== | ||
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} </math> | 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 36: | Linia 36: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
<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 62: | Linia 62: | ||
Zmień algorytm ParallelMerger, tak aby scalał dwa ciągi w czasie logarytmicznym, używając tylko | Zmień algorytm ParallelMerger, tak aby scalał dwa ciągi w czasie logarytmicznym, używając tylko | ||
<math> O(\frac{n}{\log n})</math> procesorów. | <math>O(\frac{n}{\log n})</math> procesorów. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie''' | ||
| 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> | ||
Aktualna wersja na dzień 22:18, 11 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?
