Л. Банаховски и др.: Алгоритмы и структуры данных.

Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych

Stan dobry. Zauważone defekty:

• drobne przybrudzenia okładki
• drobne uszkodzenia okładki
• drobne przybrudzenia brzegów kartek
• minimalne odgięcia rogów kartek

Z okładki — o książce

„Najważniejszym elementem procesu tworzenia dobrego programu komputerowego jest właściwy dobór algorytmów i struktur danych — szczególnie pod kątem ich efektywności.

Książka jest doskonałym wprowadzeniem w tę problematykę. Zawiera przegląd głównych zagadnień algorytmicznych. Korzystając z niej, Czytelnik pozna metody tworzenia i analizy algorytmów. Dzięki nim będzie mógł projektować efektywne algorytmy dla problemów pojawiających się w jego praktyce programistycznej lub pracy badawczej.

Algorytmy i struktury danych są tematem jednego z podstawowych przedmiotów na każdych studiach informatycznych. Książka jest sprawdzona dydaktycznie. Powstała na podstawie skryptu o tym samym tytule i notatek do wykładów prowadzonych przez Autorów na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.”

Z okładki — o autorach

„Autorzy książki są długoletnimi pracownikami naukowymi Instytutu Informatyki Uniwersytetu Warszawskiego. Specjalizują się w dziedzinie algorytmów i struktur danych. Są współautorami wielu książek wydanych przez takich znanych wydawców, jak Addison-Wesley, Cambridge University Press i Oxford University Press. Mają też na swoim koncie ponad sto prac naukowych z tej dziedziny. Publikacje tych Autorów można znaleźć w najlepszych czasopismach naukowych, poświęconych informatyce teoretycznej.”

Z przedmowy

„Niniejsza książka jest przeznaczona dla czytelników interesujących się głębiej informatyką, w tym przede wszystkim dla studentów informatyki. W szczególności może służyć jako podręcznik do wykładów: »Algorytmy i struktury danych i »Analiza algorytmów« dla studentów studiów informatycznych. Jej fragmenty mogą być także wykorzystane w nauczaniu przedmiotu »Metody programowania« i »Kombinatoryka i teoria grafów« w ujęciu algorytmicznym. Sądzimy, że książka może też zainteresować szersze kręgi czytelników, gdyż daje elementarne wprowadzenie do nowoczesnych metod tworzenia i analizy algorytmów. Metody te oraz bogactwo różnorodny struktur danych, przedstawionych w książce, mogą być pomocne w projektowaniu efektywnych algorytmów dla problemów pojawiających się w praktyce programistycznej i pracy badawczej.

Zakładamy, że czytelnik ma pewne podstawowe przygotowanie z kombinatoryki i rachunku prawdopodobieństwa (na poziomie szkoły średniej) i że umie układać algorytmy w Pascalu. Znajomość przedmiotów: »Wstęp do informatyki«, »Metody programowania« i »Analiza matematyczna I« jest pożądana przy czytaniu tej książki, ale nie konieczna.

Książka powstała z notatek do wykładów: »Algorytmy i struktury danych« oraz »Analiza algorytmów«, prowadzonych przez nas dla studentów informatyki Uniwersytetu Warszawskiego w latach 1986–1994. […]

Niniejsza książka składa się z 8 rozdziałów. Rozdział 1 stanowi wprowadzenie do dziedziny analizy algorytmów. Zdefiniowaliśmy w nim takie pojęcia, jak złożoność obliczeniowa i poprawność semantyczna algorytmu. Omówiliśmy rozwiązywanie równań rekurencyjnych i podstawowe struktury danych: listy, zbiory, grafy, drzewa i ich realizacje. Przedstawiliśmy także elementarne metody algorytmicznego rozwiązywania problemów. Rozdział 2 zawiera omówienie głównych algorytmów sortowania wraz z ich analizą i zastosowaniami wprowadzonych struktur danych do rozwiązywania pokrewnych problemów. Rozdział 3 jest poświęcony zadaniu wyszukiwania elementów w zbiorze. Przedstawiliśmy w nim podstawowe struktury danych i częściową ich analizę. W rozdziale 4 omówiliśmy i zanalizowaliśmy dwie złożone struktury danych, umożliwiające szybkie wykonywanie operacji na zbiorach rozłącznych. Opisaliśmy rozwiązanie problemu sumowania zbiorów rozłącznych 1 przedstawiliśmy implementację złączalnych kolejek priorytetowych za pomocą drzew dwumianowych. Rozdziały [5–8] są poświęcone dziedzinom informatyki teoretycznej, w której badania nad algorytmami rozwijały się w ostatnich latach najszybciej. Przedstawiliśmy w nich algorytmy tekstowe, a także algorytmy równoległe, grafowe i geometryczne. Każdy rozdział jest zakończony zestawem zadań umożliwiających pogłębienie zdobywanej wiedzy. Celem naszym nie było dostarczenie programów gotowych do uruchomienia. Pełna implementacja niektórych z zaprezentowanych algorytmów wymaga pewnego wysiłku programistycznego. […]”

