OBOWIĄZKOWE DO NAPISANIA NA KARTCE: po jednym przykładzie z zadań 1.2, 1.3, 1.4.
https://en.wikipedia.org/wiki/Strassen_algorithm
A. Fawzi, M. Balog, A. Huang, et al.,
Discovering faster matrix multiplication algorithms with reinforcement learning,
Nature 610, 47-53 (2022).
[PDF]
https://doi.org/10.1038/s41586-022-05172-4
Złożoność czasowa i pamięciowa.
Rozmiar danych wejściowych (ang. input size) wyrażony w bitach.
Przykład. Dla wyszukiwania sekwencyjnego w ciągu n liczb rozmiar danych wejściowych to n*b, gdzie b to liczba bitów wykorzystywana na przechowywanie jednej liczby. Zwykle liczbę b pomija się jako stałą i złożoność obliczeniową wyszukiwania sekwencyjnego określa się jako O(n).
Przykład. Obliczanie n-tego wyrazu ciągu Fibonacciego. Miarą danych wejściowych jest liczba bitów użyta to zakodowania wartości n, czyli |_lg(n)_| + 1. Dla n = 13 = 1101_2 mamy 4 bity [w Pythonie math.log(13,2) = 3.7].
Identyfikacja operacji podstawowej.
Złożoność w przypadku pesymistycznym, średnim, najlepszym.
Złożoność zwykle wyraża się poprzez dane wejściowe, ale czasem
można spotkać inne sposoby zapisu:
(1) algorytmy czułe na wyjście, np. algorytm Jarvisa ma złożoność O(n*h),
gdzie n to liczba punktów na płaszczyźnie, a h to liczba punktów
należących do otoczki wypukłej.
(2) algorytmy parametryzowalne, np. w teorii grafów wyraża się
złożoność obliczeniową algorytmów nie tylko przez
n, m (liczba wierzchołków i krawędzi grafu), ale również przez
Δ (największy stopień wierzchołka),
w (treewidth, szerokość drzewowa).
Notacja z dużym O(f(n)), Ω(f(n)), Θ(f(n)), małym o(f(n)).
Asymptotyczne ograniczenie górne:
g(n) ∈ O(f(n)) wtw, gdy istnieje c > 0, istnieje N > 0,
dla każdego n ≥ N zachodzi g(n) ≤ c*f(n).
Przykładowe kategorie złożoności: O(lg n), O(n), O(n lg n), O(n^2), O(n^3), O(2^n), O(n!).
Pomoce: [Neapolitan, Naimipour]
Rozwiązywanie rekurencji za pomocą indukcji. lg(x) to logarytm przy podstawie 2.
Przykład (a)+(d). t[n] = b*t[n-1] + c, t[0] = a, t[1] = b*a + c
(niehomogeniczna rekurencja liniowa).
Jeżeli b = 1, to t[1] = a + c, t[2] = a + 2*c,
t[n] = a + n*c (ciąg arytmetyczny).
Jeżeli b ≠ 1, to t[1] = b*a + c, t[2] = b^2*a + b*c + c,
t[3] = b^3*a + b^2*c + b*c + c,...
t[n] = b^n*a + c*(1 + b + b^2 + ... + b^{n-1})
= b^n*a + c*(1-b^n)/(1-b) (ciąg geometryczny).
Drugi sposób to zdefiniowanie nowego ciągu
s[n] = t[n+1] - t[n], s[0] = b*a + c -a.
s[n] = b*t[n] -b*t[n-1] = b*s[n-1] = b^n*s[0].
Zapisujemy kolejne równania t[n+1] = t[n] + s[n],
dodajemy stronami, dostajemy
t[n] = t[0] + s[0]*(1 + b + b^2 + ... + b^{n-1}) = t[0] + s[0]*(1-b^n)/(1-b).
Trzeci sposób to usunięcie niehomogeniczności przez dodanie drugiego równania,
t[n+1] -b*t[n] = t[n] -b*t[n-1].
Czwarty sposób to zdefiniowanie przesuniętego ciągu
t[n] = s[n] + e, s[0] = a -e [liczbę e trzeba wyznaczyć].
s[n] + e = b*s[n-1] + b*e + c, e*(b-1) + c = 0, e = c/(1-b).
s[n] = b*s[n-1] = b^n*s[0] = b^n*(a-e).
t[n] = b^n*a -b^n*e + e = b^n*a + e*(1-b^n) = b^n*a + c*(1-b^n)/(1-b).
Piąty sposób to zastosowanie funkcji tworzącej
G(x) = \sum_{n=0}^{+\infty} t[n] x^n.
G(x) = t[0] + \sum_{n=1}^{+\infty} (b*t[n-1] + c) x^n,
G(x) = a + b*x*G(x) + c*x/(1-x),
G(x)*(1-b*x) = a + c*x/(1-x),
G(x) = (a -a*x + c*x)/((1-x)*(1-b*x)) = A/(1-x) + B/(1-b*x),
G(x) = c/((1-b)*(1-x)) + (a -c/(1-b))/(1-b*x),
G(x) = c/(1-b) \sum x^n + (a -c/(1-b)) \sum b^n*x^n,
t[n] = c/(1-b) + (a -c/(1-b))*b^n.
Przykład (e). t[2^k] = 2^k + 2*t[2^(k-1)]
= 2^k + 2*(2^(k-1) + 2*t[2^(k-2)])
= 2^k + 2^k + 2^2*t[2^(k-2)]
= 2^k + 2^k + 2^2*(2^(k-2) + 2*t[2^(k-3)])
= 2^k + 2^k + 2^k + 2^3*t[2^(k-3)]
= k*2^k + 2^k*t[1] = k*2^k.
Homogeniczna rekurencja liniowa z różnymi pierwiastkami.
a[0]*t[n] + a[1]*t[n-1] + ... + a[k]*t[n-k] = 0, k, a[i] są stałe.
Równanie charakterystyczne
a[0]*r^k + a[1]*r^(k-1) + ... + a[k-1]*r^1 + a[k]*r^0 = 0.
Jeżeli to równanie posiada k różnych pierwiastków r[i], to jedynym rozwiązaniem rekurencji jest
t[n] = c[1]*r[1]^n + c[2]*r[2]^n + ... + c[k]*r[k]^n.
Współczynniki c[i] wyznacza się z k warunków początkowych.
Przykład: ciąg Fibonacciego. t[n] -t[n-1] -t[n-2] = 0, t[0] = 0, t[1] = 1.
Postulujemy t[n] = r^n,
równanie charakterystyczne r^2 -r -1 = 0.
Pierwiastki r[1] = (1 + sqrt(5))/2, r[2] = (1 -sqrt(5))/2.
Rozwiązanie ogólne t[n] = c[1]*r[1]^n + c[2]*r[2]^n.
Warunki początkowe 0 = c[1] + c[2], 1 = c[1]*r[1] + c[2]*r[2].
Znalezione stałe c[1] = 1/sqrt(5) = -c[2].
Dostajemy zwarty wzór na n-ty wyraz ciągu Fibonacciego!
Rozwiązać rekurencje:
Homogeniczna rekurencja liniowa z wielokrotnymi pierwiastkami.
Jeżeli równanie charakterystyczne posiada pierwiastek r wielokrotności m, to w rozwiązaniu rekurencji dla tego pierwiastka nateży brać następujące wyrazy:
t[n] = c[1]*r^n + c[2]*n*r^n + c[3]*n^2*r^n + ... + c[m]*n^(m-1)*r^n + dalsze pierwiastki.
Rozwiązać rekurencje:
Przykład (a). t[n] -7*t[n-1] + 15*t[n-2] -9*t[n-3] = 0 dla n > 2,
t[0] = 0, t[1] = 1, t[2] = 2.
Postulujemy t[n] = r^n,
równanie charakterystyczne r^3 -7*r^2 + 15*r -9 = 0, (r-1)(r-3)^2 = 0.
Pierwiastki r[1] = 1, r[2] = 3 (pierwiastek podwójny).
Rozwiązanie ogólne t[n] = c[1]*(1)^n + c[2]*3^n + c[3]*n*3^n.
Warunki początkowe 0 = c[1] + c[2], 1 = c[1] + 3*c[2] + 3*c[3],
2 = c[1] + 9*c[2] + 18*c[3].
Znalezione stałe c[1] = -1, c[2] = 1, c[3] = -1/3.
Rozwiązanie końcowe t[n] = (-1)*1^n + (1)*3^n + (-1/3)*n*3^n.
Niehomogeniczna rekurencja liniowa.
a[0]*t[n] + a[1]*t[n-1] + ... + a[k]*t[n-k] = f(n), k, a[i] są stałe.
f(n) jest niezerową funkcją. Będziemy rozważać tylko funkcje postaci f(n) = b^n*p(n), gdzie b to stała, p(n) wielomian stopnia d.
Równanie charakterystyczne
(a[0]*r^k + a[1]*r^(k-1) + ... + a[k-1]*r^1 + a[k]*r^0) * (r-b)^(d+1) = 0.
Zauważmy, że ogólne rozwiązanie będzie zawierało wyrazy pochodzące od części homogenicznej pierwotnego równania plus wyrazy pochodzące z części niehomogenicznej (może być kilka części niehomogenicznych).
Przykłady.
f(n) = c = 1^n*c, d = 0, mnożnik (r-1)^1.
f(n) = c^n, d = 0, mnożnik (r-c)^1.
f(n) = c*n^2 = 1^n*c*n^2, d = 2, mnożnik (r-1)^3.
Rozwiązać rekurencje:
Przykład (a). t[n] -3*t[n-1] = 4^n*(2*n + 1) dla n > 1,
t[0] = 0, t[1] = 12.
Równanie homogeniczne t[n] -3*t[n-1] = 0,
równanie charakterystyczne (r-3) = 0.
Część niehomogeniczna b = 4, d = 1, (r-b)^(d+1) = (r-4)^2.
Pełne równanie charakterystyczne (r-3)(r-4)^2 = 0.
Pierwiastki r[1] = 3, r[2] = 4 (pierwiastek podwójny).
Rozwiązanie ogólne t[n] = c[1]*3^n + c[2]*4^n + c[3]*n*4^n.
Są 3 stałe, a 2 warunki, trzeba obliczyć
t[2] -3*t[1] = 4^2*(2*2+1), t[2] = 116.
Warunki początkowe 0 = c[1] + c[2], 12 = 3*c[1] + 4*c[2] + 4*c[3],
116 = 9*c[1] + 16*c[2] + 32*c[3].
Znalezione stałe c[1] = 20, c[2] = -20, c[3] = 8.
Rozwiązanie końcowe t[n] = (20)*3^n + (-20)*4^n + (8)*n*4^n.
Przykład. Ciąg Fibonacciego definiujemy następująco:
f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2).
Niech t[n] oznacza liczbę wywołań funkcji f() potrzebnych
do obliczenia f(n).
Wtedy t[0] = 1, t[1] = 1, t[n] = 1 + t[n-1] + t[n-2]
(niehomogeniczna rekurencja liniowa).
Można pokazać, że t[n] = 2*f(n+1) -1.