Comenius LogoKatedra informatiky
Fakulta matematiky, fyziky a informatiky
Univerzity Komenského, Bratislava


Sylabus na štátnu skúšku blokového štúdia odboru Informatika z bloku Algoritmy a paralelné výpočty
v školskom roku 1998/99

zo dňa 16.decembra 1998


Obsah


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

Paralelné a distribuované algoritmy

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

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