Úlohy na precvičenie – PDS 2019 – séria C

Úlohy riešte samostatne a podrobne. Celý postup zaznamenajte a komentujte. Odpovede zdôvodňujte celými vetami (väčšinou je otázok v úlohe viac!). Cieľom cvičenia nie je vyhľadanie riešenia, ale získanie skúseností so samostatným riešením úloh. Vo výnimočných situáciách použité citácie uveďte v riešení. Je slušné tiež uviesť mená osôb, s ktorými ste riešenie konzultovali (čo samozrejme je povolené, pokiaľ riešenie spíšete potom samostatne). Uprednostnite ručný zápis – umožní vám jednoducho pridávať ilustračné obrázky a nákresy.

Za každé správne a vyčerpávajúce riešenie (samozrejme aj s postupom) možno získať bod (ak nie je uvedené inak). Zlomky bodov možno získať aj za čiastočné riešenia. Riešenia tejto série je nutné doručiť do 7. 3. 2019, 14:25 (do začiatku tutoriálu). Pred týmto termínom je možné odovzdať riešenia na sekretariáte Ústavu informatiky (do môjho priečinka). Neskôr dodané a opisované riešenia nebudú opravované ani hodnotené. Problémy môžete konzultovať po prednáške, elektronickou poštou alebo prostredníctvom diskusnej skupiny {pds2019@googlegroups.com}.

Úplné riešenie úlohy zahŕňa väčšinou (pokiaľ to nie je uvedené inak) aj zápis algoritmu (bez odvolávok na literatúru a knižnice)! Správne slovné úvahy bez zápisu algoritmu budú hodnotené len zlomkami bodov.

 

1. Dané je vstupné n-prvkové pole M[1..n]. Pre model EREW PRAM navrhnite a zapíšte vo WT zápise optimálny algoritmus, ktorý v čase O(log n) určí rank(x:M) pre zadanú hodnotu x v M[n+1] a výsledok uloží do M[n+2]. Optimalitu dokážte. Je vaše riešenie WT-optimálne ?

2. Dané je vstupné n-prvkové pole M[1..n] s neklesajúcimi hodnotami. Pre model CREW PRAM navrhnite a zapíšte vo WT zápise optimálny algoritmus, ktorý pre hodnotu M[n+1] konštantnom čase spočíta počet jej výskytov v poli M a zapíše ho na miesto M[n+2].

3. Pre vstupné n-prvkové pole M[1..n] s neklesajúcimi hodnotami zapíšte v CRCW-common PRAM modeli vo WT výpočtovom modeli algoritmus, ktorý v konštantnom čase určí rank(x:M) pre zadanú hodnotu x v M[n+1] a výsledok uloží do M[n+2]. Bude riešenie optimálne? Navrhnite efektívnejšie riešenie (stačí popis algoritmu s výpočtom času a práce bez WT zápisu) s podstatne nižšou prácou, pričom čas bude len O(log log n) .

4. Navrhnite paralelný algoritmus, ktorý v zadanom poli M[1..n] nájde pre každé i maximálny index k taký, že M[k] < M[i] a súčasne k < i . Výsledok uložte do poľa I[1..n] (ak požadovaný prvok neexistuje, zapíšte index 0). Zapíšte riešenie v CRCW-common modeli vo WT zápise a vypočítajte jeho časovú zložitosť a prácu. Skúste neefektívne riešenie v konštantnom čase, potom aj nejaké optimálne riešenie (s prácou O(n)). Je možné optimálne riešiť aj v CREW modeli ?

4*. Zapíšte sekvenčné riešenie úlohy 4 v čase O(n).  (riešenie používa „zátvorkovací“ princíp – teda dá sa jednoducho riešiť zásobníkom – ako v prípade úlohy 3 v sérii B)