Sylabus na štátnu skúšku blokového štúdia odboru
Informatika z bloku Algoritmy a paralelné a výpočty
Marec 2006

Obsah

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

Teória paralelných výpočtov

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

Distribuované systé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á posta
9.	Komunikačný middleware: RPC, CORBA, Message Oriented Middleware, Web Services

Paralelné a distribuované algoritmy

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)

Paralelné programovanie

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.