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

Turysta w Krakowie – miejsca, które warto zwiedzić

Kraków jest jednym z najpiękniejszych polskich miast, które jest bardzo chętnie odwiedzane przez turystów. Świadczy o tym fakt, że w 2012 roku do Miasta Kraka przybyło prawie 9 mln gości. ...

15 mln zł dla młodych badaczy w ramach Diamentowego Grantu

Badania dotyczące zmian stanów uwagi w procesie twórczym czy sztuki naskalnej w Tanzanii - to niektóre ze studenckich projektów naukowych, które otrzymają dofinansowanie w programie Diamentowy Grant. Resort nauki przeznaczył ...

Krakowski Kazimierz i jego atrakcje turystyczne

Kraków, jako stolica Małopolski oraz miasto pełne cennych zabytków, nie bez powodu jest tak chętnie odwiedzane. Liczne atrakcje turystyczne czekają jednak nie tylko na terenie Starego Miasta, ale i na te...

Najbardziej poszukiwany pracownik w 2014 roku

Najbardziej poszukiwany pracownik w 2014 roku Praca jest podstawą życia każdego człowieka. Jeżeli jesteś osobą nastawioną na sukces i chcesz rozwijać swoją karierę, musisz przebyć długą drogę, która ...