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

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