Książka "Podstawy algorytmów z przykładami w C++" - Richard Neapolitan, Kumarss Naimipour -- Wydawnictwo Helion, księgarnia helion.pl

Algorytmy są jednym z fundamentów programowania. Prawidłowo zaprojektowany algorytm jest podstawą efektywnego i niezawodnego programu. Opisanie problemu w postaci algorytmu nie jest prostym zadaniem -- wymaga wiedzy z zakresu matematyki, umiejętności oceny złożoności obliczeniowej i znajomości zasad optymalizacji obliczeń. Istnieje wiele metod projektowania algorytmów. Znajomość tych metod znacznie ułatwia analizę zagadnienia i przedstawienie go w postaci zalgorytmizowanej.

Książka "Podstawy algorytmów z przykładami w C++" to kompletny podręcznik poświęcony tym właśnie zagadnieniom. Przedstawia sposoby podejścia do rozwiązywania zagadnień projektowych, udowadnia, że sporo z nich można zrealizować różnymi metodami, a także uczy, jak dobrać właściwą metodę do postawionego problemu. Materiał podzielony jest na wykłady, zilustrowane pseudokodem przypominającym język C++, co bardzo ułatwia zastosowanie poznanej wiedzy w praktyce.

Wprowadzenie do projektowania algorytmów
Zastosowanie techniki dziel i zwyciężaj
Algorytmy programowania dynamicznego
Analiza złożoności obliczeniowej algorytmów na przykładzie algorytmów sortowania i przeszukiwania
Algorytmy z zakresu teorii liczb
Algorytmy kompresji danych i kryptografii
Programowanie równoległe

Wykłady poświęcone algorytmom są uzupełnione dodatkami, zawierającymi kompendium niezbędnej wiedzy z dziedziny matematyki, technik rekurencyjnych i algebry zbiorów.

"Podstawy algorytmów z przykładami w C++" to doskonały podręcznik dla uczniów, studentów i wszystkich, którzy chcą poznać tę dziedzinę wiedzy.

O Autorach (9)
Przedmowa (11)
Rozdział 1. Algorytmy - wydajność, analiza i rząd (17)

1.1. Algorytmy (18)
1.2. Znaczenie opracowywania wydajnych algorytmów (25)

1.2.1. Wyszukiwanie sekwencyjne a wyszukiwanie binarne (26)
1.2.2. Ciąg Fibonacciego (28)

1.3. Analiza algorytmów (33)

1.3.1. Analiza złożoności (33)
1.3.2. Zastosowanie teorii (41)
1.3.3. Analiza poprawności (42)

1.4. Rząd (42)

1.4.1. Intuicyjne wprowadzenie do problematyki rzędu (43)
1.4.2. Formalne wprowadzenie do problematyki rzędu (45)
1.4.3. Wykorzystanie granic do określenia rzędu (56)

1.5. Zarys dalszej treści książki (59)
Ćwiczenia (60)

Rozdział 2. Dziel i zwyciężaj (65)

2.1. Wyszukiwanie binarne (66)
2.2. Sortowanie przez scalanie (71)
2.3. Podejście typu dziel i zwyciężaj (77)
2.4. Sortowanie szybkie (sortowanie przez podstawienie podziałów) (78)
2.5. Algorytm Strassena mnożenia macierzy (85)
2.6. Arytmetyka wielkich liczb całkowitych (90)

2.6.1. Reprezentacja wielkich liczb całkowitych: dodawanie i inne operacje wykonywane w czasie liniowym (91)
2.6.2. Mnożenie wielkich liczb całkowitych (91)

2.7. Określanie wartości progowych (97)
2.8. Przeciwwskazania do używania podejścia dziel i zwyciężaj (101)
Ćwiczenia (103)

Rozdział 3. Programowanie dynamiczne (111)

3.1. Współczynnik dwumianowy (112)
3.2. Algorytm Floyda określania najkrótszej drogi w grafie (117)
3.3. Programowanie dynamiczne a problemy optymalizacyjne (125)
3.4. Łańcuchowe mnożenie macierzy (127)
3.5. Optymalne drzewa wyszukiwania binarnego (136)
3.6. Problem komiwojażera (145)
Ćwiczenia (152)

Rozdział 4. Podejście zachłanne (157)

4.1. Minimalne drzewo rozpinające (161)

4.1.1. Algorytm Prima (163)
4.1.2. Algorytm Kruskala (169)
4.1.3. Porównanie algorytmu Prima z algorytmem Kruskala (173)
4.1.4. Dyskusja końcowa (173)

