Algorytmy komputerowe i struktury danych
T. Adamski
J. Ogrodzki
Rok: 2005
Stron: 214
Algorytmy komputerowe i struktury danych to przedmiot podstawowy należący współcześnie do zasadniczego wykształcenia każdego inżyniera informatyka, elektronika czy inżyniera telekomunikacji.
Podręcznik "Algorytmy komputerowe i struktury danych" jest standardowym, typowym dla wszystkich wydziałów informatycznych politechnik wykładem z algorytmów komputerowych. Po krótkim wprowadzeniu w zagadnienia związane z projektowaniem algorytmów omawiane są po kolei: złożoność obliczeniowa, algorytmy sortowania, algorytmy wyszukiwania wzorca, algorytmy grafowe i słowniki.
SPIS TREŚCI
Przedmowa
Spis oznaczeń
1. WPROWADZENIE
1.1. Algorytm, analiza i projektowanie algorytmów
1.2. Złożoność obliczeniowa algorytmu - podstawowe pojęcia
1.3. Sposoby opisu algorytmów
1.4. Zapisy asymptotyczne
1.5. Elementarne struktury danych
1.6. Rekurencja i metody projektowania algorytmów
1.7. Równania rekurencyjne
1.8. Algorytmy probabilistyczne
2. KLASY ZŁOŻONOŚCI OBLICZENIOWEJ ALGORYTMÓW I NP-ZUPEŁNOŚĆ
2.1. Teoria złożoności obliczeniowej
2.2. Problemy obliczeniowe
2.3. Problemy decyzyjne
2.4. Klasy złożoności
2.5. Klasy złożoności algorytmów probabilistycznych
3. ALGORYTMY SORTOWANIA
3.1. Problem sortowania
3.2. Sortowanie bąbelkowe (bubblesort)
3.3. Zmodyfikowane sortowanie bąbelkowe (modified bubblesort)
3.4. Sortowanie przez wstawianie (insertionsort)
3.5. Sortowanie przez selekcję (selectionsort)
3.6. Sortowanie przez scalanie (mergesort)
3.7. Sortowanie przez kopcowanie (heapsort)
3.8. Sortowanie szybkie (quicksort)
3.9. Szybkie algorytmy wyznaczania k-tego elementu co do wartości w ciągu
3.10. Algorytmy sortowania w czasie liniowym (countsort, radixsort, bucketsort)
3.11. Sortowanie zewnętrzne
3.12. Sieci sortujące
4. ALGORYTMY WYSZUKIWANIA WZORCA
4.1. Problem wyszukiwania wzorca
4.2. Algorytm naiwny wyszukiwania wzorca
4.3. Algorytm Rabina-Karpa
4.4. Algorytm wyszukiwania wzorca wykorzystujący automat skończony
4.5. Algorytm Knutha-Morrisa-Pratta
5. ALGORYTMY GRAFOWE
5.1. Wprowadzenie
5.2. Przeszukiwanie grafu wszerz
5.3. Przeszukiwanie grafu w głąb
5.4. Grafy ważone skierowane. Problem najkrótszej ścieżki z jednym źródłem
6. SŁOWNIKI I OPERACJE NA SŁOWNIKACH
6.1. Wprowadzenie
6.2. Algorytmy słownikowe o złożoności liniowej
6.3. Algorytmy wykorzystujące słownik liniowo uporządkowany zaimplementowany w tablicach
6.4. Słownik zaimplementowany w drzewie poszukiwań binarnych
6.5. Słownik liniowo uporządkowany zaimplementowany w tablicach indeksowanych kluczem
6.6. Słownik liniowo uporządkowany zaimplementowany w tablicach z haszowaniem
Literatura |
