Zaprzyjaźnij się z algorytmami

Zaprzyjaźnij się z algorytmami. Przewodnik dla początkujących i średniozaawansowanych zawiera opis podstawowych i najważniejszych technik algorytmicznych i struktur danych, które zostały uporządkowane w osiemnastu rozdziałach. Do każdego tematu wyselekcjonowano zadania o zróżnicowanym poziomie trudności odpowiednie zarówno dla początkujących, jak i bardziej zaawansowanych uczniów. Książka jest również doskonałym materiałem dydaktycznym dla nauczycieli szkół gimnazjalnych i ponadgimnazjalnych.

Spis treści

Wprowadzenie XI Od autora XIII 1. Złożonosć czasowa 1 Porównanie różnych złożonosci czasowych 2 Limit czasu 3 Złożonosć pamięciowa 4 Ćwiczenie 4 Zadania treningowe 5 Żabka ? 5 Chodnik ? ? 6 Tasma ? ? 7 Rozwiązania 8 2. Zliczanie elementów 9 Ćwiczenie 10 Zadania treningowe 11 Permutacja ? 11 Ropucha ? ? 12 Przyciski ? 13 Rozwiązania 14 3. Sumy prefiksowe 16 Ćwiczenie 17 Zadania treningowe 18 Długa tasma 18 Samochody ? ? 19 Chomiki ? ? ? 20 Rozwiązania 21 4. Sortowanie 22 Sposób 1: sortowanie przez wybieranie 22 Sposób 2: sortowanie przez zliczanie 23 Sposób 3: sortowanie przez scalanie 24 Funkcje sortujące 24 Ćwiczenie 25 Zadania treningowe 25 Iloczyn ? 25 Gwozdzie ? ? 26 Tory kolejowe ? ? ? 27 Rozwiązania 28 5. Stos i kolejka 30 Stos 30 Kolejka 31 Ćwiczenie 32 Zadania treningowe 32 Nawiasy ? ? 32 Ryby ? ? ? 33 Cukiernia ? ? ? 34 Rozwiązania 35 6. Wyszukiwanie lidera 37 Sprawdzenie kandydata 37 Rozwiązanie o złożonosci O(n2) 38 Rozwiązanie o złożonosci O(n log n) 38 Rozwiązanie o złożonosci O(n) 39 Ćwiczenie 40 Zadania treningowe 41 Dwie częsci ? ? 41 Bajtocka flaga ? ? ? 42 Lider prefiksowy ? ? ? 43 Rozwiązania 44 7. Spójny podciąg o maksymalnej sumie 45 Rozwiązanie o złożonosci O(n3) 45 Rozwiązanie o złożonosci O(n2) 46 Rozwiązanie o złożonosci O(n) 46 Ćwiczenie 47 Zadania treningowe 49 Odchudzanie ? 49 Bilet ? ? 49 Praca domowa ? ? ? 51 Rozwiązania 51 8. Liczby pierwsze i złożone 53 Liczenie dzielników 53 Test pierwszosci w czasie O(?n) 54 Ćwiczenie 54 Zadania treningowe 56 Obwód ? 56 Szczyty ? ? 56 Flagi ? ? ? ? 57 Rozwiązania 58 9. Sito Eratostenesa 61 Faktoryzacja 62 Ćwiczenie 63 Zadania treningowe 64 Tablica liczb ? ? 64 Liczby półpierwsze ? ? ? 64 Liczby doskonałe ? ? ? 65 Rozwiązania 66 10. Algorytm Euklidesa 68 Najmniejsza wspólna wielokrotnosć 69 Ćwiczenie 69 Zadania treningowe 69 Mandarynki ? 69 Wesoła małpka ? ? 70 Zbiór pierwszych ? ? ? 71 Rozwiązania 72 11. Ciąg Fibonacciego 73 Ćwiczenie 74 Zadania treningowe 74 Zajączek ? ? 74 Drabina ? ? ? 75 Spotkanie ? ? ? ? 76 Rozwiązania 77 12. Wyszukiwanie binarne 79 Intuicja 79 Implementacja 80 Wyszukiwanie binarne po wyniku 81 Ćwiczenie 81 Zadania treningowe 82 Promień ? ? 82 Deski ? ? ? 82 Tort ? ? ? ? 83 Rozwiązania 85 13. Gąsienica 87 Przykład użycia 87 Ćwiczenie 88 Zadania treningowe 89 Smakołyki ? ? 89 Wycinek ? ? ? 90 Temperatura ? ? ? ? 90 Rozwiązania 92 14. Programowanie zachłanne 94 Problem wydawania reszty 94 Dowodzenie poprawnosci 95 Ćwiczenie 95 Zadania treningowe 96 Sznurki ? ? 96 Bracia ? ? ? 97 Szklanki ? ? ? 98 Rozwiązania 99 15. Programowanie dynamiczne 101 Problem wydawania reszty 101 Ćwiczenie 103 Zadania treningowe 104 Pionek ? 104 Wybrzeże ? ? ? 105 Ładny ciąg ? ? ? 106 Rozwiązania 107 16. Drzewa binarne 110 Pełne drzewo binarne 111 Reprezentacja drzew binarnych 111 Binarne drzewa wyszukiwania (BST) 112 Ćwiczenie 112 Zadania treningowe 113 Drzewko binarne ? 113 Nieskończone drzewko ? ? 114 Drzewko ? ? ? 115 Rozwiązania 116 17. Kolejka priorytetowa 119 Kopiec binarny 119 Wstawienie elementu do kopca O(log n) 120 Usunięcie elementu maksymalnego O(log n) 121 Tworzenie nowego kopca z listy elementów O(n) 122 Ćwiczenie 123 Zadania treningowe 124 Emeryci ? ? 124 Bilety ? ? ? 124 Tamy ? ? ? ? 125 Rozwiązania 127 18. Algorytmy grafowe BFS i DFS 128 Rodzaje grafów 129 Reprezentacja grafu 130 DFS, czyli przeszukiwanie grafu w głąb 132 BFS, czyli przeszukiwanie grafu wszerz 133 Ćwiczenie 134 Zadania treningowe 134 Lista kontaktów ? ? 134 Las ? ? ? 135 Wyprawa króla ? ? ? ? 136 Rozwiązania 137 A. Kolejne tematy 139 Algorytm Dijkstry 139 Srednica drzewa 139 Zbiory rozłączne 139 Algorytm Prima i Kruskala 139 Sortowanie topologiczne 140 Drzewo licznikowe 140 Szybkie potęgowanie 140 Koszt zamortyzowany 140 Najdłuższy rosnący podciąg 140 Teoria gier 140 Algorytm Knutha–Morrisa–Pratta 141 Haszowanie tekstów 141 Algorytm Karpa–Millera–Rosenberga 141 Szukanie palindromów i algorytm Manachera 141 Najdłuższy wspólny podciąg 141 Programowanie dynamiczne na drzewach 141 Podstawy geometrii obliczeniowej 142 Sortowanie kątowe 142 Otoczka wypukła 142 Para najmniej i najbardziej oddalonych punktów 142 Maski bitowe 142 Najniższy wspólny przodek 142 Silnie spójne składowe 143 Mosty i punkty artykulacji 143 Cykl Eulera 143 Przepływy i skojarzenia 143 B. STL 144 Para elementów 144 Wektor 145 Kolejka 148 Kolejka priorytetowa 149 Minimum, maksimum i zamiana 150 Sortowanie 150 Permutacje 151 Mieszanie 152 Wskazniki w C++ 152 Iteratory 153 Wyszukiwanie binarne 154 Lista 154 Zbiór i multizbiór 155 Mapa 156 Bibliografia 157 Skorowidz 158 Opinie i komentarze 161