Algorytmy i struktury danych

• Druk: Warszawa, 2018
• Autor: Krzysztof Marian Diks, Lech Banachowski, Wojciech Rytter
• Wydawca: Wydawnictwo Naukowe PWN

Jądrem informatyki jest algorytmika, a najważniejszym elementem procesu tworzenia dobrego programu komputerowego jest właściwy dobór algorytmów i struktur danych – szczególnie pod kątem ich wydajności.
Algorytmy i struktury danych są tematem jednego z podstawowych przedmiotów wykładanych na każdych studiach informatycznych. Książka została sprawdzona dydaktyczne na zajęciach prowadzonych ze studentami informatyki Uniwersytetu Warszawskiego, jak też wielu innych uczelni informatycznych w kraju.
Informacja o autorze/ redaktorze:
Autorzy są informatykami o uznanym w świecie dorobku naukowym, edukacyjnym i popularyzatorskim. W latach osiemdziesiątych XX wieku tworzyli podwaliny algorytmiki w Uniwersytecie Warszawskim. Mają na swoim koncie wiele znakomitych prac algorytmicznych opublikowanych w najlepszych wydawnictwach naukowych poświęconych informatyce teoretycznej.

• Kategorie:
  1. Ebooki i Audiobooki »
  2. Ebooki »
  3. Ebooki popularnonaukowe i specjalistyczne »
  4. Informatyka
• Język wydania: polski
• ISBN: 978-83-01-20148-7
• ISBN druku: 978-83-01-19712-4
• Liczba stron: 292

Przedmowa do nowego wydania  9
Przedmowa do pierwszego wydania  11
1 Podstawowe zasady analizy algorytmów  15
	1.1. Złożoność obliczeniowa   15
	1.2. Równania rekurencyjne    22
	1.3. Funkcje tworzące    23
	1.4. Poprawność semantyczna   24
	1.5. Podstawowe struktury danych   26
		1.5.1. Lista     27
		1.5.2. Zbiór     29
		1.5.3. Graf     30
		1.5.4. Notacja funkcyjna dla atrybutów obiektów     35
		1.5.5. Drzewo     35
	1.6. Eliminacja rekursji    38
	1.7. Koszt zamortyzowany operacji w strukturze danych     40
	1.8. Metody układania algorytmów   42
		1.8.1. Metoda „dziel i zwyciężaj”   42
		1.8.2. Programowanie dynamiczne   42
		1.8.3. Metoda zachłanna   43
		1.8.4. Inne metody    44
Zadania   44
2 Sortowanie     51
	2.1. Selectionsort – sortowanie przez selekcję   52
	2.2. Insertionsort – sortowanie przez wstawianie   53
	2.3. Quicksort – sortowanie szybkie  54
	2.4. Dolne ograniczenie na złożoność problemu sortowania    64
	2.5. Sortowanie pozycyjne    68
	2.6. Kolejki priorytetowe i algorytm heapsort   72
	2.7.. Drzewa turniejowe i zadania selekcji  79
	2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu  84
	2.9. Scalanie ciągów uporządkowanych   87
	2.10. Sortowanie zewnętrzne    90
		2.10.1. Scalanie wielofazowe z 4 plikami   91
		2.10.2. Scalanie wielofazowe z 3 plikami   92
Zadania   96
3 Słowniki      100
	3.1. Implementacja listowa nieuporządkowana   101
	3.2. Implementacja listowa uporządkowana   101
	3.3. Drzewa poszukiwań binarnych   106
		3.3.1. Drzewa AVL    114
		3.3.2. Samoorganizujące się drzewa BST   118
	3.4. Mieszanie     121
		3.4.1. Wybór funkcji mieszającej   122
		3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji  122
	3.5. Wyszukiwanie pozycyjne   127
		3.5.1. Drzewa RST    127
		3.5.2. Drzewa TRIE    130
		3.5.3. Drzewa PATRICIA   132
	3.6. Wyszukiwanie zewnętrzne   135
		3.6.1. Pliki nieuporządkowane  135
		3.6.2. Pliki z funkcją mieszającą   136
		3.6.3. Sekwencyjne pliki indeksowane   136
		3.6.4. B-drzewo jako wielopoziomowy indeks rzadki    137
		3.6.5. B-drzewo jako wielopoziomowy indeks gęsty    136
Zadania   139
4 Złożone struktury danych dla zbiorów elementów    143
	4.1. Problem sumowania zbiorów rozłącznych   143
		4.1.1. Implementacja listowa   144
		4.1.2. Implementacja drzewowa   148
	4.2. Złączalne kolejki priorytetowe   155
Zadania   162
5 Algorytmy tekstowe    164
	5.1. Problem wyszukiwania wzorca   165
		5.1.1. Algorytm N („naiwny”)  165
		5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta)     166
		5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera     169
		5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców)    171
		5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga)    172
		5.1.6. Algorytm KR (Karpa-Rabina)    174
		5.1.7. Algorytm BM (Boyera-Moore‘a)   175
		5.1.8. Algorytm FP (Fishera-Patersona)   178
	5.2. Drzewa sufiksowe i grafy podsłów   180
		5.2.1. Niezwarta reprezentacja drzewa sufiksowego    180
		5.2.2. Tworzenie drzewa sufiksowego   182
		5.2.3. Tworzenie grafu podsłów   187
	5.3. Inne algorytmy tekstowe   191
		5.3.1. Obliczanie najdłuższego wspólnego podsłowa    192
		5.3.2. Obliczanie najdłuższego wspólnego podciągu    192
		5.3.3. Wyszukiwanie słów podwójnych   192
		5.3.4. Wyszukiwanie słów symetrycznych   196
		5.3.5. Równoważność cykliczna   196
		5.3.6. Algorytm Huffmana   197
		5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu   199
		5.3.8. Jednoznaczne kodowanie   201
		5.3.9. Liczenie liczby podsłów  202
Zadania   202
6 Algorytmy równoległe    207
	6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych  209
	6.2. Sortowanie równoległe    223
Zadania   226
7 Algorytmy grafowe    229
	7.1. Spójne składowe    231
	7.2. Dwuspójne składowe    234
	7.3. Silnie spójne składowe i silna orientacja   241
	7.4. Cykle Eulera     247
	7.5. 5-kolorowanie grafów planarnych   250
	7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające     255
Zadania   257
8 Algorytmy geometryczne   260
	8.1. Elementarne algorytmy geometryczne    261
	8.2. Problem przynależności   262
	8.3. Wypukła otoczka    265
	8.4. Metoda zamiatania    273
		8.4.1. Najmniej odległa para punktów   274
		8.4.2. Pary przecinających się odcinków   277
Zadania   283
Bibliografia      285
Skorowidz      287