JustPaste.it

Liczby pierwsze - wstęp

the ISHANGO bone

W latach 60 ubiegłego wieku w Afryce znaleziono kości z wyrytymi na nich karbami liczące ponad 25000 lat. Na jednej z nich (kość z Ishango) karby układają się w liczby 11, 13, 17, 19. Są to liczby pierwsze. Wymieniona kość stanowi drugie najstarsze na Ziemi znalezisko matematyczne i można ją sobie obejrzeć w muzeum brukselskim na ulicy Rue Vautier 29 - B - 1000, około 100 metrów od Parlamentu Europejskiego. Jeśli nie wybierasz się do Brukseli, to możesz przeglądnąć z tego miejsca strony internetowe muzeum.

Skoro liczby pierwsze pojawiły się już tak wcześnie w naszej historii, to oczywistym jest fakt ich olbrzymiego znaczenia, które nic a nic nie zmniejszyło się do dnia dzisiejszego (można powiedzieć, że obecnie stało się jeszcze większe). Z tego powodu każdy adept sztuk informatycznych powinien doskonale znać zagadnienia związane z liczbami pierwszymi, ponieważ będzie je spotykał ciągle na swojej drodze.

W naszym opracowaniu przedstawiamy podstawowe algorytmy generacji liczb pierwszych oraz różne zastosowania tych liczb. Wyjaśnimy również wiele pojęć informatycznych i matematycznych związanych z tym tematem. Prezentowane rozwiązania nie są (i nawet nie mają na celu być) optymalne. Naszym głównym celem jest maksymalna prostota i zrozumiałość. Jeśli w tej prostocie posunęliśmy się za daleko (poniżej twojego poziomu), przepraszamy.

Zapraszamy

 

 

Ponieważ dostaję dużo listów od nieuważnych czytelników, wyjaśniam, iż prezentowane programy są jedynie przykładami realizacji opisywanych algorytmów w wybranych językach programowania. W żadnym razie nie są one celem artykułu. Celem są ALGORYTMY. Znając algorytm można napisać dobry program w dowolnym języku programowania. Dla uzasadnienia mojej postawy przytoczę znany cytat profesora Donalda Knutha (jednego z największych współczesnych autorytetów w dziedzinie informatyki):

"Languages come and go,
but algorithms stand the test of time
"

Donald Knuth

"Języki programowania pojawiają się i odchodzą,
lecz algorytmy wytrzymują próbę czasu
"

Donald Knuth

b193bda18b0264422ca218bf5b1c0369.gif
TRUDNE !

0f0ae1b54a1596243c28a7c7ac23f487.gif

Przy analizie algorytmów jednym z kluczowych pojęć jest złożoność obliczeniowa (computational complexity). Charakteryzuje ona ilość zasobów komputera użytych do rozwiązywanego przez algorytm problemu. Wyróżniamy dwa rodzaje złożoności obliczeniowej - czasową oraz pamięciową.

Pamięciowa złożoność obliczeniowa informuje nas o ilości pamięci komputera wymaganej przez dany algorytm dla n przetwarzanych danych. Jednostką jest komórka pamięci przechowująca jedną przetwarzaną daną. W obecnych czasach systemy komputerowe są wyposażane w coraz więcej taniej pamięci, zatem parametr ten stracił nieco na swoim znaczeniu - kiedyś walczono o każdy bajt, a dzisiaj nikt nie przejmuje się dziesiątkami megabajtów. Cóż, postęp...

Czasowa złożoność obliczeniowa informuje nas o czasie wykonania zadania przez algorytm dla n danych wejściowych. Ponieważ wielkość ta musi być niezależna od typu maszyny, na której uruchamiamy program, za jednostkę czasowej złożoności obliczeniowej przyjęto wykonanie tzw. operacji dominującej, czyli takiej, wokół której koncentruje się przetwarzanie danych w algorytmie. Ilość wykonań operacji dominujących jest proporcjonalna do czasu wykonania algorytmu.

Rozróżniamy dwa rodzaje czasowej i pamięciowej złożoności obliczeniowej:

  • Pesymistyczna złożoność obliczeniowa W(n) dotyczy najgorszego przypadku zestawu danych, zatem określa ona największą ilość operacji dominujących (lub komórek pamięci), która może być wymagana dla najgorszego przypadku n danych wejściowych.
  • Oczekiwana złożoność obliczeniowa A(n) dotyczy typowego zestawu danych i określa statystycznie średnią ilość operacji dominujących (komórek pamięci), które należy wykonać dla typowego zestawu danych, aby rozwiązać problem.

