Paralelné modely (PRAM, paralelná sieť, DAG), miery zložitosti
(čas, počet procesorov, počet operácií), optimálnosť, prezentácia
paralelných algoritmov (WT paradigma).
Základné techniky návrhu paralelných algoritmov (vyváženosť, pointer
jumping, rozdeľuj a panuj, rozklad, pipelining, accelerated cascading,
rozbitie symetrie).
Techniky na zoznamoch a stromoch: list ranking, Euler tour, tree
contraction.
Distribuované siete s chybnými procesormi (úloha o byzantínskych
generáloch, riešenie pre ústne a podpísané správy, adaptibilné algoritmy
pre eventuálnu dohodu).
Na jednoduchom príklade vysvetlite základné konštruktory programu
v jazyku UNITY.
Popíšte logický kalkulus používaný pri dokazovaní vlastností
UNITY programov.
Popíšte výpočtový model UNITY programov.
Ukážte, ako sa dajú UNITY programy realizovať na
asynchrónnej architektúre so zdieľanou pamäťou, distribuovanom a
synchrónnom systéme.
Napíšte jednoduchý program na výpočet maxima $n$ rôznych prvkov,
načrtnite formálny dôkaz jeho správnosti, urobte analýzu jeho
zložitosti pre rôzne paralelné architektúry.
Napíšte jednoduchý program na porovnanie dvoch neklesajúcich
postupností, načrtnite formálny dôkaz jeho správnosti, urobte
analýzu jeho zložitosti pre rôzne paralelné architektúry.
Sformulujte readers/writers problém, napíšte jeho možné riešenie
a načrtnite formálny dôkaz jeho správnosti.
Napíšte program na nájdenie najkratšej cesty v orientovanom grafe,
načrtnite formálny dôkaz jeho správnosti, urobte analýzu jeho
zložitosti pre rôzne paralelné architektúry.
Napíšte program na triedenie rank sort, načrtnite formálny dôkaz
jeho správnosti, urobte analýzu jeho zložitosti pre rôzne paralelné
architektúry.
Sformulujte problém komunikácie cez chybné kanály, načrtnite jeho
riešenie spolu s formálnym dôkazom.