James Cutajar jest programistą specjalizującym się w skalowalnych obliczeniach o wysokiej wydajności oraz w algorytmach rozproszonych. Pisze książki, bierze udział w projektach rozwoju otwartego oprogramowania, bloguje i zajmuje się marketingiem technologii.
Spis treści
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
