Wprowadzenie do algorytmów /

Author: Cormen, Thomas H.
Additionaly authors: Leiserson, Charles E. | Rivest, Ronald L. | Stein, Clifford. | Diks, Krzysztof.--Tł. Edition statementWyd. 7. Publisher: Wydawnictwo Naukowe PWN, (Warszawa : ) , 2013 Physical description: XIX, [1], 1300 s. : il. ; 25 cm. ISBN:. Keywords: Algorytm grafowy | Algorytm | Struktury danych | Sortowanie | Statystyka pozycyjna | Projektowanie algorytmów
pol
List(s) this item appears in: Matematyka dyskretna
Tags from this library:
No tags from this library for this title.
    rate: 0.0 (Voices: 0)
Item type Location Call number Status Unavailable to
Czytelnia (tylko na miejscu) Czytelnia (tylko na miejscu) Poznań
004 (Browse shelf) Not for loan
Czytelnia (można wypożyczyć) Czytelnia (można wypożyczyć) Poznań
004 (Browse shelf) Currently in local use 2020-03-06

Spis Treści
Przedmowa
Częśc I
Podstawy
Wprowadzenie

1. Rola Algorytmów Obliczeniach
1.1. Algorytmy
1.2. Algorytmy Jako Technologia
2. Zaczynamy
2.1. Sortowanie Przez Wstawianie
2.2. Analiza Algorytmów
2.3. Projektowanie Algorytmów
2.3.1. Metoda„dzielizwycięŜaj"
2.3.2. Analiza Algorytmów Typu„dzielizwycięŜaj"
3. Rzędy Wielkości Funkcji
3.1. Notacja Asymptotyczna
3.2. Standardowej Notacji Typowe Funkcje
4. Metoda„dzielizwycięŜaj"
4.1. Problem Maksymalnej Podtablicy
4.2. AlgorytmStrassenamnoŜeniamacierzy
4.3. Metoda Podstawiania
4.4. Metoda Drzewo Rekursji
4.5. Metoda Rekurencji Uniwersalnej
4.6. Dowód Twierdzenie O'Rekurencji Uniwersalnej
4.6.1. Dowód Dla Dokładnych Potęg
4.6.2. Podłogi Sufity
5. Analiza Probabilistyczna Algorytmy Random Izowaneh
5.1. Problem Zatrudnienia Sekretarki
5.2. Zmienne Losowe Wskaźnikowe
5.3. Algorytmy Randomizowane
5.4. Analiza Probabilistyczna Dalsze Zastosowanie zamiennych losowych wskaźnikowych
5.4.1. Paradoks Dnia Urodzin
5.4.2. Kulinarny
5.4.3. Ciągi„dobrej passy",czyli sukcesów
5.4.4. Problem Online Zatrudnienia Sekretarki

Część II
Sortowanie Statystyki Pozycyjne
Wprowadzenie
6. Heap Sort Sortowanie Przez Kopcowanie
6.1. Kopce
6.2. Przywracanie Własności Kopca
6.3. Budowanie Kopca
6.4. Algorytm Sortowania Przez Kopcowanie(heapsort)
6.5. Kolejki Priorytetowe
7. Quick Sort Sortowanie Szybkie
7.1. Opis Algorytmu
7.2. Czas Działania Algorytmu Quicksort
7.3. Randomizowana Wersja Algorytmu Quicksort
7.4. Analiza Algorytmu Quicksort
7.4.1. Analiza Przypadku Pesymistycznego
7.4.2. Analiza Oczekiwanego Czasu Działania
8. Sortowanie Czasie Liniowym
8.1. Dolne Ograniczenie Dla Problemu Sortowania
8.2. Sortowanie Przez Zliczanie
8.3. Sortowanie Pozycyjne
8.4. Sortowanie Kubełkowe
9. Mediany Statystyki Pozycyjne
9.1. Minimum Maximum
9.2. Wybór Oczekiwanym Czasie Liniowym
9.3. Wybór Pesymistycznym Czasie Liniowym

