Używamy cookies, aby ułatwić korzystanie z Portalu. Możesz określić warunki przechowywania, dostępu do plików cookies w Twojej przeglądarce. Dowiedz się więcej.
strona główna Strona główna | Nowości | Promocje | Zapowiedzi Twoje konto | Zarejestruj | Schowek | Kontakt | Pomoc
mapa działów
Szukaj: szukanie zaawansowane
Koszyk
Książki \ Programowanie \ Algorytmy

Wprowadzenie do algorytmów Język: 1

978-83-01-16911-4

Cena Brutto: 149.00

Cena netto: 141.90

Ilość:
Wersja: Drukowana
Autor Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Liczba_stron 1400
Wydawnictwo PWN
Oprawa twarda
Data_Wydania 2012-01-01

Wprowadzenie do algorytmów

Prezentowana książka to nowe wydanie najlepszego na świecie podręcznika z dziedziny algorytmów i struktur danych, nazywanego BIBLIĄ ALGORYTMÓW

To kolejne, VII wydanie trzeciego wydania amerykańskiego znakomitego podręcznika z dziedziny algorytmów i struktur danych. W obecnym wydaniu został ulepszony cały tekst książki. Zmiany obejmują dodanie nowych rozdziałów, poprawienie pseudokodu i wprowadzenie aktywniejszego stylu prezentacji.


Omówiono w niej metody matematyczne stosowane do analizy algorytmów, sortowanie i statystyki pozycyjne, struktury danych, podstawowe metody projektowania efektywnych algorytmów. Dużo miejsca poświęcono złożonym strukturom danych i podstawowym algorytmom grafowym.


Poszczególne części książki to materiał dydaktyczny do wielu przedmiotów informatycznych (takich jak np. matematyka dyskretna, kombinatoryka, algorytmy i struktury danych, teoria grafów, metody programowania) wykładanych na uczelniach wyższych. Podręcznik stanowi zamkniętą całość. Zawiera dużo zadań i problemów do rozwiązania (o różnym stopniu trudności).


