ALGORYTMY KOMBINATORYCZNE

Edward M. Reingold

Jurg Nievergelt

Narsingh Deo

Wydawnictwo: PWN, 1985
Oprawa: miękka
Stron: 424
Stan: bardzo dobry, nieaktualne pieczątki

Książka jest próbą systematyzacji wiedzy z dziedziny algorytmów kombinatorycznych. Przedstawione są w niej metody szacowania efektywności i ogólne zasady konstrukcji takich algorytmów. Szczególnie dużo miejsca autorzy poświęcają algorytmom wyszukiwania i sortowania oraz algorytmom grafowym, które są szczególnie ważne przy rozwiązywaniu problemów związanych z działaniem na dużych zbiorach danych. Ogólne problemy rozważane są w oparciu o dużą ilość dokładnie omawianych przykładów. Istotną zaletą książki jest także duża ilość ćwiczeń związanych z każdym rozdziałem, jak również specjalne paragrafy poświęcone komentarzom historyczno-bibliograficznym.


SPIS TREŚCI:

Wstęp

Rozdział I. Co to są obliczenia kombinatoryczne
§1.1. Przykład: zliczanie jedynek w ciągu bitów
§ 1.2. Problem reprezentacji danych: kody zachowujące różnice.
§1.3. Metody kompozycji
§ 1.4. Metody dekompozycji.
§1.5. Klasy algorytmów
§1.6. Analiza algorytmów
§1.7. Komentarze i literatura
§ 1.8. Ćwiczenia

Rozdział 2, Reprezentacja obiektów kombinatorycznych
§2.1. Liczby całkowite
§2.2. Ciągi
§2.3. Drzewa
§2.4. Zbiory i multizbiory
§2.5. Komentarze i literatura
§2.6. Ćwiczenia.

Rozdział 3. Obliczanie i szacowanie
§3.1. Przybliżenia
§ 3.2. Równania rekurencyjne
§3.3. Funkcje tworzące
§3.4. Liczenie klas równoważności: twierdzenie Polya
§3.5. Komentarze i literatura
§3.6. Ćwiczenia.

Rozdział 4. Wyszukiwanie wyczerpujące
§4.1. Metoda powrotów
§4.2. Sita
§4.3. Przybliżenia wyczerpującego wyszukiwania..
4.4. Komentarze i literatura
§4.5. Ćwiczenia

Rozdział 5. Generowanie elementarnych obiektów kombinatorycznych
§5.1. Permutacje różnych elementów
§5.2. Podzbiory
§ 5.3. Kompozycje i rozkłady liczb całkowitych
§5.4. Komentarze i literatura
§5.5. Ćwiczenia

Rozdział 6. Szybkie wyszukiwanie
§6.1. Wyszukiwanie i inne operacje na tablicach
§6.2. Wyszukiwanie sekwencyjne
§ 6.3. Wyszukiwanie logarytmiczne w tablicach statycznych
§6.4. Wyszukiwanie logarytmiczne w tablicach dynamicznych
§6.5. Metody obliczania adresu
§6.6. Komentarze i literatura
§6.7. Ćwiczenia.

Rozdział 7. Sortowanie
§7.1. Sortowanie wewnętrzne.
§ 7.2. Sortowanie zewnętrzne.
§ 7.3. Sortowanie częściowe
§ 7.4. Komentarze i literatura
§7.5. Ćwiczenia

Rozdział 8. Algorytmy grafowe
§ 8.1. Reprezentacje
§ 8.2. Spójność grafu i odległość wierzchołków
§ 8.3. Cykle
§ 8.4. Kliki
§ 8.5. Izomorfizm
§ 8.6. Grafy płaskie
§ 8.7. Komentarze i literatura
§ 8.8. Ćwiczenia.

Rozdział 9. Równoważność pewnych problemów kombinatorycznych.
§9.1. Klasa P i NP
§9.2. N.P-trudne i .N P-zupełne problemy
§9.3. Komentarze i literatura
§9.4. Ćwiczenia
Skorowidz