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ż:

Niewykrywalne drony na wodór

Prototyp cichego i niewidzialnego dla detektorów podczerwieni drona napędzanego wodorem powstał dzięki pracom badaczy z Akademii Górniczo-Hutniczej, a także Politechniki Rzeszowskiej. Taki samolot mógłby znaleźć zastosowanie np. w wojsku i...

Kredyt studencki ułatwi ci start

Świat w szalonym tempie pędzi do przodu. Aby dostać niezłą pracę nie wystarczy już tylko zdać maturę. Młodzi ludzie muszą w siebie inwestować, dlatego zdecydowana większość z nich decyduje się na...

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

Jak poznać swoje mocne strony?

Nie ma ludzi zwyczajnych. Każdy z nas jest wyjątkowy i posiada unikatowy zestaw talentów, z których korzysta we właściwy sobie sposób. Od osób, które osiągnęły sukces, resztę odróżnia tylko jedna ...