ASD - kolokwium 1 - zagadnienia
Algorytmy rekurencyjne i iteracyjne: podstawy teoretyczne, wady i zalety rekurencji i iteracji, zasady działania i umiejętność budowy algorytmów rekurencyjnych i iteracyjnych, metoda „dziel i zwyciężaj” konstruowania algorytmów
Kolejki i stosy: zasada działania, konstrukcja algorytmów w oparciu o te struktury danych, ONP
Algorytmy sortowania: bąbelkowe, przez wybór, przez wstawianie, przez zliczanie, pozycyjne, przez scalanie, quicksort.
Zasada działania
Złożoność obliczeniowa i pamięciowa
Ograniczenia stosowania
Stabilność
Podstawowe możliwości optymalizacji
Podział na algorytmy działające w oparciu o porównania i pozostałe
Przypadek optymistyczny i pesymistyczny
Złożoność obliczeniowa
Pojęcie operacji dominującej i jej wykorzystanie do szacowania złożoności obliczeniowej
Złożoność czasowa i pamięciowa
Notacje złożoności: O, Ω, Θ
Klasy złożoności
Przykłady algorytmów należących do danej klasy w określonej notacji
Szacowanie złożoności obliczeniowej algorytmów: przez podstawianie, metoda rekurscji uniwersalnej
UWAGA: w sekcji przyklady pojawiły się materiały dotyczące obliczania złożoności - pochodzące z „Wprowadzenia do algorytmów” Cormena, do którego Państwa odsyłamy!