Algorytmy

[ Pobierz całość w formacie PDF ]
//-->Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całościlub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione.Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanieksiążki na nośniku filmowym, magnetycznym lub innym powoduje naruszeniepraw autorskich niniejszej publikacji.Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymibądź towarowymi ich właścicieli.Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawartew tej książce informacje były kompletne i rzetelne. Nie biorą jednakżadnejodpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualnenaruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELIONnie ponoszą równieżżadnejodpowiedzialności za ewentualne szkody wynikłez wykorzystania informacji zawartych w książce.Redaktor prowadzący: Michał MrowiecProjekt okładki: Aleksander KopiaFotografia na okładce została wykorzystana za zgodą Shutterstock.comWydawnictwo HELIONul. Kościuszki 1c, 44-100 GLIWICEtel. 32 231 22 19, 32 230 98 63e-mail:helion@helion.plWWW:(księgarnia internetowa, katalog książek)Drogi Czytelniku!Jeżeli chcesz ocenić tę książkę, zajrzyj pod adresalgor5_ebookMożesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.Kodyźródłowewybranych przykładów dostępne są pod adresem:ftp://ftp.helion.pl/przyklady/algor5.zipISBN:13: 978-83-283-2132-8Copyright © Helion 2015Poleć książkę na Facebook.comKup w wersji papierowejOceń książkęKsięgarnia internetowaLubię to!»Nasza społecznośćSpis treściPrzedmowa . .................................................................................... 9Co odróżnia tę książkę od innych podręczników? . ........................................................... 9Dlaczego C++? . ............................................................................................................... 10Jak należy czytać tę książkę? ........................................................................................... 11Co zostało opisane w tej książce? .................................................................................... 11Programy przykładowe .................................................................................................... 13Konwencje typograficzne i oznaczenia . .......................................................................... 14Uwagi do wydania V ....................................................................................................... 15Rozdział 1. Zanim wystartujemy . ..................................................................... 17Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych ................... 19Jak to się niedawno odbyło,czyli o tym, kto „wymyślił” metodologię programowania . .......................................... 23Proces koncepcji programów ........................................................................................... 24Poziomy abstrakcji opisu i wybór języka . ...................................................................... 25Poprawność algorytmów ................................................................................................. 26Zadania . ........................................................................................................................... 28Rozwiązania i wskazówki do zadań . .............................................................................. 28Rozdział 2. Rekurencja . .................................................................................. 31Definicja rekurencji ......................................................................................................... 31Ilustracja pojęcia rekurencji ............................................................................................. 33Jak wykonują się programy rekurencyjne? . .................................................................... 34Niebezpieczeństwa rekurencji ......................................................................................... 36Ciąg Fibonacciego ....................................................................................................... 36Stack overflow! ............................................................................................................ 38Pułapek ciąg dalszy ......................................................................................................... 39Stąd do wieczności ....................................................................................................... 40Definicja poprawna, ale… ........................................................................................... 40Typy programów rekurencyjnych .................................................................................... 41Myślenie rekurencyjne .................................................................................................... 43Przykład 1.: Spirala ...................................................................................................... 44Przykład 2.: Kwadraty „parzyste” . .............................................................................. 45Uwagi praktyczne na temat technik rekurencyjnych . ..................................................... 46Zadania . ........................................................................................................................... 47Rozwiązania i wskazówki do zadań . .............................................................................. 504Algorytmy, struktury danych i techniki programowaniaRozdział 3. Typy i struktury danych . ................................................................ 55Typy podstawowe i złożone ............................................................................................ 56Tablice . ............................................................................................................................ 57Ciągi znaków i napisy w C++ .......................................................................................... 58Typy złożone . .................................................................................................................. 60Struktury i wprowadzenie pojęcia referencji . ............................................................. 60Klasy i programowanie obiektowe . ............................................................................ 62Abstrakcyjne struktury danych ........................................................................................ 63Listy jednokierunkowe ................................................................................................ 64Tablicowa implementacja list ...................................................................................... 84Stos . ............................................................................................................................. 89Kolejki FIFO ................................................................................................................ 93Sterty i kolejki priorytetowe ........................................................................................ 96Drzewa i ich reprezentacje ......................................................................................... 101Zbiory . ....................................................................................................................... 113STL, czyli struktury danych dla leniuchów . ................................................................. 115Klasyczne kontenery sekwencyjne . .......................................................................... 116Adaptery (nakładki na inne kontenery) . .................................................................... 120Kontenery asocjacyjne ............................................................................................... 121Algorytmy w STL ...................................................................................................... 122Dalsze materiały na temat STL . ................................................................................ 123Zadania . ......................................................................................................................... 123Rozwiązania zadań ........................................................................................................ 124Rozdział 4. Analiza złożoności algorytmów . .................................................... 125Definicje i przykłady ..................................................................................................... 126Jeszcze raz funkcja silnia ........................................................................................... 129Zerowanie fragmentu tablicy ..................................................................................... 133Wpadamy w pułapkę ................................................................................................. 134Różne typy złożoności obliczeniowej . ...................................................................... 136Nowe zadanie: uprościć obliczenia! . ............................................................................ 137Analiza programów rekurencyjnych . ............................................................................ 138Terminologia i definicje ............................................................................................. 138Ilustracja metody na przykładzie . ............................................................................. 140Rozkład logarytmiczny .............................................................................................. 140Zamiana dziedziny równania rekurencyjnego . .......................................................... 142Funkcja Ackermanna, czyli coś dla smakoszy . ......................................................... 143Złożoność obliczeniowa to nie religia! . ........................................................................ 144Techniki optymalizacji programów . ............................................................................. 144Zadania . ......................................................................................................................... 145Rozwiązania i wskazówki do zadań . ............................................................................ 146Jak pracuje kompilator? ................................................................................................. 150Odrobina formalizmu nie zaszkodzi! . ........................................................................... 151Kilka przykładów derekursywacji algorytmów . ........................................................... 153Derekursywacja z wykorzystaniem stosu . .................................................................... 156Eliminacja zmiennych lokalnych . ............................................................................. 156Metoda funkcji przeciwnych ......................................................................................... 158Klasyczne schematy derekursywacji . ........................................................................... 160Schemat typu while .................................................................................................... 160Schemat typu if-else ................................................................................................... 161Schemat z podwójnym wywołaniem rekurencyjnym . ............................................... 163Podsumowanie ............................................................................................................... 165Rozdział 5. Derekursywacja i optymalizacja algorytmów . ................................ 149Spis treści5Rozdział 6. Algorytmy sortowania . ................................................................. 167Sortowanie przez wstawianie, algorytm klasy O(N2) . .................................................. 168Sortowanie bąbelkowe, algorytm klasy O(N2) . ............................................................ 169Quicksort, algorytm klasy O(N log N) . ........................................................................ 171Heap Sort — sortowanie przez kopcowanie . ................................................................ 174Scalanie zbiorów posortowanych . ................................................................................ 176Sortowanie przez scalanie, algorytm klasy O(N log N) . ............................................... 176Sortowanie zewnętrzne .................................................................................................. 178Uwagi praktyczne .......................................................................................................... 181Rozdział 7. Algorytmy przeszukiwania . ........................................................... 183Przeszukiwanie liniowe ................................................................................................. 183Przeszukiwanie binarne ................................................................................................. 184Transformacja kluczowa (hashing) . .............................................................................. 185W poszukiwaniu funkcji H ........................................................................................ 187Najbardziej znane funkcje H ...................................................................................... 188Obsługa konfliktów dostępu ...................................................................................... 190Powrót doźródeł........................................................................................................ 190Jeszcze raz tablice! ..................................................................................................... 191Próbkowanie liniowe ................................................................................................. 192Podwójne kluczowanie .............................................................................................. 193Zastosowania transformacji kluczowej . .................................................................... 195Podsumowanie metod transformacji kluczowej . ....................................................... 195Rozdział 8. Przeszukiwanie tekstów . ............................................................. 197Algorytm typu brute-force ............................................................................................. 197Nowe algorytmy poszukiwań ........................................................................................ 199Algorytm K-M-P ....................................................................................................... 200Algorytm Boyera i Moore’a ....................................................................................... 203Algorytm Rabina i Karpa ........................................................................................... 205Rozdział 9. Zaawansowane techniki programowania . ..................................... 209Programowanie typu „dziel i zwyciężaj” . ..................................................................... 210Odszukiwanie minimum i maksimum w tablicy liczb . ............................................. 211Mnożenie macierzy o rozmiarze N×N . ..................................................................... 213Mnożenie liczb całkowitych ...................................................................................... 216Inne znane algorytmy „dziel i zwyciężaj” . ................................................................ 217Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas… ................................. 217Problem plecakowy, czyli niełatwe jestżycieturysty piechura ................................ 218Wydawanie reszty, czyli „A nie ma pan drobnych?” w praktyce . ............................ 220Programowanie dynamiczne .......................................................................................... 221Ciąg Fibonacciego ..................................................................................................... 223Równania z wieloma zmiennymi . ............................................................................. 223Najdłuższa wspólna podsekwencja . .......................................................................... 225Inne techniki programowania ........................................................................................ 227Uwagi bibliograficzne ................................................................................................... 230Rozdział 10. Elementy algorytmiki grafów . ....................................................... 231Definicje i pojęcia podstawowe ..................................................................................... 232Cykle w grafach ............................................................................................................. 234Sposoby reprezentacji grafów ........................................................................................ 237Reprezentacja tablicowa ............................................................................................ 237Słowniki węzłów ....................................................................................................... 239Listy kontra zbiory ..................................................................................................... 240 [ Pobierz całość w formacie PDF ]