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

Aby aplikacje mogły spełniać oczekiwania dotyczące wydajności i szybkości działania, programista musi orientować się w typowych problemach z wykonywaniem kodu i wiedzieć, które techniki sprawdzą się w danej sytuacji. W tym celu powinien biegle posługiwać się algorytmami i strukturami danych. Wiedza ta umożliwia rozpoznawanie typowych zagrożeń i wybór najlepszych rozwiązań. Warto pamiętać, że w przypadku większości codziennych problemów z kodem istnieją już wypróbowane rozwiązania. Znajomość tych zagadnień jest niezwykle ważna dla każdego inżyniera oprogramowania.

To książka przeznaczona dla programistów, którzy chcą w praktyczny sposób posługiwać się popularnymi algorytmami i strukturami danych, zrozumieć ich działanie i skuteczniej poprawiać wydajność swojego kodu w Javie. Przedstawiono tu narzędzia przydatne w pracy z algorytmami i w tworzeniu efektywnych aplikacji. Opisano praktyczne aspekty złożoności algorytmów. Omówiono algorytmy sortowania oraz inne popularne wzorce programowania, a także takie struktury danych jak drzewa binarne, tablice z haszowaniem i grafy. Następnie zaprezentowano koncepcje bardziej zaawansowane, wśród nich paradygmaty projektowania algorytmów i teorię grafów.

W tej książce między innymi:

• definiowanie algorytmu i złożoność algorytmiczna
• struktury danych i ich implementacje
• algorytmy sortowania i wyszukiwania wzorca w tekście
• paradygmaty projektowania algorytmów
• grafy i sposoby ich reprezentacji w programach komputerowych
• grafy jako moduły do budowy złożonych algorytmów

Algorytm i struktura danych: tak działa optymalny kod!

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