Algorytmika - wykład monograficzny

Algorytmy równoległe 2016

Poniedziałek 17⁰⁵ - 18⁴⁵ C-13/1.31 wykład

Poniedziałek 9¹⁵ - 11⁰⁰ C-7/303A ćwiczenia
Poniedziałek 13¹⁵ - 15⁰⁰ C-7/303A ćwiczenia
Wtorek 17⁰⁵ - 18⁴⁵ C-7/303A ćwiczenia
Środa 15¹⁵ - 16⁵⁵ C-7/303A ćwiczenia

Wyniki studentów

Kolokwium odbedzie się na wykładzie 30 maja.

Literatura

1. Joseph JaJa, An Introduction to Parallel Algorithms, Addison Wesley Longman Publishing Co., 1992 (ISBN 0-201-54856-9)
2. Behrooz Parhami, Introduction to Parallel Processing: Algorithms and Architectures, Kluwer Academic Publisher 2002 (ISBN 0-306-46964-2)
3. Frank Thomson Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Kaufmann Publishers 1992 (ISBN 1-55860-117-1)
4. Zbigniew J. Czech, Wprowadzenie do obliczeń równoległych, Wydawnictwo Naukowe PWN 2013 (ISBN 978-83-01-17290-9)
5. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
   Rozdział 30: Algorytmy równoległe
   Rozdział 28: Sieci sortujące

Listy na ćwiczenia

• Lista nr 0
• Lista nr 1
• Lista nr 2
• Lista nr 3
• Lista nr 4
• Lista nr 5
• Lista nr 6
• Lista nr 7
• Lista nr 8
• Lista nr 9
• Lista nr 10

Dodatkowe zadanie programistyczne

Tematy wykładów (w przybliżeniu)

1. Modele obliczeń równoległych. (22-02-2016)
   [Model z pamięcią wspólną PRAM: EREW, CREW, common CRCW; Model sieciowy: kraty, torusy, hiperkostki;]
2. Efektywność - zużycie zasobów. (29-02-2016)
   [Czas, przyspieszenie, koszt i efektywność dla obliczeń równoległych; Prawo Amdahla; Miara Karpa-Flatta; Klasa NC;]
3. Podstawowe algorytmy na PRAM. (7-03-2016)
   [Algorytmy na minimum, sumę, sumy prefiksowe; Sortowanie; Twierdzenie Brenta;]
4. Podstawowe algorytmy na PRAM. (14-03-2016)
   [Obliczenia na listach; Metoda cyklu Eulera;]
5. Podstawowe algorytmy na PRAM. (21-03-2016)
   [Łamanie symetri; Kolorowanie listy; Maksymalny zbiór niezależny na liście;]
6. Podstawowe algorytmy na PRAM. (4-04-2016)
   [Oblicznie wyrażeń arytmetycznych; Najbliższy wspólny przodek w drzewie;]
7. Podstawowe algorytmy na PRAM. (11-04-2016)
   [Składowe spójne w grafie; Minimalne drzewo rozpinające;]
8. Sieci sortujące. (18-04-2016)
   [Komparator. Sieć odd-even. Zasada zero-jedynkowa. Sieć bitoniczn.]
9. Sieci sortujące. (25-04-2016)
   [Sieć Batchera. Sortowanie Shella-Prata. Sieci permutacyjne.]
10. Dzień Rektorski. (2-05.2016)
11. Sumator równoległy. Sieci logiczne. (9-05-2016)
    []
12. Architektury komputerów równoległych. (16-05-2016)
    []
13. Podsumowanie wykładu (23-05-2016)
    []
14. Kolokwium (30-05-2016)
15. Omówienie wybranych problemów. (6-06-2016)
    []

Zasady zaliczenia kursu

Ćwiczenia

• Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru.
• Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach studenci prezentują rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości dotyczące rozwiązania oraz przedstawiane alternatywne rozwiązania.
• W czasie ćwiczeń odbędą się 4 niezapowiedziane krótkie sprawdziany. Sprawdziany będą polegały na rozwiązaniu jednego zadania i punktowane od 0 do 5. Materiałem obowiązującym na sprawdzianie są tematy przerobione na trzech poprzednich ćwiczeniach. Nieobecność na sprawdzianie daje 0.
• Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) dwóch wyznaczonych zadań. Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty. Zadania wyznacza prowadzący ćwiczenia. Zadnie oddane na następnych ćwiczeniach pozwala zdobyć do 5 punktów (liczba punktów zależna od jakości rozwiązania).
• Za aktywność na ćwiczeniach prowadzący może przyznać dodatkowe punkty.
• Dodatkowe 5 punktów będzie można zdobyć za implementację pewnych wyznaczonych problemów w języku C przy użyciu biblioteki Open MP.
• Punktacja nie podlega poprawianiu po zakończeniu zajęć.

Wykład

• Kolokwium odbędzie się na ostatnim wykładzie i będzie na nim można zdobyć 30 punktów.
• Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu A4 podpisana w ten sposób aby z odległości 2 metrów dało się ustalić jej właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek, książek i innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.

Ocena końcowa zależy od ilości zdobytych punktów.

0-24 - ndst.

25-30 - dst.

31-36 - dst+.

37-42 - db.

43-48 - db+.

48-54 - bdb.

55-∞ - cel.