algorytmy, struktury danych i techniki programowania. wydanie iv cała książka.pdf
(
9617 KB
)
Pobierz
4
Algorytmy, struktury danych i techniki programowania
Analiza programów rekurencyjnych ............................................................................... 62
Terminologia i definicje ........................................................................................... 62
Ilustracja metody na przykładzie .............................................................................. 63
Rozkład logarytmiczny ............................................................................................. 64
Zamiana dziedziny równania rekurencyjnego .......................................................... 66
Funkcja Ackermanna, czyli coś dla smakoszy ......................................................... 66
Złożoność obliczeniowa to nie religia! ........................................................................... 68
Techniki optymalizacji programów ................................................................................ 68
Zadania ........................................................................................................................... 69
Rozwiązania i wskazówki do zadań ............................................................................... 70
Rozdział 4. Algorytmy sortowania ..................................................................... 73
Sortowanie przez wstawianie, algorytm klasy O(N
2
) ..................................................... 74
Sortowanie bąbelkowe, algorytm klasy O(N
2
) ............................................................... 75
Quicksort, algorytm klasy O(N log N) ........................................................................... 77
Heap Sort — sortowanie przez kopcowanie ................................................................... 80
Scalanie zbiorów posortowanych ................................................................................... 82
Sortowanie przez scalanie ............................................................................................... 83
Sortowanie zewnętrzne ................................................................................................... 84
Uwagi praktyczne ........................................................................................................... 87
Rozdział 5. Typy i struktury danych .................................................................. 89
Typy podstawowe i złożone ........................................................................................... 89
Ciągi znaków i napisy w C++ ......................................................................................... 90
Abstrakcyjne struktury danych ....................................................................................... 92
Listy jednokierunkowe ............................................................................................. 93
Tablicowa implementacja list ................................................................................. 115
Stos ......................................................................................................................... 119
Kolejki FIFO .......................................................................................................... 123
Sterty i kolejki priorytetowe ................................................................................... 125
Drzewa i ich reprezentacje ..................................................................................... 131
Zbiory ..................................................................................................................... 143
Zadania ................................................................................................................... 145
Rozwiązania zadań ................................................................................................. 146
Rozdział 6. Derekursywacja i optymalizacja algorytmów .................................. 147
Jak pracuje kompilator? ................................................................................................ 148
Odrobina formalizmu nie zaszkodzi! ............................................................................ 150
Kilka przykładów derekursywacji algorytmów ............................................................ 151
Derekursywacja z wykorzystaniem stosu ..................................................................... 154
Eliminacja zmiennych lokalnych ............................................................................ 154
Metoda funkcji przeciwnych ........................................................................................ 156
Klasyczne schematy derekursywacji ............................................................................ 158
Schemat typu while ................................................................................................ 159
Schemat typu if-else ............................................................................................... 160
Schemat z podwójnym wywołaniem rekurencyjnym ............................................. 162
Podsumowanie .............................................................................................................. 163
Rozdział 7. Algorytmy przeszukiwania ............................................................. 165
Przeszukiwanie liniowe ................................................................................................ 165
Przeszukiwanie binarne ................................................................................................ 166
Transformacja kluczowa (hashing) ............................................................................... 167
W poszukiwaniu funkcji H ..................................................................................... 169
Najbardziej znane funkcje H .................................................................................. 169
Obsługa konfliktów dostępu ................................................................................... 171
Spis treści
5
Powrót do źródeł .................................................................................................... 172
Jeszcze raz tablice! ................................................................................................. 173
Próbkowanie liniowe .............................................................................................. 173
Podwójne kluczowanie ........................................................................................... 175
Zastosowania transformacji kluczowej ................................................................... 176
Podsumowanie metod transformacji kluczowej ..................................................... 176
Rozdział 8. Przeszukiwanie tekstów ............................................................... 179
Algorytm typu brute-force ............................................................................................ 179
Nowe algorytmy poszukiwań ....................................................................................... 181
Algorytm K-M-P .................................................................................................... 182
Algorytm Boyera i Moore’a ................................................................................... 185
Algorytm Rabina i Karpa ....................................................................................... 187
Rozdział 9. Zaawansowane techniki programowania ....................................... 191
Programowanie typu „dziel i zwyciężaj” ...................................................................... 192
Odszukiwanie minimum i maksimum w tablicy liczb ............................................ 193
Mnożenie macierzy o rozmiarze N×N .................................................................... 195
Mnożenie liczb całkowitych ................................................................................... 197
Inne znane algorytmy „dziel i zwyciężaj” .............................................................. 198
Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas... .................................. 199
Problem plecakowy, czyli niełatwe jest życie turysty piechura .............................. 200
Programowanie dynamiczne ......................................................................................... 202
Ciąg Fibonacciego .................................................................................................. 203
Równania z wieloma zmiennymi ........................................................................... 204
Najdłuższa wspólna podsekwencja ........................................................................ 205
Inne techniki programowania ....................................................................................... 208
Uwagi bibliograficzne .................................................................................................. 210
Rozdział 10. Elementy algorytmiki grafów ......................................................... 211
Definicje i pojęcia podstawowe .................................................................................... 212
Cykle w grafach ............................................................................................................ 214
Sposoby reprezentacji grafów ....................................................................................... 217
Reprezentacja tablicowa ......................................................................................... 217
Słowniki węzłów .................................................................................................... 218
Listy kontra zbiory ................................................................................................. 219
Podstawowe operacje na grafach .................................................................................. 220
Suma grafów .......................................................................................................... 220
Kompozycja grafów ............................................................................................... 220
Potęga grafu ........................................................................................................... 220
Algorytm Roy-Warshalla ............................................................................................. 221
Algorytm Floyda-Warshalla ......................................................................................... 224
Algorytm Dijkstry ........................................................................................................ 227
Algorytm Bellmana-Forda ............................................................................................ 228
Drzewo rozpinające minimalne .................................................................................... 228
Algorytm Kruskala ................................................................................................. 229
Algorytm Prima ...................................................................................................... 230
Przeszukiwanie grafów ................................................................................................. 230
Strategia „w głąb” (przeszukiwanie zstępujące) ..................................................... 231
Strategia „wszerz” .................................................................................................. 232
Inne strategie przeszukiwania ................................................................................. 234
Problem właściwego doboru ......................................................................................... 235
Podsumowanie .............................................................................................................. 239
Zadania ......................................................................................................................... 239
6
Algorytmy, struktury danych i techniki programowania
Rozdział 11. Algorytmy numeryczne ................................................................. 241
Poszukiwanie miejsc zerowych funkcji ........................................................................ 241
Iteracyjne obliczanie wartości funkcji .......................................................................... 243
Interpolacja funkcji metodą Lagrange’a ....................................................................... 244
Różniczkowanie funkcji ............................................................................................... 245
Całkowanie funkcji metodą Simpsona .......................................................................... 247
Rozwiązywanie układów równań liniowych metodą Gaussa ....................................... 248
Uwagi końcowe ............................................................................................................ 251
Rozdział 12. Czy komputery mogą myśleć? ....................................................... 253
Przegląd obszarów zainteresowań Sztucznej Inteligencji ............................................. 254
Systemy eksperckie ................................................................................................ 255
Sieci neuronowe ..................................................................................................... 256
Reprezentacja problemów ............................................................................................ 257
Ćwiczenie 1. ........................................................................................................... 258
Gry dwuosobowe i drzewa gier .................................................................................... 259
Algorytm mini-max ...................................................................................................... 260
Rozdział 13. Kodowanie i kompresja danych .................................................... 265
Kodowanie danych i arytmetyka dużych liczb ............................................................. 267
Kodowanie symetryczne ........................................................................................ 267
Kodowanie asymetryczne ....................................................................................... 268
Metody prymitywne ............................................................................................... 274
Łamanie szyfrów .................................................................................................... 275
Techniki kompresji danych ........................................................................................... 275
Kompresja poprzez modelowanie matematyczne ................................................... 277
Kompresja metodą RLE ......................................................................................... 278
Kompresja danych metodą Huffmana .................................................................... 279
Kodowanie LZW .................................................................................................... 283
Idea kodowania słownikowego na przykładach ..................................................... 284
Opis formatu GIF ................................................................................................... 286
Rozdział 14. Zadania różne .............................................................................. 289
Teksty zadań ................................................................................................................. 289
Rozwiązania ................................................................................................................. 291
Dodatek A Poznaj C++ w pięć minut! ............................................................. 295
Elementy języka C++ na przykładach .......................................................................... 295
Pierwszy program ................................................................................................... 295
Dyrektywa #include ............................................................................................... 296
Podprogramy ................................................................................................................ 296
Procedury ............................................................................................................... 296
Funkcje ................................................................................................................... 297
Operacje arytmetyczne ................................................................................................. 298
Operacje logiczne ................................................................................................... 298
Wskaźniki i zmienne dynamiczne .......................................................................... 299
Referencje ..................................................................................................................... 300
Typy złożone ................................................................................................................ 300
Tablice .................................................................................................................... 300
Rekordy .................................................................................................................. 301
Instrukcja switch .................................................................................................... 301
Iteracje .......................................................................................................................... 302
Struktury rekurencyjne ................................................................................................. 303
Parametry programu main() .......................................................................................... 303
Operacje na plikach w C++ .......................................................................................... 303
Spis treści
7
Programowanie obiektowe w C++ ............................................................................... 304
Terminologia .......................................................................................................... 304
Obiekty na przykładzie ........................................................................................... 305
Składowe statyczne klas ......................................................................................... 308
Metody stałe klas .................................................................................................... 308
Dziedziczenie własności ......................................................................................... 308
Kod warunkowy w C++ ............................................................................................... 311
Dodatek B Systemy obliczeniowe w pigułce ................................................... 313
Kilka definicji ............................................................................................................... 313
System dwójkowy ........................................................................................................ 313
Operacje arytmetyczne na liczbach dwójkowych ................................................... 315
Operacje logiczne na liczbach dwójkowych ........................................................... 315
System ósemkowy ........................................................................................................ 317
System szesnastkowy ................................................................................................... 317
Zmienne w pamięci komputera .................................................................................... 317
Kodowanie znaków ...................................................................................................... 318
Dodatek C Kompilowanie programów przykładowych ...................................... 321
Zawartość archiwum ZIP na ftp .................................................................................... 321
Darmowe kompilatory C++ .......................................................................................... 321
Kompilacja i uruchamianie ........................................................................................... 322
GCC ....................................................................................................................... 322
Visual C++ Express Edition ................................................................................... 323
Dev C++ ................................................................................................................. 327
Literatura ..................................................................................... 329
Spis tabel ................................................................................... 331
Spis ilustracji .............................................................................. 333
Skorowidz ................................................................................... 339
Plik z chomika:
AGAPE_AGAPE
Inne pliki z tego folderu:
autocad 2005 i 2005 pl full.pdf
(22413 KB)
intensywny kurs przywództwa. szybki program rozwoju zdolności przywódczych full.pdf
(9732 KB)
płytki umysł. jak internet wpływa na nasz mózg helion.pdf
(34503 KB)
analiza statystyczna. microsoft excel 2010 pl cała książka.pdf
(27781 KB)
matematyczne-szkielko-i-oko.-mniej-i-bardziej-powazne-zastosowania-matmy full scan.pdf
(28897 KB)
Inne foldery tego chomika:
! # Wrzucone - sprawdzone i pełne Ebooki #
! # Wrzucone - sprawdzone i pełne Ebooki #(1)
! # Wrzucone - sprawdzone i pełne Ebooki #(10)
! # Wrzucone - sprawdzone i pełne Ebooki #(2)
! # Wrzucone - sprawdzone i pełne Ebooki #(3)
Zgłoś jeśli
naruszono regulamin