Kombinatoryka dla programistów

Witold Lipski

Kategoria: Programy matematyczne Matematyka, Teoria matematyki Matematyka
Wydawnictwo: WNT

Ilość stron: 274
ISBN: 83-204-2968-4

W książce "Kombinatoryka dla programistów" 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:

1. Wprowadzenie do kombinatoryki1.1. Pojęcia wstępne1.2. Funkcje i rozmieszczenia1.3. Permutacje: rozkład na cykle, znak permutacji1.4. Generowanie permutacji 1.5. Podzbiory zbioru, zbiory z powtórzeniami, generowanie podzbiorów zbioru1.6. Podzbiory k-elementowe, współczynnik dwumienny1.7. Generowanie podzbiorów k-elementowych1.8. Podziały zbioru1.9. Liczby Stirlinga drugiego i pierwszego rodzaju1.10.Generowanie podziałów zbioru1.11.Podziały liczby1.12.Funkcje tworzące1.13.Zasada włącznia-wyłącznia1.14.Zadania2. Algorytmy grafowe2.1. Reprezentacja maszynowa grafu2.2. Przeszukowanie grafu w głąb2.3. Przeszukiwanie grafu wszerz2.4. Drzewa rozpinające2.5. Znajdowanie fundamentalnego zbioru cykli w grafie2.6. Znajdowanie składowych dwuspójnych2.7. Drogi Eulera2.8. Algorytmy z powracaniem2.9. Zadania3. Znajdowanie najkrótszych dróg w grafie3.1. Pojęcia wstępne3.2. Najkrótsze drogi z ustalonego wierzchołka3.3. Przypadek nieujemnych wag – algorytm Dijkstry3.4. Drogi w grafie acyklicznym3.5. Najkrótsze drogi między wszystkimi parami wierzchołków, domknięcie przechodnie relacji3.6. Zadania4. Przepływy w sieciach i zagadnienia pokrewne4.1. Maksymalny przepływ w sieci4.2. Algorytm znajdowania maksymalnego przepływu4.3. Skojarzenia o maksymalnej liczności w grafach dwudzielnych4.4. Systemy różnych reprezentantów4.5. Rozkład na łańcuchy4.6. Zadania5. Matroidy5.1. Algorytmy zachłanne rozwiązywania problemów optymalizacyjnych5.2. Matroidy i ich podstawowe własności5.3. Twierdzenie Rado-Edmondsa5.4. Matroidy macierzowe5.5. Matroidy grafowe5.6. Matroidy transwersalne5.7. Zadania

Dodatek: Algorytmy w języku C++ i przykłady użycia

Podobne książki: