Wybrane zagadnienia informatyki 2020

Wtorek 15¹⁵ - 16⁵⁵ MS Teams wykład

Wtorek 17⁰⁵ - 18⁴⁵ MS Teams ćwiczenia

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. (6-10-2020)
[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. (13-10-2020)
[Algorytmy na minimum, sumę, sumy prefiksowe; Dodawanie równoległe; Obliczenia na listach;]

3. Podstawowe algorytmy na PRAM. (20-10-2020)
[Metoda cyklu Eulera; Kolorowanie cyklu i maksymalny zbiór niezależny;]

4. Podstawowe algorytmy na PRAM. (27-10-2020)
[Drzewa obliczeń - algorytm RAKE; Sortowanie;]

5. Sieci sortujące. (3-11-2020)
[Komparatory i sieci komparatorów; Zasada zero-jedynkowa; Sieć bitoniczna; Sieć permutująca Benesa;]

Ćwiczenia

Lista zadań

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

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

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

3. Paging problem. (24-11-2020)
[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.]

4. Bin packing. (1-12-2020)
[Dolna granica na wsp. konkurencyjności. Algorytm Next-Fit. Algorytmy First-Fit i Best-Fit.]

5. Zrandomizowane algorytmy online - Yao's Principle. (8-12-2020)
[Yao's Principle zastosowane do dolnych granic algorytmów zrandomizowanych. Dolna granica na zrandomizowany algorytm paging-u.]

Ćwiczenia

Lista zadań

Część 3: Wybrane algorytmy i struktury danych

Literatura

1. S. Dasgupta, C. Papadimitriou, U. Vazirani: Algorytmy. WN PWN, Warszawa 2011 (ISBN 9788301162788)
2. J. Kleinberg, E. Tardos: Algorithm Design. (ISBN: 9780321295354)
3. D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM (1985). 32 (3): 652–686.

Wykłady

1. Koszt zamortyzowany. (15-12-2020)
[Metody kosztu sumarycznego, księgowania i potencjału. Tablice dynamiczne.]

2. Koszt zamortyzowany. (12-01-2021)
[Kopiec dwumianowy. Kopiec Fibonacciego. Samoorganizujące się drzewa binarne (splay).]

3. Przepływy i skojarzenia. (19-01-2021)
[Algorytm Forda-Fulkersona. Algorytm Edmondsa-Karpa. Skojarzenie w grafie dwudzielnym.]

4. Przepływy i skojarzenia. (26-01-2021)
[Modyfikacje przepływów. Skojarzenia w dowolnym grafie.]

Ćwiczenia

Lista zadań

Zasady zaliczenia kursu

Kurs będzie zaliczony na podstawie pisemnych (PDF) rozwiązań zadań wyznaczonych przez prowadzącego ćwiczenia.