Algorytmy i struktury danych

W niniejszej książce przedstawiono struktury danych i algorytmy stanowiące podstawę współczesnego programowania komputerów. Algorytmy są niczym przepis na rozwiązanie postawionego przed programistę problemu. Są one nierozerwalnie związane ze strukturami danych - listami, rekordami, tablicami, kolejkami, drzewami... podstawowymi elementami wiedzy każdego programisty.

Książka obejmuje szeroki zakres materiału, a do jej lektury wystarczy znajomość dowolnego języka programowania strukturalnego (np. Pascala). Opis klasycznych algorytmów uzupełniono o algorytmy związane z zarządzaniem pamięcią operacyjną i pamięciami zewnętrznymi.

Książka przedstawia algorytmy i struktury danych w kontekście rozwiązywania problemów za pomocą komputera. Z tematyką rozwiązywania problemów powiązano zagadnienie zliczania kroków oraz złożoności czasowej - wynika to z głębokiego przekonania autorów tej książki, iż wraz z pojawianiem się coraz szybszych komputerów, pojawiać się będą także coraz bardziej złożone problemy do rozwiązywania i - paradoksalnie - złożoność obliczeniowa używanych algorytmów zyskiwać będzie na znaczeniu.

W książce omówiono m.in.:

Tradycyjne struktury danych: listy, kolejki, stosy
Drzewa i operacje na strukturach drzew
Typy danych oparte na zbiorach, słowniki i kolejki priorytetowe wraz ze sposobami ich implementacji
Grafy zorientowane i niezorientowane
Algorytmy sortowania i poszukiwania mediany
Asymptotyczne zachowanie się procedur rekurencyjnych
Techniki projektowania algorytmów: "dziel i rządź", wyszukiwanie lokalne i programowanie dynamiczne
Zarządzanie pamięcią, B-drzewa i struktury indeksowe

Każdemu rozdziałowi towarzyszy zestaw ćwiczeń, o zróżnicowanym stopniu trudności, pomagających sprawdzić swoją wiedzę. "Algorytmy i struktury danych" to doskonały podręcznik dla studentów informatyki i pokrewnych kierunków, a także dla wszystkich zainteresowanych tą tematyką.
Spis treści:
Od tłumacza (7)

Wstęp (11)

Rozdział 1. Projektowanie i analiza algorytmów (15)

1.1. Od problemu do programu (15)
1.2. Abstrakcyjne typy danych (23)
1.3. Typy danych, struktury danych i ADT (25)
1.4. Czas wykonywania programu (28)
1.5. Obliczanie czasu wykonywania programu (33)
1.6. Dobre praktyki programowania (39)
1.7. Super Pascal (41)
Ćwiczenia (44)
Uwagi bibliograficzne (48)

Rozdział 2. Podstawowe abstrakcyjne typy danych (49)

2.1. Lista jako abstrakcyjny typ danych (49)
2.2. Implementacje list (52)
2.3. Stosy (64)
2.4. Kolejki (68)
2.5. Mapowania (73)
2.6. Stosy a procedury rekurencyjne (75)
Ćwiczenia (80)
Uwagi bibliograficzne (84)

Rozdział 3. Drzewa (85)

3.1. Podstawowa terminologia (85)
3.2. Drzewa jako abstrakcyjne obiekty danych (92)
3.3. Implementacje drzew (95)
3.4. Drzewa binarne (102)
Ćwiczenia (113)
Uwagi bibliograficzne (116)

Rozdział 4. Podstawowe operacje na zbiorach (117)

4.1. Wprowadzenie do zbiorów (117)
4.2. Słowniki (129)
4.3. Tablice haszowane (132)
4.4. Implementacja abstrakcyjnego typu danych MAPPING (146)
4.5. Kolejki priorytetowe (148)
4.6. Przykłady złożonych struktur zbiorowych (156)
Ćwiczenia (163)
Uwagi bibliograficzne (165)

Rozdział 5. Zaawansowane metody reprezentowania zbiorów (167)

