Algorytmy, struktury danych i techniki programowania dla programistów Java

Opanuj Javę jak prawdziwy profesjonalista! Podstawy algorytmiki dla praktyków Modelowanie struktur danych w Javie Skuteczne techniki programowania na przykładach Java jest obecnie jednym z najpopularniejszych języków programowania, co zawdzięcza przede wszystkim swojej prostocie, nowoczesności, dużym możliwościom oraz niezależności od architektury platform sprzętowych i systemowych, na których mają pracować napisane w tym języku programy. Java znalazła zastosowanie w wielu różnych branżach - zdecydowanie dominuje w rozwiązaniach działających w sieci, stanowiących obecnie dużą część oprogramowania tworzonego komercyjnie. Mimo to dotychczas trudno było znaleźć rzetelne źródło wiedzy o algorytmach, które byłoby przeznaczone dla użytkowników Javy, wyjaśniało zasady modelowania danych w tym języku i pozwalało szybko testować gotowe programy. Na szczęście to już przeszłość! Książka Algorytmy, struktury danych i techniki programowania dla programistów Java jest pierwszą poważną pozycją przybliżającą tematykę algorytmów osobom posługującym się tym językiem. W prosty i praktyczny sposób przedstawia najważniejsze zagadnienia algorytmiki, pozwala poznać struktury danych i ich zastosowania, prezentuje popularne algorytmy oraz problemy, które można za ich pomocą rozwiązać, omawia także techniki programowania wykorzystywane przez miliony specjalistów w ich codziennej pracy. Jeśli chcesz być profesjonalnym programistą Javy, nie mogłeś trafić lepiej! Podstawy algorytmiki i kodowania liczb Algorytmy rekurencyjne i iteracyjne Analiza złożoności i optymalizacja algorytmów Modelowanie i wykorzystanie struktur danych Wykorzystanie biblioteki java.util Przeszukiwanie i sortowanie danych Przegląd technik programowania Algorytmy grafowe i numeryczne Kodowanie i kompresja danych Wprowadzenie do języka Java i narzędzi JDK Rozwiązuj problemy programistyczne w Javie! Spis treści 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 Tablicowa implementacja list Listy innych typów 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 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! 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-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×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ą Lagrange’a Różniczkowanie funkcji Całkowanie funkcji metodą Simpsona Rozwiązywanie układów równań liniowych metodą Gaussa 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