IDZ DO
IDZ DO
PRZYKŁADOWY ROZDZIAŁ
PRZYKŁADOWY ROZDZIAŁ
Zagadnienia maturalne
SPIS TRERCI
SPIS TRERCI
z informatyki.
KATALOG KSIĄŻEK Wydanie II. Tom II
KATALOG KSIĄŻEK
KATALOG ONLINE
KATALOG ONLINE
Autorzy: Tomasz Francuz, Marcin Szeliga
ISBN: 83-246-0298-4
ZAMÓW DRUKOWANY KATALOG Format: B5, stron: 232
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
TWÓJ KOSZYK
Przystąp do matury odpowiednio przygotowany
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
" Opanuj wszystkie wymagane zagadnienia
" Rozwiąż przykładowe zadania
CENNIK I INFORMACJE
CENNIK I INFORMACJE
" Poznaj zasady działania komputera
JeSli przygotowujesz się do egzaminu maturalnego z informatyki, chcesz pogłębić
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
O NOWORCIACH wiedzę informatyczną, którą zdobywasz w szkole, lub poznać budowę komputera
O NOWORCIACH
i zasady programowania zajrzyj do tej książki. Znajdziesz tu wszystkie informacje,
jakich możesz do tego potrzebować. Przeczytasz o różnych aspektach programowania,
ZAMÓW CENNIK
ZAMÓW CENNIK
językach programowania, szyfrowaniu danych i kryptografii oraz metodach
numerycznych.
CZYTELNIA
CZYTELNIA
Opracowując Zagadnienia maturalne z informatyki. Wydanie II , autorzy
wykorzystywali materiały udostępnione przez Ministerstwo Edukacji Narodowej, zadania
FRAGMENTY KSIĄŻEK ONLINE
FRAGMENTY KSIĄŻEK ONLINE
z olimpiad informatycznych oraz podręczniki szkolne. Dzięki temu przedstawione
w książce zagadnienia są dostosowane do zakresu tematycznego zadań maturalnych.
" Programowanie strukturalne i obiektowe
" Podstawowe elementy języków programowania
" Sterowanie przebiegiem działania programu
" Pobierane danych ze xródeł zewnętrznych
" System binarny, ósemkowy i szesnastkowy
" Algebra Boole a
" Podstawy algorytmiki
" Algorytmy sortowania i przeszukiwania
" Szyfrowanie danych
" Metody numeryczne
Wydawnictwo Helion
ul. Chopina 6 " Analiza złożonoSci algorytmów
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treści
Tom I
Wstęp ......................................................................................................... 9
Część I Komputer z zewnątrz i od środka ........................................ 15
Rozdział 1. Budowa i działanie komputera PC .............................................................. 17
Rozdział 2. Systemy operacyjne .................................................................................. 63
Rozdział 3. Sieci komputerowe .................................................................................... 85
Rozdział 4. Internet .................................................................................................. 119
Rozdział 5. Bezpieczeństwo systemów komputerowych .............................................. 163
Rozdział 6. Zagadnienia etyczne i prawne związane
z ochroną własności intelektualnej i danych ............................................. 177
Rozdział 7. Sprawdzian ............................................................................................. 193
Część II Programy użytkowe ......................................................... 207
Rozdział 8. Arkusz kalkulacyjny ................................................................................. 209
Rozdział 9. Relacyjne bazy danych ............................................................................. 221
Rozdział 10. Podstawy języka SQL ............................................................................... 253
Rozdział 11. Grafika komputerowa .............................................................................. 285
Rozdział 12. Sprawdzian ............................................................................................. 307
Dodatki ........................................................................................ 317
Skorowidz ............................................................................................... 319
4 Zagadnienia maturalne z informatyki. Tom II
Tom II
Wstęp ......................................................................................................... 7
Część III Podstawy programowania .................................................. 13
Rozdział 1. Wybrane techniki i metody programowania ................................................. 15
Elementarz ......................................................................................................................................16
Klasyczne podejście do programowania a programy
z graficznym interfejsem użytkownika ..................................................................................17
Programowanie strukturalne ....................................................................................................17
Programowanie zorientowane obiektowo ................................................................................19
Zmienne ..........................................................................................................................................27
Zmienne i ich reprezentacja w pamięci komputera ..................................................................27
Proste typy danych ...................................................................................................................34
Operatory .................................................................................................................................35
Konwersja (rzutowanie) typów ................................................................................................35
Zmienne tekstowe ....................................................................................................................36
Sterowanie wykonaniem programu ................................................................................................ 37
Instrukcje warunkowe ..............................................................................................................37
Pętle .........................................................................................................................................41
Procedury i funkcje .........................................................................................................................43
Funkcje i procedury użytkownika ............................................................................................45
Dane zewnętrzne ............................................................................................................................48
Pobieranie danych od użytkownika ..........................................................................................49
Wyświetlanie wyników ............................................................................................................50
Podstawowe operacje na plikach ..............................................................................................50
Dostęp do pliku ........................................................................................................................53
Aączenie wielu plików .............................................................................................................54
Wyszukiwanie informacji w pliku ...........................................................................................55
Rozdział 2. Trochę teorii ............................................................................................. 59
Arytmetyka komputera ...................................................................................................................59
Systemy: dwójkowy, dziesiętny, szesnastkowy .......................................................................59
Reprezentacja liczb w pamięci komputera ...............................................................................61
Algebra Boole a .......................................................................................................................64
Abstrakcyjne typy danych (ADT) ...................................................................................................67
Tablice .....................................................................................................................................68
Zbiory ......................................................................................................................................69
Listy .........................................................................................................................................77
Stosy ........................................................................................................................................83
Kolejki .....................................................................................................................................85
Mapowania ..............................................................................................................................87
Drzewa .....................................................................................................................................87
Rozdział 3. Wstęp do algorytmiki ................................................................................ 97
Pojęcia podstawowe .......................................................................................................................98
Algorytm ..................................................................................................................................98
Poprawność algorytmów ..........................................................................................................99
Przykładowe algorytmy ......................................................................................................... 100
Iteracja i rekurencja ...................................................................................................................... 112
Iteracja ................................................................................................................................... 112
Rekurencja .............................................................................................................................114
Obliczanie silni ......................................................................................................................116
Obliczanie wyrazów ciągu Fibonacciego ............................................................................... 119
Rozdział 4. Sortowanie i przeszukiwanie .................................................................... 121
Algorytmy sortowania ..................................................................................................................121
Sortowanie przez wstawianie .................................................................................................121
Sortowanie bąbelkowe ........................................................................................................... 123
Spis treści 5
Quicksort ................................................................................................................................124
Sortowanie rozrzutowe .......................................................................................................... 127
Algorytmy przeszukiwania ...........................................................................................................130
Przeszukiwanie liniowe .......................................................................................................... 130
Przeszukiwanie binarne .......................................................................................................... 130
Wyszukiwanie obiektu leżącego najbliżej podanych współrzędnych ....................................131
Wyszukiwanie wzorca w tekście ............................................................................................132
Rozdział 5. Liczby pseudolosowe ............................................................................... 137
Algorytmy generatorów liczb pseudolosowych ............................................................................ 140
Rozdział 6. Symulacje komputerowe .......................................................................... 143
LIFE przykładowa symulacja ..................................................................................................144
Rozdział 7. Szyfrowanie ............................................................................................. 147
Podstawowe pojęcia .....................................................................................................................148
Zasada Kerckhoffsa ............................................................................................................... 149
Klucze .................................................................................................................................... 150
Bezpieczeństwo szyfrogramów ..............................................................................................150
Zalety szyfrowania .................................................................................................................151
Kryptoanaliza .........................................................................................................................153
Funkcje mieszania ........................................................................................................................154
Kolizje ................................................................................................................................... 154
MD5 ....................................................................................................................................... 155
Szyfrowanie blokowe i strumieniowe ........................................................................................... 156
DES ........................................................................................................................................ 156
Tryby szyfrów blokowych .....................................................................................................158
Szyfrowanie symetryczne .............................................................................................................160
Szyfrowanie przez proste podstawianie .................................................................................161
Szyfrowanie przez przestawianie ........................................................................................... 162
Szyfr Playfaira .......................................................................................................................163
Szyfrowanie asymetryczne ...........................................................................................................167
Algorytm RSA .......................................................................................................................168
Podpis cyfrowy ......................................................................................................................169
Systemy hybrydowe .....................................................................................................................170
EFS ........................................................................................................................................ 170
Rozdział 8. Metody numeryczne ................................................................................ 171
Szukanie miejsc zerowych funkcji metodą numeryczną ...............................................................172
Znalezienie przybliżenia pierwiastka kwadratowego ....................................................................176
Rozdział 9. Analiza sprawności algorytmów ................................................................ 177
Złożoność obliczeniowa ............................................................................................................... 178
Szacowanie złożoności pesymistycznej .................................................................................180
Optymalizacja ............................................................................................................................... 182
Obliczanie symbolu Newtona ................................................................................................182
Schemat Hornera ....................................................................................................................185
Rozdział 10. Sprawdzian wiadomości ........................................................................... 187
Zadania maturalne ........................................................................................................................187
Matura 2002 ...........................................................................................................................187
Matura 2003 ...........................................................................................................................190
Matura 2004 ...........................................................................................................................192
Matura 2005 ...........................................................................................................................194
Zadania dodatkowe ................................................................................................................ 198
Odpowiedzi .................................................................................................................................. 199
Skorowidz ............................................................................................... 221
Rozdział 5.
Liczby pseudolosowe
Liczby losowe mają ogromne zastosowanie w informatyce. Przede wszystkim są uży-
wane do generowania kluczy i haseł, a więc to od nich zależy bezpieczeństwo sys-
temów komputerowych i przechowywanych w nich danych. Klucz wygenerowany
na podstawie ciągu niebędącego ciągiem losowym może zostać w prosty sposób złamany
znając wady generatora, możemy je odtworzyć i wygenerować podobny ciąg, a co za
tym idzie odtworzyć klucz. Oprócz kryptografii i problemów bezpieczeństwa liczby
losowe znajdują zastosowanie w symulacjach różnych zjawisk fizycznych, a także w&
grach. Innym ich zastosowaniem są symulacje, np. Monte Carlo. Służą one do nume-
rycznego rozwiązywania różnych problemów. Wiele układów lub zjawisk jest zbyt skom-
plikowanych, aby przetestować wszystkie możliwe kombinacje i sprawdzić zachowanie
badanego układu. W takich przypadkach wykorzystuje się generatory liczb losowych do
sprawdzenia układu w przypadkowych sytuacjach testując odpowiednią liczbę kom-
binacji metodami statystycznymi, możemy udowodnić prawidłowe lub wadliwe działa-
nie układu, możemy też ocenić typowe zachowanie badanego układu.
Liczby losowe możemy stosunkowo łatwo wygenerować wyobrazmy sobie, że rzu-
camy monetą. Prawdopodobieństwo, że wypadnie reszka lub orzeł wynosi dokładnie 1/2
i z góry nie daje się przewidzieć co wypadnie w kolejnym rzucie. Na tym prostym przy-
kładzie łatwo zauważyć cechy, jakimi powinien charakteryzować się idealny generator
liczb losowych:
powinien dawać losowe wyniki;
kolejny wynik nie powinien być uzależniony od poprzednio uzyskanych wyników.
Niektóre definicje liczb losowych i generatorów liczb losowych obejmują warunek rów-
ności rozkładu uzyskanych liczb losowych w podanym przedziale. Jednak znane są gene-
ratory liczb losowych, których wynikiem jest rozkład inny niż równomierny np. rozkład
normalny lub Poissona.
Czy wynik rzutu monetą rzeczywiście jest losowy? Czy podczas gry w ruletkę prawdo-
podobieństwo wypadnięcia czarnych lub czerwonych rzeczywiście wynosi 1/2? Na pierw-
szy rzut oka mogłoby się tak wydawać. Jednak sami łatwo jesteśmy w stanie nauczyć
się tak rzucać monetą, aby uzyskać z góry ustalony rezultat, podobnie jak doświadczony
krupier potrafi tak rzucić kulką, aby rozkład uzyskanych wartości wcale nie był losowy.
Potrzebne są testy, które określą jak dobry jest dany generator i czy otrzymywane sekwen-
cje rzeczywiście są losowe. Takimi testami zajmiemy się pod koniec tej części rozdziału.
138 Część III Podstawy programowania
Niezależnie od naszych umiejętności, czy umiejętności krupiera, wszystkie zdarzenia pod-
legają ścisłym prawom fizyki. W takim razie czy w ogóle możemy uzyskać losowe dane?
Na pewno współczesne komputery, jako układy deterministyczne (choć ich działanie
może nam się wydawać przypadkowe) nie mogą być zródłem liczb losowych.
Jednak nawet proste układy, które doskonale potrafimy opisać prawami fizyki zachowują
się w pewnych okolicznościach niby-losowo. Wyobrazmy sobie grę w snookera. Ruchem
bil rządzą proste prawa, typu kąt padania równa się kątowi odbicia, zasada zachowania
pędu itd. Powodują one, że w przypadku uderzenia jednej bili w drugą jesteśmy w stanie
bardzo precyzyjnie przewidzieć zachowanie obu bil po zderzeniu. Jednak już w przypad-
ku zderzenia trzech bil, mimo że posiadamy dokładne równania opisujące ich ruch, efekt
tego zderzenia jest kompletnie nieprzewidywalny. Końcowa pozycja bil różni się diame-
tralnie w zależności od drobnych różnic przed zderzeniem, np. niewielkiej różnicy w pręd-
kości, czy minimalnych różnic w czasie pomiędzy kolejnymi zderzeniami. Pojawia się
w układzie chaos, a my, choć potrafimy opisać go równaniami, to nie znamy z wyprze-
dzeniem konkretnych wyników. Nazywamy go chaosem deterministycznym.
Komputery realizują dokładnie instrukcje programu, w związku z tym nie mają możli-
wości generowania liczb losowych nie da się tak napisać programu, aby procesor
wykonywał losowe instrukcje. Wynika z tego, że dla każdego algorytmu przy tych sa-
mych danych wejściowych zawsze uzyskamy te same dane wyjściowe. Dlatego wszelkie
generatory liczb losowych, jako oparte na algorytmach deterministycznych, umoż-
liwiają wygenerowanie liczb pseudolosowych, liczb które posiadają tylko pewne cechy
liczb losowych. Liczby pseudolosowe zawsze posiadają pewien wzór, według którego są
generowane, a osoba znająca algorytm generowania oraz wartość początkową generatora
jest w stanie przewidzieć kolejną liczbę losową. Jednak w pewnych zastosowaniach nie
jest to przeszkodą i takie liczby mimo wszystko są użyteczne.
Problem deterministycznych algorytmów generowania liczb jest omijany na różne spo-
soby. Komputery na potrzeby generowania liczb losowych rejestrują różne zdarzenia, np.
naciskanie klawiszy przez użytkownika, dostęp do plików, liczbę transmitowanych pa-
kietów przez sieć, a następnie tych przypadkowych danych używają do generowania liczb
losowych za pomocą algorytmów deterministycznych. Dzięki temu nawet znając algorytm,
nie jesteśmy w stanie przewidzieć kolejnej liczby losowej, gdyż nie znamy dokładnych
parametrów początkowych generatora. Niektóre procesory, np. Pentium III i nowsze
posiadają wbudowany generator liczb losowych oparty na zjawisku szumu termicznego.
Jednak nawet taki, wydawałoby się idealny, generator nie gwarantuje, że uzyskamy lo-
sowe ciągi cyfr, gdyż nie ma dowodów na to, że fluktuacje temperatury w procesorze
rzeczywiście są losowe1.
Profesjonalne środowiska programistyczne udostępniają funkcje pseudolosowe o dużej
zmienności. Nigdy nie używaj własnych albo słabo udokumentowanych funkcji pseudo-
losowych, jeśli istnieje odpowiednia funkcja systemowa raczej nie uda Ci się uzy-
skać równie dobrych wyników. Na przykład, funkcja Win API CryptGenrandom zwraca
dane obliczone na podstawie: identyfikatora procesu, aktualnego identyfikatora wątku,
liczby taktów zegara od momentu uruchomienia systemu, czasu systemowego, kilku-
nastu liczników wydajności (np. czasu użycia procesora), dodatkowych informacji o sys-
temie (np. liczby operacji porządkowania pamięci) i wewnętrznych licznikach procesora.
1
W rzeczywistości są przekonujące dowody (np. teoria superstrun), że te fluktuacje podlegają
deterministycznemu opisowi.
Rozdział 5. Liczby pseudolosowe 139
Problem ten jest bardziej ogólny i dotyczy różnych zjawisk. Na przykład zachowania
ludzi jako jednostek są nieprzewidywalne, jednak zachowanie tłumu statystycznie daje
się świetnie opisywać. Podobnie rzeczy, które wcale nie są losowe, w pewnych sytuacjach
świetnie przybliżają generator losowy. Wyobrazmy sobie prostą sytuację, w której oczeku-
jemy wygenerowania liczby losowej z zakresu 0 100. Najprostszym takim generatorem
będzie wykorzystanie zegara komputera i zwracanie liczby milisekund. Dopóki użytkownik
nie pozna naszego triku, taki generator będzie się doskonale sprawował. Aby zrozumieć, jak
działają używane w praktyce algorytmy generowania liczb losowych, musimy wprowadzić
nieco teorii.
Generatory liczb pseudolosowych generują sekwencje liczb lub zbiory liczb na pod-
stawie ściśle określonego algorytmu, dając tylko złudzenie ich losowości. Stopień złożo-
ności algorytmu decyduje o jakości generowanych liczb pseudolosowych. Generatory tego
typu wymagają pewnej początkowej liczby, zalążka (ang. Seed), na podstawie którego
generują pseudolosowy ciąg (pseudolosowy, gdyż kolejne elementy ciągu determinuje wy-
korzystana funkcja matematyczna, a nie przypadek). Generowane liczby mogą być użyte
do różnych celów, np. realizacji automatów do gier lub symulowania sztucznej inteligen-
cji w programie. Ich podstawową wadą jest okresowość po pewnym czasie powta-
rzają się te same sekwencje liczb. Ta cecha eliminuje tego typu generatory ze stosowania
w kryptografii. Osoba znająca algorytm wykorzystywany do generowania liczby pseu-
dolosowej jest w stanie przewidzieć generowany ciąg liczb (podobnie jak w przypadku
naszego przykładu z zegarkiem osoba znająca sposób zwracania wyniku i posiadają-
ca stosowny refleks może uzyskać z góry założone wyniki).
W przeciwieństwie do generatorów liczb pseudolosowych, generatory liczb losowych
bazują na danych uzyskanych z otaczającego świata. Generowane liczby zależą od ta-
kich czynników, jak ruchy myszą, sekwencje i czas naciskania klawiszy, i wiele innych.
W profesjonalnych zastosowaniach używa się generatorów wykorzystujących niedeter-
ministyczny proces rozpadu pierwiastków promieniotwórczych.
Dla wielu zastosowań potrzebne są ciągi liczb, które mają tylko niektóre własności praw-
dziwych ciągów liczb losowych. Najbardziej pożądaną cechą są właściwości statystycz-
ne. Uzyskujemy je, wykorzystując generatory liczb pseudolosowych, których jedynym
w pełni losowym składnikiem jest zalążek wartość ustalana podczas uruchomienia ge-
neratora. W tym celu można posłużyć się np. odpowiednio zmodyfikowanym czasem
zwracanym przez zegar komputera.
Prawie wszystkie stosowane generatory tworzą liczby pseudolosowe na podstawie funkcji
rekurencyjnych wykorzystujących operator modulo. Dla dwóch liczb naturalnych n, m
wynikiem działania n modulo m (co zapisujemy n mod m) jest reszta z dzielenia liczby n
przez liczbę m. Przykładowo: 3 mod 2 = 1, 2015 mod 3 = 2. Obecnie najczęściej stoso-
wanymi generatorami o rozkładzie równomiernym są:
generatory liniowe,
generatory rejestrów przesuwnych,
generatory Fibonacciego,
generatory oparte na nadmiarowym odejmowaniu,
generatory nieliniowe.
140 Część III Podstawy programowania
Żaden generator nie jest idealny, niektóre nadają się lepiej niż inne do konkretnych zasto-
sowań, dlatego generatory należy testować pod względem jakości otrzymywanych ciągów
pseudolosowych. Testy takie wymagają wiedzy z zakresu statystyki i rachunku prawdopo-
dobieństwa wykraczającej poza zakres szkoły średniej. Pod koniec rozdziału omówmy tylko
jeden, ciekawy przypadek testu Ą.
W następnym podrozdziale poznamy przykłady generatora liniowego i nieliniowego.
Osobom, które potrzebują prawdziwych liczb losowych, polecamy serwis internetowy
www.random.org, z którego bezpłatnie można pobrać ciągi losowe.
Algorytmy generatorów
liczb pseudolosowych
Generatory liniowe wykorzystują następującą zależność rekurencyjną:
xn+1 = (a0"xn+a1"xn 1+ak"xn k+1+c) mod m,
gdzie a0, a1, ..., ak, c, m są ustalonymi liczbami całkowitymi stanowiącymi parametry
generatora, natomiast początkowe wartość x0, x0, ..., xk stanowią zalążek generatora. Je-
żeli c = 0, to generator taki nazywamy multiplikatywnym, w przeciwnym razie mówimy
o generatorze mieszanym.
Zakres liczb, jaki otrzymujemy, stosując generator liniowy, wynosi {0...m}. Okres ge-
neratora liniowego wynosi maksymalnie m, co osiągalne jest jednak tylko dla generatorów
mieszanych przy spełnieniu przez parametry wywołania dodatkowych założeń. Generato-
ry liniowe nie dają dobrych wyników, obecnie używa się ich stosunkowo rzadko. Zaletą
jest łatwość implementacji i szybkość działania. W typowych implementacjach wykorzy-
stuje się najprostszą postać generatora liniowego:
xn+1 = (axn+c) mod m
Wszystkie przedstawiane funkcje implementujące generatory liczb pseudolosowych za-
deklarujemy następująco: argumentami funkcji będą zalążek i parametry generatora. Zwra-
caną wartością będzie liczba pseudolosowa, będzie ona stanowiła jednocześnie zalążek
dla kolejnej generowanej liczby pseudolosowej. Dodatkowo zakładamy, że operację mo-
dulo (n mod m) realizuje niezdefiniowana przez nas w tym rozdziale funkcja mod zwra-
cająca resztę z dzielenia całkowitego x przez y.
Funkcję realizującą generator liniowy w najprostszej postaci zadeklarujemy następująco:
function generatoLiniowy(zalazek, a, c, m : Integer) : real;
Przyjmujemy, że funkcja ma zwracać liczby pseudolosowe z przedziału <0, m>. Zanim
zdefiniujemy ciało funkcji, przekształcimy zależność rekurencyjną w postać iteracyjną.
Rekurencja na kolejne liczby pseudolosowe z zakresu {0...m} wygląda następująco:
(a * zalazek + c) mod m dla n = 0
ż#
gl(n) =
#(a * gl(n -1) + c) mod m dla n > 0
#
Rozdział 5. Liczby pseudolosowe 141
Ostatecznie definicja funkcji generatorLiniowy mogłaby wyglądać jak poniżej:
function generatorLiniowy(zalazek, a, c, m : Integer ) : Integer;
begin
generatorLiniowy:=(a*zalazek+c) mod m;
end;
Istnieje wiele nieliniowych generatorów liczb pseudolosowych, o których przewadze nad
generatorami liniowymi świadczy to, że na podstawie ciągu wygenerowanych liczb pseu-
dolosowych praktycznie nie można odgadnąć parametrów generatora, a co za tym idzie
przewidzieć kolejnych wartości ciągu. Własność taka jest niezbędna w przypadku za-
stosowań kryptograficznych.
Poniżej omówimy generator BBS (Blum-Blum-Shuba nazwa pochodzi od nazwisk twór-
ców). Jak w wielu zagadnieniach związanych z kryptografią, podstawą działania algoryt-
mu są liczby pierwsze. W przypadku generatora BBS parametrami będą dwie różne liczby
pierwsze p i q, na których podstawie wyliczane jest n = p"q, a wartości pseudolosowe
wyliczane są rekurencyjnie według wzoru:
xk+1 = xk2 mod n.
Przekształcenie rekurencji na iterację zachodzi podobnie jak w generatorze liniowym. De-
finicja funkcji generatorBBS wygląda następująco:
function generatorBBS(zalazek, p, q : Integer) : Integer;
begin
generatorBBS:=(zalazek*zalazek) mod (p*q);
end;
Spełnienie dodatkowego warunku: p mod 4 = q mod 4 = 3 oraz wybór zalążka innego
niż p, q lub n powoduje, że generator ma odpowiednio silne własności kryptograficzne.
Jak wspomnieliśmy na początku rozdziału, generatory liczb pseudolosowych nie są dosko-
nałe i wymagają testów. Jednym z nich jest test Ą, którego idea polega na tym, że generuje
się losowe pary punktów z kwadratu o boku 1, a następnie sprawdza, jaka liczba punktów
leży wewnątrz koła wpisanego w ten kwadrat.
Wiemy, że powierzchnia koła wpisanego w kwadrat jednostkowy wynosi Ą/4, stąd sto-
sunek liczby punktów leżących wewnątrz koła do liczby wszystkich wygenerowanych
punktów powinien wynosić Ą/4. Wartość ta pomnożona przez 4 powinna dać przybliżo-
ną wartość liczby Ą. Oczywiście, im lepszy generator i większa liczba generowanych punk-
tów, tym przybliżenie Ą powinno być lepsze. Przypuśćmy, że interesujący nas kwadrat
w układzie współrzędnych kartezjańskich będzie miał rogi w punktach o współrzędnych
(0,0); (0,1); (1,0); (1,1), wówczas interesujące nas koło możemy opisać nierównością:
(x 0,5)2+(y 0,5)2 d" 0,52 = 0,25
Funkcja testPi() będzie pobierała ciągi liczb pseudolosowych w postaci dwóch tablic
równej długości X[], Y[], losowy i-ty punkt będzie miał współrzędne x[i], y[i]; funkcja
powinna zwracać wyliczone przybliżenie liczby Ą:
142 Część III Podstawy programowania
function testPi (x, y : Array of Real; n : Integer) : Real;
var
i, ilosc : Integer;
temp,a,b : Real;
begin
for i:=0 to n do
begin
a:=x[i]-0.5; b:=y[i]-0.5;
temp:=a*a+b*b;
if temp<=0.25 then ilosc:=ilosc+1;
end;
testPi:=(ilosc/n)*4;
end;
Wyszukiwarka
Podobne podstrony:
informatyka excel 2007 pl leksykon kieszonkowy wydanie ii curt frye ebookinformatyka internet ilustrowany przewodnik wydanie ii radoslaw sokol ebookCore Java Servlets i JavaServer Pages Tom II Wydanie II2015 matura INFORMATYKA poziom rozszerzony TEST IIinformatyka mysql leksykon kieszonkowy wydanie ii george reese ebookinformatyka internet pierwsza pomoc wydanie ii maria sokol ebookGIMP cwiczenia praktyczne Wydanie IIC cwiczenia praktyczne Wydanie IIbiznes i ekonomia mistrz sprzedazy wydanie ii rozszerzone arkadiusz bednarski ebookwięcej podobnych podstron