Details zum E-Book

Algorytmy, struktury danych i techniki programowania. Wydanie IV

Algorytmy, struktury danych i techniki programowania. Wydanie IV

Piotr Wróblewski

E-book

Podstawowy podręcznik do nauki algorytmiki

  • Przystępne wprowadzenie do algorytmiki
  • Bez zbędnej teorii
  • Gotowe rozwiązania w C++

Oto kolejne wydanie sprawdzonej i cenionej przez programistów, wykładowców oraz studentów książki, będącej podstawowym podręcznikiem do nauki algorytmiki. W pierwszej kolejności autor zapozna Cię z elementarnymi zagadnieniami z tej dziedziny oraz wyjaśni, skąd bierze się tak szybki postęp w tej dyscyplinie nauki. Podczas dalszej lektury poznasz takie pojęcia, jak rekurencja, analiza złożoności oraz algorytmy sortowania i przeszukiwania czy algorytmy numeryczne. Szybko opanujesz metody optymalizacji algorytmów, sposoby kodowania i kompresji danych oraz elementy algorytmiki grafów. Przedstawione w książce algorytmy zilustrowane zostały przykładowymi kodami źródłowymi w C++ , ułatwiającymi zrozumienie poznawanych zagadnień. Przejrzysta forma, praktyczne przykłady oraz przystępny język sprawiają, że książka ta pozwala szybko, a także bezboleśnie opanować zarówno algorytmy, jak i struktury danych oraz najlepsze techniki programowania.

  • Historia algorytmiki
  • Wykorzystanie rekurencji
  • Analiza złożoności algorytmów
  • Algorytmy sortowania
  • Algorytmy przeszukiwania
  • Przeszukiwanie tekstów
  • Struktury danych i ich implementacja
  • Optymalizacja algorytmów
  • Zaawansowane techniki programowania
  • Wykorzystanie grafów
  • Wprowadzenie do sztucznej inteligencji
  • Kodowanie i kompresja danych
  • Algorytmy numeryczne
  • Poradnik kompilacji i uruchamiania programów (GCC, DevC++, Microsoft Visual C++ Express Edition).

Szybko i bezboleśnie opanuj wszystkie zagadnienia algorytmiki!

Przedmowa (9)

Rozdział 1. Zanim wystartujemy (17)

  • Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych (18)
  • Jak to się niedawno odbyło, czyli o tym, kto "wymyślił" metodologię programowania (21)
  • Proces koncepcji programów (22)
  • Poziomy abstrakcji opisu i wybór języka (23)
  • Poprawność algorytmów (24)

Rozdział 2. Rekurencja (27)

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

Rozdział 3. Analiza złożoności algorytmów (49)

  • Definicje i przykłady (50)
    • Jeszcze raz funkcja silnia (53)
    • Zerowanie fragmentu tablicy (57)
    • Wpadamy w pułapkę (58)
    • Różne typy złożoności obliczeniowej (59)
  • Nowe zadanie: uprościć obliczenia! (61)
  • Analiza programów rekurencyjnych (62)
    • Terminologia i definicje (62)
    • Ilustracja metody na przykładzie (63)
    • Rozkład logarytmiczny (64)
    • Zamiana dziedziny równania rekurencyjnego (66)
    • Funkcja Ackermanna, czyli coś dla smakoszy (66)
  • Złożoność obliczeniowa to nie religia! (68)
  • Techniki optymalizacji programów (68)
  • Zadania (69)
  • Rozwiązania i wskazówki do zadań (70)

Rozdział 4. Algorytmy sortowania (73)

  • Sortowanie przez wstawianie, algorytm klasy O(N2) (74)
  • Sortowanie bąbelkowe, algorytm klasy O(N2) (75)
  • Quicksort, algorytm klasy O(N log N) (77)
  • Heap Sort - sortowanie przez kopcowanie (80)
  • Scalanie zbiorów posortowanych (82)
  • Sortowanie przez scalanie (83)
  • Sortowanie zewnętrzne (84)
  • Uwagi praktyczne (87)

Rozdział 5. Typy i struktury danych (89)

  • Typy podstawowe i złożone (89)
  • Ciągi znaków i napisy w C++ (90)
  • Abstrakcyjne struktury danych (92)
    • Listy jednokierunkowe (93)
    • Tablicowa implementacja list (115)
    • Stos (119)
    • Kolejki FIFO (123)
    • Sterty i kolejki priorytetowe (125)
    • Drzewa i ich reprezentacje (131)
    • Zbiory (143)
    • Zadania (145)
    • Rozwiązania zadań (146)

Rozdział 6. Derekursywacja i optymalizacja algorytmów (147)

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

Rozdział 7. Algorytmy przeszukiwania (165)

  • Przeszukiwanie liniowe (165)
  • Przeszukiwanie binarne (166)
  • Transformacja kluczowa (hashing) (167)
    • W poszukiwaniu funkcji H (169)
    • Najbardziej znane funkcje H (169)
    • Obsługa konfliktów dostępu (171)
    • Powrót do źródeł (172)
    • Jeszcze raz tablice! (173)
    • Próbkowanie liniowe (173)
    • Podwójne kluczowanie (175)
    • Zastosowania transformacji kluczowej (176)
    • Podsumowanie metod transformacji kluczowej (176)

Rozdział 8. Przeszukiwanie tekstów (179)

  • Algorytm typu brute-force (179)
  • Nowe algorytmy poszukiwań (181)
    • Algorytm K-M-P (182)
    • Algorytm Boyera i Moore'a (185)
    • Algorytm Rabina i Karpa (187)