Pozycja jest przeznaczona dla studentów kierunków informatycznych, pracowników naukowych, jak również wszystkich tych, którzy chcą zajmować się projektowaniem i programowaniem systemów informatycznych.

Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XIII
Część I Podstawy
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1. Rola algorytmów w obliczeniach . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Algorytmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Algorytmy jako technologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Zaczynamy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1. Sortowanie przez wstawianie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2. Analiza algorytmów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3. Projektowanie algorytmów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1. Metoda „dziel i zwyciężaj” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2. Analiza algorytmów typu „dziel i zwyciężaj” . . . . . . . . . . . . . . . . . . . 34
3. Rzędy wielkości funkcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1. Notacja asymptotyczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2. Standardowe notacje i typowe funkcje . . . . . . . . . . . . . . . . . . . . . . . 53
4. Metoda „dziel i zwyciężaj” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1. Problem maksymalnej podtablicy . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2. Algorytm Strassena mnożenia macierzy . . . . . . . . . . . . . . . . . . . . . . 75
4.3. Metoda podstawiania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4. Metoda drzewa rekursji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5. Metoda rekurencji uniwersalnej . . . . . . . . . . . . . . . . . . . . . . . . . . 93
V
SPIS TREŚCI
⋆ 4.6. Dowód twierdzenia o rekurencji uniwersalnej . . . . . . . . . . . . . . . . . . . 96
4.6.1. Dowód dla dokładnych potęg . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6.2. Podłogi i sufity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5. Analiza probabilistyczna i algorytmy randomizowane . . . . . . . . . . . . . . . 112
5.1. Problem zatrudnienia sekretarki . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.2. Zmienne losowe wskaźnikowe . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.3. Algorytmy randomizowane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
⋆ 5.4. Analiza probabilistyczna i dalsze zastosowania zmiennych losowych wskaźnikowych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.4.1. Paradoks dnia urodzin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.4.2. Kule i urny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.4.3. Ciągi „dobrej passy”, czyli sukcesów . . . . . . . . . . . . . . . . . . . . . . . 133
5.4.4. Problem on-line zatrudnienia sekretarki . . . . . . . . . . . . . . . . . . . . . . 138
Część II Sortowanie i statystyki pozycyjne
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6. Heapsort – sortowanie przez kopcowanie . . . . . . . . . . . . . . . . . . . . . . 151
6.1. Kopce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.2. Przywracanie własności kopca . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.3. Budowanie kopca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.4. Algorytm sortowania przez kopcowanie (heapsort) . . . . . . . . . . . . . . . . 159
6.5. Kolejki priorytetowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7. Quicksort – sortowanie szybkie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.1. Opis algorytmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.2. Czas działania algorytmu quicksort . . . . . . . . . . . . . . . . . . . . . . . . 172
7.3. Randomizowana wersja algorytmu quicksort . . . . . . . . . . . . . . . . . . . 177
7.4. Analiza algorytmu quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.4.1. Analiza przypadku pesymistycznego . . . . . . . . . . . . . . . . . . . . . . . . 178
7.4.2. Analiza oczekiwanego czasu działania . . . . . . . . . . . . . . . . . . . . . . . 179
8. Sortowanie w czasie liniowym . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.1. Dolne ograniczenia dla problemu sortowania . . . . . . . . . . . . . . . . . . . 189
8.2. Sortowanie przez zliczanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
8.3. Sortowanie pozycyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
8.4. Sortowanie kubełkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
9. Mediany i statystyki pozycyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9.1. Minimum i maksimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
9.2. Wybór w oczekiwanym czasie liniowym . . . . . . . . . . . . . . . . . . . . . 212
9.3. Wybór w pesymistycznym czasie liniowym . . . . . . . . . . . . . . . . . . . . 217
VI
SPIS TREŚCI
Część III Struktury danych
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
10. Elementarne struktury danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
10.1. Stosy i kolejki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
10.2. Listy (z dowiązaniami) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
10.3. Reprezentowanie struktur wskaźnikowych za pomocą tablic . . . . . . . . . . . 239
10.4. Reprezentowanie drzew (ukorzenionych) . . . . . . . . . . . . . . . . . . . . . . 244
11. Tablice z haszowaniem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
11.1. Tablice z adresowaniem bezpośrednim . . . . . . . . . . . . . . . . . . . . . . . 252
11.2. Tablice z haszowaniem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
11.3. Funkcje haszujące . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
11.3.1. Haszowanie modularne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
11.3.2. Haszowanie przez mnożenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
⋆ 11.3.3. Haszowanie uniwersalne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
11.4. Adresowanie otwarte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
⋆ 11.5. Haszowanie doskonałe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
12. Drzewa wyszukiwań binarnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
12.1. Co to jest drzewo wyszukiwań binarnych? . . . . . . . . . . . . . . . . . . . . . 288
12.2. Wyszukiwanie w drzewie wyszukiwań binarnych . . . . . . . . . . . . . . . . 290
12.3. Wstawianie i usuwanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
⋆ 12.4. Losowo skonstruowane drzewa wyszukiwań binarnych . . . . . . . . . . . . . . 300
13. Drzewa czerwono-czarne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
13.1. Własności drzew czerwono-czarnych . . . . . . . . . . . . . . . . . . . . . . . 309
13.2. Operacje rotacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
13.3. Operacja wstawiania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
13.4. Operacja usuwania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
14. Wzbogacanie struktur danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
14.1. Dynamiczne statystyki pozycyjne . . . . . . . . . . . . . . . . . . . . . . . . . 342
14.2. Jak wzbogacać strukturę danych . . . . . . . . . . . . . . . . . . . . . . . . . . 347
14.3. Drzewa przedziałowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
Część IV Zaawansowane metody konstruowania i analizowania algorytmów
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
15. Programowanie dynamiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
15.1. Rozcinanie pręta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
VII
SPIS TREŚCI
15.2. Mnożenie ciągu macierzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
15.3. Podstawy programowania dynamicznego . . . . . . . . . . . . . . . . . . . . . 382
15.4. Najdłuższy wspólny podciąg . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
15.5. Optymalne drzewa wyszukiwań binarnych . . . . . . . . . . . . . . . . . . . . . 401
16. Algorytmy zachłanne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
16.1. Problem wyboru zajęć . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
16.2. Podstawy strategii zachłannej . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
16.3. Kody Huffmana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
⋆ 16.4. Matroidy a strategie zachłanne . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
⋆ 16.5. Problem szeregowania zadań . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
17. Analiza kosztu zamortyzowanego . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
17.1. Metoda kosztu sumarycznego . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
17.2. Metoda księgowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
17.3. Metoda potencjału . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
17.4. Tablice dynamiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
17.4.1. Powiększanie tablicy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
17.4.2. Powiększanie i zmniejszanie tablicy . . . . . . . . . . . . . . . . . . . . . . . . 474
Część V Złożone struktury danych
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
18. B-drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
18.1. Definicja B-drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
18.2. Podstawowe operacje na B-drzewach . . . . . . . . . . . . . . . . . . . . . . . . 498
18.3. Usuwanie klucza z B-drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
19. Kopce Fibonacciego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
19.1. Struktura kopców Fibonacciego . . . . . . . . . . . . . . . . . . . . . . . . . . 516
19.2. Operacje kopca złączalnego . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
19.3. Zmniejszanie wartości klucza i usuwanie węzła . . . . . . . . . . . . . . . . . . 527
19.4. Oszacowanie maksymalnego stopnia . . . . . . . . . . . . . . . . . . . . . . . . 531
20. Drzewa van Emde Boasa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
20.1. Wstępne koncepcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
20.2. Struktura rekurencyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
20.2.1. Prototypowe struktury van Emde Boasa . . . . . . . . . . . . . . . . . . . . . . 547
20.2.2. Operacje na prototypowej strukturze van Emde Boasa . . . . . . . . . . . . . . 549
20.3. Drzewo van Emde Boasa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
20.3.1. Drzewa van Emde Boasa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
20.3.2. Operacje na drzewie van Emde Boasa . . . . . . . . . . . . . . . . . . . . . . . 559
21. Struktury danych dla zbiorów rozłącznych . . . . . . . . . . . . . . . . . . . . . 571
21.1. Operacje na zbiorach rozłącznych . . . . . . . . . . . . . . . . . . . . . . . . . 571
21.2. Listowa reprezentacja zbiorów rozłącznych . . . . . . . . . . . . . . . . . . . . 574
VIII
SPIS TREŚCI
21.3. Lasy zbiorów rozłącznych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
⋆ 21.4. Analiza metody łączenia według rangi z kompresją ścieżki . . . . . . . . . . . 583
Część VI Algorytmy grafowe
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
22. Podstawowe algorytmy grafowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
22.1. Reprezentacja grafów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
22.2. Przeszukiwanie wszerz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
22.3. Przeszukiwanie w głąb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
22.4. Sortowanie topologiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
22.5. Silnie spójne składowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
23. Minimalne drzewa rozpinające . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
23.1. Rozrastanie się minimalnego drzewa rozpinającego . . . . . . . . . . . . . . . 637
23.2. Algorytmy Kruskala i Prima . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
24. Najkrótsze ścieżki z jednym źródłem . . . . . . . . . . . . . . . . . . . . . . . . . 656
24.1. Algorytm Bellmana-Forda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
24.2. Najkrótsze ścieżki z jednym źródłem w acyklicznych grafach . . . . . . . . . . . 668
24.3. Algorytm Dijkstry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
24.4. Ograniczenia różnicowe i najkrótsze ścieżki . . . . . . . . . . . . . . . . . . . . 678
24.5. Dowody własności najkrótszych ścieżek . . . . . . . . . . . . . . . . . . . . . . 684
25. Najkrótsze ścieżki między wszystkimi parami wierzchołków . . . . . . . . . . . 698
25.1. Najkrótsze ścieżki i mnożenie macierzy . . . . . . . . . . . . . . . . . . . . . . 700
25.2. Algorytm Floyda-Warshalla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
25.3. Algorytm Johnsona dla grafów rzadkich . . . . . . . . . . . . . . . . . . . . . . 714
26. Maksymalny przepływ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
26.1. Sieci przepływowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724
26.2. Metoda Forda-Fulkersona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729
26.3. Najliczniejsze skojarzenia w grafach dwudzielnych . . . . . . . . . . . . . . . . 747
⋆ 26.4. Algorytmy typu „prześlij-przemianuj” . . . . . . . . . . . . . . . . . . . . . . . 752
⋆ 26.5. Algorytm „przemianuj i przesuń na początek” . . . . . . . . . . . . . . . . . . 766
Część VII Wybrane zagadnienia
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
27. Algorytmy wielowątkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
27.1. Podstawy dynamicznej wielowątkowości . . . . . . . . . . . . . . . . . . . . . . 794
27.2. Wielowątkowe mnożenie macierzy . . . . . . . . . . . . . . . . . . . . . . . . . 812
27.3. Wielowątkowe sortowanie przez scalanie . . . . . . . . . . . . . . . . . . . . . 817
IX
SPIS TREŚCI
28. Operacje na macierzach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833
28.1. Rozwiązywanie układów równań liniowych . . . . . . . . . . . . . . . . . . . . 833
28.2. Odwracanie macierzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
28.3. Symetryczne macierze dodatnio określone i metoda najmniejszych kwadratów . 853
29. Programowanie liniowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863
29.1. Postać standardowa i uzupełnieniowa . . . . . . . . . . . . . . . . . . . . . . . 871
29.2. Formułowanie problemów w postaci programów liniowych . . . . . . . . . . . 879
29.3. Algorytm sympleks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
29.4. Dualność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 901
29.5. Początkowe bazowe rozwiązanie dopuszczalne . . . . . . . . . . . . . . . . . . 907
30. Wielomiany i FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920
30.1. Reprezentacja wielomianów . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922
30.2. DFT i FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 929
30.3. Efektywne implementacje FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . 937
31. Algorytmy teorioliczbowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948
31.1. Podstawowe pojęcia teorii liczb . . . . . . . . . . . . . . . . . . . . . . . . . . 950
31.2. Największy wspólny dzielnik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956
31.3. Arytmetyka modularna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
31.4. Rozwiązywanie modularnych równań liniowych . . . . . . . . . . . . . . . . . . 969
31.5. Chińskie twierdzenie o resztach . . . . . . . . . . . . . . . . . . . . . . . . . . 973
31.6. Potęgi elementu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976
31.7. System kryptograficzny z kluczem publicznym RSA . . . . . . . . . . . . . . . 981
⋆ 31.8. Sprawdzanie, czy dana liczba jest pierwsza . . . . . . . . . . . . . . . . . . . . 988
⋆ 31.9. Rozkład na czynniki pierwsze . . . . . . . . . . . . . . . . . . . . . . . . . . . 999
32. Wyszukiwanie wzorca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1009
32.1. Algorytm „naiwny” wyszukiwania wzorca . . . . . . . . . . . . . . . . . . . . 1012
32.2. Algorytm Rabina-Karpa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014
32.3. Wyszukiwanie wzorca z wykorzystaniem automatów skończonych . . . . . . . . 1019
⋆ 32.4. Algorytm Knutha-Morrisa-Pratta . . . . . . . . . . . . . . . . . . . . . . . . . . 1026
33. Geometria obliczeniowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1038
33.1. Własności odcinków . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1039
33.2. Sprawdzanie, czy jakakolwiek para odcinków się przecina . . . . . . . . . . . . 1046
33.3. Znajdowanie otoczki wypukłej . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053
33.4. Znajdowanie pary najmniej odległych punktów . . . . . . . . . . . . . . . . . . 1064
34. NP-zupełność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1073
34.1. Czas wielomianowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079
34.2. Weryfikacja w czasie wielomianowym . . . . . . . . . . . . . . . . . . . . . . . 1087
34.3. NP-zupełność i redukowalność . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092
34.4. Dowodzenie NP-zupełności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103
34.5. Problemy NP-zupełne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111
34.5.1. Problem kliki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1112
34.5.2. Problem pokrycia wierzchołkowego . . . . . . . . . . . . . . . . . . . . . . . . 1114
X
SPIS TREŚCI
34.5.3. Problem cyklu Hamiltona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1116
34.5.4. Problem komiwojażera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1121
34.5.5. Problem sumy podzbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1122
35. Algorytmy aproksymacyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1131
35.1. Problem pokrycia wierzchołkowego . . . . . . . . . . . . . . . . . . . . . . . . 1133
35.2. Problem komiwojażera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1137
35.2.1. Problem komiwojażera z nierównością trójkąta . . . . . . . . . . . . . . . . . . 1138
35.2.2. Ogólny problem komiwojażera . . . . . . . . . . . . . . . . . . . . . . . . . . . 1140
35.3. Problem pokrycia zbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1143
35.4. Randomizacja i programowanie liniowe . . . . . . . . . . . . . . . . . . . . . . 1148
35.5. Problem sumy podzbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1153
Część VIII Dodatek: Podstawy matematyczne
Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1168
A. Sumy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1170
A.1. Wzory i własności dotyczące sum . . . . . . . . . . . . . . . . . . . . . . . . . 1170
A.2. Szacowanie sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174
B. Zbiory i nie tylko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183
B.1. Zbiory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183
B.2. Relacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1188
B.3. Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1190
B.4. Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1193
B.5. Drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1197
B.5.1. Drzewa wolne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1198
B.5.2. Drzewa ukorzenione i uporządkowane . . . . . . . . . . . . . . . . . . . . . . . 1200
B.5.3. Drzewa binarne i pozycyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1201
C. Zliczanie i prawdopodobieństwo . . . . . . . . . . . . . . . . . . . . . . . . . . . 1206
C.1. Zliczanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1206
C.2. Prawdopodobieństwo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212
C.3. Dyskretne zmienne losowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1219
C.4. Rozkłady: geometryczny i dwumianowy . . . . . . . . . . . . . . . . . . . . . . 1224
⋆ C.5. Krańce rozkładu dwumianowego . . . . . . . . . . . . . . . . . . . . . . . . . . 1230
D. Macierze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1239
D.1. Macierze i operacje na macierzach . . . . . . . . . . . . . . . . . . . . . . . . . 1239
D.2. Podstawowe własności macierzy . . . . . . . . . . . . . . . . . . . . . . . . . . 1244
Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1252
Skorowidz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1269
powrót
 
Produkty Podobne
Algorytmy, struktury danych i techniki programowania dla programistów Java
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Algorytmy, struktury danych i techniki programowania. Wydanie VI
Zrozum struktury danych. Algorytmy i praca na danych w Javie
Algorytmy. Ilustrowany przewodnik
Inteligentna sieć. Algorytmy przyszłości. Wydanie II
Naczelny Algorytm. Jak jego odkrycie zmieni nasz świat
Algorytmy
Algorithms in a Nutshell, 2nd Edition
Piramidy, szyszki i inne konstrukcje algorytmiczne
Więcej produktów