Wybrane zagadnienia informatyki 2019

Środa 1515 - 1655 A-1/321 ćwiczenia

Środa 1705 - 1845 A-1/321 wykład

Tematy zajęć (w przybliżeniu)

Część 1: Algorytmy równoległe

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ł 28: Sieci sortujące, Rozdział 29: Układy arytmetyczne, Rozdział 30: Algorytmy równoległe

Wykłady

1. Modele obliczeń równoległych. (2-10-2019)
[Model z pamięcią wspólną PRAM: EREW, CREW, common CRCW; Model sieciowy: kraty, torusy, hiperkostki; Czas, przyspieszenie, koszt i efektywność dla obliczeń równoległych;]

2. Podstawowe algorytmy na PRAM. (2-10-2019)
[Algorytmy na minimum, sumę, sumy prefiksowe; Obliczenia na listach;]

3. Podstawowe algorytmy na PRAM. (9-10-2019)
[Dodawanie równoległe; Metoda cyklu Eulera; Kolorowanie cyklu i maksymalny zbiór niezależny; Sortowanie;]

4. Sieci sortujące. (16-10-2019)
[Komparatory i sieci komparatorów; Zasada zero-jedynkowa; Sieć bitoniczna; Sieć permutująca Benesa;]

Ćwiczenia

Lista zadań (9-10-2019 - 1-5, 16-10-2019 - 6-10, 23-10-2019 - 11-17, 30-10-2019 - 18-22)

Część 2: Algorytmy online

Literatura

  1. A. Fiat, G. J. Woeginger: Online Algorithms: The State of the Art. Springer-Verlag, 1998
  2. S. Albers: Competitive online algorithms. Optima, 54:1-8, 1997.
  3. S. Albers: Lecture notes on competitive online algorithms. BRICS Lecture Series LS-96-2, AArhus University, Denmark, 1996.

Wykłady

5. Wprowadzenie. (23-10-2019)
[Podstawowe pojęcia - współczynnik konkurencyjności. Problem wypożyczania nart; Problem szukania krowy.]

6. Samoorganizujące się listy. (30-10-2019)
[Algorytmy Move-to-Front, Transpose, Frequency-Count. Dolna granica na współczynnik konkurencyjności dla algorytmów deterministycznych. Algorytm zrandomizowany Bit.]

7. Paging problem. (6-11-2019)
[Paging problem - definicja. Algorytmy FIFO, FWF, LRU, LFU. Algorytm oznaczający. Dolne ograniczenie algorytmów deterministycznych. Optymalność algorytmów oznaczających. Randomized Marking Algorithm. Oczekiwany współczynnik konkurencyjności RMA.]

8. Bin packing. (20-11-2019)
[Dolna granica na wsp. konkurencyjności. Algorytm Next-Fit. Algorytmy First-Fit i Best-Fit.]

Ćwiczenia

Lista zadań (6-11-2019 - 1-7, 20-11-2019 - 8-13, 27-11-2019 - 14-18)

Część 3: Elementy Teorii kategorii

Literatura

  1. Benjamin C. Pierce, Basic Category Theory for Computer Scientists, The MIT Press, 1991
  2. B. Milewski, Category Theory for Programmers, Creative Licence, 2017

Wykłady

9. Kategorie. Monoidy. Obiekty początkowe i końcowe. Monomorfizmy i epimorfizmy. (27-11-2019)

10. Iloczyn kartezjański. Komutowanie diagramów. Funktory i endofunktory. (4-12-2019)

11. Equalizery. D-cone. Odwzorowania naturalne. (11-12-2019)

12. Lemat Yonedy. (8-01-2020)

Ćwiczenia

Lista zadań

Część 4: Algorytmy aproksymacyjne oparte o programowanie liniowe

Literatura

  1. D. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011
  2. V. Vazirani, Approximation Algorithms, Springer-Verlag, 2003

Wykłady

13. Schemat prymalno-dualny i osłabione warunki swobody. Minimalne ważone pokrycie wierzchołkowe. (18-12-2019)

14. Problem multiprzekroju i wielotowarowego całkowitego przepływu na drzewach. (15-01-2020)

15. Minimalny problem plecakowy - luka całkowitoliczbowości. (22-01-2020)

Zasady zaliczenia kursu

???

Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl