Algorytmy i struktury danych. Wybrane zagadnienia (wyd.2, 2010)  

Zbigniew J. Czech, Sebastian Deorowicz,Piotr Fabian Wydawnictwo Politechniki Śląskiej
ISBN: 978[zasłonięte][zasłonięte]33566
rok wydania: 2010 (wyd.II)
stron: 225
oprawa: miękka
format: B5 

Książka poświęcona jest wybranym zagadnieniom dotyczącym algorytmów i struktur danych. Dobry algorytm oraz właściwie dobrana struktura danych stanowią podstawę efektywnego programu komputerowego, dlatego dużą wagę przykłada się do złożoności obliczeniowej algorytmów, różnorodności struktur danych oraz ich przydatności w konkretnych zastosowaniach. Omawiane są podstawowe metody układania algorytmów, takie jak "dziel i zwyciężaj", programowanie dynamiczne, postępowanie zachłanne oraz wyszukiwanie wyczerpujące. Prezentowane są wybrane algorytmy rozwiązywania problemów sortowania, wyszukiwania, generowania obiektów kombinatorycznych, kompresji danych oraz problemów związanych z grafami.


SPIS TREŚCI:

1. WYBRANE ELEMENTY MATEMATYKI DYSKRETNEJ
1.1. Wprowadzenie
1.2. Problem wież w Hanoi
1.2.1. Indukcja matematyczna
1.2.2. Zmienna pomocnicza
1.3. Sumy
1.3.1. Własności sum
1.3.2. Metoda zaburzania
1.3.3. Różniczkowanie
1.3.4. Sumy jako równania rekurencyjne
1.3.5. Metoda czynnika sumacyjnego
1.4. Szereg harmoniczny
1.5. Szacowanie wartości n!
1.6. Współczynniki dwumianowe
1.7. Zadania
Bibliografia

2. WYZNACZANIE ZŁOŻONOŚCI PROSTYCH ALGORYTMÓW
2.1. Wprowadzenie
2.2. Znajdowanie minimalnego i maksymalnego elementu w tablicy
2.2.1. Algorytm minmax1
2.2.2. Algorytm minmax2
2.2.3. Algorytm minmax3
2.2.4. Porównanie algorytmów
2.3. Sortowanie minimax
2.4. Zadania
Bibliografia

3. PROSTE ALGORYTMY SORTOWANIA
3.1. Wprowadzenie
3.2. Sortowanie przez proste wybieranie
3.3. Sortowanie przez proste wstawianie
3.3.1. Proste wstawianie 1 - bez wartownika
3.3.2. Proste wstawianie 2 - z wartownikiem
3.3.3. Ulepszenie algorytmu sortowania przez proste wstawianie
3.4. Sortowanie Shella
3.5. Porównanie złożoności algorytmów sortowania
3.6. Zadania
Bibliografia

4. SORTOWANIE SZYBKIE ORAZ WYZNACZANIE k-TEGO CO DO WIELKOŚCI ELEMENTU
4.1. Sortowanie szybkie
4.1.1. Ogólna wersja sortowania szybkiego
4.1.2. Algorytm sortowania szybkiego
4.1.3. Wybór klucza osiowego
4.1.4. Porównanie różnych wersji algorytmów sortowania szybkiego
4.2. Algorytmy wyboru k-tego co do wielkości elementu
4.2.1. Wybór w średnim czasie liniowym
4.2.2. Wybór w pesymistycznym czasie liniowym
4.3. Zadania
Bibliografia

5. STRUKTURY DRZEWIASTE
5.1. Wprowadzenie
5.2. Drzewa binarne
5.3. Drzewa poszukiwań binarnych
5.3.1. Wyszukiwanie elementu
5.3.2. Wyszukiwanie elementu minimalnego i maksymalnego
5.3.3. Wyszukiwanie następnika
5.3.4. Wstawianie nowego elementu
5.3.5. Usuwanie elementu
5.4. Drzewa zrównoważone
5.5. Listy z przeskokami
5.5.1. Wyszukiwanie elementów
5.5.2. Operacja usuwania
5.5.3. Operacja wstawiania
5.5.4. Złożoność operacji słownikowych
5.6. Zadania
Bibliografia

6. TABLICE MIESZAJĄCE
6.1. Wprowadzenie
6.2. Tablice i funkcje mieszające
6.3. Kolizje i metody ich rozwiązywania
6.3.1. Metoda łańcuchowa
6.3.2. Adresowanie liniowe
6.3.3. Adresowanie kwadratowe
6.3.4. Podwójne mieszanie
6.3.5. Typowe funkcje mieszające
6.4. Restrukturyzacja tablic mieszających
6.5. Doskonałe funkcje mieszające
6.6. Zadania
Bibliografia

7. PROGRAMOWANIE DYNAMICZNE
7.1.Wprowadzenie
7.2. Wyznaczanie liczb Fibonacciego
7.2.1. Rozwiązywanie rekursywne
7.2.2. Rozwiązywanie iteracyjne
7.3. Wyznaczanie podciągu podtablicy o maksymalnej sumie
7.3.1. Wprowadzenie
7.3.2. Podciąg o maksymalnej sumie
7.3.3. Podtablica o maksymalnej sumie
7.4. Wyznaczanie odległości edycyjnej
7.5. Zadania
Bibliografia

8. ALGORYTMY GRAFOWE
8.1. Wprowadzenie
8.2. Oznaczenia i pojęcia
8.3. Metody reprezentowania grafów w pamięci komputera
8.4. Algorytmy wyznaczania najkrótszych dróg w grafie ważonym
8.5. Algorytm Floyda-Warshalla
8.6. Algorytm Dijkstry
8.7. Zadania
Bibliografia