English version

• polskie
podział tematyczny
 
• anglojęzyczne
podział tematyczny
 
Newsletter:

• Zamów informacje o nowościach z wybranego tematu
 
Informacje:

• o księgarni

• koszty wysyłki

• kontakt

• Cookies na stronie

Algorytmy + struktury danych = abstrakcyjne typy danych

Algorytmika jest dziedziną wiedzy, która w ostatnich dziesięcioleciach dostarczyła mnóstwa narzędzi, pozwalających rozwiązać różnorodne zadania za pomocą komputera.

W książce poruszono wiele tematów z tej dziedziny, kładąc szczególny nacisk na analizę efektywności użytych struktur danych oraz algorytmów.

Opisano podstawowe struktury danych, takie jak tablice, listy czy kolejki, oraz bardziej złożone: drzewa, kopce, słowniki oraz strtuktury Union-Find.

Osobny rozdział poświęcono alorytmom sortowania, od najprostszych: SelectionSort czy BubbleSort, po bardziej skomplikowane jak QuickSort czy sortowanie pozycyjne.

Zaprezentowane w książce algorytmy w większości zaimplementowano w postaci funkcji w języku C++.

Wstęp

1. Metody analizy algorytmów
1.1. Poprawność i efektywność algorytmów
1.2. Analiza poprawności semantycznej algorytmów
1.2.1. Specyfikacja zadania
1.2.2. Poprawność algorytmu
1.2.3. Analiza modyfikacji warunków ( reguły wnioskowania )
1.2.4. Częściowa poprawność
1.2.5. Metody dowodzenia własności stopu
Metoda liczników iteracji
Metoda malejących wielkości
1.2.6. Przykład analizy poprawności .
Algorytm Euklidesa
Częściowa poprawność
Własność określoności
Własność stopu
1.2.7. Poprawność algorytmów rekurencyjnych
Przykład 1 . Rekurencyjny algorytm Euklidesa
Przykład 2 . Wyszukiwanie w drzewie binarnym
1.3. Analiza złożoności obliczeniowej
1.3.1. Określanie złożoności . O - notacja
1.3.2. Właściwości O - notacji
1.3.3. Przykłady analizy złożoności
1.3.4. Złożoność średnia
1.3.5. Przykłady złożoności
1.3.6. Złożoność pamięciowa

2. Metody projektowania algorytmów
2.1. Wprowadzenie
2.2. Strategia „ Dziel i rządź ”
Przykład 1 . Znajdowanie minimalnego i maksymalnego elementu zbioru
Przykład 2 . Mnożenie dwóch liczb binarnych n - bitowych
2.3. Rekurencja
2.4. Programowanie dynamiczne ( optymalizacja dynamiczna )

3. Proste struktury danych
3.1. Wprowadzenie
3.2. Tablice
3.3. Listy
3.4. Drzewa

4. Abstrakcyjne typy danych
4.1. Wprowadzenie
4.2. Stosy i kolejki

5. Kolejki priorytetowe
5.1. Kopiec
5.2. Dwukopiec

6. Kopce złączalne
6.1. Wprowadzenie
6.2. Kopiec lewostronny ( leftist heap )
6.3. Kopiec skośny ( skew heap )
6.4. Kolejka dwumianowa Implementacja kolejki dwumianowej
6.5. 2 - 3 drzewo +

7. Słowniki
7.1. Wprowadzenie
7.2. Wyszukiwanie w listach  i tablicach
7.3. Drzewa BST
7.4. Zrównoważone drzewa binarne AVL
7.5. Samoorganizujące się drzewa BST ( drzewa Splay)
7.6. Optymalne drzewa BST
7.7. B - drzewa
7.8. 2 - 3 drzewa
7.8.1. 2 - 3 drzewa jako B - drzewa
7.8.2. 2 - 3 drzewa poziomo - pionowe
7.9 . 2 - 3 - 4 drzewa
7.9.1. 2 - 3 - 4 drzewa poziomo - pionowe
7.9.2. 2 - 3 - 4 drzewa czerwono - czarne
7.10. Porównanie drzew binarnych
7.11. Drzewa wyszukiwań pozycyjnych
7.11.1. Wprowadzenie
7.11.2. Drzewa RST
7.11.3. Drzewa TRIE
7.11.4  Drzewa Patricia
7.12. Haszowanie
7.12.1. Wprowadzenie
7.12.2. Metody usuwania kolizji
7.12.3. Mieszanie łańcuchowe
7.12.4. Mieszanie rozproszone
7.12.5. Mieszanie otwarte

8. Kolejki konkatenowalne

9. Struktury Union - Find
9.1. Wprowadzenie
9.2. Tablicowa realizacja reprezentacji zbioru
9.3. Struktury drzewiaste

10. Sortowanie
10.1. Wprowadzenie
10.2. Sortowanie wewnętrzne przez porównania
10.2.1. Metody  elementarne
Sortowanie przez wybór (  SelectionSort)
Sortowanie przez wstawianie ( InsertionSort )
Sortowanie bąbelkowe ( BubbleSort )
10.2.2. Metody nieelementarne
Sortowanie przez kopcowanie ( HeapSort )
Sortowanie szybkie ( QuickSort )
Sortowanie Shella ( ShellSort )
10.2.3. Dolne oszacowanie złożoności sortowania przez porównania
10.3. Sortowanie elementów o wartościach z niewielkiego zbioru
10.3.1. Założenia
10.3.2. Sortowanie kubełkowe ( BucketSort )
10.3.3. Sortowanie przez zliczanie ( CountSort )
10.3.4. Sortowanie leksykograficzne
Sortowanie leksykograficzne przy użyciu BucketSort
Sortowanie leksykograficzne słów o niejednakowej długości
Sortowanie leksykograficzne przy użyciu CountSort
10.3.5. Sortowanie pozycyjne – RadixSort
10.4. Sortowanie zewnętrzne ( plików )
10.4.1. Założenia
10.4.2. Sortowanie przez łączenie ( MergeSort )

11. Zadanie wyboru
11.1. Wprowadzenie
11.2. Wybór wartości minimalnej i maksymalnej
11.3. Wybór k - tego elementu
11.3.1.Algorytm Hoare’a
11.3.2.Algorytm o pesymistycznej złożoności liniowej

Literatura