Dla przykładu rozważmy wyszukiwanie elementu w n elementowym, nieuporządkowanym zbiorze danych. Za operację dominującą przyjmujemy sprawdzenie, czy i-ty element zbioru jest elementem poszukiwanym, i = 1,2,3,...,n. W przypadku najgorszym poszukiwany element jest ostatnim, zatem znaleziony będzie po sprawdzeniu wszystkich elementów tego zbioru. Również stwierdzenie, iż elementu w zbiorze nie ma, wymaga przeglądnięcia wszystkich elementów. Stąd:

W(n) = n

Jeśli prawdopodobieństwo wystąpienia poszukiwanego elementu na każdej pozycji w zbiorze jest takie samo, to dla każdego elementu wynosi ono:

pi = 1  dla i = 1,2,...,n
n

Oczekiwana złożoność obliczeniowa jest równa wartości oczekiwanej zmiennej losowej rozkładu prawdopodobieństwa pi, zatem otrzymujemy wzór:

3bd38801f4a142ecd76a41fc22420a3d.gif

b193bda18b0264422ca218bf5b1c0369.gif
DLA
GENIUSZA

b5adbc6c70b1132431d17446c349b30a.gif

W teorii złożoności obliczeniowej bardzo duże znaczenie ma notacja Omikron służąca do określania rzędu funkcji złożoności obliczeniowej. Zapis:

 f(n) = O(g(n))

czytamy: funkcja f jest co najwyżej rzędu g, jeśli istnieje taka stała rzeczywista c i liczba naturalna no, iż dla każdego n większego lub równego no funkcja f(n) jest niewiększa od iloczynu c d4040ad4cd6e23fe16d99b530b288472.gif g(n).

d6554823f32bd54627345408e2d7e4c7.gif

Notacja O(g(n)) pozwala nam oszacować zachowanie się złożoności obliczeniowej wraz ze wzrostem n do nieskończoności.

5b6dca9d2f7d1aca5b04c41b7b78414b.gif

Załóżmy, iż wyznaczyliśmy oczekiwaną złożoność obliczeniową pewnego algorytmu i otrzymaliśmy następujący wzór:

A(n) = n2 + 3n

Gdy n będzie dążyło do nieskończoności czynnik 3n stanie się coraz mniej znaczący w stosunku do czynnika n2. Stąd wnioskujemy, iż jest to algorytm o złożoności O(n2). Aby to udowodnić, musimy znaleźć stałą c oraz no, dla których zachodzi:

n2 + 3n 13aaabd697759f8da4fba8461d6c967e.gif cn2 dla n e979e4a7055f8770c490436b7d261fd9.gif no

Wystarczy przyjąć c = 4 i no = 1:

n2 + 3n 13aaabd697759f8da4fba8461d6c967e.gif 4n2 dla n e979e4a7055f8770c490436b7d261fd9.gif 1

 co dowodzi, iż podany algorytm ma rzeczywiście rząd złożoności obliczeniowej równy O(n2).

Większość algorytmów posiada klasę złożoności zgodną z jedną z podanych niżej klas:

Złożoność obliczeniowa stała - O(1)

Algorytm wykonuje stałą ilość operacji dominujących bez względu na rozmiar danych wejściowych. W takim algorytmie czas wykonania jest stały i nie zmienia się przy zmianie liczby przetwarzanych elementów.

Złożoność obliczeniowa liniowa - O(n)

Dla każdej danej algorytm wykonuje stałą ilość operacji dominujących. Czas wykonania jest proporcjonalny do liczby n danych wejściowych. Czas wykonania rośnie liniowo ze wzrostem liczby elementów.

Złożoność obliczeniowa kwadratowa - O(n2)

Algorytm dla każdej danej wykonuje ilość operacji dominujących proporcjonalną do liczby wszystkich przetwarzanych danych. Czas wykonania jest proporcjonalny do kwadratu liczby danych n.

Inne złożoności tego typu O(n3), O(n4)... noszą nazwę wielomianowych złożoności obliczeniowych.

Złożoność obliczeniowa logarytmiczna - O(log n)

W algorytmie zadanie rozmiaru n da się sprowadzić do zadania rozmiaru n/2. Typowym przykładem jest wyszukiwanie binarne w zbiorze uporządkowanym. Sprawdzenie środkowego elementu pozwala określić, w której z dwóch połówek zbioru może znajdować się poszukiwany element.

Ponieważ uczniowie młodszych klas liceum nie znają pojęcia logarytmu, podajemy jego skróconą definicję:

Zapis logax czytamy: logarytm przy podstawie a z liczby x. Wartością jest wykładnik potęgowy y, do którego należy podnieść podstawę logarytmu a, aby otrzymać liczbę logarytmowaną x.

logax = y wtedy i tylko wtedy, gdy ay = x

W określeniu klasy złożoności obliczeniowej nie podajemy podstawy logarytmu, ponieważ logarytmy o różnych podstawach z tej samej wartości różnią się od siebie jedynie iloczynem przez stałą:

Niech
logax = y oraz logbx = cy

