2005

Algorytmy Równoległe i Rozproszone

Wyniki pierwszego kolokwium (28 listopada) i drugiego (23 stycznia)

Reklamacje w ciągu tygodnia: w trakcie konsultacji lub po ćwiczeniach.

Do zaliczenia wykładu wystarczy 100pkt. Poprawki ustnie. Proponowane terminy: wtorek 31 stycznia, piątek 3 lutego. Kolejne w sesji poprawkowej.

Harmonogram najbliższych prezentacji

• 21 listopada - Pan Karol Sz. - Chłodzenie superkomputerów,
• 25 listopada - Pan Sylwester H. - Neurokomputery,
• 5 grudnia - Pan Bartosz I. - Sieci P2P,
• 12 grudnia - Pan Marcin W. - Techniki zrównoleglania w językach imperatywnych,
• 19 grudnia - Pan Krzysztof B. - Algorytmy równoległe w biologii obliczeniowej,
• 6 stycznia - Pan Mariusz G. - Rozproszona kompilacja (16 stycznia),
• 9 stycznia - Pan Patryk M. - Samostabilizujące algorytmy dla drzewa spinającego,
• 13 stycznia - Pan Łukasz L. - Elementy równoległe w komputerach osobistych,
• 20 stycznia - Patryk P. - Obliczenia równoległe w grafice(25 stycznia),
• 25 stycznia - Pan Łukasz L. - Elementy równoległe w komputerach osobistych (c. d.)

Warunki Zaliczenia

Notatki do wykładu

• Wprowadzenie i Sieci porównujące (slajdy-pdf)   (1 - pdf)   (1 - ps)   (2 - pdf)   (2 - ps)
• Układy kombinacyjne i P-zupełność (slajdy-pdf)   (pdf)   (ps)
• Model PRAM (slajdy-pdf)   (pdf)   (ps)
• Model PRAM II (slajdy-pdf)   (pdf)   (ps)
• Model PRAM - algorytmy numeryczne (slajdy-pdf)   (pdf)   (ps)
• Systemy rozproszone, wstęp (slajdy-pdf)   (pdf)   (ps)
• Systemy rozproszone, c. d. (slajdy-pdf)   (pdf)   (ps)
• Rozproszone algorytmy probabilistyczne (slajdy-pdf)   (pdf)   (ps)

Materiały do ćwiczeń

• Propozycje tematów do przygotowania (pdf)   (ps)

Poprawki i uzupełnienia

• Sieci porównujące, notatki str 8: Zły rysunek na schemacie sieci scalającej. Zamiast elementu: HALF CLEANER powinien się pojawić jego odpowiednik z odwróconym wejściem (poprzedni slajd).
• Model PRAM, Twierdzenie Brent'a. Powinno być: ... da się symulować na ...
• Model PRAM, Algorytm 3, należy usunąć linię 3.

Literatura

Książki

1. T. H. Cormen, C. E. Leiserson and R. L. Rivest, ,,Introduction to Algorithms'', The MIT Press/McGraw-Hill Company, 1990 (wydanie polskie WNT).
2. Gerard Tel, ,,Introduction to Distributed Algorithms'', Cambridge University Press, 2nd edition, 2000.
3. Shlomi Dolev. Self-Stabilization. The MIT Press, 2000.
4. C. Xavier, S. S. Iyengar, ,,Introduction to Parallel Algorithms'', Wiley-IEEE, 1998.
5. Hagit Attiya, Jennifer Welch ,,Distributed Computing: Fundamentals, Simulations, and Advanced Topics'', McGraw-Hill, 1998.
6. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar ,,Introduction to Parallel Computing'', Addison Weslesy, 2003.
7. J. Jaja, ,,An Introduction to Parallel Algorithms'', Addison-Wesley, Reading, MA, 1992.
8. S.G. Akl, ,,The Design and Analysis of Parallel Algorithms'', Prentice-Hall, 1989.

- książka w posiadaniu wykładowcy

Materiały w wersji elektronicznej

1. Hagit Attiya Lecture Notes for Course Distributed Algorithms, 1994.
2. Guy E. Blelloch, Bruce M. Maggs: Parallel Algorithms. The Computer Science and Engineering Handbook, 1997: 277-315.
3. Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo Limits to Parallel Computation: P-Completeness Theory , Oxford University Press, 1998.
4. Designing and Building Parallel Programs, by Ian Foster.
5. Lecture Notes Repository, maintained by University of Padeborn.

Wybrane artykuły

1. The Byzantine Generals Problem, by L. Lamport, R. Shostak i M. Pease (pdf).

Inne

• Kurs programowania równolegełego w TASK.
• 500 najszybszych komputerów na świecie: top500 .
• Sphere Online Judge
• Binboy at Sphere - serwis programistów (język polski).
• Więcej odnośników: R. B. Muhhamad
• Materiały do kursu Parallel and Distributed Algorithms
• Materiały do kursu Distributed Algorithms - Christos T. Karamanolis i Jeff Magee.

Hasła przydatne w samodzielnym wyszukiwaniu:

• parallel algorithms
• distributed algorithms
• parallel computing
• distributed computing
• self-stabilizing algorithms
• self-stabilization
• distributed resilient algorithm
• lecture notes
• course notes