Zaawansowane algorytmy i struktury danych/Ćwiczenia 13: Różnice pomiędzy wersjami
Nie podano opisu zmian |
m Zastępowanie tekstu - "\ =\" na "=" |
||
| 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 | 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}\} | \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> | ||
Wersja z 12:51, 9 cze 2020
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?
