Wybrane zagadnienia informatyki 2022

Poniedziałek 11¹⁵ - 13⁰⁰ D-1/215 wykład

Czwartek 13⁴⁰ - 15¹⁰ ćwiczenia

Lista drugich zadań domowych

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

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

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

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

Ćwiczenia

Lista zadań

Część 2: 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. (07-11-2022)
[Metody kosztu sumarycznego, księgowania i potencjału. Tablice dynamiczne.]

2. Koszt zamortyzowany. (14-11-2022)
[Kopiec dwumianowy. Kopiec Fibonacciego. Samoorganizujące się drzewa binarne (splay).]

Ćwiczenia

Lista zadań

Część 3: Krótkie wprowadzenie do λ-rachunku

Literatura

1. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Wykłady

1. Wprowadzenie do λ-rachunku. (21-11-2022)
[Składnia λ-rachunku, α-kongruencje, β-redukcje i η-redukcje. Rachunek zdań w λ-rachunku.]

2. Liczebniki Church-a. Twierdzenie o punkcie stałym. (28-11-2022)
[]

Ćwiczenia i notatki

Notatki i lista zadań

Część 4: Obliczenia kwantowe

Literatura

1. Ch. Bernhardt, Obliczenia kwantowe dla każdego, WN PWN, Warszawa 2020 (ISBN 978-83-012-1215-5)

Wykłady

1. Obliczenia kwantowe. Kubity i splątanie. (05-12-2022)
[]

2. Kwantowe układy logiczne. Klasa QPP (12-12-2022)
[]

3. Przykładowe algorytmy kwantowe. (19-12-2022)
[]

4. Przykładowe algorytmy kwantowe. (9-01-2023)
[]

Ćwiczenia i notatki

Notatki i lista zadań

Zasady zaliczenia kursu

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