Część III
Struktury Danych
Wprowadzenie
10. Elementarne Struktury Danych
10.1. Stosy Kolejki
10.2. Listy(z dowiązaniami)
10.3. Reprezentowanie Struktur Wskaźnikowych Zapom
ocą tablic
10.4. Reprezentowanie Drzew(ukorzenionych)
11. Tablice Z Haszowaniem
11.1. Tablice Z Adresowaniem Bezpośrednim
11.2. Tablice Z Haszowaniem
11.3. Funkcje Haszujące
11.3.1.Haszowanie Modularne
11.3.2.Haszowanie przez mnożenie
11.3.3.Haszowanie Uniwersalne
11.4. Adresowanie Otwarte
11.5.Haszowanie Doskonałe
12. Drzewa Wyszukiwań Binarnych
12.1. Cotojest Drzewa Wyszukiwań Binarnych?
12.2. Wyszukiwanie Drzewa Wyszukiwań Binarnych
12.3. Wstawianie Usuwanie
12.4.Losowo Skonstruowane Drzewa Wyszukiwań Binarnych
13. Drzewa Czerwono Czarne
13.1. Własności Drzew Czerwono 8 Czarnych
13.2. Operacje Rotacji
13.3. Operacja Wstawiania
13.4. Operacja Usuwania
14. Wzbogacanie Struktury Danych
14.1. Dynamiczne Statystyki Pozycyjne
14.2. Jak Wzbogacać Strukturę Danych
14.3. Drzewa Przedziałowe

Część IV
Zaawansowane Metody Konstruowania I Analizowania Algorytmów
Wprowadzenie
15.Programowanie Dynamiczne
15.1. Rozciąganie Pręta
15.2. Mnożenie ciągu macierzy
15.3. Podstawy Programowania Dynamicznego
15.4. Najdłuższy wspólny podciąg
15.5. Optymalne Drzewa Wyszukiwań Binarnych
16. Algorytmy Zachłanne
16.1. Problem Wyboru Zajęć
16.2. Podstawy Strategii Zachłannej
16.3. KodyHuffmana
16.4.Matroidyastrategiezachłanne
16.5.Problem Szeregowania Zadań
17. Analiza Kosztu Zamortyzowanego
17.1. Metoda Kosztu Sumarycznego
17.2. Metoda Księgowania
17.3. Metoda Potencjału
17.4. Tablice Dynamiczne
17.4.1.Powiększenie Tablicy
17.4.2.Powiększanie Zmniejszanie Tablicy

Część V
Złożone struktury danych
Wprowadzenie
18. Drzewa
18.1. Definicja B8 drzewa
18.2. Podstawowe operacje na 8 drzewach
18.3. Usuwanie klucza z B-drzewa
19. Kopce Fibonacciego
19.1. Struktura kopców Fibonacciego
19.2. Operacje Kopca Złączalnego
19.3. Zmniejszanie Wartości Klucza Usuwanie Węzła
19.4. Oszacowanie Maksymalnego Stopnia
20. Drzewa van Emde Boas
20.1. Wstępne Koncepcje
20.2. Struktura Rekurencyjna
20.2.1.Prototype we struktury van Emde Boas
20.2.2.Operacje na prototypowej strukturze and eBoasa
20.3. Drzewo van Emde Boas
20.3.1.Drzewa van Emde Boas
20.3.2.Operacje na drzewie van Emde Boas
21. Struktury Danych Dla Zbiorów Rozłącznych
21.1. Operacje Na Zbiorach Rozłącznych
21.2. List Reprezentacja Zbiorów Rozłącznych
21.3. Lasy Zbiorów Rozłącznych
21.4.Analiza Metody Łączenia Według Rangi Kompresją ścieżki

Część VI
Algorytmy Grafowe
Wprowadzenie
22. Podstawowe Algorytmy Grafowe
22.1. Reprezentacja Grafów
22.2. Przeszukiwanie Wszerz
22.3. Przeszukiwanie W Głąb
22.4. Sortowanie Topologiczne
22.5. Silnie Spójne Składowe
23. Minimalne Drzewa Rozpinające
23.1. Rozrastanie Się Minimalne Drzewa Rozpinającego
23.2. Algorytm Kruskala Prima
24. Najkrótsze Ścieżki Jednym Źródłem
24.1. Algorytm Bellmana 8 Forda
24.2. Najkrótsze Ścieżki Z Jednym Źródłem Wacyk Licznych grafach
24.3. Algorytm Dijkstry
24.4. Ograniczenia Różnicowe Najkrótsze Ścieżki
24.5. Dowody Własności Najkrótszych Ścieżek
25. Najkrótsze Ścieżki Między Wszystkimi Parami Wiechołków
25.1. Najkrótsze Ścieżki Mnożenie Macierzy
25.2. Algorytm Floyda 8 Warshalla
25.3. Algorytm Johnsona dla grafów rzadkich
26. Maksymalny Przepływ
26.1. Sieci Przepływowe
26.2. Metoda Forda Fulkersona
26.3. Najliczniejsze Skojarzenia W Grafach Dwudzielnych
26.4.Algorytmy Typu„prześlij 8 przemianuj"
26.5.Algorytm„przemianuj przesuń na początek"

