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.