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 zespoły w światowym finale mistrzostw programowania

Zespoły z Uniwersytetów: Jagiellońskiego, Warszawskiego i Wrocławskiego wystartują w światowym finale Akademickich Mistrzostw w Programowaniu Zespołowym (ACM-ICPC). Finały odbędą się w dniach 22-26 czerwca w Jekaterynburgu w Rosji.Do finału dotarły ...

W Gdańsku będzie testowany pilotażowy system zarządzania miastem

W Gdańsku testowany będzie pilotażowy system inteligentnego zarządzania miastem, nad którym – w ramach unijnego projektu - pracują naukowcy i prywatne firmy z ośmiu europejskich państw, w tym Polski. System ...

Superkomputer Zeus znowu najlepszy w Polsce

Superkomputer „Zeus” z Akademickiego Centrum Komputerowego Cyfronet AGH po raz kolejny okazał się najlepszy w Polsce. Zajął 176. miejsce w rankingu TOP 500 najpotężniejszych komputerów na świecie. Na 277. miejscu ...

Studenckie finanse - czyli gdzie wpłacić oszczędności aby na nich zarabiać bez ryzyka?

Według ogólnie dostępnych statystyk, lokaty bankowe są wciąż najchętniej wybieranym produktem oszczędnościowym w Polsce. Wpływa na to charakterystyka tych depozytów. Wszystkie lokaty gwarantują wypłatę odsetek oraz bezpieczeństwo. Niestety w ostatnim ...