Zagadnienia maturalne z informatyki Wydanie II Tom II.pdf

IDZ DO

PRZYK£ADOW Y ROZDZIA£

Zagadnienia maturalne

SPIS TREŒCI

z informatyki.

Wydanie II. Tom II

KATALOG KSI¥¯EK

KATALOG ONLINE

Autorzy: Tomasz Francuz, Marcin Szeliga

ISBN: 83-246-0298-4

Format: B5, stron: 232

ZAMÓW DRUKOWANY KATALOG

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

ONOWOŒ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

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

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

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

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ć — 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: