Obsah

• Teória paralelných výpočtov
• Distribuované systémy
• Paralelné a distribuované algoritmy
• Paralelné programovanie

1. Paralelné gramatiky: paralelné prepisovanie (Lindenmayerove systémy, Indické a Ruské paralelné gramatiky, generatívne systémy), kooperujúce distribuované gramatiky, paralelné gramatické systémy.
2. Paralelné stroje: alternujúce Turingove stroje, alternujúce konečné automaty, boolovské obvody, PRAM, počítače druhej triedy.
3. Ťažké problémy: Trieda NC, redukovateľnosť, P-úplné problémy.

1. Referenčný model ISO OSI, pojmy interfejs a protokol, úlohy jednotlivých vrstiev
2. Fyzická vrstva: prenosová kapacita kanálu, prenosové médiá, analógové a digitálne prenosové systémy, telefónny systém, multiplexovanie
3. Linková vrstva: framing, detekcia a oprava chýb, sliding windows, IEEE 802.3
4. Sieťová vrstva: siete zalozené na virtuálnych okruhoch a datagramoch, IPv4, IPv6 a súvisiace protokoly (ARP, DHCP, routovanie)
5. Transportná vrstva (UDP, TCP) a DNS
6. ATM: virtuálne okruhy, nadväzovanie spojenia, smerovacie tabuľky, QoS
7. Bezpečnosť: základy kryptografie, bezpečné kanály (autentifikácia, integrita, dôvernosť), distribúcia kľúčov, IPsec, SSL/TLS
8. Aplikácie: web a elektronická pošta
9. Komunikačný middleware: RPC, CORBA, Message Oriented Middleware, Web Services

1. 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).
2. Základné techniky návrhu paralelných algoritmov (vyváženosť, pointer jumping, rozdeľuj a panuj, rozklad, pipelining, accelerated cascating, rozbitie symetrie).
3. Techniky na zoznamoch a stromoch: list ranking, Euler tour, tree contraction (operácia rake, vyhodnocovanie aritmetických výrazov).
4. Efektívne paralelné spájanie (merge), triedenie, triediace siete, paralelný výber
5. Paralelné algoritmy pre grafové a geometrické problémy (súvislé a dvojsúvislé komponenty, minimálna kostra, konvexný obal,...)
6. 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).
7. Distribuovaná voľba šéfa na ľubovolných grafoch (Algoritmy Gallager, Humblet a Spira (GHS) a Korach, Kutten, Moran (KKM) pre minimálnu kostru grafu).
8. Distribuované prehľadávanie grafov (stratégia do šírky a do hĺbky).
9. Routovacie algoritmy (Tajibnapisov algoritmus Netchange, kompaktné routovacie metódy, hierarchické routovanie).
10. Routovanie paketov (greedy algoritmus na cestách a mriežkach)
11. 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)

1. Na jednoduchom príklade vysvetlite základné konštruktory programu v jazyku UNITY.
2. Popíšte logický kalkulus používaný pri dokazovaní vlastností UNITY programov.
3. Popíšte výpočtový model UNITY programov.
4. Ukážte, ako sa dajú UNITY programy realizovať na asynchrónnej architektúre so zdieľanou pamäťou distribuovanom a synchrónnom systéme.
5. 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.
6. 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.
7. Sformulujte readers/writers problém, napíšte jeho možné riešenie a načrtnite formálny dôkaz jeho správnosti.
8. 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.
9. 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.
10. Sformulujte problém komunikácie cez chybné kanály, načrtnite jeho riešenie spolu s formálnym dôkazom.