Algorytmika jest dziedziną wiedzy zajmującą się badaniem algorytmów (konstrukcja, własności). Algorytm to zbiór reguł postępowania umożliwiających rozwiązanie określonego zadania w skończonej liczbie kroków i w skończonym czasie. W informatyce algorytmy są ściśle związane z przetwarzanymi przez nie strukturami danych (algorytmy + struktury danych = programy).
Specyfikacja to ścisła definicja problemu do rozwiązania (zadania do wykonania). Składa się z danych początkowych, warunków jakie mają one spełniać (warunki początkowe) oraz danych wyjściowych i warunków, jakie muszą one spełniać (warunki końcowe). Warunki końcowe określają również związek danych wyjściowych z wejściowymi.
Model algorytmu.
Sposoby zapisu algorytmu.
Klasyfikacja algorytmów.
Techniki rozwiązywania problemów.
Algorytm liniowy (sekwencyjny) ma postać listy kroków, które bezwarunkowo mają być wszystkie wykonane zgodnie z kolejnością, w jakiej występują.
SPECYFIKACJA Problem: Obliczanie pola trójkąta o danych długościach jego boków. DANE WEJŚCIOWE Trzy liczby a, b i c, będące długościami boków trójkąta. DANE WYJŚCIOWE S - pole trójkąta o bokach długości a, b, c.
LISTA KROKÓW
K01: Obliczyć połowę długości obwodu trójkąta
p = (a + b + c)/2.
K02: Obliczyć pole trójkąta S według wzoru Herona
S = sqrt(p * (p-a) * (p-b) * (p-c)).
Sprawdzenie warunku, aby trzy liczby były długościami boków trójkąta. Oznaczamy: 2 * p = a + b + c. a < b + c, b < a + c, c < a + b, 2 * a < 2 * p, 2 * b < 2 * p, 2 * c < 2 * p, p - a > 0, p - b > 0, p - c > 0. Możemy zmodyfikować specyfikację zadania. SPECYFIKACJA Problem: Obliczanie pola trójkąta. DANE WEJŚCIOWE Trzy dowolne liczby a, b i c. DANE WYJŚCIOWE Jeżeli liczby a, b i c są długościami boków pewnego trójkąta, to oblicz pole S tego trójkąta. W przeciwnym razie wyprowadź komunikat, że dane liczby nie są długościami boków żadnego trójkąta.
Algorytm z warunkami (rozgałęzieniami) zawiera pewną liczbę kroków warunkowych, które są wykonywane wtedy, gdy spełnione są pewne warunki.
Problem: Analiza rozwiązań równania liniowego postaci a * x + b * y = c.
Problem: Analiza rozwiązań równania kwadratowego postaci a * x * x + b * x + c = 0.
W algorytmie iteracyjnym pewna liczba kroków jest wielokrotnie powtarzana z liczbą powtórzeń z góry zadaną lub zależną od wyników obliczeń. Iteracja to powtarzanie pewnych operacji.
SPECYFIKACJA Problem: Obliczanie wartości wielomianu. WEJŚCIE n - stopień wielomianu, a[] - współczynniki wielomianu (n+1 liczb), x - argument wielomianu. WYJŚCIE Wartość wielomianu dla argumentu x.
w(x) = a[1] * x + a[0] # 1 mnożenie, 1 dodawanie w(x) = a[2] * x * x + a[1] * x + a[0] # 3 mnożenia, 2 dodawania w(x) = (a[2] * x + a[1]) * x + a[0] # 2 mnożenia, 2 dodawania w(x) = a[3] * x * x * x + a[2] * x * x + a[1] * x + a[0] # 6 m, 3 d w(x) = ((a[3] * x + a[2]) * x + a[1]) * x + a[0] # 3 m, 3 d p = a[3] # przygotowanie do iteracji p = p * x + a[2] # 3 iteracje p = p * x + a[1] p = p * x + a[0]
Algorytm: Schemat Hornera (1819 rok). Lista kroków. K01: Przyjmij współczynnik wielomianu przy najwyższej potędze za początkową wartość, czyli podstaw p = a[n] (p jest zmienną pomocniczą). K02: n razy oblicz wartość wyrażenia p = p * x + a[i] dla kolejnych współczynników wielomianu, czyli dla i = (n-1), (n-2), ..., 1, 0.
Złożoność: dla wielomianu stopnia n należy wykonać n mnożeń i n dodawań.
Schemat Hornera jest optymalny pod względem liczby wykonywanych działań (1971 Borodin).
Zastosowania: zamiana liczb z systemu binarnego na dziesiętny, szybkie podnoszenie do potęgi.
Liczba naturalna jest pierwsza, jeśli dzieli się tylko przez 1 i przez siebie. Liczbę naturalną, która nie jest pierwszą, nazywa się liczbą złożoną.
Rozkładem liczby na czynniki pierwsze (faktoryzacją) nazywamy przedstawienie liczby w postaci iloczynu jej czynników pierwszych z uwzględnieniem ich krotności.
Problem: Podać rozkład liczby n na czynniki pierwsze lub sprawdzić, że jest to liczba pierwsza.
Problem: Znaleźć wszystkie liczby pierwsze w wybranym przedziale liczb lub znaleźć dużą liczbę pierwszą.
SPECYFIKACJA Problem: Znaleźć wszystkie liczby pierwsze mniejsze od danej liczby. WEJŚCIE Liczba naturalna n. WYJŚCIE Lista liczb pierwszych mniejszych od n. Algorytm: Sito Eratostenesa.
SPECYFIKACJA Problem: Rozkład liczby na czynniki pierwsze. WEJŚCIE Liczba naturalna n. WYJŚCIE Przedstawienie liczby n w postaci n = p[1] * p[2] * ... * p[k], p[1] <= p[2] <= ... <= p[k], gdzie p[i] to liczby pierwsze.
Algorytm siłowy (brute force algorithm) - tak określa się algorytm, który opiera się na sukcesywnym sprawdzeniu wszystkich możliwości w poszukiwaniu rozwiązania problemu, zamiast skupiać się na jego szczegółowej analizie. Jest to zwykle nieoptymalna, ale najprostsza do zaimplementowania i najbardziej skuteczna metoda postępowania (tzn. znajdziemy rozwiązanie, jeżeli istnieje, ale często dużym nakładem pracy).