5.1. Binarne drzewa wyszukiwawcze (167)
5.2. Analiza złożoności operacji wykonywanych na binarnym drzewie wyszukiwawczym (171)
5.3. Drzewa trie (175)
5.4. Implementacja zbiorów w postaci drzew wyważonych - 2-3-drzewa (181)
5.5. Operacje MERGE i FIND (193)
5.6. Abstrakcyjny typ danych z operacjami MERGE i SPLIT (202)
Ćwiczenia (207)
Uwagi bibliograficzne (209)

Rozdział 6. Grafy skierowane (211)

6.1. Podstawowe pojęcia (211)
6.2. Reprezentacje grafów skierowanych (213)
6.3. Graf skierowany jako abstrakcyjny typ danych (215)
6.4. Znajdowanie najkrótszych ścieżek o wspólnym początku (217)
6.5. Znajdowanie najkrótszych ścieżek między każdą parą wierzchołków (221)
6.6. Przechodzenie przez grafy skierowane - przeszukiwanie zstępujące (229)
6.7. Silna spójność i silnie spójne składowe digrafu (237)
Ćwiczenia (240)
Uwagi bibliograficzne (242)

Rozdział 7. Grafy nieskierowane (243)

7.1. Definicje (243)
7.2. Metody reprezentowania grafów (245)
7.3. Drzewa rozpinające o najmniejszym koszcie (246)
7.4. Przechodzenie przez graf (253)
7.5. Wierzchołki rozdzielające i składowe dwuspójne grafu (256)
7.6. Reprezentowanie skojarzeń przez grafy (259)
Ćwiczenia (262)
Uwagi bibliograficzne (264)

Rozdział 8. Sortowanie (265)

8.1. Model sortowania wewnętrznego (265)
8.2. Proste algorytmy sortowania wewnętrznego (266)
8.3. Sortowanie szybkie (quicksort) (273)
8.4. Sortowanie stogowe (283)
8.5. Sortowanie rozrzutowe (287)
8.6. Dolne ograniczenie dla sortowania za pomocą porównań (294)
8.7. Szukanie k-tej wartości (statystyki pozycyjne) (298)
Ćwiczenia (302)
Uwagi bibliograficzne (304)

Rozdział 9. Techniki analizy algorytmów (305)

9.1. Efektywność algorytmów (305)
9.2. Analiza programów zawierających wywołania rekurencyjne (306)
9.3. Rozwiązywanie równań rekurencyjnych (308)
9.4. Rozwiązanie ogólne dla pewnej klasy rekurencji (311)
Ćwiczenia (316)
Uwagi bibliograficzne (319)

Rozdział 10. Techniki projektowania algorytmów (321)

10.1. Zasada "dziel i zwyciężaj" (321)
10.2. Programowanie dynamiczne (327)
10.3. Algorytmy zachłanne (335)
10.4. Algorytmy z nawrotami (339)
10.5. Przeszukiwanie lokalne (349)
Ćwiczenia (355)
Uwagi bibliograficzne (358)

Rozdział 11. Struktury danych i algorytmy obróbki danych zewnętrznych (359)

11.1. Model danych zewnętrznych (359)
11.2. Sortowanie zewnętrzne (362)
11.3. Przechowywanie informacji w plikach pamięci zewnętrznych (373)
11.4. Zewnętrzne drzewa wyszukiwawcze (381)
Ćwiczenia (387)
Uwagi bibliograficzne (390)

Rozdział 12. Zarządzanie pamięcią (391)

12.1. Podstawowe aspekty zarządzania pamięcią (391)
12.2. Zarządzanie blokami o ustalonej wielkości (395)
12.3. Algorytm odśmiecania dla bloków o ustalonej wielkości (397)
12.4. Przydział pamięci dla obiektów o zróżnicowanych rozmiarach (405)
12.5. Systemy partnerskie (412)
12.6. Upakowywanie pamięci (416)
Ćwiczenia (419)
Uwagi bibliograficzne (421)

Bibliografia (423)

Skorowidz (429)