Borowska A. Algorytmy i struktury danych - ćwiczenia. Część I. Analiza i techniki projektowania algorytmów

Podręcznik. — Białystok: Politechnika Białostocka, 2020. — 114 s. — ISBN 978-83-66391-35-2.Niniejszy skrypt jest przeznaczony dla Czytelników zainteresowanych projektowaniem efektywnych algorytmów, w tym przede wszystkim dla studentów studiów informatycznych. Może także posłużyć jako podręcznik do samodzielnej nauki dla uczniów szkół średnich pasjonujących się programowaniem lub jako wskazówka przy pisaniu konspektu do przedmiotu algorytmy i struktury danych. Część I skryptu prezentuje podstawy współczesnych metod projektowania i analizy algorytmów. Planowana część II – Struktury danych – będzie zawierała algorytmy wykorzystujące podstawowe struktury danych, takie jak listy, grafy i drzewa. Skrypt powstał na podstawie wybranych materiałów do wykładu, ćwiczeń i pracowni komputerowej z przedmiotu algorytmy i struktury danych, przeznaczonych do nauki dla studentów informatyki Politechniki Białostockiej. Autorka zakłada, że Czytelnik opanował podstawy kombinatoryki, matematyki dyskretnej i (w przypadku rozdziału 1) analizy matematycznej oraz potrafi zaimplementować (zrozumieć) algorytm w języku C++.Wstęp
Analiza algorytmów
Specyfikacja algorytmu
Poprawność częściowa i całkowita algorytmu
Złożoność obliczeniowa algorytmu
Rzędy wielkości funkcji
Zadania różne
Rekurencja
Definicja rekurencyjna
Rodzaje rekurencji
Nieuzasadnione użycie rekurencji
Metody rozwiązywania rekurencji
Sortowanie przez kopcowanie
Zadania różne
Technika projektowania algorytmów „dziel i zwyciężaj”
Technika „dziel i zwyciężaj”
Wyszukiwanie binarne
Metoda bisekcji
Wyszukiwanie minimum i maksimum
Sortowanie przez scalanie (MergeSort)
Sortowanie szybkie (QuickSort)
k-ty największy element (algorytm Hoare’a)
Zadania różne
Technika projektowania algorytmów: programowanie dynamiczne
Programowanie dynamiczne
Wyznaczanie n-tego wyrazu ciągu Fibonacciego
Najdłuższy wspólny podciąg
Zero-jedynkowe zagadnienie plecakowe
Zadania różne
Technika projektowania algorytmów: metoda zachłanna
Algorytm zachłanny
Problem wydawania reszty o minimalnej liczbie monet
Problem znajdowania najkrótszych ścieżek z ustalonego wierzchołka w grafie G (algorytm Dijkstry)
Problem wyznaczania minimalnego drzewa rozpinającego (algorytm Kruskala)
Kompresja Huffmana
Zadania różne
Algorytmy tekstowe – wyszukiwanie wzorca w tekście
Problem wyszukiwania wzorca
Algorytm naiwny
Algorytm Knutha–Morrisa–Pratta (KMP)
Algorytm Rabina–Karpa (RK)
Zadania różne
Wykaz skrótów i oznaczeń
Literatura