ALGORYTMY STRUKTURY DANYCH I TECHNIKI PROGRAMOWANIA DLA PROGRAMISTÓW JAVA

Przedmowa

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
Zadania
Rozwiązania i wskazówki do zadań

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
Zadania
Rozwiązania i wskazówki do zadań

Rozdział 4. Analiza złożoności algorytmów
Definicje i przykłady
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
Zadania
Rozwiązania i wskazówki do zadań

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
Realizacja struktur danych listy jednokierunkowej
Proste dołączanie elementów do listy
Dołączanie elementów do listy z sortowaniem
Usuwanie danych z listy
Metody łączenia list
Sortowanie list za pomocą list referencji
Tablicowa implementacja list
Klasyczna reprezentacja tablicowa
Metoda tablic równoległych
Listy innych typów
Lista dwukierunkowa
Lista cykliczna
Listy z iteratorem
Podsumowanie

Rozdział 7. Struktury danych o dostępie ograniczonym
Stos
Zasada działania stosu
Realizacja programowa stosu
Kolejki FIFO
Sterty i kolejki priorytetowe
Zadania
Rozwiązania i wskazówki do zadań

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
Zadania
Rozwiązania zadań

Rozdział 9. java.util, czyli struktury danych dla leniuchów
Java 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
Suma modulo 2
Suma modulo Rmax
Mnożenie
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 O(N2)
Sortowanie bąbelkowe, algorytm klasy O(N2)
Sortowanie szybkie (Quicksort) algorytm klasy O(N log N)
Heapsort sortowanie przez kopcowanie
Scalanie zbiorów posortowanych
Sortowanie przez scalanie, algorytm klasy O(N log N)
Sortowanie zewnętrzne
Uwagi praktyczne

Rozdział 12. Derekursywacja i optymalizacja algorytmów
Jak pracuje kompilator?
Odrobina formalizmu nie zaszkodzi!
Przykład
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
Podsumowanie

Rozdział 13. Przeszukiwanie tekstów
Algorytm typu brute force
Nowe algorytmy poszukiwań
Algorytm KMP
Algorytm Boyera-Moorea
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?N
Mnożenie liczb całkowitych
Inne znane algorytmy dziel i zwyciężaj
Algorytmy żarłoczne, czyli przekąsić coś nadszedł już czas
Problem plecakowy, czyli niełatwe jest życie turysty piechura
Wydawanie reszty, czyli A nie ma pan drobnych? w praktyce
Programowanie dynamiczne
Ciąg Fibonacciego
Równania z wieloma zmiennymi
Najdłuższa wspólna podsekwencja
Najdłuższy wspólny podłańcuch
Heurystyczne techniki programowania
Uwagi bibliograficzne

Rozdział 15. Algorytmy grafowe
Definicje i pojęcia podstawowe
Etykiety i wartości
Cykle w grafach
Sposoby reprezentacji grafów
Reprezentacja tablicowa
Słowniki węzłów
Listy kontra zbiory
Podstawowe operacje na grafach
Suma grafów
Kompozycja grafów
Graf do potęgi
Algorytm Roya-Warshalla
Algorytm Floyda-Warshalla
Algorytm Dijkstry
Algorytm Bellmana-Forda
Drzewo rozpinające minimalne
Algorytm Kruskala
Algorytm Prima
Przeszukiwanie grafów
Strategia w głąb (przeszukiwanie zstępujące)
Strategia wszerz
Inne strategie przeszukiwania
Problem właściwego doboru
Podsumowanie
Zadania

Rozdział 16. Algorytmy numeryczne
Poszukiwanie miejsc zerowych funkcji
Iteracyjne obliczanie wartości funkcji
Interpolacja funkcji metodą Lagrangea
Różniczkowanie funkcji
Całkowanie funkcji metodą Simpsona
Biblioteki naukowe dla Javy
Uwagi końcowe

Rozdział 17. Kodowanie i kompresja danych
Kodowanie danych i arytmetyka dużych liczb
Metody prymitywne
Kodowanie symetryczne
Kodowanie asymetryczne
Obliczenia na bardzo dużych liczbach całkowitych
Klasa BigInteger
Łamanie kodów
Jakość klucza szyfrującego
Metody łamania szyfrów
Techniki kompresji danych
Kompresja za pomocą modelowania matematycznego
Kompresja metodą RLE
Kompresja danych metodą Huffmana
Kodowanie LZW

Rozdział 18. Czy komputery mogą myśleć?
Przegląd obszarów zainteresowań sztucznej inteligencji (SI)
Systemy eksperckie
Sieci neuronowe
Reprezentacja problemów
Gry dwuosobowe i drzewa gier
Algorytm min-max

Rozdział 19. Zadania różne
Teksty zadań
Rozwiązania

Dodatek A. Java szybki start
Instalacja środowiska Java
Środowiska IDE do Javy
Konfiguracja środowiska Java
Systemy pochodne UNIX (np. Linux)
System Windows
Kompilujemy program w Javie
Pakiety w Javie
Poznaj Javę w 5 minut!
Elementy języka Java na przykładach
Sterowanie przebiegiem programu
Konwersje typów i wprowadzanie danych
Operacje na plikach w Javie
Funkcje matematyczne w Javie

Literatura

Spis rysunków

Spis tabel

Skorowidz