Algorytmy_struktury_danych_i_techniki_programowania_Wydanie_VI_algor6.pdf

(3460 KB) Pobierz
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,
fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym
powoduje naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi
ich właścicieli.
Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje
były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie,
ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz
Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody
wynikłe z wykorzystania informacji zawartych w książce.
Redaktor prowadzący: Małgorzata Kulik
Projekt okładki: Studio Gravite / Olsztyn
Obarek, Pokoński, Pazdrijowski, Zaprucki
Grafika na okładce została wykorzystana za zgodą Shutterstock.com
Wydawnictwo HELION
ul. Kościuszki 1c, 44-100 GLIWICE
tel. 32 231 22 19, 32 230 98 63
e-mail:
helion@helion.pl
WWW:
http://helion.pl
(księgarnia internetowa, katalog książek)
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie/algor6
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
ISBN: 978-83-283-5374-9
Copyright © Helion 2019
Printed in Poland.
•
Kup książkę
•
Poleć książkę
•
Oceń książkę
•
Księgarnia internetowa
•
Lubię to! » Nasza społeczność
Spis treści
Przedmowa
...................................................................................... 9
Uwagi do wydania VI
..................................................................................................... 9
Co odróżnia tę książkę od innych podręczników?
................................................... 10
Dlaczego C++?
.............................................................................................................. 11
Jak należy czytać tę książkę?
...................................................................................... 11
Co zostało opisane w tej książce?
.............................................................................. 12
Programy przykładowe
............................................................................................... 14
Konwencje typograficzne i oznaczenia
..................................................................... 15
Rozdział 1. Zanim wystartujemy
....................................................................... 17
Czym powinien się charakteryzować algorytm?
...................................................... 18
Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych
.......... 20
— 1804 —
.................................................................................................................. 20
— 1830 i później —
.................................................................................................... 21
— 1890 —
.................................................................................................................. 21
— lata 30. XX w. —
..................................................................................................... 21
— lata 40. XX w. —
..................................................................................................... 22
— okres powojenny —
.............................................................................................. 22
— 1969 —
.................................................................................................................. 23
— teraz —
.................................................................................................................. 23
Jak to się niedawno odbyło, czyli o tym,
kto „wymyślił” metodologię programowania
....................................................... 24
Proces koncepcji programów
..................................................................................... 25
Poziomy abstrakcji opisu i wybór języka
.................................................................. 26
Modelowanie działania algorytmów (maszyna Turinga)
....................................... 28
Poprawność algorytmów
............................................................................................ 29
Zadania
......................................................................................................................... 31
Rozwiązania i wskazówki do zadań
........................................................................... 31
Rozdział 2. Rekurencja
.................................................................................... 33
Definicja rekurencji
..................................................................................................... 33
Ilustracja pojęcia rekurencji
....................................................................................... 35
Jak wykonują się programy rekurencyjne?
.............................................................. 36
Niebezpieczeństwa rekurencji
................................................................................... 38
Ciąg Fibonacciego
...................................................................................................... 38
Stack overflow!
........................................................................................................... 40
Kup książkę
Poleć książkę
4
Algorytmy, struktury danych i techniki programowania
Pułapek ciąg dalszy
..................................................................................................... 42
Stąd do wieczności
..................................................................................................... 43
Definicja poprawna, ale…
......................................................................................... 43
Typy programów rekurencyjnych
............................................................................. 45
Myślenie rekurencyjne
................................................................................................ 46
Przykład 1. Spirala
...................................................................................................... 47
Przykład 2. Kwadraty „parzyste”
................................................................................. 48
Uwagi praktyczne na temat technik rekurencyjnych
.............................................. 50
Zadania
......................................................................................................................... 51
Rozwiązania i wskazówki do zadań
........................................................................... 53
Rozdział 3. Systemy obliczeniowe i podstawy kodowania
.................................. 59
System dziesiętny i kilka definicji
.............................................................................. 60
System dwójkowy
........................................................................................................ 60
Operacje arytmetyczne na liczbach dwójkowych
..................................................... 61
Operacje logiczne na liczbach dwójkowych
............................................................. 62
Kod BCD
........................................................................................................................ 64
System ósemkowy
....................................................................................................... 65
System szesnastkowy
.................................................................................................. 65
Kodowanie liczb ze znakiem
...................................................................................... 65
Kod znak-moduł (ZM)
................................................................................................ 66
Kod U2 (system uzupełnienia dwójkowego)
............................................................. 66
Zmienne w pamięci komputera
................................................................................. 67
Kodowanie znaków
..................................................................................................... 68
Kodowanie obrazów
.................................................................................................... 70
Mapy bitowe na przykładzie formatu BMP
................................................................ 71
Rozdział 4. Typy i struktury danych
.................................................................. 75
Typy podstawowe i złożone
....................................................................................... 76
Tablice
........................................................................................................................... 77
Ciągi znaków i napisy w C++
...................................................................................... 78
Typy złożone
................................................................................................................. 80
Struktury i wprowadzenie pojęcia referencji
............................................................. 80
Klasy i programowanie obiektowe
............................................................................ 83
Abstrakcyjne struktury danych
.................................................................................. 83
Listy jednokierunkowe
............................................................................................... 85
Tablicowa implementacja list
.................................................................................. 106
Stos
........................................................................................................................... 111
Kolejki FIFO
............................................................................................................... 116
Sterty i kolejki priorytetowe
..................................................................................... 119
Drzewa i ich reprezentacje
....................................................................................... 125
Zbiory
....................................................................................................................... 138
STL, czyli struktury danych dla leniuchów
............................................................. 140
Klasyczne kontenery sekwencyjne
.......................................................................... 141
Adaptery (nakładki na inne kontenery)
................................................................... 147
Kontenery asocjacyjne
............................................................................................. 148
Algorytmy w STL
...................................................................................................... 151
Dalsze materiały na temat STL
................................................................................. 152
Zadania
....................................................................................................................... 152
Rozwiązania zadań
.................................................................................................... 153
Kup książkę
Poleć książkę
Spis treści
5
Rozdział 5. Analiza złożoności algorytmów
..................................................... 155
Definicje i przykłady
.................................................................................................. 156
Jeszcze raz funkcja silnia
.......................................................................................... 160
Zerowanie fragmentu tablicy
.................................................................................. 163
Wpadamy w pułapkę
............................................................................................... 165
Różne typy złożoności obliczeniowej
...................................................................... 166
Nowe zadanie: uprościć obliczenia!
......................................................................... 168
Analiza programów rekurencyjnych
....................................................................... 169
Terminologia i definicje
........................................................................................... 169
Ilustracja metody na przykładzie
............................................................................. 170
Rozkład logarytmiczny
............................................................................................. 171
Przeszukiwanie binarne… tym razem bez matematyki wyższej!
........................... 173
Zamiana dziedziny równania rekurencyjnego
........................................................ 174
Funkcja Ackermanna, czyli coś dla smakoszy
.......................................................... 174
Złożoność obliczeniowa to nie religia!
.................................................................... 176
Techniki optymalizacji programów
......................................................................... 176
Zadania
....................................................................................................................... 177
Rozwiązania i wskazówki do zadań
......................................................................... 178
Rozdział 6. Derekursywacja i optymalizacja algorytmów
................................. 181
Jak pracuje kompilator?
............................................................................................ 182
Odrobina formalizmu nie zaszkodzi!
....................................................................... 184
Kilka przykładów derekursywacji algorytmów
...................................................... 185
Derekursywacja z wykorzystaniem stosu
............................................................... 188
Eliminacja zmiennych lokalnych
.............................................................................. 188
Metoda funkcji przeciwnych
.................................................................................... 190
Klasyczne schematy derekursywacji
....................................................................... 192
Schemat typu while
................................................................................................. 193
Schemat typu if-else
................................................................................................. 194
Schemat z podwójnym wywołaniem rekurencyjnym
............................................. 196
Podsumowanie
........................................................................................................... 198
Rozdział 7. Algorytmy sortowania
.................................................................. 199
Sortowanie przez wstawianie, algorytm klasy O(N
2
)
............................................ 200
Sortowanie bąbelkowe, algorytm klasy O(N
2
)
....................................................... 201
Sortowanie szybkie (Quicksort) — algorytm klasy O(N log N)
............................. 203
Heapsort — sortowanie przez kopcowanie
............................................................ 206
Scalanie zbiorów posortowanych
............................................................................ 209
Sortowanie przez scalanie, algorytm klasy O(N log N)
......................................... 209
Sortowanie zewnętrzne
............................................................................................ 211
Uwagi praktyczne
...................................................................................................... 214
Rozdział 8. Algorytmy przeszukiwania
............................................................ 217
Przeszukiwanie liniowe
............................................................................................. 217
Przeszukiwanie binarne
............................................................................................ 218
Transformacja kluczowa (hashing)
.......................................................................... 220
W poszukiwaniu funkcji H
........................................................................................ 221
Najbardziej znane funkcje H
.................................................................................... 222
Obsługa konfliktów dostępu
................................................................................... 224
Powrót do źródeł
...................................................................................................... 225
Jeszcze raz tablice!
................................................................................................... 226
Próbkowanie liniowe
............................................................................................... 226
Kup książkę
Poleć książkę

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin