Rozdział 1. Zanim wystartujemy Czym powinien się charakteryzować algorytm? Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych —1804— —1830 i później— —1890— —lata 30. XX w. —lata 40. XX w. — —okres powojenny — —1969— —teraz— Jak to się niedawno odbyło, czyli o tym, kto „wymyślił" metodologię programowania Proces koncepcji programów Poziomy abstrakcji opisu i wybór języka Modelowanie działania algorytmów (maszyna Turinga) Poprawność algorytmów Rozdział 2. Systemy obliczeniowe i podstawy kodowania System dziesiętny i kilka definicji System dwójkowy Operacje arytmetyczne na liczbach dwójkowych Operacje logiczne na liczbach dwójkowych Kod BCD System ósemkowy System szesnastkowy Kodowanie liczb ze znakiem Kod znak-moduł (ZM) Kod U2 (system uzupełnienia dwójkowego) Zmienne w pamięci komputera Kodowanie znaków Kodowanie obrazów Mapy bitowe na przykładzie formatu BMP Rozdział 3. Rekurencja Definicja rekurencji Ilustracja pojęcia rekurencji Jak wykonują się programy rekurencyjne? Niebezpieczeństwa rekurencji Ciąg Fibonacciego Stack overflow! Pułapek ciąg dalszy Stąd do wieczności Definicja poprawna, ale Typy programów rekurencyjnych Myślenie rekurencyjne Przykład 1. Spirala Przykład 2. Kwadraty „parzyste" Uwagi praktyczne na temat technik rekurencyjnych Rozdział 4. Analiza złożoności algorytmów Jeszcze raz funkcja silnia Zerowanie fragmentu tablicy Wpadamy w pułapkę Różne typy złożoności obliczeniowej Nowe zadanie: uprościć obliczenia! Analiza programów rekurencyjnych Terminologia i definicje Ilustracja metody na przykładzie Rozkład logarytmiczny Przeszukiwanie binarne... tym razem bez matematyki wyższej! Zamiana dziedziny równania rekurencyjnego Funkcja Ackermanna, czyli coś dla smakoszy Złożoność obliczeniowa to nie religia! Techniki optymalizacji programów Rozdział 5. Podstawy modelowania danych Typy proste i złożone Operatory i zmienne Obiektowe typy proste, czyli klasy osłonowe Ciągi znaków i napisy Tablice Pojęcie referencji, czyli gdzie te wskaźniki z dawnych lat Programowanie obiektowe jako narzędzie modelowania danych i algorytmów Terminologia Modelowanie danych na przykładzie liczb zespolonych Pola i metody statyczne klas Dziedziczenie własności Struktury rekurencyjne w Javie Rozdział 6. Modelowanie abstrakcyjnych typów danych Abstrakcyjne typy danych Listy jednokierunkowe Tablicowa implementacja list Listy innych typów Listy z iteratorem Rozdział 7. Struktury danych o dostępie ograniczonym Stos Zasada działania stosu Realizacja programowa stosu Kolejki FIFO Sterty i kolejki priorytetowe Rozdział 8. Drzewa i zbiory Drzewa i ich reprezentacje Binarne drzewa poszukiwań (BST) Drzewa binarne i wyrażenia arytmetyczne Uniwersalna struktura słownikowa Drzewa „egzotyczne" Zbiory Rozdział 9. java.util, czyli struktury danych dla leniuchów ]ava i interfejsy Klasa Arrays, operacje na tablicach Klasa Vector, czyli tablice dynamiczne Listy Iteratory, czyli wygodne indeksowanie kolekcji Stos Sortowanie kolekcji Klasa HashSet, czyli szybko do celu Rozdział 10. Algorytmy przeszukiwania Przeszukiwanie liniowe Przeszukiwanie binarne Transformacja kluczowa (hashing) W poszukiwaniu funkcji H Najbardziej znane funkcje H Obsługa konfliktów dostępu Powrót do źródeł Jeszcze raz tablice! Próbkowanie liniowe Podwójne kluczowanie Zastosowania transformacji kluczowej Klasyczne funkcje C/C++ oraz Java Funkcje hashujące a klasy Javy Podsumowanie metod transformacji kluczowej Rozdział 11. Algorytmy sortowania Sortowanie przez wstawianie, algorytm klasy 0(N2) Sortowanie bąbelkowe, algorytm klasy 0(N2) Sortowanie szybkie (Quicksort) — algorytm klasy 0(N log N] Heapsort — sortowanie przez kopcowanie Scalanie zbiorów posortowanych Sortowanie przez scalanie, algorytm klasy 0(N log N) Sortowanie zewnętrzne Rozdział 12. Derekursywacja i optymalizacja algorytmów Jak pracuje kompilator? Odrobina formalizmu nie zaszkodzi! Kilka przykładów derekursywacji algorytmów Derekursywacja z wykorzystaniem stosu Eliminacja zmiennych lokalnych Metoda funkcji przeciwnych Klasyczne schematy derekursywacji Schemat typu while Schemat typu if-else Schemat z podwójnym wywołaniem rekurencyjnym Rozdział 13. Przeszukiwanie tekstów Algorytm typu brute force Nowe algorytmy poszukiwań Algorytm KMP Algorytm Boyera-Moore'a Algorytm Rabina-Karpa Rozdział 14. Zaawansowane techniki programowania Programowanie typu „dziel i zwyciężaj" Odszukiwanie minimum i maksimum w tablicy liczb Mnożenie macierzy o rozmiarze N>