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] = ba+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] = ba+c, t[2] = b^2*a+bc+c, t[3] = b^3*a+b^2*c+bc+c,...
t[n] = b^n*a+c*(1+b+b^2+...+b^{n-1}) = b^n*a+c*(1-b^n)/(1-b).
Drugi sposób to zdefiniowanie nowego ciągu s[n] = t[n+1]-t[n], s[0] = ba+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,
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.
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.
Rozwiązania r[1] = (1+sqrt(5))/2, r[2] = (1-sqrt(5))/2,
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],
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-7r^2+15r-9 = 0, (r-1)(r-3)^2 = 0, jest pierwiastek podwójny.
Rozwiązanie 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].
Rozwiązanie c[1] = -1, c[2] = 1, c[3] = -1/3, 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, jest pierwiastek podwójny.
Rozwiązanie 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].
Rozwiązanie c[1] = 20, c[2] = -20, c[3] = 8, 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.