Część II
Wybrane zagadnienia
Wprowadzenie

27. Algorytmy Wielowątkowe
27.1. Podstawy Dynamicznej Wielowątkowości
27.2. WielowątkowemnoŜeniemacierzy
27.3. Wielowątkowe Sortowanie Przez Scalanie
28. Operacje Na Macierzach
28.1. Rozwiązywanie Układów Równań Liniowych
28.2. Odwracanie Macierzy
28.3. Symetryczna Macierz Dodatnio Określona Metoda najmniejszych kwadratów
29. Programowanie Liniowe
29.1. Postać Standardowa Uzupełnieniowa
29.2. Formułowanie Problemów W Postaci Programów niowych
29.3. Algorytm Sympleks
29.4. Dualność
29.5. Początkowe Bazowe Rozwiązanie Dopuszczalne
30. Wielomiany iFFT
30.1. Reprezentacja Wielomianów
30.2. DFTiFFT
30.3. Efektywne implementacje FFT
31. Algorytmy Teorioliczbowe
31.1. Podstawowe Pojęcia Teorii Liczb
31.2. Największy Wspólny Dzielnik
31.3. Arytmetyka Modularna
31.4. Rozwiązywanie Modularnych Równań Liniowych
31.5. Chińskie Twierdzenie O'Resztach
31.6. Potęgielementu
31.7. System kryptograficzny z kluczem publicznym RSA
31.8.Sprawdzanie,czy dana liczba jest pierwsza
31.9.Rozkład Na Czynniki Pierwsze
32. Wyszukiwanie Wzorca
32.1. Algorytm„naiwny"wyszukiwania wzorca
32.2. Algorytm Rabina 8 Karpa
32.3. Wyszukiwanie Wzorca Z Wykorzystaniem Automatów
skończonych
32.4.Algorytm Knutha 8 Morrisa 8 Pratta
33. Geometria Obliczeniowa
33.1. Własności Odcinków
33.2. Sprawdzanie,czy jakakolwiek para odcinków
przecina
33.3. Znajdowanie Otoczki Wypukłej
33.4. Znajdowanie Pary Najmniej Odległych Punktów
34. NP zupełność
34.1. Czas Wielomianowy
34.2. Weryfikacja W Czasie Wielomianowym
34.3. NP zupełność redukowalność
34.4. Dowodzenie NP zupełności
34.5. Problemy NP zupełne
34.5.1.Problem Kliki
34.5.2.Problem Pokrycia Wierzchołkowego
34.5.3.Problem cyklu Hamiltona
34.5.4.Problem Komiwojażera
34.5.5.Problem Sumy Podzbioru
35. Algorytmy Aproksymacyjne
35.1. Problem Pokrycia Wierzchołkowego
35.2. Problem Komiwojażera
35.2.1.Problem Komiwojażera Z Nierównością Trójkąta
35.2.2.Ogólny Problem Komiwojażera
35.3. Problem Pokrycia Zbioru
35.4. Randomizacja Programowanie Liniowe
35.5. Problem Sumy Podzbioru

Część VIII
Dodatek:Podstawy Matematyczne
Wprowadzenie
A. Sumy
1170
A.1. Wzory Własności Dotyczące Sum
1170
A.2. Szacowanie Sum
1174
B. Zbiory 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 Uporządkowane
B.5.3. Drzewa Binarne Pozycyjne
1201
C. Zliczanie Prawdopodobieństwo
C.1. Zliczanie
1206
C.2. Prawdopodobieństwo
1212
C.3. Dyskretne Zmienne Losowe
1219
C.4. Rozkłady:geometryczny dwumianowy
*C.5.Krańce Rozkładu Dwumianowego
1230
D. Macierze
1239
D.1. Macierze Operacje Na Macierzach
1239
D.2. Podstawowe Własności Macierzy
1244
Bibliografia
1252
Skorowidz
1269

Bibliogr. s. 1252-1268. Indeks.

Click on an image to view it in the image viewer

Languages: