« powrót do strony głównej

Zaawansowane algorytmy

Komunikaty

Bieżące informacje o wykładzie (np. odwołania itp.) oraz materiały do przedmiotu będą umieszczane na zespole MS Teams:

Tematy wykładów

  1. Wstępnie
    • Drzewa binarne
    • Złożoność asymptotyczna
    • Twierdzenie o rekursji uniwersalnej
  2. Algorytmy w czasie stałym
  3. Technika drzewa zbalansowanego
  4. Obliczanie sum prefiksowych
    • Algorytm nieoptymalny/optymalny.
    • Zastosowanie: sumowanie liczb binarnych.
  5. Pointer jumping
    • Wyznaczanie korzeni w lesie.
    • Sumy prefiksowe na drzewie.
    • List ranking.
  6. Technika cyklu Eulera
    • Sprawdzian 1 (zakres: Tematy 1-5)
  7. Technika cyklu Eulera c.d.
    • Ukorzenianie drzewa.
    • Vertex level.
    • Wyznaczanie drzew.
  8. Łamanie symetrii i mergesort
    • 3-Kolorowanie cyklu.
    • Sortowanie przez scalanie.
  9. Ewaluacja wyrażeń arytmetycznych
    • Algorytm tree-contraction
  10. Zaliczenia
    • Sprawdzian 2 (zakres: Tematy 6-9)

Zaliczenie wykładu

Egzamin pisemny na ocenę.

Zaliczenie ćwiczeń

Składa się z: Ocena 3.0 od 51% maksymalnej liczby podstawowych punktów. Każde kolejne 10% to pół oceny w górę.

Materiały i literatura

  1. Joseph Jaja, An Introduction to Parallel Algorithms, Addison-Wesley Publishing Company, 1992.
  2. Selim Akl, The Design and Analysis of Parallel Algorithms, Prentice-Hall, 1989.