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.
wersja strony: 6, ostatnia edycja: 17 Aug 2010 10:42