Paralelné modely (PRAM a jeho varianty), miery zložitosti (čas, počet
procesov, 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 cascating,
rozbitie symetrie).
Techniky na zoznamoch a stromoch: list ranking, Euler tour, tree
contraction (operácia rake, vyhodnocovanie aritmetických výrazov).
Efektívne paralelné spájanie (merge), triedenie, triediace siete,
paralelný výber
Paralelné algoritmy pre grafové a geometrické problémy (súvislé a
dvojsúvislé komponenty, minimálna kostra, konvexný obal,...)
Distribuovaná voľba šéfa (synchrónne a asynchrónne algoritmy,
jednosmerné, dvojsmerné kruhy a úplné grafy, priemerný a najhorší
prípad počtu správ).
Distribuovaná voľba šéfa na ľubovolných grafoch (Algoritmy Gallager,
Humblet a Spira (GHS) a Korach, Kutten, Moran (KKM) pre minimálnu
kostru grafu).
Distribuované prehľadávanie grafov (stratégia do šírky a do hĺbky).
Routovanie paketov (greedy algoritmus na cestách a mriežkach)
Distribuované siete s chybnými procesormi (problém dohody
v distribuovaných systémoch pre stop-chyby a byzantínske chyby, horný
odhad počtu byzantínsky chybných procesorov, algoritmy pre problém dohody)
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 SnS 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.