Literatura

Podstawy algorytmiki

Algorytmy: struktury danych i techniki programowania / Piotr Wróblewski
Perełki oprogramowania / Jon Bentley
Algorytmy + struktury danych = programy / Niklaus Wirth

Podstawy + zaawansowane techniki

Wprowadzenie do algorytmów / Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Clifford Stein
Wprowadzenie do teorii grafów / Robin J. Wilson
Kombinatoryka dla programistów / Witold Lipski
Algorytmy i struktury danych / Lech Banachowski, Krzysztof Diks, Wojciech Rytter

Uwaga

Książka Cormena jest lekturą obowiązkową. Niektóre rozdziały można co prawda potraktować jako ciekawostkę, jednak w ramach przygotowania do OI konieczne jest przeczytanie rozdziałów (mogą być trochę inne nazwy w innych wydaniach niż WNT 2005):

  • Rola algorytmów w obliczeniach [1]
  • Zaczynamy [2]
  • Rzędy wielkości funkcji [3]
  • Rekurencje [4] (bez wchodzenia w szczegóły)
  • Analiza probabilistyczna i algorytmy randomizowane [5] (wystarczy zrozumieć ideę randomizacji)
  • Heapsort - sortowanie przez kopcowanie [6]
  • Quicksort - sortowanie szybkie [7]
  • Sortowanie w czasie liniowym [8]
  • Mediany i statystki pozycyjne [9]
  • Elementarne struktury danych [10]
  • Tablice z haszowaniem [11] (wystarczy zrozumieć ideę haszowania i poznać wybrany algorytm)
  • Drzewo wyszukiwań binarnych [12]
  • jeśli po lekturze rozdziału [12] zainteresowało Cię równoważenie BST, przeczytaj lepiej artykuły w internecie o drzewach AVL albo drzepcach (treap), a nie rozdział o drzewach czerwono-czarnych [13]. Te rzeczy nie bywają jednak koniecznie potrzebne na większości zawodów.
  • jeśli przeczytałeś o jakichś drzewach zrównoważonych, możesz przeczytać Wzbogacanie struktur danych [14]
  • Programowanie dynamiczne [15]
  • Algorytmy zachłanne [16]
  • Analiza kosztu zamortyzowanego [17]
  • Struktury danych dla zbiorów rozłącznych [21] (bez analizy czasu działania metody łączenia wg rangi z kompresją ścieżki)
  • Podstawowe algorytmy grafowe [22]
  • Minimalne drzewa rozpinające [23]
  • Najkrótsze ścieżki z jednym źródłem [24]
  • Najkrótsze ścieżki między wszystkimi parami wierzchołków [25]
  • Maksymalny przepływ [26] (algorytmy "prześlij i …" niekoniecznie)
  • Algorytmy teorioliczbowe [31]
  • Wyszukiwanie wzorca [32]
  • Geometria obliczeniowa [33]
  • NP-zupełność [34] (bez wchodzenia w szczegóły)
  • Algorytmy aproksymacyjne [35] (bez wchodzenia w szczegóły)

W nawiasach [] numery rozdziałów wg wydania WNT 2005.