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

Ú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 21. 3. 2019, 14:25 (do začiatku testu). 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. Pre zadanú postupnosť v poli M[1..n] a hodnotu k v M[n+1] zapíšte CRCW-common PRAM WT algoritmus, ktorý v čase O(1) a práci O(n) nájde najmenšie i, že M[i] = k. Do M[n+2] zapíše index i alebo nulu, pokiaľ sa k v poli M nenachádza.(naznačili sme na prednáške).

2. Pre model CRCW-common PRAM navrhnite a zapíšte optimálny algoritmus vo WT modeli, ktorý v čase O(1) zistí, či vstupné pole M[1..n] obsahuje bitonickú postupnosť čísel.

3. Vstupné n-prvkové pole M[1..n] obsahuje červené a modré čísla (ofarbenie je v poli L[1..n] kódované číslami 0 a 1). Zapíšte vo WT modeli EREW PRAM algoritmus, ktorý v čase O(log n) preusporiada prvky poľa M tak, aby boli na začiatku červené čísla a na konci modré, pričom sa ale uchová pôvodné usporiadanie prvkov v jednotlivých farebných triedach. Bude riešenie optimálne ?

4. Nech T je zakorenený strom, ktorý sa skladá z n uzlov číslovaných 1, ..., n. Ďalej nech pole P obsahuje pre každý uzol stromu identifikátor jeho predchodcu, t.j. rodičom uzla i je uzol P[i]. Pre koreň r platí P[r] = r. Navrhnite a zapíšte algoritmus, ktorý v čase O(log n) na CREW PRAM priradí ku každému uzlu do poľa L[1..n] hodnoty 0 a 1 tak, že žiaden uzol stromu nemá priradenú rovnakú hodnotu ako jeho rodič (okrem koreňa).

5. „nevšímavý“ (oblivious) algoritmus na usporiadanie n-prvkového poľa M[1..n] strieda postupne paralelné porovnania všetkých susedných prvkov M[k] a M[k+1] pre nepárne k a paralelné porovnania všetkých prvkov M[k] a M[k+1] pre párne k. Zapíšte algoritmus pre n/2 procesorov modelu EREW PRAM z pohľadu i-teho procesora (nie vo WT-modeli). Spočítajte jeho zrýchlenie a efektivitu.

5*. S využitím 0-1 princípu dokážte korektnosť „nevšímavého“ (oblivious) algoritmu na usporiadanie n-prvkového poľa M[1..n] z úlohy 5. (koľko cyklov bude stačiť na usporiadanie poľa ?).