4.2. Algorytm Dijkstry najkrótszych dróg z jednego źródła (174)
4.3. Szeregowanie (177)

4.3.1. Minimalizacja całkowitego czasu w systemie (178)
4.3.2. Szeregowanie z terminami granicznymi (180)

4.4. Kod Huffmana (188)

4.4.1. Kody prefiksowe (189)
4.4.2. Algorytm Huffmana (190)

4.5. Podejście zachłanne a programowanie dynamiczne: problem plecakowy (194)

4.5.1. Podejście zachłanne do problemu plecakowego 0-1 (195)
4.5.2. Podejście zachłanne do ułamkowego problemu plecakowego (196)
4.5.3. Podejście programowania dynamicznego do problemu plecakowego 0-1 (197)
4.5.4. Poprawiona wersja algorytmu programowania dynamicznego dla problemu plecakowego 0-1 (197)

Ćwiczenia (201)

Rozdział 5. Algorytmy z powrotami (207)

5.1. Techniki algorytmów z powrotami (208)
5.2. Problem n-królowych (215)
5.3. Zastosowanie algorytmu Monte Carlo do oszacowania wydajności algorytmu z powrotami (219)
5.4. Problem sumy podzbiorów (223)
5.5. Kolorowanie grafu (228)
5.6. Problem cyklu Hamiltona (232)
5.7. Problem plecakowy 0-1 (235)

5.7.1. Algorytm z powrotami dla problemu plecakowego 0-1 (235)
5.7.2. Porównanie algorytmu programowania dynamicznego z algorytmem z powrotami do rozwiązywania problemu plecakowego 0-1 (244)

Ćwiczenia (245)

Rozdział 6. Metoda podziału i ograniczeń (251)

6.1. Ilustracja metody podziału i ograniczeń dla problemu plecakowego 0-1 (253)

6.1.1. Przeszukiwanie wszerz z przycinaniem metodą podziału i ograniczeń (253)
6.1.2. Przeszukiwanie typu najpierw najlepszy z przycinaniem metodą podziału i ograniczeń (258)

6.2. Problem komiwojażera (264)
6.3. Wnioskowanie abdukcyjne (diagnozowanie) (272)
Ćwiczenia (281)

Rozdział 7. Wprowadzenie do złożoności obliczeniowej: problem sortowania (285)

7.1. Złożoność obliczeniowa (286)
7.2. Sortowanie przez wstawianie i sortowanie przez wybieranie (288)
7.3. Dolne ograniczenia dla algorytmów usuwających co najwyżej jedną inwersję dla jednej operacji porównania (294)
7.4. Przypomnienie algorytmu sortowania przez scalanie (297)
7.5. Przypomnienie algorytmu szybkiego sortowania (303)
7.6. Sortowanie stogowe (305)

7.6.1. Stogi i podstawowe na nich operacje (305)
7.6.2. Implementacja algorytmu sortowania stogowego (309)

7.7. Zestawienie algorytmów sortowania przez scalanie, sortowania szybkiego i sortowania stogowego (316)
7.8. Dolne ograniczenia dla algorytmów sortujących wyłącznie na podstawie operacji porównania kluczy (317)

7.8.1. Drzewa decyzyjne dla algorytmów sortujących (317)
7.8.2. Dolne ograniczenia dla najgorszego przypadku (320)
7.8.3. Dolne ograniczenia dla średniego przypadku (323)

7.9. Sortowanie przez podział (sortowanie pozycyjne) (328)
Ćwiczenia (332)

Rozdział 8. Więcej o złożoności obliczeniowej: problem przeszukiwania (339)

8.1. Dolne ograniczenia dla przeszukiwania wyłącznie na podstawie porównywania wartości kluczy (340)

8.1.1. Dolne ograniczenia dla najgorszego przypadku (343)
8.1.2. Dolne ograniczenia dla średniego przypadku (345)

8.2. Przeszukiwanie przez interpolację (351)
8.3. Przeszukiwanie w drzewach (354)

8.3.1. Drzewa wyszukiwania binarnego (355)
8.3.2. B-drzewa (360)

8.4. Mieszanie (361)
8.5. Problem wyboru: wprowadzenie metody dyskusji z adwersarzem (367)

8.5.1. Znajdowanie największego klucza (367)
8.5.2. Znajdowanie zarówno najmniejszego, jak i największego klucza (369)
8.5.3. Znajdowanie drugiego największego klucza (376)
8.5.4. Znajdowanie k-tego najmniejszego klucza (381)
8.5.5. Algorytm probabilistyczny dla problemu wyboru (390)