Rozdział 9. Zaawansowane techniki programowania (191)

  • Programowanie typu "dziel i zwyciężaj" (192)
    • Odszukiwanie minimum i maksimum w tablicy liczb (193)
    • Mnożenie macierzy o rozmiarze N(N (195)
    • Mnożenie liczb całkowitych (197)
    • Inne znane algorytmy "dziel i zwyciężaj" (198)
  • Algorytmy "żarłoczne", czyli przekąsić coś nadszedł już czas... (199)
    • Problem plecakowy, czyli niełatwe jest życie turysty piechura (200)
  • Programowanie dynamiczne (202)
    • Ciąg Fibonacciego (203)
    • Równania z wieloma zmiennymi (204)
    • Najdłuższa wspólna podsekwencja (205)
  • Inne techniki programowania (208)
  • Uwagi bibliograficzne (210)

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

  • Definicje i pojęcia podstawowe (212)
  • Cykle w grafach (214)
  • Sposoby reprezentacji grafów (217)
    • Reprezentacja tablicowa (217)
    • Słowniki węzłów (218)
    • Listy kontra zbiory (219)
  • Podstawowe operacje na grafach (220)
    • Suma grafów (220)
    • Kompozycja grafów (220)
    • Potęga grafu (220)
  • Algorytm Roy-Warshalla (221)
  • Algorytm Floyda-Warshalla (224)
  • Algorytm Dijkstry (227)
  • Algorytm Bellmana-Forda (228)
  • Drzewo rozpinające minimalne (228)
    • Algorytm Kruskala (229)
    • Algorytm Prima (230)
  • Przeszukiwanie grafów (230)
    • Strategia "w głąb" (przeszukiwanie zstępujące) (231)
    • Strategia "wszerz" (232)
    • Inne strategie przeszukiwania (234)
  • Problem właściwego doboru (235)
  • Podsumowanie (239)
  • Zadania (239)

Rozdział 11. Algorytmy numeryczne (241)

  • Poszukiwanie miejsc zerowych funkcji (241)
  • Iteracyjne obliczanie wartości funkcji (243)
  • Interpolacja funkcji metodą Lagrange'a (244)
  • Różniczkowanie funkcji (245)
  • Całkowanie funkcji metodą Simpsona (247)
  • Rozwiązywanie układów równań liniowych metodą Gaussa (248)
  • Uwagi końcowe (251)

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

  • Przegląd obszarów zainteresowań Sztucznej Inteligencji (254)
    • Systemy eksperckie (255)
    • Sieci neuronowe (256)
  • Reprezentacja problemów (257)
    • Ćwiczenie 1. (258)
  • Gry dwuosobowe i drzewa gier (259)
  • Algorytm mini-max (260)

Rozdział 13. Kodowanie i kompresja danych (265)

  • Kodowanie danych i arytmetyka dużych liczb (267)
    • Kodowanie symetryczne (267)
    • Kodowanie asymetryczne (268)
    • Metody prymitywne (274)
    • Łamanie szyfrów (275)
  • Techniki kompresji danych (275)
    • Kompresja poprzez modelowanie matematyczne (277)
    • Kompresja metodą RLE (278)
    • Kompresja danych metodą Huffmana (279)
    • Kodowanie LZW (283)
    • Idea kodowania słownikowego na przykładach (284)
    • Opis formatu GIF (286)

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

  • Teksty zadań (289)
  • Rozwiązania (291)

Dodatek A: Poznaj C++ w pięć minut! (295)

  • Elementy języka C++ na przykładach (295)
    • Pierwszy program (295)
    • Dyrektywa #include (296)
  • Podprogramy (296)
    • Procedury (296)
    • Funkcje (297)
  • Operacje arytmetyczne (298)
    • Operacje logiczne (298)
    • Wskaźniki i zmienne dynamiczne (299)
  • Referencje (300)
  • Typy złożone (300)
    • Tablice (300)
    • Rekordy (301)
    • Instrukcja switch (301)
  • Iteracje (302)
  • Struktury rekurencyjne (303)
  • Parametry programu main() (303)
  • Operacje na plikach w C++ (303)
  • Programowanie obiektowe w C++ (304)
    • Terminologia (304)
    • Obiekty na przykładzie (305)
    • Składowe statyczne klas (308)
    • Metody stałe klas (308)
    • Dziedziczenie własności (308)
  • Kod warunkowy w C++ (311)

Dodatek B: Systemy obliczeniowe w pigułce (313)

  • Kilka definicji (313)
  • System dwójkowy (313)
    • Operacje arytmetyczne na liczbach dwójkowych (315)
    • Operacje logiczne na liczbach dwójkowych (315)
  • System ósemkowy (317)
  • System szesnastkowy (317)
  • Zmienne w pamięci komputera (317)
  • Kodowanie znaków (318)

Dodatek C: Kompilowanie programów przykładowych (321)

  • Zawartość archiwum ZIP na ftp (321)
  • Darmowe kompilatory C++ (321)
  • Kompilacja i uruchamianie (322)
    • GCC (322)
    • Visual C++ Express Edition (323)
    • Dev C++ (327)

Literatura (329)

Spis tabel (331)

Spis ilustracji (333)

Skorowidz (339)

  • Titel: Algorytmy, struktury danych i techniki programowania. Wydanie IV
  • Autor: Piotr Wróblewski
  • ISBN: 978-83-246-5378-2, 9788324653782
  • Veröffentlichungsdatum: 2012-05-31
  • Format: E-book
  • Artikelkennung: algo4
  • Verleger: Helion