Algorytmy.Struktury.danych.i.techniki.programowania.9788324623068.pdf
(
14097 KB
)
Pobierz
Podstawowy podręcznik do nauki algorytmiki
•
Przystępne wprowadzenie do algorytmiki
•
Bez zbędnej teorii
·
Gotowe rozwiązania w
•
C++
A LGORYT MY
STRUKTURY
DANYC H
------
---
-
I
TECHNIKI
PRO
G
RAMOWANIA
WYDANIE
IV
-
PI
OTR WRÓBLE
WSKI
1
IR
Helion
Podstawowy podręcznik do nauki algorytmiki
-
ALGORYTMY
� -- -
-
-
--
-
STRUKTURY
DANYCH
I
TECHNIKI
PROGRAMOWANIA
-- ---
-
-
-
-
-- - -
WYDANIE
IV
\
\
\
\
\ \\
\
---
��,
�
-
-
-- -�
-
PIOTR WRÓBLEWSKI
.
�HeHon
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszecnianie całości lub ragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograiczną,
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.
Redakcja: Michał Mrowiec
Projekt okładki: Maciej Pasek
Fotografia na okładce została wykorzystana za zgodą iStockPhoto Inc.
Wydawnictwo HELION
ul. Kościuszki
le,
44-100 GLIWICE
tel. 32 231 22 19, 32 230 98 63
e-mail:
helion@helionpl
WW
:
http://helion.pl
(księgania intenetowa, katalog książek)
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie?algo4
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
ISBN: 978-83-246-2306-8
Copyright© Helion 2010
Printed in Poland.
Spis treści
Pzedmowa
...... „ „ „ ••• „ „ „ ••••••• „ „. „ •• „ •••••••••••••••••••••••••••••••••••••••• „ „ .••
9
Rozdział
1.
Zanim wystatujemy
......
.
...........
.
..
.
.........
.
..........
...
.....................
...
.
. 17
Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych
18
...................
Jak to się niedawno odbyło,
czyli o tym, kto „wymyślił" metodologię programowania
..... „„ .................... „„
.......... 21
Proces koncepcji programów
......................................................... „ .............. „ ...............
22
Poziomy abstrakcji opisu i wybór języka
.........„ ........... „ ......„ ... „.„ ......„ ......„ „.„..........
23
Poprawność algorytmów
............................................... „ .......... „ .. „ ............ ...................
24
Rozdział
2.
Rekurencja
.
..........
.
...
.
..........
..
...........
...
......
..
.......
.
..
.
.
.
..
.
......
..
..........
27
Deinicja rekurencji
.................................... „ ..................................................................
27
Ilustracja pojęcia rekurencji
............................................................................................
28
Jak wykonują się programy rekurencyjne?
............„ .......•........... „ ..•....•..•....•..•.•..•..........
30
Niebezpieczeństwa rekurencji
........................................................................................
31
Ciąg Fibonacciego
................ ....................................................................................
31
Stack overflow!
........................................................................................................
33
Pułapek ciąg dalszy
... ....... „ .......•............•....•..•............•.......•.......•............•..•... „ .............
34
Stąd do wieczności
..................... „ .............. „ ................... „ .......•...............................
34
Definicja poprawna, ale
... ........................... „ ................... „ ........................ „.„ ..........
35
Typy programów rekurencyjnych
..... „ ......................................... „ „ ........ „ .. „ „. „ „ ..........
36
Myślenie rekurencyjne
38
Przykład 1.: Spirala
„ ........................... „ .. „ ........... „.„ ...... „ .... „ ........ „ .......................
38
Przykład 2.: Kwadraty „parzyste"
...... „ .................................„ .. „.„ ....... „ .................
40
Uwagi praktyczne na temat teclmik rekurencyjnych
..................„.„ .........„ ... „ .... „„„„ ...
41
Zadania
............................................................... „ ....................... „ ........... „„ ......... „ .......
42
Rozwiązania i wskazówki do zadań
........................... „.„„„ ............ „„ .............. „ .............. „ ...„ ..........
44
.............. „ ....... „ ...........................•.......•....•.............
Rozdział
3.
Analiza zożoności algorytmów
...
.
.............
.
...... „. „ ••••••••••• „ •• „ ..........
49
Definicje i przykłady
........................................... „ ................................ „„„ ....... „ .. „„„ ..
50
Jeszcze raz unkcja silnia
........... „ ....„......„„ ...... „ ...„„„........ „„„ ............ „„.„
.......... 53
Zerowanie ragmentu tablicy
„„.„ .......... „„ ...... „ .. „ .. „ ...........„„„„........„ ..................
57
Wpadamy w pułapkę
................................................................................................
58
Różne typy złożoności obliczeniowej
59
............„ .... „. „ ... „ ....... „ „ ... „ ......... „ ...............
Nowe zadanie: uprościć obliczenia!
.......... 61
.„„„„ ....... „.„„.„„„„.„„.„ ... „.„„ .. „ ...... „„„.„
4
Algorytmy, struktury danych i techniki programowania
Analiza programów rekurencyjnych
...............................................................................
62
Terminologia i deinicje
...........................................................................................
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 sotowania
....
.
.
...
...........
...............................
.
.
..
...
.
...
.
.
.....
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 sury 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
.......
.
.
...
..........
.
...
......
.
.
14 7
Jak pracuje kompilator?
................................................................................................
148
Odrobina ormalizmu nie zaszkodzi!
............................................................................
150
Kilka przykładów derekursywacji algorytmów
............................................................
151
Derekursywacja z wykorzystaniem stosu
.....................................................................
154
Eliminacja zmiennych lokalnych
............................................................................
154
Metoda unkcji 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 binane
..... „ .........................................................................................
166
Transformacja kluczowa (hashing)
...............................................................................
167
W poszukiwaniu unkcji H
.....................................................................................
169
Najbardziej znane unkcje H
..................................................................................
169
Obsuga konfliktów dostępu
...................................................................................
171
Plik z chomika:
kendzior21
Inne pliki z tego folderu:
Algorytmy. Ćwiczenia - Bogdan Buczek [HQ].pdf
(60676 KB)
Algorytmy, struktury danych i techniki programowania. Wydanie IV - Piotr Wróblewski [HQ].pdf
(58007 KB)
Algorytmy, struktury danych i techniki programowania. Wydanie V - Piotr Wróblewski [HQ].pdf
(62351 KB)
Algorytmy bez tajemnic - Thomas H. Cormen [HQ].pdf
(57955 KB)
Algorytmy_genetyczne.pdf
(21798 KB)
Inne foldery tego chomika:
Adobe
Ajax
Analiza
Android
AngularJS
Zgłoś jeśli
naruszono regulamin