ALGORYTMY STRUKTURY DANYCH I ZŁOŻONOŚĆ OBLICZENIOWA

ISBN: 978-83-283-9530-5   126 stron format: A5 oprawa: miękka Rok wydania: 2022

Algorytmy to skończone ciągi jasno zdefiniowanych czynności, prowadzących do wykonania określonych zadań. Niniejszy podręcznik, skupiony na algorytmach imperatywnych (od łacińskiego słowa imporo - rozkazywać) wprowadza podstawowe pojęcia algorytmiki niezbędne do nauki programowania. Uczy projektowania, zapisywania i analizy poprawności, jak również podstaw szacowania złożoności czasowej i pamięciowej algorytmów.

Wraz z książką, którą trzymasz w ręku między innymi:

Poznasz szereg ważnych algorytmów, jak wyszukiwanie binarne, sortowanie szybkie, algorytmy klasy dziel i zwyciężaj, algorytmy zachłanne etc.
Nauczysz się korzystać ze stosowanych powszechnie w programowaniu struktur danych: tablic, słowników, list wiązanych, stosów, kolejek, drzew binarnych i grafów.
Dowiesz się jak praktycznie stosować iterację i rekurencję w programowaniu.
Zdobędziesz podstawy języka Java

W książce zamieszczono szereg zadań, których rozwiązanie zmusza czytelnika do lepszego zrozumienia i pogłębienia jego umiejętności praktycznych. Książka jest bogato ilustrowana rysunkami poglądowymi i fragmentami kodów.

SPIS TREŚCI

Wstęp
Rozdział 1. Pojęcie i własności algorytmu
1.1. Przetwarzanie imperatywne
1.2. Metody zapisu algorytmu
1.3. Pseudokod
1.4. Skończoność algorytmu
1.5. Ogólny schemat konstruowania poprawnych algorytmów
Rozdział 2. Algorytmy iteracyjne i rekurencyjne
2.1. Pętle iteracyjne. Warunek stopu
2.2. Pętla for
2.3. Przykłady algorytmów iteracyjnych
2.4. Wyszukiwanie liniowe i binarne. Złożoność obliczeniowa algorytmów iteracyjnych
2.5. Algorytmy rekurencyjne - pierwsze podejście
Rozdział 3. Typy danych proste i złożone
3.1. Typy wartościowe i referencyjne
3.2. Proste typy wartościowe
3.3. Typy złożone - obiekty, struktury, tablice, słowniki
3.3.1. Typ obiektowy i strukturowy
3.4. Typ tablicowy. Tablice asocjacyjne (słowniki)
Rozdział 4. Algorytmy sortowania tablic
4.1. Sortowanie przez proste wstawianie
4.2. Sortowanie przez prostą zamianę (sortowanie bąbelkowe)
4.3. Sortowanie szybkie (QuickSort). Metoda "dziel i zwyciężaj"
4.4. Sortowanie z użyciem dodatkowej tablicy
Rozdział 5. Algorytmy i procesy rekurencyjne
5.1. Anatomia przetwarzania rekurencyjnego
5.2. Szacowanie złożoności obliczeniowej w rekurencji
5.3. Derekursywacja
5.4. Rekurencja ogonowa i bezogonowa
5.5. Rekurencja zagnieżdżona
Rozdział 6. Programowanie liniowych struktur dynamicznych
6.1. Cechy struktur dynamicznych
6.2. Zjawiska na stosie i na stercie w programowaniu struktur dynamicznych
6.3. Oparte na referencji listy liniowe
6.3.1. Lista liniowa jednokierunkowa
6.3.2. Lista liniowa jednokierunkowa z wartownikiem
6.3.3. Dynamiczne LIFO-stosy i FIFO-kolejki
6.3.4. Samoorganizujące się listy
6.4. Listy cykliczne
6.5. Listy z przeskokami. Przeszukiwanie indeksowo-sekwencyjne
6.6. Listy liniowe dwukierunkowe
Rozdział 7. Drzewa i lasy
7.1. Rekurencyjna definicja drzewa
7.2. Drzewa binarne
7.3. Algorytm tzw. naturalnego przekształcenia dowolnego lasu w drzewo binarne
7.4. Algorytmy przeglądania drzew binarnych
7.5. Drzewa binarnych poszukiwań (drzewa BST)
7.6. Drzewa wyważone i dokładnie wyważone
7.7. Drzewa z priorytetem
Rozdział 8. Algorytmy obsługi grafów
8.1. Grafy. Podstawowe pojęcia
8.2. Metody reprezentacji grafu w pamięci
8.3. Dynamiczna lista incydencji
8.4. Rekurencyjny algorytm szukania w głąb dla grafu (algorytm DFS)
Rozdział 9. Algorytmy z nawrotami
9.1. Ogólna postać algorytmu z nawrotami
9.2. Klasyczne przykłady algorytmów z nawrotami
9.3. Implementacje algorytmów z nawrotami
9.3.1. Implementacja algorytmu z nawrotami oparta na zbiorach
9.3.2. Implementacja algorytmu z nawrotami wykorzystująca drzewa poszukiwań
Rozdział 10. Metody usprawniania algorytmów o dużej złożoności czasowej
10.1. Metody systematyczne
10.1.1. Metoda obcinania gałęzi
10.1.2. Metoda sklejania gałęzi
10.1.3. Metoda dekompozycji
10.2. Metody heurystyczne
10.3. Metody wykorzystujące sztuczną inteligencję
10.3.1. Algorytm mrówkowy
10.3.2. Algorytm genetyczny
Rozdział 11. Problemy algorytmicznie trudne
11.1. Klasy problemów decyzyjnych
Rozwiązania zadań ćwiczeniowych
Bibliografia
Skorowidz