Podporuje nás:
Partnerské organizácie:
Aktuálne informácie o Bez(a)Dis-e:
1. Spoločná pamäť v EREW PRAM obsahuje n bitov, uložených na prvých n miestach. Navrhnite algoritmus pre výpočet booleovského súčinu (AND) týchto bitov. Spočítajte jeho časovú zložitosť, zrýchlenie a efektivitu. Navrhnite čo najefektívnejšiu verziu. Tú istú úlohu riešte na CRCW PRAM.
2. Daný je cyklus C = (v1, v2, ..., vn) a množina hrán E, ktoré spájajú vrcholy cyklu C tak, že pre každý vrchol vi existuje najviac jedna hrana E s ním incidentná. Riešte paralelným algoritmom v čase O(log n) pomocou EREW PRAM modelu problém, či je alebo nie je možné nakresliť hrany E vnútri cyklu C tak, aby sa vzájomne nepretínali.
3. Navrhnite algoritmus, ktorý pre každý prvok vstupného poľa A = (a1, a1, ...,an) nájde najbližší menší prvok vľavo (ak existuje) a najbližší menší prvok vpravo (ak existuje). Skúste nájsť paralelný algoritmus, ktorý túto úlohu vyrieši v čase O(1).
4. Je daná postupnosť n čísel, ktoré sú naviac ofarbené farbou z množiny {1, 2, …, k}, kde k <= log n. Nájdite pre každú farbu i prefixové súčty prvkov postupnosti, ktoré sú touto farbou ofarbené. Skúste to v čase O(log n) s najviac W(n)=O(n) operáciami na EREW PRAM.
5. Pre zadaný zakorenený strom je v zdieľanom poli M informácia o rodičovskom vrchole (susednom vrchole smerom ku koreňu) vrchola i. ( M[i]=p(i); ak i je koreň, vtedy M[i]=i ). Navrhnite algoritmus, ktorý v čase O(log n) v CREW PRAM výpočtovom modeli nájde ofarbenie vrcholov stromu dvoma farbami tak, aby susediace vrcholy (spojené hranou) mali rôzne farby.
Poznámka: