W książce przedstawiono wybrane zagadnienia kombinatoryki, teorii grafów i
algorytmów kombinatorycznych. Szczególny nacisk położono na algorytmiczne podejście
do problemów kombinatorycznych.
Każdemu omawianemu problemowi towarzyszy szczegółowy algorytm jego rozwiązania i
analiza złożoności obliczeniowej. Warto zaznaczyć, że wszystkie algorytmy
zamieszczone w książce to zwarte nieformalne wersje programów napisanych w Pascalu i w
języku C++, przy czym te ostatnie są zebrane w oddzielnym Dodatku. Każdy rozdział
kończy się zbiorem zadań do samodzielnego rozwiązania.
Książka jest przeznaczona dla studentów informatyki, programistów i projektantów
systemów informatycznych.
Spis treści:
Od Autora
1. Wprowadzenie do kombinatoryki
1.1. Pojęcia wstępne
1.2. Funkcje i rozmieszczenia
1.3. Permutacje: rozkład na cykle, znak permutacji
1.4. Generowanie permutacji
1.5. Podzbiory zbioru, zbiory z powtórzeniami, generowanie podzbiorów zbioru
1.6. Podzbiory k-elementowe, współczynnik dwumienny
1.7. Generowanie podzbiorów k-elementowych
1.8. Podziały zbioru
1.9. Liczby Stirlinga drugiego i pierwszego rodzaju
1.10.Generowanie podziałów zbioru
1.11.Podziały liczby
1.12.Funkcje tworzące
1.13.Zasada włącznia-wyłącznia
1.14.Zadania
2. Algorytmy grafowe
2.1. Reprezentacja maszynowa grafu
2.2. Przeszukowanie grafu w głąb
2.3. Przeszukiwanie grafu wszerz
2.4. Drzewa rozpinające
2.5. Znajdowanie fundamentalnego zbioru cykli w grafie
2.6. Znajdowanie składowych dwuspójnych
2.7. Drogi Eulera
2.8. Algorytmy z powracaniem
2.9. Zadania
3. Znajdowanie najkrótszych dróg w grafie
3.1. Pojęcia wstępne
3.2. Najkrótsze drogi z ustalonego wierzchołka
3.3. Przypadek nieujemnych wag - algorytm Dijkstry
3.4. Drogi w grafie acyklicznym
3.5. Najkrótsze drogi między wszystkimi parami wierzchołków, domknięcie przechodnie
relacji
3.6. Zadania
4. Przepływy w sieciach i zagadnienia pokrewne
4.1. Maksymalny przepływ w sieci
4.2. Algorytm znajdowania maksymalnego przepływu
4.3. Skojarzenia o maksymalnej liczności w grafach dwudzielnych
4.4. Systemy różnych reprezentantów
4.5. Rozkład na łańcuchy
4.6. Zadania
5. Matroidy
5.1. Algorytmy zachłanne rozwiązywania problemów optymalizacyjnych
5.2. Matroidy i ich podstawowe własności
5.3. Twierdzenie Rado-Edmondsa
5.4. Matroidy macierzowe
5.5. Matroidy grafowe
5.6. Matroidy transwersalne
5.7. Zadania
Literatura
Dodatek
Algorytmy w języku C++ i przykłady użycia
Skorowidz
274 stron, B5, oprawa twarda
