E-book details

Algorytmy, struktury danych i techniki programowania. Wydanie V

Algorytmy, struktury danych i techniki programowania. Wydanie V

Piotr Wróblewski

Ebook
  • Wprowadzenie do algorytmiki
  • Tylko niezbędna teoria
  • Gotowe rozwiązania w C++
Oto kolejne wydanie sprawdzonej, cenionej przez programistów, wykładowców oraz studentów książki, będącej podstawowym podręcznikiem do nauki algorytmiki. Jej autor zapozna Cię z elementarnymi zagadnieniami z tej dziedziny oraz wyjaśni, skąd bierze się tak szybki postęp w tej dyscyplinie nauki. Poznasz podstawowe struktury danych używane do rozwiązywania problemów algorytmicznych oraz nauczysz się je projektować w C++ z użyciem technik obiektowych i klas parametryzowanych.

Podczas dalszej lektury poznasz takie pojęcia, jak rekurencja, analiza złożoności oraz algorytmy sortowania i przeszukiwania czy algorytmy numeryczne. Opanujesz metody optymalizacji algorytmów, sposoby kodowania i kompresji danych oraz elementy algorytmiki grafów. Przedstawione tu algorytmy są zilustrowane gotowymi kodami źródłowymi w C++ , co ułatwia zrozumienie poznawanych zagadnień. Przejrzysta forma, praktyczne przykłady oraz przystępny język sprawiają, że książka pozwala szybko i bez trudu opanować zarówno algorytmy, jak i struktury danych oraz najlepsze techniki programowania.
  • Historia algorytmiki
  • Struktury danych i ich implementacja
  • Wprowadzenie do bibliotek STL, czyli algorytmy i struktury danych dla „leniuchów”
  • Analiza złożoności algorytmów
  • Wykorzystanie rekurencji i optymalizacja algorytmów
  • Algorytmy sortowania i przeszukiwania
  • Przeszukiwanie tekstów
  • Zaawansowane techniki programowania
  • Wykorzystanie grafów
  • Algorytmy numeryczne
  • Wprowadzenie do sztucznej inteligencji
  • Kodowanie i kompresja danych
  • Błyskawiczny kurs C++ z uwzględnieniem programowania obiektowego
  • Poradnik kompilacji i uruchamiania programów konsolowych oraz graficznych w darmowych środowiskach IDE (GCC/Dev-C++, Microsoft Visual C++ z pakietu Visual Studio).

Szybko i bezboleśnie opanuj wszystkie zagadnienia algorytmiki!

Przedmowa (9)

  • Co odróżnia tę książkę od innych podręczników? (9)
  • Dlaczego C++? (10)
  • Jak należy czytać tę książkę? (11)
  • Co zostało opisane w tej książce? (11)
  • Programy przykładowe (13)
  • Konwencje typograficzne i oznaczenia (14)
  • Uwagi do wydania V (15)

Rozdział 1. Zanim wystartujemy (17)

  • Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych (19)
  • Jak to się niedawno odbyło, czyli o tym, kto "wymyślił" metodologię programowania (23)
  • Proces koncepcji programów (24)
  • Poziomy abstrakcji opisu i wybór języka (25)
  • Poprawność algorytmów (26)
  • Zadania (28)
  • Rozwiązania i wskazówki do zadań (28)

Rozdział 2. Rekurencja (31)

  • Definicja rekurencji (31)
  • Ilustracja pojęcia rekurencji (33)
  • Jak wykonują się programy rekurencyjne? (34)
  • Niebezpieczeństwa rekurencji (36)
    • Ciąg Fibonacciego (36)
    • Stack overflow! (38)
  • Pułapek ciąg dalszy (39)
    • Stąd do wieczności (40)
    • Definicja poprawna, ale... (40)
  • Typy programów rekurencyjnych (41)
  • Myślenie rekurencyjne (43)
    • Przykład 1.: Spirala (44)
    • Przykład 2.: Kwadraty "parzyste" (45)
  • Uwagi praktyczne na temat technik rekurencyjnych (46)
  • Zadania (47)
  • Rozwiązania i wskazówki do zadań (50)

Rozdział 3. Typy i struktury danych (55)

  • Typy podstawowe i złożone (56)
  • Tablice (57)
  • Ciągi znaków i napisy w C++ (58)
  • Typy złożone (60)
    • Struktury i wprowadzenie pojęcia referencji (60)
    • Klasy i programowanie obiektowe (62)
  • Abstrakcyjne struktury danych (63)
    • Listy jednokierunkowe (64)
    • Tablicowa implementacja list (84)
    • Stos (89)
    • Kolejki FIFO (93)
    • Sterty i kolejki priorytetowe (96)
    • Drzewa i ich reprezentacje (101)
    • Zbiory (113)
  • STL, czyli struktury danych dla leniuchów (115)
    • Klasyczne kontenery sekwencyjne (116)
    • Adaptery (nakładki na inne kontenery) (120)
    • Kontenery asocjacyjne (121)
    • Algorytmy w STL (122)
    • Dalsze materiały na temat STL (123)
  • Zadania (123)
  • Rozwiązania zadań (124)

