INFO - Informacie o MFF UK

Algoritmy a paralelne vypocty (IS: 642321)

Blok :  Algoritmy a paralelne vypocty

Gestor: Doc. RNDr. Peter Ruzicka, CSc.

 Predmet: Algoritmy a paralelne vypocty.

1 Teoria paralelnych vypoctov.

1. Paralelne gramatiky: paralelne prepisovanie (Lindenmayerove systemy,
   Indicke a Ruske paralelne gramatiky, generativne systemy), kooperujuce
   distribuovane gramatiky, paralelne gramaticke systemy.

2. Paralelne stroje: alternujuce Turingove stroje, alternujuce konecne
   automaty, boolovske obvody, PRAM, pocitace druhej triedy.

3. Tazke problemy: Trieda NC, redukovatelnost, P-uplne problemy.

-----------------------

2 Distribuovane systemy

 1. Pojem pocitacovej siete, pouzitie pocitacovych sieti.
 2. Zakladna klasifikacia pocitacovych sieti.
 3. Principy vrstvovej architektury, connection-oriented a connectionless
    sluzby.
 4. Referencny model ISO OSI.
 5. Referencny model TCP/IP.
 6. Porovnanie referencnych modelov ISO OSI a TCP/IP.
 7. Priklady sietovych systemov: ARPANET, Novell, NSFNET, Internet, Gigabit
    testbeds.
 8. Priklady datovych sluzieb: X.25, Frame Relay, Broadband ISDN, ATM.
 9. Teoreticke zaklady datovej komunikacie.
10. Prenosove media.
11. Bezdrotovy prenos.
12. Telefonne systemy.
13. Rozhrania RS 232 a RS 449.
14. FDM a TDM.
15. SONET/SDH.
16. Prepinanie (switching).
17. N-ISDN.
18. B-ISDN a ATM.
19. Pagere a celularne telefony.
20. Komunikacne satelity.
21. Internetworking.
22. Sietova vrstva v Internete - Protokol IP.
23. Protokol UDP.
24. Protokol TCP.
25. System DNS.
26. Sietova vrstva v sietach ATM.

-----------------------

3 Paralelne a distribuovane algoritmy

 1. Paralelne modely (PRAM, paralelna siet, DAG), miery zlozitosti (cas,
    pocet procesorov, pocet operacii), optimalnost, prezentacia paralelnych
    algoritmov (WT paradigma).

 2. Zakladne techniky navrhu paralelnych algoritmov (vyvazenost, pointer
    jumping, rozdeluj a panuj, rozklad, pipelining, accelerated cascading,
    rozbitie symetrie).

 3. Techniky na zoznamoch a stromoch: list ranking, Euler tour, tree
    contraction.

 4. Efektivne paralelne prehladavanie, spajanie, triedenie, triediace
    siete. Paralelny vyber, vyhladavanie vzoriek v texte.

 5. Model distribuovanych vypoctov (prechodovy system s asynchronnym
    posielanim sprav), casova a komunikacna zlozitost.

 6. Distribuovana volba sefa (synchronne a asynchronne algoritmy,
    jednosmerne a dvojsmerne kruhy, priemerny a najhorsi pripad).

 7. Distribuovana volba sefa na lubovolnych grafoch (Gallagerov, Humbletov
    a Spirov algoritmus pre minimalnu kostru grafu).

 8. Distribuovane prehladavanie grafov (strategia do sirky a do hlbky).

 9. Routovacie algoritmy (Tajibnapisov algoritmus Netchange, routovanie s
    kompaktnymi tabulkami, hierarchicke routovanie).

10. Distribuovane siete s chybnymi procesormi (uloha o byzantinskych
    generaloch, riesenie pre ustne a podpisane spravy, adaptibilne algoritmy
    pre eventualnu dohodu).

-----------------------

4 Paralelne programovanie

 1. Na jednoduchom priklade vysvetlite zakladne konstruktory programu v
    jazyku UNITY.

 2. Popiste logicky kalkulus pouzivany pri dokazovani vlastnosti UNITY
    programov.

 3. Popiste vypoctovy model UNITY programov.

 4. Ukazte, ako sa daju UNITY programy realizovat na asynchronnej
    architekture so zdielanou pamatou, distribuovanom a synchronnom
    systeme.

 5. Napiste jednoduchy program na vypocet maxima n roznych prvkov,
    nacrtnite formalny dokaz jeho spravnosti, urobte analyzu jeho
    zlozitosti pre rozne paralelne architektury.

 6. Napiste jednoduchy program na porovnanie dvoch neklesajucich
    postupnosti, nacrtnite formalny dokaz jeho spravnosti, urobte analyzu
    jeho zlozitosti pre rozne paralelne architektury.

 7. Sformulujte readers/writers problem, napiste jeho mozne riesenie a
    nacrtnite formalny dokaz jeho spravnosti.

 8. Napiste program na najdenie najkratsej cesty v orientovanom grafe,
    nacrtnite formalny dokaz jeho spravnosti, urobte analyzu jeho
    zlozitosti pre rozne paralelne architektury.

 9. Napiste program na triedenie rank sort, nacrtnite formalny dokaz jeho
    spravnosti, urobte analyzu jeho zlozitosti pre rozne paralelne
    architektury.

10. Sformulujte problem komunikacie cez chybne kanaly, nacrtnite jeho
    riesenie spolu s formalnym dokazom.

Datum poslednej aktualizacie tohto dokumentu: 30.4.99.
Posledna aktualizacia udajov v systeme: 091006-V393.