Część I Notacja asymptotyczna.

1. Dla każdej z poniższych funkcji znajdź najmniejszą liczbę k taką, że f(n) = O(n^k ).
• f(n) = 6 n² + 3n + 20
• f(n) = (n² + 1)( 2n⁴ + 3n - 8)
• f(n) = ( n⁶ + 2n³ +1)/(n³ + 1)


2. Zbadaj, która z równości jest prawdziwa:
• 2 ⁿ⁺¹ = O(2ⁿ)
• 2 ²ⁿ = O(2ⁿ)
• 50n +100 = O(n)
• n³ + 6n + 4 = O(n⁶)


3. Podaj przykłady ciągów a(n) i b(n) takich, że a(n) = O(n⁶), b(n)= O(n²), ale a(n)/b(n) nie jest O(n⁴).



4. Udowodnij, że jeśli a(n)= O(c(n)) i b(n)= O(c(n)), to a(n)+b(n)= O(c(n)).



5. Uporządkuj, ze względu na rosnący rząd następujące funkcje:
   lg n!, 2^{3lg n}, n², 2^{lg n}, n!, log n
.


6. Zaproponuj algorytm pozwalający na wyliczenie sumy teoriomnogościowej dwóch zbiorów skończonych. Zakładamy, że zbiory są zapisane w tablicach A i B. Przedyskutuj trzy przypadki :
• Elementy zbiorów są dowolne, ale ich przecięcie jest puste.
• Elementy zbiorów są liczbami naturalnymi niewiększymi od k.
• Elementy zbiorów są zapisane w tablicach A i B jako ciągi uporządkowane rosnąco.

Część II Weryfikacja programów.

1. We wszystkich podanych przykładach n jest liczbą naturalną,  A[1..n] tablicą liczb całkowitych, a rozważaną strukturą danych jest zbiór liczb rzeczywistych z operacjami dodawania i mnożenia oraz relacjami < i £. Zbadać co robi podany algorytm formułując  odpowiedni niezmiennik pętli i warunek końcowy:
    
   • { i := 1; s := 0; while ( i £ n) do s := s + A[i]; i := i + 1; od },
   • { i := 1; s := 1; while ( i £ n) do s := s ´ i; i := i + 1; od},
   • { i := 0; z := 0; while ( i< n) do z := z+(2i+1); i := i+1; od},
   • { i := 1; s := 0; while ( i £ n) do if ( x = A[i]) then s:= s+1 fi; od;  i := i + 1;}.
      
2. Udowodnij, stosując zasadę indukcji lub metodą niezmiennika pętli, że wartością zmiennej result, po wykonaniu następującego algorytmu w strukturze liczb rzeczywistych jest n!:
   { i:=2; result :=1; while (i < n+1) do  result := result ´ i; i := i+1; od;}
    
3. Zbadaj, która z wymienionych formuł
   (a)  (i< n Ù nÎ N)     (b)  (s= i² + i Ù i £ n)      (c)  (2s = i² - i Ù i £ n+1 )      (d)  ( i = i+1 Ù s =  s + i)
   jest niezmiennikiem  pętli w podanym  poniżej algorytmie A, jeśli wiadomo, n jest liczbą naturalną większą od zera.
   A = { i := 1; s :=  0;  while ( i £ n)  do  s :=  s + i; i :=  i + 1; od }.
    
4. Rozważmy następujący algorytm AXX w strukturze liczb rzeczywistych dodatnich. Zbadaj co robi ten algorytm?
   AXX{z:=0; if x<1 then y :=1 else y := x fi;  while abs(y-z)>eps do  z := y; y := (z+x/z)/2  od; result := y}
    
5. Dana jest funkcja f : (a, b) --> R odwzorowująca przedział otwarty (a,b) w zbiór liczb rzeczywistych, oraz liczba rzeczywista dodatnia epsilon. Uzasadnij, że podany niżej algorytm Newton znajduje przybliżenie jakiegoś pierwiastka tej funkcji w przedziale (a,b), przy założeniu, że a < b, oraz f(a) ´ f(b) < 0.
   Newton{aa:=a; bb:=b;  while (abs(bb - aa) > epsilon) do  c := (bb+aa)/2; if f(c) ´ f(aa)<0 then bb := c else aa := c fi }

Część III Złożoność.

1. Oszacuj koszt algorytmu postaci {P1;P2}, wiedząc że  P1 jest algorytmem o koszcie liniowym, a funkcja koszt algorytmu P2  jest kwadratowa względem rozmiaru danych.
    
2. Jaki jest koszt algorytmu   {i:=0; while i<n do P; i := i+1; od }, jeżeli wiadomo, że wykonanie algorytmu P zależy od parametru i, a jego funkcja kosztu wyraża się wzorem T(P,i) =  i+1?
    
3. Niech A będzie algorytmem o złożoności T(n) = lg n. Wykonanie tego algorytmu dla danych rozmiaru n=32 na pewnym komputerze zajmuje 16s. Ile czasu zajmie wykonanie tego algorytmu dla danych o rozmiarze n=8? Jaki jest maksymalny rozmiar zadania, które można wykonać w czasie  32s?
    
4. Jakiego rozmiaru zadanie można zrealizować na pewnym komputerze w  czasie t  przy pomocy algorytmu A o złożoności T(A,n) = n², jeśli wiadomo, że  ten sam algorytm na komputerze 64 razy wolniejszym wykonuje w czasie t zadanie o rozmiarze 16?