Rozdział 4. Analiza złożoności algorytmów (125)

  • Definicje i przykłady (126)
    • Jeszcze raz funkcja silnia (129)
    • Zerowanie fragmentu tablicy (133)
    • Wpadamy w pułapkę (134)
    • Różne typy złożoności obliczeniowej (136)
  • Nowe zadanie: uprościć obliczenia! (137)
  • Analiza programów rekurencyjnych (138)
    • Terminologia i definicje (138)
    • Ilustracja metody na przykładzie (140)
    • Rozkład logarytmiczny (140)
    • Zamiana dziedziny równania rekurencyjnego (142)
    • Funkcja Ackermanna, czyli coś dla smakoszy (143)
  • Złożoność obliczeniowa to nie religia! (144)
  • Techniki optymalizacji programów (144)
  • Zadania (145)
  • Rozwiązania i wskazówki do zadań (146)

Rozdział 5. Derekursywacja i optymalizacja algorytmów (149)

  • Jak pracuje kompilator? (150)
  • Odrobina formalizmu nie zaszkodzi! (151)
  • Kilka przykładów derekursywacji algorytmów (153)
  • Derekursywacja z wykorzystaniem stosu (156)
    • Eliminacja zmiennych lokalnych (156)
  • Metoda funkcji przeciwnych (158)
  • Klasyczne schematy derekursywacji (160)
    • Schemat typu while (160)
    • Schemat typu if-else (161)
    • Schemat z podwójnym wywołaniem rekurencyjnym (163)
  • Podsumowanie (165)

Rozdział 6. Algorytmy sortowania (167)

  • Sortowanie przez wstawianie, algorytm klasy O(N2) (168)
  • Sortowanie bąbelkowe, algorytm klasy O(N2) (169)
  • Quicksort, algorytm klasy O(N log N) (171)
  • Heap Sort - sortowanie przez kopcowanie (174)
  • Scalanie zbiorów posortowanych (176)
  • Sortowanie przez scalanie, algorytm klasy O(N log N) (176)
  • Sortowanie zewnętrzne (178)
  • Uwagi praktyczne (181)

Rozdział 7. Algorytmy przeszukiwania (183)

  • Przeszukiwanie liniowe (183)
  • Przeszukiwanie binarne (184)
  • Transformacja kluczowa (hashing) (185)
    • W poszukiwaniu funkcji H (187)
    • Najbardziej znane funkcje H (188)
    • Obsługa konfliktów dostępu (190)
    • Powrót do źródeł (190)
    • Jeszcze raz tablice! (191)
    • Próbkowanie liniowe (192)
    • Podwójne kluczowanie (193)
    • Zastosowania transformacji kluczowej (195)
    • Podsumowanie metod transformacji kluczowej (195)

Rozdział 8. Przeszukiwanie tekstów (197)

  • Algorytm typu brute-force (197)
  • Nowe algorytmy poszukiwań (199)
    • Algorytm K-M-P (200)
    • Algorytm Boyera i Moore'a (203)
    • Algorytm Rabina i Karpa (205)

