Autor: Alfred V. Aho, John E. Hopcroft. Jeffrey D. Ullman

ISBN: 83-7361-177-0

Ilość stron: 442

Data wydania: 09/2003

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.

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ą.

Rozdziały:

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)