WPROWADZENIE DO ALGORYTMÓW CORMEN T.H. LEISERSON C.E. RIVEST R.L. STEIN C. Księgarnia

Wprowadzenie do algorytmów

Nowe wydanie najlepszego na świecie podręcznika z dziedziny algorytmów i struktur danych.

Omówiono w nim 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.

W nowym wydaniu znajdziesz:

- nowe rozdziały dotyczące dopasowania w grafach dwudzielnych, algorytmów online i uczenia maszynowego,
- zaktualizowany materiał dotyczący rozwiązywania równań rekurencyjnych, tablic z haszowaniem, potencjalnych funkcji i tablic sufiksów,
- 140 nowych ćwiczeń i 22 nowe problemy do rozwiązania.

Poszczególne części książki to materiał dydaktyczny do wielu przedmiotów informatycznych, takich jak: matematyka dyskretna, kombinatoryka, algorytmy i struktury danych, teoria grafów, metody programowania. Publikacja jest niezbędnym źródłem wiedzy dla wszystkich, którzy chcą zajmować się projektowaniem i programowaniem systemów informatycznych.

I Podstawy

Wprowadzenie 3

1 Rola algorytmów w obliczeniach 5
1.1 Algorytmy 5
1.2 Algorytmy jako technologia 11

2 Zaczynamy 16
2.1 Sortowanie przez wstawianie 16
2.2 Analiza algorytmów 24
2.3 Projektowanie algorytmów 31

3 Rzędy wielkości funkcji ´ 46
3.1 Notacje O, i ‚ 47
3.2 Notacja asymptotyczna: definicje formalne 50
3.3 Standardowe notacje i typowe funkcje 59

4 Metoda „dziel i zwycięzaj" ˙ 71
4.1 Mnozenie macierzy kwadratowych ˙ 75
4.2 Algorytm Strassena mnozenia macierzy ˙ 79
4.3 Metoda podstawiania 84
4.4 Metoda drzewa rekursji 89
4.5 Metoda rekurencji uniwersalnej 95
? 4.6 Dowód ciągłej wersji twierdzenia o rekurencji uniwersalnej 100
? 4.7 Rekurencje Akry-Bazziego 108

5 Analiza probabilistyczna i algorytmy randomizowane 119
5.1 Problem zatrudnienia sekretarki 119
5.2 Zmienne losowe wska´znikowe 122
5.3 Algorytmy randomizowane 127
? 5.4 Analiza probabilistyczna i dalsze zastosowania zmiennych losowych wskaźnikowych 132

II Sortowanie i statystyki pozycyjne

Wprowadzenie 149

6 Heapsort – sortowanie przez kopcowanie 153
6.1 Kopce 153
6.2 Przywracanie własnosci kopca ´ 156
6.3 Budowanie kopca 158
6.4 Algorytm sortowania przez kopcowanie (heapsort) 161
6.5 Kolejki priorytetowe 163

7 Quicksort – sortowanie szybkie 172
7.1 Opis algorytmu 173
7.2 Czas działania algorytmu quicksort 177
7.3 Randomizowana wersja algorytmu quicksort 181
7.4 Analiza algorytmu quicksort 182

8 Sortowanie w czasie liniowym 193
8.1 Dolne ograniczenia dla problemu sortowania 193
8.2 Sortowanie przez zliczanie 196
8.3 Sortowanie pozycyjne 199
8.4 Sortowanie kubełkowe 203

9 Mediany i statystyki pozycyjne 214
9.1 Minimum i maksimum 215
9.2 Wybór w oczekiwanym czasie liniowym 216
9.3 Wybór w pesymistycznym czasie liniowym 223

III Struktury danych

Wprowadzenie 235

10 Elementarne struktury danych 238
10.1 Proste tablicowe struktury danych: tablice, macierze, stosy i kolejki 238
10.2 Listy (z dowiązaniami) 244
10.3 Reprezentowanie drzew (ukorzenionych) 249