Rozdział 9. Zaawansowane techniki programowania (209)

  • Programowanie typu "dziel i zwyciężaj" (210)
    • Odszukiwanie minimum i maksimum w tablicy liczb (211)
    • Mnożenie macierzy o rozmiarze N(N (213)
    • Mnożenie liczb całkowitych (216)
    • Inne znane algorytmy "dziel i zwyciężaj" (217)
  • Algorytmy "żarłoczne", czyli przekąsić coś nadszedł już czas... (217)
    • Problem plecakowy, czyli niełatwe jest życie turysty piechura (218)
    • Wydawanie reszty, czyli "A nie ma pan drobnych?" w praktyce (220)
  • Programowanie dynamiczne (221)
    • Ciąg Fibonacciego (223)
    • Równania z wieloma zmiennymi (223)
    • Najdłuższa wspólna podsekwencja (225)
  • Inne techniki programowania (227)
  • Uwagi bibliograficzne (230)

Rozdział 10. Elementy algorytmiki grafów (231)

  • Definicje i pojęcia podstawowe (232)
  • Cykle w grafach (234)
  • Sposoby reprezentacji grafów (237)
    • Reprezentacja tablicowa (237)
    • Słowniki węzłów (239)
    • Listy kontra zbiory (240)
  • Podstawowe operacje na grafach (240)
    • Suma grafów (240)
    • Kompozycja grafów (240)
    • Graf do potęgi (241)
  • Algorytm Roya-Warshalla (242)
  • Algorytm Floyda-Warshalla (245)
  • Algorytm Dijkstry (248)
  • Algorytm Bellmana-Forda (249)
  • Drzewo rozpinające minimalne (249)
    • Algorytm Kruskala (250)
    • Algorytm Prima (251)
  • Przeszukiwanie grafów (251)
    • Strategia "w głąb" (przeszukiwanie zstępujące) (252)
    • Strategia "wszerz" (253)
    • Inne strategie przeszukiwania (255)
  • Problem właściwego doboru (255)
  • Podsumowanie (259)
  • Zadania (259)

Rozdział 11. Algorytmy numeryczne (261)

  • Poszukiwanie miejsc zerowych funkcji (261)
  • Iteracyjne obliczanie wartości funkcji (263)
  • Interpolacja funkcji metodą Lagrange'a (264)
  • Różniczkowanie funkcji (265)
  • Całkowanie funkcji metodą Simpsona (267)
  • Rozwiązywanie układów równań liniowych metodą Gaussa (268)
  • Uwagi końcowe (271)

Rozdział 12. Czy komputery mogą myśleć? (273)

  • Przegląd obszarów zainteresowań sztucznej inteligencji (SI) (274)
    • Systemy eksperckie (275)
    • Sieci neuronowe (276)
  • Reprezentacja problemów (278)
  • Gry dwuosobowe i drzewa gier (279)
  • Algorytm mini-max (280)

Rozdział 13. Kodowanie i kompresja danych (285)

  • Kodowanie danych i arytmetyka dużych liczb (287)
    • Kodowanie symetryczne (287)
    • Kodowanie asymetryczne (288)
    • Metody prymitywne (293)
    • Łamanie szyfrów (295)
  • Techniki kompresji danych (295)
    • Kompresja za pomocą modelowania matematycznego (297)
    • Kompresja metodą RLE (298)
    • Kompresja danych metodą Huffmana (299)
    • Kodowanie LZW (303)
    • Idea kodowania słownikowego na przykładach (304)
    • Opis formatu GIF (306)

Rozdział 14. Zadania różne (309)

  • Teksty zadań (309)
  • Rozwiązania (311)

Dodatek A. Poznaj C++ w pięć minut! (315)

  • Elementy języka C++ na przykładach (315)
    • Pierwszy program (315)
    • Dyrektywa #include (316)
  • Podprogramy (316)
    • Procedury (316)
    • Funkcje (317)
  • Operacje arytmetyczne (318)
    • Operacje logiczne (318)
    • Wskaźniki i zmienne dynamiczne (319)
  • Referencje (320)
  • Typy złożone (320)
    • Tablice (321)
    • Rekordy (321)
    • Instrukcja switch (322)
  • Iteracje (322)
  • Struktury rekurencyjne (323)
  • Parametry programu main() (323)
  • Operacje na plikach w C++ (323)
  • Programowanie obiektowe w C++ (324)
    • Terminologia (325)
    • Obiekty na przykładzie (326)
    • Składowe statyczne klas (328)
    • Metody stałe klas (329)
    • Dziedziczenie własności (329)
  • Kod warunkowy w C++ (331)

Dodatek B. Systemy obliczeniowe w pigułce (333)

  • System dziesiętny i kilka definicji (333)
  • System dwójkowy (334)
    • Operacje arytmetyczne na liczbach dwójkowych (335)
    • Operacje logiczne na liczbach dwójkowych (336)
  • System ósemkowy (337)
  • System szesnastkowy (337)
  • Zmienne w pamięci komputera (338)
  • Kodowanie znaków (339[x1])

Dodatek C. Kompilowanie programów przykładowych (341)

  • Zawartość archiwum ZIP na ftp (341)
  • Darmowe kompilatory C++ (342)
    • GNU C Compiler (342)
    • Microsoft Visual Studio Community (344)
    • Dev-C++ (Orwell) (345)
  • Kompilacja i uruchamianie programów w C++ (345)
    • GCC (346)
    • Microsoft Visual Studio (347)
    • Dev-C++ (352)

Literatura (355)

Spis tabel (357)

Spis ilustracji (359)

Skorowidz (365)

  • Title: Algorytmy, struktury danych i techniki programowania. Wydanie V
  • Author: Piotr Wróblewski
  • ISBN: 978-83-283-2132-8, 9788328321328
  • Date of issue: 2015-09-07
  • Format: Ebook
  • Item ID: algor5
  • Publisher: Helion