Algorytmy i struktury danych

Lech Banachowski, Krzysztof Marian Diks, Wojciech Rytter

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

978-83-01-20148-7

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2018

Liczba stron:

293

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Banachowski, Lech; Diks, Krzysztof Marian; Rytter, Wojciech. Algorytmy i struktury danych. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2018, 293 s. ISBN 978-83-01-20148-7

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Banachowski, L.

A1 Diks, K.M.

A1 Rytter, W.

T1 Algorytmy i struktury danych

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2018

SN 978-83-01-20148-7

Bibliografia BibTex:

@Book{ 197970, author = "Banachowski, Lech and Diks, Krzysztof Marian and Rytter, Wojciech", editor = "", title = "Algorytmy i struktury danych", publisher = "Wydawnictwo Naukowe PWN", year = "2018", address = "Warszawa", isbn = "978-83-01-20148-7" }

Bibliografia endNote:

TY - BOOK

AU - Banachowski, Lech

AU - Diks, Krzysztof Marian

AU - Rytter, Wojciech

ED -

TI - Algorytmy i struktury danych

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2018

SN - 978-83-01-20148-7

ER -

Netografia (standard APA):

Banachowski, Lech; Diks, Krzysztof Marian; Rytter, Wojciech. Algorytmy i struktury danych [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2018 [dostęp: 20 04 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/algorytmy-i-struktury-danych-lech-banachowski-krzysztof-197970.

algorytmy, Struktury danych, algorytmika, analiza algorytmów

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

Więcej

ISBN/ISSN:

978-83-01-20148-7

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2018

Liczba stron:

293

XML:ISBN/ISSN:

ONIX MARC21

Przedmowa do nowego wydania10
Przedmowa do pierwszego wydania12
1 Podstawowe zasady analizy algorytmów16
1.1. Złożoność obliczeniowa16
1.2. Równania rekurencyjne23
1.3. Funkcje tworzące24
1.4. Poprawność semantyczna25
1.5. Podstawowe struktury danych27
1.5.1. Lista28
1.5.2. Zbiór30
1.5.3. Graf31
1.5.4. Notacja funkcyjna dla atrybutów obiektów36
1.5.5. Drzewo36
1.6. Eliminacja rekursji39
1.7. Koszt zamortyzowany operacji w strukturze danych41
1.8. Metody układania algorytmów43
1.8.1. Metoda „dziel i zwyciężaj”43
1.8.2. Programowanie dynamiczne43
1.8.3. Metoda zachłanna44
Zadania45
1.8.4. Inne metody45
2 Sortowanie52
2.1. Selectionsort – sortowanie przez selekcję53
2.2. Insertionsort – sortowanie przez wstawianie54
2.3. Quicksort – sortowanie szybkie55
2.4. Dolne ograniczenie na złożoność problemu sortowania65
2.5. Sortowanie pozycyjne69
2.6. Kolejki priorytetowe i algorytm heapsort73
2.7.. Drzewa turniejowe i zadania selekcji80
2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu85
2.9. Scalanie ciągów uporządkowanych88
2.10. Sortowanie zewnętrzne91
2.10.1. Scalanie wielofazowe z 4 plikami92
2.10.2. Scalanie wielofazowe z 3 plikami93
Zadania97
3 Słowniki101
3.1. Implementacja listowa nieuporządkowana102
3.2. Implementacja listowa uporządkowana102
3.3. Drzewa poszukiwań binarnych107
3.3.1. Drzewa AVL115
3.3.2. Samoorganizujące się drzewa BST119
3.4. Mieszanie122
3.4.1. Wybór funkcji mieszającej123
3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji123
3.5. Wyszukiwanie pozycyjne128
3.5.1. Drzewa RST128
3.5.2. Drzewa TRIE131
3.5.3. Drzewa PATRICIA133
3.6. Wyszukiwanie zewnętrzne136
3.6.1. Pliki nieuporządkowane136
3.6.2. Pliki z funkcją mieszającą137
3.6.3. Sekwencyjne pliki indeksowane137
3.6.5. B-drzewo jako wielopoziomowy indeks gęsty137
3.6.4. B-drzewo jako wielopoziomowy indeks rzadki138
Zadania140
4 Złożone struktury danych dla zbiorów elementów144
4.1. Problem sumowania zbiorów rozłącznych144
4.1.1. Implementacja listowa145
4.1.2. Implementacja drzewowa149
4.2. Złączalne kolejki priorytetowe156
Zadania163
5 Algorytmy tekstowe165
5.1. Problem wyszukiwania wzorca166
5.1.1. Algorytm N („naiwny”)166
5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta)167
5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera170
5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców)172
5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga)173
5.1.6. Algorytm KR (Karpa-Rabina)175
5.1.7. Algorytm BM (Boyera-Moore‘a)176
5.1.8. Algorytm FP (Fishera-Patersona)179
5.2. Drzewa sufiksowe i grafy podsłów181
5.2.1. Niezwarta reprezentacja drzewa sufiksowego181
5.2.2. Tworzenie drzewa sufiksowego183
5.2.3. Tworzenie grafu podsłów188
5.3. Inne algorytmy tekstowe192
5.3.1. Obliczanie najdłuższego wspólnego podsłowa193
5.3.2. Obliczanie najdłuższego wspólnego podciągu193
5.3.3. Wyszukiwanie słów podwójnych193
5.3.4. Wyszukiwanie słów symetrycznych197
5.3.5. Równoważność cykliczna197
5.3.6. Algorytm Huffmana198
5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu200
5.3.8. Jednoznaczne kodowanie202
Zadania203
5.3.9. Liczenie liczby podsłów203
6 Algorytmy równoległe208
6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych210
6.2. Sortowanie równoległe224
Zadania227
7 Algorytmy grafowe230
7.1. Spójne składowe232
7.2. Dwuspójne składowe235
7.3. Silnie spójne składowe i silna orientacja242
7.4. Cykle Eulera248
7.5. 5-kolorowanie grafów planarnych251
7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające256
Zadania258
8 Algorytmy geometryczne261
8.1. Elementarne algorytmy geometryczne262
8.2. Problem przynależności263
8.3. Wypukła otoczka266
8.4. Metoda zamiatania274
8.4.1. Najmniej odległa para punktów275
8.4.2. Pary przecinających się odcinków278
Zadania284
Bibliografia286
Skorowidz288