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

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!

• Przedmowa
  • Dlaczego Java?
  • Co odróżnia tę książkę od innych podręczników?
  • Jak należy czytać tę książkę?
  • Co zostało opisane w tej książce?
    • Rozdział 1. Zanim wystartujemy
    • Rozdział 2. Systemy obliczeniowe i podstawy kodowania
    • Rozdział 3. Rekurencja
    • Rozdział 4. Analiza złożoności algorytmów
    • Rozdział 5. Podstawy modelowania danych
    • Rozdział 6. Modelowanie abstrakcyjnych typów danych
    • Rozdział 7. Struktury danych o dostępie ograniczonym
    • Rozdział 8. Drzewa i zbiory
    • Rozdział 9. java.util, czyli struktury danych dla leniuchów
    • Rozdział 10. Algorytmy przeszukiwania
    • Rozdział 11. Algorytmy sortowania
    • Rozdział 12. Derekursywacja i optymalizacja algorytmów
    • Rozdział 13. Przeszukiwanie tekstów
    • Rozdział 14. Zaawansowane techniki programowania
    • Rozdział 15. Algorytmy grafowe
    • Rozdział 16. Algorytmy numeryczne
    • Rozdział 17. Kodowanie i kompresja danych
    • Rozdział 18. Czy komputery mogą myśleć?
    • Rozdział 19. Zadania różne
    • Dodatek A
  • Programy przykładowe
  • Konwencje typograficzne i oznaczenia
• 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
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
  • Rozwiązania i wskazówki do zadań
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
• 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)
      • Przykład wyliczania liczby dziesiętnej w U2:
      • Przykład wyliczania liczby przeciwnej w U2:
  • 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!
      • Ćwiczenie 3.1.
      • Ćwiczenie 3.2.
  • 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
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
      • Pytanie 1.
      • Pytanie 2.
    • Zadanie 4.
    • Zadanie 5.
    • Zadanie 6.
  • Rozwiązania i wskazówki do zadań
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
    • Zadanie 4.
    • Zadanie 5.
    • Zadanie 6.
• 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
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
    • Zadanie 4.
  • Rozwiązania i wskazówki do zadań
    • Zadanie 2.
    • Zadanie 4.
• 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
    • Zadanie 1.
  • Rozwiązania i wskazówki do zadań
    • Zadanie 1.
• 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
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
    • Zadanie 4.
  • Rozwiązania zadań
    • Zadanie 1.
• 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
      • Ćwiczenie 1.
    • 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
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
    • Zadanie 4.
• 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
      • FAZA REDUKCJI (kierunek: w dół)
      • FAZA KONSTRUKCJI KODU (kierunek: w górę)
    • Kodowanie LZW
      • Przykład kodowania LZW
      • Przykład dekodowania LZW
      • Praktyczne użycie LZW w formacie GIF
• Rozdział 18. Czy komputery mogą myśleć?
  • Przegląd obszarów zainteresowań sztucznej inteligencji (SI)
    • Systemy eksperckie
    • Sieci neuronowe
  • Reprezentacja problemów
    • Przykład 1.
    • Przykład 2.
    • Ćwiczenie 1.
  • Gry dwuosobowe i drzewa gier
    • Algorytm min-max
• Rozdział 19. Zadania różne
  • Teksty zadań
    • Zadanie 1.
    • Zadanie 2.
    • Zadanie 3.
    • Zadanie 4.
    • Zadanie 5.
    • Zadanie 6.
    • Zadanie 7.
    • Zadanie 8.
    • Zadanie 9.
    • Zadanie 10.
    • Zadanie 11.
    • Zadanie 12.
  • Rozwiązania
    • Zadanie 1.
    • Zadanie 3.
    • Zadanie 4.
    • Zadanie 10.
    • Zadanie 11.
• 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
      • Instrukcja if else
      • Instrukcja wyboru (switch)
      • Iteracje
        • Pętla for
        • Pętle while
    • Konwersje typów i wprowadzanie danych
    • Operacje na plikach w Javie
    • Funkcje matematyczne w Javie
• Literatura
• Spis rysunków
• Spis tabel