Ćwiczenia (395)

Rozdział 9. Złożoność obliczeniowa i trudność problemów: wprowadzenie do teorii o zbiorze NP (401)

9.1. Trudność (402)
9.2. Ponowne omówienie zagadnienia rozmiaru danych wejściowych (404)
9.3. Trzy główne kategorie problemów (409)

9.3.1. Problemy, dla których wynaleziono algorytmy wielomianowe (409)
9.3.2. Problemy, których trudność została udowodniona (410)
9.3.3. Problemy, których trudność nie została udowodniona, jednak nie udało się znaleźć rozwiązujących je algorytmów wielomianowych (411)

9.4. Teoria o zbiorze NP (411)

9.4.1. Zbiory P i NP (414)
9.4.2. Problemy NP-zupełne (419)
9.4.3. Problemy NP-trudne, NP-łatwe i NP-równoważne (431)

9.5. Sposoby rozwiązywania problemów NP-trudnych (435)

9.5.1. Algorytm przybliżony dla problemu komiwojażera (436)
9.5.2. Przybliżony algorytm dla problemu pakowania (441)

Ćwiczenia (446)

Rozdział 10. Algorytmy teorii liczb (449)

10.1. Przegląd teorii liczb (450)

10.1.1. Liczby złożone i liczby pierwsze (450)
10.1.2. Największy wspólny dzielnik (451)
10.1.3. Rozkładanie liczb całkowitych na czynniki pierwsze (455)
10.1.4. Najmniejsza wspólna wielokrotność (457)

10.2. Wyznaczanie największego wspólnego dzielnika (457)

10.2.1. Algorytm Euklidesa (458)
10.2.2. Rozszerzenie algorytmu Euklidesa (462)

10.3. Przegląd arytmetyki modularnej (465)

10.3.1. Teoria grup (465)
10.3.2. Kongruencja modulo n (467)
10.3.3. Podgrupy (473)

(10.4. Rozwiązywanie modularnych równań liniowych 479)
(10.5. Obliczanie modularnych potęg 485)
10.6. Znajdowanie wielkich liczb pierwszych (488)

10.6.1. Szukanie liczby pierwszej (488)
(10.6.2. Sprawdzanie, czy dana liczba całkowita jest liczbą pierwszą 489)

10.7. System szyfrowania RSA z publicznym kluczem (508)

10.7.1. Systemy szyfrowania z kluczem publicznym (508)
10.7.2. System szyfrowania RSA (509)

Ćwiczenia (512)

Rozdział 11. Wprowadzenie do algorytmów równoległych (517)

11.1. Architektury równoległe (521)

11.1.1. Mechanizm sterowania (521)
11.1.2. Organizacja przestrzeni adresowej (522)
11.1.3. Sieci łączące (524)

11.2. Model PRAM (527)

11.2.1. Projektowanie algorytmów dla modelu CREW PRAM (531)
11.2.2. Projektowanie algorytmów dla modelu CRCW PRAM (538)

Ćwiczenia (541)

Dodatek A Przegląd niezbędnej wiedzy matematycznej (543)

A.1. Notacja (543)
A.2. Funkcje (545)
A.3. Indukcja matematyczna (546)
A.4. Twierdzenia i lematy (553)
A.5. Logarytmy (554)

A.5.1. Definicja i właściwości logarytmów (554)
A.5.2. Logarytm naturalny (557)

A.6. Zbiory (559)
A.7. Permutacje i kombinacje (560)
A.8. Prawdopodobieństwo (563)

A.8.1. Losowość (569)
A.8.2. Wartość oczekiwana (573)

Ćwiczenia (575)

Dodatek B Rozwiązywanie równań rekurencyjnych na potrzeby analizy algorytmów rekurencyjnych (581)

B.1. Rozwiązywanie rekurencji za pomocą indukcji (581)
B.2. Rozwiązywanie rekurencji z zastosowaniem równań charakterystycznych (585)

B.2.1. Homogeniczna rekurencja liniowa (585)
B.2.2. Niehomogeniczna rekurencja liniowa (594)
B.2.3. Zamiana zmiennej (przekształcenie dziedziny) (600)

B.3. Rozwiązywanie rekurencji przez podstawianie (603)
B.4. Rozszerzanie wyników dla n będącego potęgą dodatniej stałej b do wyników dla dowolnego n (605)
B.5. Dowody twierdzeń (611)
Ćwiczenia (614)

Dodatek C Struktury danych dla zbiorów rozłącznych (621)
Dodatek D Bibliografia (631)
Skorowidz (637)

Tag cloud