11 Tablice z haszowaniem 256
11.1 Tablice z adresowaniem bezposrednim ´ 257
11.2 Tablice z haszowaniem 259
11.3 Funkcje haszujące 266
11.4 Adresowanie otwarte 276
11.5 Rozwazania praktyczne ˙ 284

12 Drzewa wyszukiwan binarnych ´ 294
12.1 Co to jest drzewo wyszukiwan binarnych? ´ 294
12.2 Wyszukiwanie w drzewie wyszukiwan binarnych ´ 297
12.3 Wstawianie i usuwanie 302

13 Drzewa czerwono-czarne 312
13.1 Własnosci drzew czerwono-czarnych ´ 312
13.2 Operacje rotacji 316
13.3 Operacja wstawiania 318
13.4 Operacja usuwania 327

IV Zaawansowane metody konstruowania i analizowania algorytmów

Wprowadzenie 341

14 Programowanie dynamiczne 342
14.1 Rozcinanie pręta 343
14.2 Mnozenie ciągu macierzy ˙ 352
14.3 Podstawy programowania dynamicznego 360
14.4 Najdłuzszy wspólny podciąg ˙ 371
14.5 Optymalne drzewa wyszukiwan binarnych ´ 376

15 Algorytmy zachłanne 392
15.1 Problem wyboru zajęc´ 393
15.2 Podstawy strategii zachłannej 400
15.3 Kody Huffmana 405
15.4 Zarządzanie pamięcią podręczną w trybie offline 413

16 Analiza kosztu zamortyzowanego 421
16.1 Metoda kosztu sumarycznego 422
16.2 Metoda księgowania 426
16.3 Metoda potencjału 428
16.4 Tablice dynamiczne 432

V Złozone struktury danych ˙

Wprowadzenie 449

17 Wzbogacanie struktur danych 452
17.1 Dynamiczne statystyki pozycyjne 452
17.2 Jak wzbogacac strukturę danych ´ 458
17.3 Drzewa przedziałowe 461

18 B-drzewa 469
18.1 Definicja B-drzewa 473
18.2 Podstawowe operacje na B-drzewach 476
18.3 Usuwanie klucza z B-drzewa 483

19 Struktury danych dla zbiorów rozłącznych 490
19.1 Operacje na zbiorach rozłącznych 490
19.2 Listowa reprezentacja zbiorów rozłącznych 493
19.3 Lasy zbiorów rozłącznych 497
19.4 Analiza metody łączenia według rangi z kompresją scieżki ˙ 501

VI Algorytmy grafowe

Wprowadzenie 515

20 Podstawowe algorytmy grafowe 517
20.1 Reprezentacje grafów 517
20.2 Przeszukiwanie wszerz 521
20.3 Przeszukiwanie w głąb 530
20.4 Sortowanie topologiczne 539
20.5 Silnie spójne składowe 543

21 Minimalne drzewa rozpinające 551
21.1 Rozrastanie się minimalnego drzewa rozpinającego 552
21.2 Algorytmy Kruskala i Prima 557

22 Najkrótsze scieżki z jednym źródłem ˙ 569
22.1 Algorytm Bellmana-Forda 576
22.2 Najkrótsze scieżki z jednym źródłem w acyklicznych grafach . . . ˙ 580
22.3 Algorytm Dijkstry 584
22.4 Ograniczenia róznicowe i najkrótsze ścieżki ˙ 590
22.5 Dowody własnosci najkrótszych ´ scieżek ˙ 596

23 Najkrótsze scieżki między wszystkimi parami wierzchołków ˙ 609
23.1 Najkrótsze scieżki i mno ˙ zenie macierzy ˙ 611
23.2 Algorytm Floyda-Warshalla 617
23.3 Algorytm Johnsona dla grafów rzadkich 624

24 Maksymalny przepływ 632
24.1 Sieci przepływowe 633
24.2 Metoda Forda-Fulkersona 638
24.3 Najliczniejsze skojarzenia w grafach dwudzielnych 654

25 Skojarzenia w grafach dwudzielnych 665
25.1 Najliczniejsze skojarzenia w grafach dwudzielnych (raz jeszcze) 666
25.2 Problem stabilnych małze˙ nstw ´ 676
25.3 Algorytm węgierski dla problemu przydziału 682

