Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących

Spis treści książki

O autorze 7

Wstęp 9

Rozdział 1. Algorytmy i ich złożoność 13

• Tworzymy nasz pierwszy algorytm 14
• Algorytm konwersji liczb dwójkowych na dziesiętne 14
• Mierzenie złożoności algorytmów za pomocą notacji dużego O 16
• Przykład na złożoność 16
• Zrozumienie złożoności 18
• Notacja złożoności 22
• Identyfikacja algorytmów o różnej złożoności 26
• Złożoność liniowa 26
• Złożoność kwadratowa 27
• Złożoność logarytmiczna 28
• Złożoność wykładnicza 30
• Złożoność stała 31
• Podsumowanie 33

Rozdział 2. Algorytmy sortowania i podstawowe struktury danych 35

• Wprowadzenie do sortowania bąbelkowego 35
• Zrozumienie sortowania bąbelkowego 36
• Udoskonalanie sortowania bąbelkowego 37
• Zrozumienie sortowania szybkiego 40
• Zrozumienie rekurencji 40
• Podział w wyszukiwaniu szybkim 41
• Jak to wszystko poskładać razem 44
• Korzystanie z sortowania przez scalanie 45
• Dzielenie problemu 46
• Scalanie problemu 47
• Rozpoczęcie pracy z podstawowymi strukturami danych 50
• Wprowadzenie do struktur danych 50
• Struktura list powiązanych 51
• Operacje na listach powiązanych 53
• Kolejki 56
• Stosy 57
• Modelowanie stosów i kolejek przy użyciu tablic 59
• Podsumowanie 63

Rozdział 3. Tablice z haszowaniem i binarne drzewa poszukiwań 65

• Wprowadzenie do tablic z haszowaniem 65
• Zrozumienie tablic z haszowaniem 66
• Rozwiązywanie kolizji przez łańcuchowanie 68
• Rozwiązywanie kolizji przez adresowanie otwarte 71
• Haszowanie uniwersalne 76
• Rozpoczęcie pracy z binarnymi drzewami poszukiwań 78
• Struktura drzewa binarnego 78
• Operacje na binarnych drzewach poszukiwań 80
• Przechodzenie przez binarne drzewo poszukiwań 83
• Zrównoważone binarne drzewa poszukiwań 85
• Podsumowanie 90

Rozdział 4. Paradygmaty projektowania algorytmów 91

• Wprowadzenie do algorytmów zachłannych 92
• Problem wyboru zajęć 92
• Rozwiązanie problemu wyboru zajęć 94
• Składniki algorytmu zachłannego 94
• Kodowanie Huffmana 96
• Ćwiczenie: Implementacja algorytmu zachłannego do obliczania ułamków egipskich 100
• Wprowadzenie do algorytmów typu "dziel i zwyciężaj" 101
• Podejście "dziel i zwyciężaj" 101
• Metoda rekurencji uniwersalnej 102
• Problem najbliższej pary punktów 104
• Ćwiczenie: Rozwiązywanie problemu podtablicy o największej sumie 106
• Zrozumienie programowania dynamicznego 108
• Elementy problematyki programowania dynamicznego 108
• Dyskretny problem plecakowy 109
• Najdłuższy wspólny podciąg 112
• Ćwiczenie: Problem wydawania reszty 114
• Podsumowanie 115

Rozdział 5. Algorytmy wyszukiwania wzorca w tekście 117

• Algorytm wyszukiwania naiwnego 117
• Implementacja wyszukiwania naiwnego 118
• Usprawnienie algorytmu wyszukiwania naiwnego 119
• Pierwsze kroki z algorytmem wyszukiwania wzorca Boyera-Moore'a 120
• Zasada niezgodności 120
• Zasada dobrego sufiksu 123
• Zastosowanie algorytmu Boyera-Moore'a 126
• Prezentacja innych algorytmów wyszukiwania wzorca w tekście 127
• Algorytm Rabina-Karpa 128
• Algorytm Knutha-Morrisa-Pratta 129
• Algorytm Aho-Corasick 130
• Podsumowanie 130

Rozdział 6. Grafy, liczby pierwsze i klasy złożoności 131

• Reprezentacja grafów 132
• Listy sąsiedztwa 133
• Macierz sąsiedztwa 135
• Przechodzenie przez graf 137
• Przeszukiwanie wszerz 138
• Przeszukiwanie w głąb 140
• Wykrywanie cykli 143
• Obliczanie najkrótszych ścieżek 145
• Najkrótsza ścieżka z pojedynczego źródła: algorytm Dijkstry 145
• Najkrótsze ścieżki dla wszystkich par wierzchołków: algorytm Floyda-Warshalla 150
• Liczby pierwsze w algorytmach 153
• Sito Eratostenesa 154
• Rozkład na czynniki pierwsze 154
• Inne koncepcje związane z grafami 155
• Minimalne drzewa rozpinające 155
• Algorytm A* 156
• Problem maksymalnego przepływu 156
• Zrozumienie klas złożoności problemów 157
• Podsumowanie 158

Skorowidz 159

pokaż cały spis treści

ukryj recenzje