Autor: Witold Lipski
ISBN: 978-83-204-3259-6
Ilość stron: 276
Data wydania: 02/2007 (dodruk)
Twarda oprawa
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 "Kombinatoryka dla programistów wydanie III rozszerzone" jest przeznaczona dla studentów informatyki, programistów i projektantów systemów informatycznych.
Rozdziały:
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
Kombinatoryka dla programistów wydanie III --- Pozycja niedostępna.---
|