VII Wybrane zagadnienia

Wprowadzenie 703

26 Algorytmy równoległe 706
26.1 Podstawy równoległosci typu fork-join ´ 708
26.2 Równoległe mnozenie macierzy ˙ 727
26.3 Równoległe sortowanie przez scalanie 731

27 Algorytmy online 746
27.1 Czekając na windę 747
27.2 Utrzymywanie listy wyszukiwania 750
27.3 Zrządzanie pamięcią podręczną online 756

28 Operacje na macierzach 772
28.1 Rozwiązywanie układów równań liniowych ´ 772
28.2 Odwracanie macierzy 785
28.3 Symetryczne macierze dodatnio okreslone i metoda najmniejszych kwadratów ´ 790

29 Programowanie liniowe 801
29.1 Formułowanie programów liniowych i algorytmy 804
29.2 Formułowanie problemów w postaci programów liniowych 810
29.3 Dualność 816

30 Wielomiany i FFT 826
30.1 Reprezentacja wielomianów 828
30.2 DFT i FFT 834
30.3 Układy obliczające dla FFT 842

31 Algorytmy teorioliczbowe 851
31.1 Podstawowe pojęcia teorii liczb 852
31.2 Największy wspólny dzielnik 858
31.3 Arytmetyka modularna 863
31.4 Rozwiązywanie modularnych równan liniowych ´ 870
31.5 Chinskie twierdzenie o resztach ´ 874
31.6 Potęgi elementu 877
31.7 System kryptograficzny z kluczem publicznym RSA 881
? 31.8 Sprawdzanie, czy dana liczba jest pierwsza 888

32 Wyszukiwanie wzorca 901
32.1 Algorytm „naiwny” wyszukiwania wzorca 904
32.2 Algorytm Rabina-Karpa 906
32.3 Wyszukiwanie wzorca z wykorzystaniem automatów skonczonych ´ 910
32.4 Algorytm Knutha-Morrisa-Pratta 917
32.5 Tablice sufiksowe 926

33 Algorytmy uczenia maszynowego 943
33.1 Grupowanie (klasteryzacja) 945
33.2 Algorytmy multiplikatywnych wag 954
33.3 Zejscie gradientowe ´ 961

34 NP-zupełność´ 980
34.1 Czas wielomianowy 985
34.2 Weryfikacja w czasie wielomianowym 992
34.3 NP-zupełność i redukowalność 997
34.4 Dowodzenie NP-zupełnosci ´ 1007
34.5 Problemy NP-zupełne 1014

35 Algorytmy aproksymacyjne 1036
35.1 Problem pokrycia wierzchołkowego 1038
35.2 Problem komiwojazera ˙ 1041
35.3 Problem pokrycia zbioru 1047
35.4 Randomizacja i programowanie liniowe 1050
35.5 Problem sumy podzbioru 1055

VIII Dodatek: Podstawy matematyczne

Wprowadzenie 1069

A Sumy 1070
A.1 Wzory i własnosci dotyczące sum ´ 1070
A.2 Szacowanie sum 1075
B Zbiory i nie tylko 1083
B.1 Zbiory 1083
B.2 Relacje 1088
B.3 Funkcje 1090
B.4 Grafy 1093
B.5 Drzewa 1097

C Zliczanie i prawdopodobienstwo ´ 1106
C.1 Zliczanie 1106
C.2 Prawdopodobienstwo ´ 1112
C.3 Dyskretne zmienne losowe 1118
C.4 Rozkłady: geometryczny i dwumianowy 1124
? C.5 Krance rozkładu dwumianowego ´ 1130

D Macierze 1140
D.1 Macierze i operacje na macierzach 1140
D.2 Podstawowe własnosci macierzy ´ 1145

Bibliografia 1152
Skorowidz 1173

1190 stron, Format: 20.0x24.0cm, oprawa miękka

Po otrzymaniu zamówienia poinformujemy,
czy wybrany tytuł polskojęzyczny lub anglojęzyczny jest aktualnie na półce księgarni.