E-book details

Algorytmy. Struktury danych i złożoność obliczeniowa

Algorytmy. Struktury danych i złożoność obliczeniowa

Feliks Kurp

Ebook

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.

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

  • Title: Algorytmy. Struktury danych i złożoność obliczeniowa
  • Author: Feliks Kurp
  • ISBN: 978-83-8322-242-4, 9788383222424
  • Date of issue: 2022-10-07
  • Format: Ebook
  • Item ID: alstda
  • Publisher: Helion