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. Pojem počítačovej siete, použitie počítačových sietí.
2. Základná klasifikácia počítačových sietí.
3. Princípy vrstvovej architektúry, connection-oriented a connectionless služby.
4. Referenčný model ISO OSI.
5. Referenčný model TCP/IP.
6. Porovnanie referenčných modelov ISO OSI a TCP/IP.
7. Príklady sieťových systémov: ARPANET, Novell, NSFNET, Internet, Gigabit testbeds.
8. Príklady dátových služieb: X.25, Frame Relay, Broadband ISDN, ATM.
9. Teoretické základy dátovej komunikácie.
10. Prenosové médiá.
11. Bezdrôtový prenos.
12. Telefónne systémy.
13. Rozhrania RS 232 a RS 449.
14. FDM a TDM.
15. SONET/SDH.
16. Prepínanie (switching).
17. N-ISDN.
18. B-ISDN a ATM.
19. Pagere a celulárne telefóny.
20. Komunikačné satelity.
21. Internetworking.
22. Sieťová vrstva v Internete --- Protokol IP.
23. Protokol UDP.
24. Protokol TCP.
25. Systém DNS.
26. Sieťová vrstva v sieťach ATM.

1. 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).
2. Základné techniky návrhu paralelných algoritmov (vyváženosť, pointer jumping, rozdeľuj a panuj, rozklad, pipelining, accelerated cascading, rozbitie symetrie).
3. Techniky na zoznamoch a stromoch: list ranking, Euler tour, tree contraction.
4. Efektívne paralelné prehľadávanie, spájanie, triedenie, triediace siete. Paralelný výber, vyhľadávanie vzoriek v texte.
5. Model distribuovaných výpočtov (prechodový system s asynchrónnym posielaním správ), časová a komunikačná zložitosť.
6. Distribuovaná voľba šéfa (synchrónne a asynchrónne algoritmy, jednosmerné a dvojsmerné kruhy, priemerný a najhorší prípad).
7. Distribuovaná voľba šéfa na ľubovolných grafoch (Gallagerov, Humbletov a Spirov algoritmus 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, routovanie s kompaktnými tabuľkami, hierarchické routovanie).
10. 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).

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 $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.
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.