Książki

Autor: Agnieszka Debudaj-Grabysz,Sebastian Deorowicz,Jacek Widuch
rok wydania: 2010
wydawnictwo: Wydawnictwo Politechniki Śląskiej


Książka poświęcona jest wybranym, zaawansowanym algorytmom i strukturom danych. Jest ona skierowana głównie do studentów kierunku informatyka oraz kierunków pokrewnych, którzy mają za sobą podstawowe kursy dotyczące algorytmiki i programowania. Może jednak być przydatna wszystkim osobom zainteresowanym algorytmiką. Są w niej omawiane zaawansowane algorytmy grafowe, drzewa i tablice sufiksów wraz z działającymi na nich algorytmami, trwałe struktury danych oraz wybrane metaheurystyki optymalizacyjne.




SPIS TREŚCI:

Wstęp 7

1. Trwałe struktury danych 11
1.1. Wprowadzenie 11
1.2. Metoda grubych węzłów 13
1.3. Metoda kopiowania ścieżki 13
1.4. Metoda Sleatora, Tarjana i in. 16
1.5. Zastosowania 19
1.6. Problemy 22
1.7. Uwagi bibliograficzne 23
1.8. Zadania 23
Bibliografia 24

2. Drzewa i tablice sufiksów 26
2.1. Wprowadzenie 26
2.2. Drzewa sufiksów 27
2.2.1. Podstawy 27
2.2.2. Algorytmy tworzenia 28
2.2.3. Idea algorytmu Ukkonena 31
2.3. Zastosowania drzew sufiksów 34
2.3.1. Wyszukiwanie wystąpień wzorców 34
2.3.2. Najdłuższe wspólne podsłowo dwóch tekstów 35
2.3.3. Najdłuższe odwrócone powtórzenia 37
2.3.4. Transformata Burrowsa-Wheelera 37
2.4. Tablice sufiksów 38
2.4.1. Algorytmy tworzenia 38
2.4.2. Operacje na tablicy sufiksów 39
2.5. Uwagi bibliograficzne 41
2.6. Zadania 41
Bibliografia 43

3. Sieci i algorytmy przepływowe 45
3.1. Wprowadzenie 45
3.2. Sieć przepływowa i przepływ w sieci 46
3.3. Algorytmy wyznaczania maksymalnego przepływu 50
3.3.1. Algorytm Forda-Fulkersona 50
3.3.2. Algorytm Edmondsa-Karpa 53
3.3.3. Zastosowanie przepływu blokującego 53
3.4. Sieć przepływowa z wieloma źródłami i wieloma ujściami 60
3.5. Uwagi bibliograficzne 61
3.6. Zadania 62
Bibliografia 68

4. Wybrane zaawansowane algorytmy grafowe 70
4.1. Wprowadzenie 70
4.2. Sortowanie topologiczne 70
4.3. Grafy dwudzielne 73
4.3.1. Wykrywanie dwudzielności 74
4.3.2. Maksymalne skojarzenie w grafie dwudzielnym 75
4.4. Wykrywanie ujemnego cyklu 78
4.4.1. Algorytm Floyda-Warshalla 78
4.4.2. Algorytm Bellmana-Forda 81
4.5. Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków 84
4.5.1. Algorytm Johnsona 84
4.6. Uwagi bibliograficzne 88
4.7. Zadania 89
Bibliografia 94

5. Metaheurystyki optymalizacyjne 97
5.1. Wprowadzenie 97
5.2. Przeszukiwanie lokalne 100
5.2.1. Przykład 101
5.3. Symulowane wyżarzanie 105
5.3.1. Algorytm 105
5.3.2. Zbieżność algorytmu 106
5.3.3. Parametry 108
5.3.4. Przykład 109
5.4. Przeszukiwanie tabu 111
5.4.1. Zakazy 111
5.4.2. Kryteria aspiracji 112
5.4.3. Zakończenie algorytmu 112
5.4.4. Zarys algorytmu 112
5.4.5. Lista kandydatów 113
5.4.6. Dywersyfikacja 114
5.4.7. Przykład 114
5.5. Uwagi bibliograficzne 120
5.6. Zadania 121
Bibliografia 122

6. Algorytmy genetyczne 124
6.1. Wprowadzenie 124
6.2. Etapy algorytmu 125
6.2.1. Generowanie populacji początkowej 125
6.2.2. Kodowanie 125
6.2.3. Wyznaczanie jakości chromosomów 126
6.2.4. Selekcja 127
6.2.5. Krzyżowanie 129
6.2.6. Mutacja 130
6.2.7. Warunek zatrzymania 130
6.3. Przykład 131
6.4. Algorytmy pokrewne 134
6.4.1. Programowanie ewolucyjne 135
6.4.2. Strategie ewolucyjne 135
6.4.3. Programowanie genetyczne 137
6.5. Uwagi bibliograficzne 138
6.6. Zadania 138
Bibliografia 140

Spis rysunków 141
Spis tabel 144
Skorowidz 145

 

Zobacz również:

Trzy polskie uczelnie będą modernizować śmigłowce Airbus Helicopters

Firma Airbus Helicopters zajmująca się produkcją śmigłowców podpisała we wtorek w Gdańsku umowę o współpracy z trzema polskimi uczelniami technicznymi. Szkoły wyższe będą pracować nad ulepszaniem systemów i podzespołów helikopterów ...

Zakończył się remont Biblioteki Głównej AGH

Zakończył się remont Biblioteki Głównej Akademii Górniczo-Hutniczej w Krakowie. Pawilon, którego rozbudowa i odnowienie trwały ok. dwóch lat i kosztowały prawie 15 mln zł, uroczyście otwarto w środę.Połowę kosztów renowacji sf...

Studencie – nie zmarnuj pięciu lat!

Legendarne opowieści o mocno zakrapianych imprezach podczas studiów nikogo już nie szokują, a nawet nie dziwią. Pytanie tylko, czy jest to właściwy sposób na przetrwanie tych pięciu lat, które miały ...

Lista wyższych uczelni w Polsce wg typu - publiczne uczelnie akademickie

Lista zawiera wykaz wyższych uczelnie publicznych, które nadzorowane są przez Ministra ds. szkolnictwa wyższego, uporządkowane wg typu uczelni. Uniwersytety: Uniwersytet Warszawski Uniwersytet w Białymstoku Uniwersytet Gdański Uniwersytet im. Adama Mickiewicza w Poznaniu Uniwersytet Jagielloński w Krakowie Uniwersytet ...