Wtedy
ay = x, oraz bcy = x

Stąd
ay = bcy

(a)y = (bc)y

Zatem
a = bc oraz logbx = c logax

Ponieważ podstawy a i b są stałe, to i c musi być stałe. Z kolei z definicji notacji Omikron wynika, iż klasa złożoności dwóch funkcji różniących się jedynie iloczynem przez stałą jest taka sama. W informatyce bardzo często stosuje się logarytmy przy podstawie 2.

5b6dca9d2f7d1aca5b04c41b7b78414b.gif

log24 = 2, bo 22 = 4

log216 = 4, bo 24 = 16

log2256 = 8, bo 28 = 256, itd.

Złożoność obliczeniowa liniowo logarytmiczna - O(n log n)

Zadanie rozmiaru n daje się sprowadzić do dwóch podzadań rozmiaru n/2 plus pewna ilość operacji, których liczba jest proporcjonalna do ilości danych n. Tego typu złożoność obliczeniową posiadają dobre algorytmy sortujące.

Złożoność obliczeniowa wykładnicza - O(2n), O(n!)

Złożoność obliczeniową O(2n) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdego podzbioru n danych wejściowych.

Złożoność obliczeniową O(n!) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdej permutacji n danych wejściowych.

Złożoność obliczeniowa wykładnicza jest bardzo niekorzystna, ponieważ czas wykonania rośnie szybko wraz ze wzrostem liczby danych wejściowych. Dla porównania załóżmy, iż posiadamy dwa komputery. Pierwszy potrafi wykonać milion operacji dominujących w ciągu sekundy. Drugi jest superkomputerem i potrafi tych operacji wykonać milion razy więcej (bardzo optymistyczne założenie), czyli 1000 miliardów w ciągu sekundy. W poniższej tabeli zebraliśmy dane o czasie wykonania algorytmu klasy O(2n) na tych dwóch komputerach.

Czasy wykonania algorytmu klasy O(2n)
Rozmiar danych n 20 50 100 200

Czas wykonania
dla komputera 1

1,05
sekund
35,7
lat
40169423
mld lat
5x1037
mld lat

Czas wykonania dla
superkomputera 2

10-6
sekund
1126
sekund
40,17
mld lat
5x1031
mld lat

Z tabelki jasno wynika, iż zastosowanie superszybkiego komputera niewiele pomaga algorytmowi. Czas wyznaczenia rozwiązania może stać się niewyobrażalnie duży (już dla n = 100 w obu przypadkach raczej nie doczekamy się wyników). Dlatego algorytm o wykładniczej złożoności obliczeniowej uważa się za wewnętrznie nierealizowalny i należy go unikać.

Porównanie klas złożoności obliczeniowych
Klasa złożoności
obliczeniowej
Nazwa klasy złożoności
obliczeniowej
Cechy algorytmu
O(1) stała działa prawie natychmiast
O(log n) logarytmiczna niesamowicie szybki
O(n) liniowa szybki
O(n log n) liniowo-logarytmiczna dosyć szybki
O(n2) kwadratowa wolny dla dużych n
O(n3) sześcienna wolny dla większych n
O(2n), O(n!) wykładnicza nierealizowalny dla większych n

Nieformalnie mówiąc klasa złożoność obliczeniowej informuje nas, iż czas t w funkcji liczby elementów n jest proporcjonalny do funkcji określonej przez klasę złożoności, a stała c jest współczynnikiem tej proporcjonalności. Spostrzeżenie to pozwala w przybliżeniu oszacować czas wykonania algorytmu dla n elementów, jeśli jest znana jego klasa złożoności obliczeniowej oraz czas wykonania dla innej liczby elementów.

5b6dca9d2f7d1aca5b04c41b7b78414b.gifZałóżmy, iż dla n1 = 100 elementów algorytm o klasie złożoności obliczeniowej O(n2) wykonywał się przez czas t1 = 5 sekund. Ile przypuszczalnie czasu t2 zajmie przetworzenie w tym algorytmie n2 = 400 elementów?

Rozwiązanie

Skoro klasa złożoności obliczeniowej algorytmu jest rzędu O(n2), to czas wykonania jest proporcjonalny do kwadratu liczby przetwarzanych elementów. Zatem możemy zapisać:

cd08ee4bbd0d7fa12fb987c1fb652a20.gif

Stąd

t2  13aaabd697759f8da4fba8461d6c967e.gif  cn22
t1 cn12

Z otrzymanej nierówności wyznaczamy czas t2:

t2  13aaabd697759f8da4fba8461d6c967e.gif t1  cn22
cn12

Do otrzymanego wzoru podstawiamy wartości liczbowe i otrzymujemy wynik:

28cd67dd5a3bd48bdc60c9bad02cdc7d.gif

 

 

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

 

 

 

 

Źródło: mgr Jerzy Wałaszek