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.

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 permutacji1.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.Zadania

2. 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. Zadania

3. 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. Zadania

4. 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. Zadania

5. 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

Literatura

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

Podobne książki:

Modelowanie matematyczne systemów W poprawionym i rozszerzonym III wydaniu książki przedstawione są podstawy metodologiczne i przykłady budowy, w uniwersalnym języku matematyki, modeli różnorodnych systemów: technologicznych, ekonomicznych, rolniczych, ekologicznych. Rozważania...

 

Teoria liczb w informatyce Nowoczesny, interdyscyplinarny podręcznik akademicki, w którym szczególny nacisk położono na obliczeniową teorię liczb.Książka "Teoria liczb w informatyce"  składa się z 3 rozdziałów. Pierwszy to podstawowy wykład z elementarnej teorii...

 

Rachunek prawdopodobieństwa dla prawie każdego Wydanie 2 Prowadząc od przeszło dwudziestu lat wykłady i ćwiczenia z teorii prawdopodobieństwa na Wydziale Matematyki Uniwersytetu Warszawskiego zdaliśmy sobie sprawę, że przedmiot ten z rozmaitych względów nie jest łatwy. Napisaliśmy tę książkę, aby...