Str014 (2)

24 I. Kilki mgidnicrt elementarnej teorii Herb

Definicja. Mówimy, żc Algorytm wykonujący obliczenie na liczbach n_t, n_?i ...,

N_r, mających odpowiednio k_l% k₂.....k_r cyfr, działa w czasie wielomianowym,

jeśli istnieją liczby całkowite d_x% d₂, .... d_f takie, żc liczba operacji na bitach potrzebnych do wykonania tego algorytmu wynosi 0(k^dx^t ki¹... ki').

Zatem zwyczajne działania arytmetyczne -f, —, x, : są przykładami algorytmów działających w czasie wielomianowym; podobnie zamiana podstawy. Z drugiej strony, algorytm obliczający n\ nic jest takim algorytmem. (Jednakże, jeśli wystarczy nam znajomość tylko pewnej liczby cyfr znaczących liczby n!, np. pierwszych 1000 cyfr, to możemy uzyskać je w czasie wielomianowym, korzystając ze wzoru Stirlinga, dającego przybliżoną wartość ni.)

ćwiczenia

1.    Pomnóż (212)₃ przez (122)₃.

2.    Podziel (40122)., przez (126)₇.

3.    W systemie dwójkowym pomnóż 101101 przez 11001 i podziel 10011001 przez 1011.

4.    W systemie o podstawie 26, gdzie litery A-Z oznaczają cyfry od 0 do 25,

(a)    pomnóż YES przez NO i (b) podziel JQVXHJ przez WE.

5.    Zapisz e = 2,7182818... (a) w systemie dwójkowym z dokładnością do 15 cyfr po przecinku i (b) w systemie o podstawie 26 z dokładnością do 3 cyfr po przecinku.

6.    Mówimy, że ułamek okresowy o okresie długości /ma rozwinięcie okresowe „czyste", jeśli jest liczbą zawartą między 0 i 1, której cyfry w rozwinięciu przy podstawie b powtarzają się w blokach mających po /cyfr. Na przykład ułamek 1/3 jest ułamkiem o rozwinięciu okresowym czystym o okresie długości 1, a 1/7 jest ułamkiem o rozwinięciu okresowym czystym o okresie długości 6 w systemie dziesiętnym. Udowodnij, że ułamek c/d (w postaci nieskracalnej), zawarty między 0 i 1 i zapisany przy podstawie ó, jest ułamkiem o rozwinięciu okresowym czystym o okresie długości / wtedy i tylko wtedy, gdy b^f — 1 jest wielokrotnością d.

7.    (a) System „szesnastkowy” jest to system pozycyjny o podstawie b = 16,

w którym litery A-F oznaczają odpowiednio cyfry od dziesiątej do piętnastej. Podziel (131B6C3)₁₆ przez (1A2F)₁₆.

(b)    Wyjaśnij, w jaki sposób można zamieniać podstawy z dwójkowej na szesnastkową i na odwrót oraz dlaczego czas potrzebny do wykonania tych zamian jest znacznie krótszy od podanego w przykładzie 11 oszacowania ogólnego zamiany podstawy z dwójkowej na inną.

8.    Opisz operacje na bitach potrzebne do odejmowania liczb w taki sposób, jak w tekście zostały opisane operacje na bitach potrzebne do dodawania (lista pięciu przypadków).

9.    (a) Używając notacji 0, oszacuj za pomocą prostych funkcji zmiennej n

liczbę operacji na bitach potrzebnych do obliczenia 3" w systemie dwójkowym.

(b) Zrób to samo dla rf.

10.    Oszacuj za pomocą prostych funkcji zmiennych n i N liczbę operacji na bitach potrzebnych do obliczenia N*.

11.    Następujący wzór wyraża sumę kwadratów pierwszych n liczb naturalnych:

0

Yjj² = n(n + 1 )(2n + l)/6. y-1

12.

13.

(a)    Używając notacji O, oszacuj (za pomocą n) liczbę operacji na bitach potrzebnych do obliczenia lewej strony tego wzoru.

(b)    Oszacuj liczbę operacji na bitach potrzebnych do obliczenia prawej strony tego wzoru.

Korzystając z notacji O, oszacuj liczbę operacji na bitach potrzebnych do pomnożenia macierzy wymiaru rxn przez macierz wymiaru nxs, przy czym wszystkie wyrazy obu macierzy są nie większe niż m.

W tym ćwiczeniu chcemy wyrazić liczbę operacji na bitach potrzebnych do obliczenia iloczynu wszystkich liczb pierwszych mniejszych od n jako funkcję zmiennej n. Będziemy zakładać, że mamy już utworzoną niezwykle długą listę zawierającą wszystkie liczby pierwsze aż do n.

(a) Zgodnie z twierdzeniem o liczbach pierwszych liczba liczb pierwszych mniejszych od n (oznaczana zwykle przez n(n)) jest w przybliżeniu równa n/logn. To znaczy, że następująca granica jest równa 1, gdy

*(»)

n dąży do nieskończoności: lim

n/logn

Wykorzystaj twierdzenie

14.

o liczbach pierwszych do oszacowania liczby cyfr dwójkowych w iloczynie wszystkich liczb pierwszych mniejszych od n.

(b)    Znajdź ograniczenie na liczbę operacji na bitach w jednym z mnożeń potrzebnych do obliczenia tego iloczynu.

(c)    Oszacuj liczbę operacji na bitach potrzebnych do obliczenia iloczynu wszystkich liczb pierwszych mniejszych od n.

(a)    Przypuśćmy, że chcesz sprawdzić, czy pewna duża liczba nieparzysta n jest liczbą pierwszą, dzieląc ją przez wszystkie liczby nieparzyste nie większe niż <Jn . Oszacuj liczbę operacji na bitach, jakie wykonasz.

(b)    W punkcie (a) załóż, że masz listę wszystkich liczb pierwszych aż

do <Jn i sprawdzasz, czy liczba n jest pierwsza, dzieląc ją przez te liczby pierwsze (tzn. nie musisz dzielić już przez wszystkie liczby nieparzyste). Podaj oszacowanie czasu w tym przypadku. Skorzystaj z twierdzenia o liczbach pierwszych.

1S. Oszacuj czas potrzebny do sprawdzenia, czy liczba n dzieli się przez liczbę pierwszą nie większą niż m. Załóż, że masz listę wszystkich liczb pierwszych nie większych niż m i znów skorzystaj z twierdzenia o liczbach pierwszych.