Spis treści

Przedmowa

1. Podstawowe zasady analizy algorytmów

  1.1. Złożoność obliczeniowa

  1.2. Równania rekurencyjne

  1.3. Funkcje tworzące

  1.4. Poprawność semantyczna

  1.5. Podstawowe struktury danych

    1.5.1. Lista

    1.5.2. Zbiór

    1.5.3. Graf

    1.5.4. Notacja funkcyjna dla atrybutów obiektów.

    1.5.5. Drzewo

  1.6. Eliminacja rekursji

  1.7. Koszt zamortyzowany operacji w strukturze danych

  1.8. Metody układania algorytmów

    1.8.1. Metoda „dziel i zwyciężaj”

    1.8.2. Programowanie dynamiczne

    1.8.3. Metoda zachłanna

    1.8.4. Inne metody

  Zadania

2. Sortowanie

  2.1. Selectionsort — sortowanie przez selekcję

  2.2. Insertionsort — sortowanie przez wstawianie

  2.3. Quicksort — sortowanie szybkie

  2.4. Dolne ograniczenie na złożoność problemu sortowania

  2.5. Sortowanie pozycyjne

  2.6. Kolejki priorytetowe i algorytm heapsort

  2.7. Drzewa turniejowe i zadania selekcji

  2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu

  2.9. Scalanie ciągów uporządkowanych

  2.10. Sortowanie zewnętrzne

    2.10.1. Scalanie wielofazowe z 4 plikami

    2.10.2. Scalanie wielofazowe z 3 plikami

  Zadania

3. Słowniki

  3.1. Implementacja listowa nieuporządkowana

  3.2. Implementacja listowa uporządkowana

  3.3. Drzewa poszukiwań binarnych

    3.3.1. Drzewa AVL

    3.3.2. Samoorganizujące się drzewa BST

  3.4. Mieszanie

    3.4.1. Wybór funkcji mieszającej

    3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji

  3.5. Wyszukiwanie pozycyjne

    3.5.1. Drzewa RST

    3.5.2. Drzewa TRIE

    3.5.3. Drzewa PATRICIA

  3.6. Wyszukiwanie zewnętrzne

    3.6.1. Pliki nieuporządkowane

    3.6.2. Pliki z funkcją mieszającą

    3.6.3. Sekwencyjne pliki indeksowane

    3.6.4. B-drzewo jako wielopoziomowy indeks rzadki

    3.6.5. B-drzewo jako wielopoziomowy indeks gęsty

  Zadania

4. Złożone struktury danych dla zbiorów elementów

  4.1. Problem sumowania rozłącznych zbiorów

    4.1.1. Implementacja listowa

    4.1.2. Implementacja drzewowa

  4.2. Złączalne kolejki priorytetowe

  Zadania

5. Algorytmy tekstowe

  5.1. Problem wyszukiwania wzorca

    5.1.1. Algorytm N („naiwny”)

    5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta)

    5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera

    5.1.4. Algorytm GS’ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców)

    5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga)

    5.1.6. Algorytm KR (Karpa-Rabina)

    5.1.7. Algorytm BM (Boyera-Moore’a)

    5.1.8. Algorytm FP (Fishera-Patersona)

  5.2. Drzewa sufiksowe i grafy podsłów

    5.2.1. Niezwarta reprezentacja drzewa sufiksowego

    5.2.2. Tworzenie drzewa sufiksowego

    5.2.3. Tworzenie grafu podsłów

  5.3. Inne algorytmy tekstowe

    5.3.1. Obliczanie najdłuższego wspólnego podsłowa

    5.3.2. Obliczanie najdłuższego wspólnego podciągu

    5.3.3. Wyszukiwanie słów podwójnych

    5.3.4. Wyszukiwanie słów symetrycznych

    5.3.5. Równoważność cykliczna

    5.3.6. Algorytm Huffmana

    5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu

    5.3.8. Jednoznaczne kodowanie

    5.3.9. Liczenie liczby podsłów

  Zadania

6. Algorytmy równoległe

  6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych

  6.2. Sortowanie równoległe

  Zadania

7. Algorytmy grafowe

  7.1. Spójne składowe

  7.2. Dwuspójne składowe

  7.3. Silnie spójne składowe i silna orientacja

  7.4. Cykle Eulera

  7.5. 5-kolorowanie grafów planarnych

  7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające

  Zadania

8. Algorytmy geometryczne

  8.1. Elementarne algorytmy geometryczne

  8.2. Problem przynależności

  8.3. Wypukła otoczka

  8.4. Metoda zamiatania

    8.4.1. Najmniej odległa para punktów

    8.4.2. Pary przecinających się odcinków

  Zadania

Bibliografia

Skorowidz