[ Pobierz całość w formacie PDF ]
Spis treści
Przedmowa...
9
Rozdział1 Zanim wystartujemy
17
1.1. Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych
19
1.2. Jak to się niedawno odbyło, czyli o tym kto "wymyślił" metodologię programowania
21
1.3. Proces koncepcji programów
22
1.4. Poziomy abstrakcji opisu i wybór języka
23
1.5. Poprawność algorytmów
25
Rozdział 2 Rekurencja
29
2.1. Definicja rekurencji
29
2.2. Ilustracja pojęcia rekurencji
31
2.3. Jak wykonujÄ… siÄ™ programy rekurencyjne?
33
2.4. Niebezpieczeństwa rekurencji
34
2.4.1. CiÄ…g Fibonacciego
35
2.4.2. Stack overflow!
36
2.5. Pułapek ciąg dalszy
37
2.5.1. Stąd do wieczności
38
2.5.2. Definicja poprawna, ale
38
2.6. Typy programów
rekurcncyjnych
40
2.7. Myślenie rekurencyjne
42
2.7.1. Spirala
42
2.7.2. Kwadraty „parzyste"
44
2.8. Uwagi praktyczne na temat technik rekurencyjnych
45
2.9. Zadania
47
2.10. Rozwiązania i wskazówki do zadań
49
Rozdział 3 Analiza sprawności algorytmów
53
3.1. Dobre samopoczucie użytkownika programu
54
6
3.2. Przykład 1: Jeszcze raz funkcja silnia
3.3. Przykład 2; Zerowanie fragmentu tablicy
3.4. Przykład 3: Wpadamy w pułapkę
3.5. Przykład 4: Różne typy złożoności obliczeniowej...
3.6. Nowe zadanie: uprościć obliczenia!
3.7. Analiza programów rekurencyjnych
3.7.1. Terminologia
3.7.2. Ilustracja metody na przykładzie
3.7.3. Rozkład „logarytmiczny"
3.7.3
3.7.4. Zamiana dziedziny równania rekurencyjnego
3.7.5. Funkcja Ackermanna, czyli coÅ› dla smakoszy
3.8. Zadania
3.9. Rozwiązania i wskazówki do zadań
Rozdział 4 Algorytmy sortowania
4.1. Sortowanie przez wstawianie, algorytm klasy 0(N
2
)
4.2. Sortowanie bÄ…belkowe, algorytm klasy O
(N2)
4.3. Quicksort, algorytm klasy 0(N log^N)
4.4. Uwagi praktyczne
Rozdział5 Struktury danych
5.1. Listy jednokierunkowe
5.1.1. Realizacja struktur danych listy jednokierunkowej
5.1.2. Tworzenie listy jednokierunkowej
5.1.3. Listy jednokierunkowe- teoria i rzeczywistość....
5.2. Tablicowa implementacja list
5.2.1. Klasyczna reprezentacja tablicowa
5.2.2. Metoda tablic równoległych
5.2.3. Listy innych typów
5.3. Stos
5.3.1. Zasada działania stosu
5.4. Kolejki FIFO
5.5. Sterty i kolejki priorytetowe
5.6. Drzewa i ich reprezentacje
5.6.1. Drzewa binarne i wyrażenia arytmetyczne
5.7. Uniwersalna struktura słownikowa
5.8. Zbiory
5.9. Zadania
5.10. Rozwiązania zadań
Rozdział 6 Derekursywacja
6.1. Jak pracuje kompilator?
6.2. Odrobina formalizmu... nie zaszkodzi!
6.3. Kilka przykładów derekursywacji algorytmów
6.4. Derekursywacja z wykorzystaniem stosu
6.4.1. Eliminacja zmiennych lokalnych
6.5. Metoda funkcji przeciwnych
6.6. Klasyczne schematy derekursywacji
Spis treści
7
6.6.1. Schemat typu
while
181
6.6.2. Schemat typu
if..
else
182
6.6.3. Schemat z podwójnym wywołaniem rekurencyjnym
185
6.7. Podsumowanie
187
Rozdział 7 Algorytmy przeszukiwania
189
7.1. Przeszukiwanie liniowe
189
7.2. Przeszukiwanie binarne
190
7.3. Transformacja kluczowa.
191
7.3.1. W poszukiwaniu funkcji
H
193
7.3.2. Najbardziej znane funkcje
H
194
7.3.3. Obsługa konfliktów dostępu
197
7.3.4. Zastosowania transformacji kluczowej
204
7.3.5. Podsumowanie metod transformacji kluczowej
204
Rozdział 8 Przeszukiwanie tekstów
207
8.1. Algorytm typu
brute-force
207
8.2. Nowe algorytmy poszukiwań
210
8.2.1. Algorytm K-M-P
211
8.2.2. Algorytm Boyera i Moore'a
216
8.2.3. Algorytm Rabina i Karpa
218
Rozdział 9 Zaawansowane techniki programowania 223
9.1. Programowanie typu „dziel i rządź" . 224
9.1.1. Odszukiwanie minimum i maksimum w tablicy liczb 225
9.1.2. Mnożenie macierz)' o rozmiarze N*N 229
9.1.3. Mnożenie liczb całkowitych 232
9.1.4. Inne znane algorytmy „dziel-i-rządź".. 233
9.2. Algorytmy ,"żarłoczne", czyli przekąsić coś nadszedł już czas 234
9.2.1. Problem plecakowy, czyli niełatwe jest życie turysty-piechura 235
9.3. Programowanie dynamiczne
238
9.4. Uwagi bibliograficzne
243
Rozdział 10 Elementy algorytmiki gratów
245
10.1. Definicje i pojęcia podstawowe
246
10.2. Sposoby reprezentacji grafów
248
10.3. Podstawowe operacje na grafach
249
10.4. Algorytm Roy-Warshalla
251
10.5. Algorytm Floyda
254
10.6. Przeszukiwanie grafów
257
10.6.1. Strategia „w głąb"
257
10.6.2. Strategia „wszerz"
259
10.7. Problem właściwego
doboru
261
10.8. Podsumowanie
266
Rozdziału Algorytmy numeryczne
267
11.1. Poszukiwanie miejsc zerowych funkcji
268
11.2. Iteracyjne obliczanie wartości funkcji
269
11.3. Interpolacja funkcji metodÄ… Lagrange'a
270
11.4. Różniczkowanie funkcji
272
[ Pobierz całość w formacie PDF ]