Zagadnienia maturalne z informatyki Wydanie II Tom II.pdf

(334 KB) Pobierz
IDZ DO
PRZYK£ADOWY ROZDZIA£
SPIS TREŒCI
KATALOG KSI¥¯EK
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
Zagadnienia maturalne
z informatyki.
Wydanie II. Tom II
Autorzy: Tomasz Francuz, Marcin Szeliga
ISBN: 83-246-0298-4
Format: B5, stron: 232
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Przyst¹p do matury odpowiednio przygotowany
• Opanuj wszystkie wymagane zagadnienia
• Rozwi¹¿ przyk³adowe zadania
• Poznaj zasady dzia³ania komputera
Jeœli przygotowujesz siê do egzaminu maturalnego z informatyki, chcesz pog³êbiæ
wiedzê informatyczn¹, któr¹ zdobywasz w szkole, lub poznaæ budowê komputera
i zasady programowania — zajrzyj do tej ksi¹¿ki. Znajdziesz tu wszystkie informacje,
jakich mo¿esz do tego potrzebowaæ. Przeczytasz o ró¿nych aspektach programowania,
jêzykach programowania, szyfrowaniu danych i kryptografii oraz metodach
numerycznych.
Opracowuj¹c „Zagadnienia maturalne z informatyki. Wydanie II”, autorzy
wykorzystywali materia³y udostêpnione przez Ministerstwo Edukacji Narodowej, zadania
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 Ÿróde³ zewnêtrznych
• System binarny, ósemkowy i szesnastkowy
• Algebra Boole’a
• Podstawy algorytmiki
• Algorytmy sortowania i przeszukiwania
• Szyfrowanie danych
• Metody numeryczne
• Analiza z³o¿onoœci algorytmów
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOŒCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treści
Tom I
Wstęp ......................................................................................................... 9
Część I
Rozdział 1.
Rozdział 2.
Rozdział 3.
Rozdział 4.
Rozdział 5.
Rozdział 6.
Rozdział 7.
Komputer z zewnątrz i od
środka
........................................ 15
Budowa i działanie komputera PC .............................................................. 17
Systemy operacyjne .................................................................................. 63
Sieci komputerowe .................................................................................... 85
Internet .................................................................................................. 119
Bezpieczeństwo systemów komputerowych .............................................. 163
Zagadnienia etyczne i prawne związane
z ochroną własności intelektualnej i danych ............................................. 177
Sprawdzian ............................................................................................. 193
Część II
Rozdział 8.
Rozdział 9.
Programy użytkowe ......................................................... 207
Arkusz kalkulacyjny ................................................................................. 209
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
Łączenie
wielu plików ............................................................................................................. 54
Wyszukiwanie informacji w pliku ........................................................................................... 55
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
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
Algorytmy sortowania .................................................................................................................. 121
Sortowanie przez wstawianie ................................................................................................. 121
Sortowanie bąbelkowe ........................................................................................................... 123
Rozdział 2.
Trochę teorii ............................................................................................. 59
Rozdział 3.
Wstęp do algorytmiki ................................................................................ 97
Rozdział 4.
Sortowanie i przeszukiwanie .................................................................... 121
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.
Rozdział 6.
Rozdział 7.
Liczby pseudolosowe ............................................................................... 137
Symulacje komputerowe .......................................................................... 143
LIFE — przykładowa symulacja .................................................................................................. 144
Algorytmy generatorów liczb pseudolosowych ............................................................................ 140
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
Szukanie miejsc zerowych funkcji metodą numeryczną ............................................................... 172
Znalezienie przybliżenia pierwiastka kwadratowego .................................................................... 176
Rozdział 8.
Rozdział 9.
Metody numeryczne ................................................................................ 171
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
Zadania maturalne ........................................................................................................................ 187
Matura 2002 ........................................................................................................................... 187
Matura 2003 ........................................................................................................................... 190
Matura 2004 ........................................................................................................................... 192
Matura 2005 ........................................................................................................................... 194
Zadania dodatkowe ................................................................................................................ 198
Odpowiedzi .................................................................................................................................. 199
Rozdział 10. Sprawdzian wiadomości ........................................................................... 187
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ć — wyobraźmy 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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin