Informatyka Europejczyka Informatyka Podrecznik dla szkol ponadgimnazjalnych Czesc 1.pdf

(734 KB) Pobierz
Informatyka Europejczyka.
Informatyka. Podrêcznik dla
szkó³ ponadgimnazjalnych.
Czêœæ I
Autor: Gra¿yna Zawadzka
ISBN: 978-83-246-0925-3
Format: 170×240, stron: 288
Z komputerami stykamy siê dziœ niemal ka¿dego dnia. Wykorzystujemy je do pracy
i rozrywki, wyszukiwania informacji w sieci, komunikowania siê ze znajomymi i wielu
innych zadañ. Jednak komputer to nie tylko gry, edytory tekstu, poczta elektroniczna,
portale spo³ecznoœciowe czy komunikatory – to tak¿e wiele przydatnych narzêdzi,
które staj¹ siê niezbêdne do codziennego funkcjonowania we wspó³czesnym œwiecie.
„Informatyka Europejczyka. Informatyka. Podrêcznik dla szkó³ ponadgimnazjalnych.
Czêœæ I” przedstawia zagadnienia zwi¹zane z algorytmik¹ i programowaniem.
Dowiesz siê z tego podrêcznika, jakimi prawami rz¹dz¹ siê algorytmy, i nauczysz siê
rozpoznawaæ ich typy. Zyskasz mo¿liwoœæ samodzielnego analizowania algorytmów
okreœlaj¹cych najczêstsze metody numerycznego rozwi¹zywania problemów obliczeniowych.
W dalszej czêœci podrêcznika znajdziesz informacje dotycz¹ce programowania w jêzyku
C++ – typy danych i instrukcji, strukturê programu, sposoby realizacji typowych zadañ
programistycznych oraz podstawy programowania obiektowego.
Na p³ycie CD-ROM do³¹czonej do ksi¹¿ki znajdziesz przyk³ady programów napisanych
w jêzykach C++ i Pascal, uzupe³niaj¹cy materia³ dotycz¹cy programowania obiektowego,
dane do zadañ, pliki potrzebne do wykonywania æwiczeñ oraz wybrane zadania
z egzaminów maturalnych.
• Pojêcie algorytmu
• Sposoby przedstawiania algorytmów
• Metody programowania: liniowe, warunkowe, iteracja, rekurencja,
„dziel i zwyciê¿aj”, zach³anna
• Analiza i realizacja algorytmów
• Podstawy kryptografii i wybrane algorytmy szyfruj¹ce
• Podstawy jêzyka C++: struktura programu, operacje wejœcia i wyjœcia,
typy instrukcji, proste i z³o¿one typy danych, strukturalizacja programu,
dynamiczne struktury danych, plikowe operacje wejœcia i wyjœcia oraz
programowanie obiektowe
Spis treści
Spis treści
Od autorek
7
9
10
11
12
13
14
15
16
17
17
20
23
31
40
41
43
47
51
52
55
55
57
60
60
63
64
65
Rozdział 
1.  Wprowadzenie do algorytmiki
 
 
1.1. Pojęcie algorytmu
1.2. Etapy rozwiązywania zadań za pomocą komputera
1.3.
1.3.1.
1.3.2.
1.3.3.
1.3.4.
1.4.
1.4.1.
1.4.2.
1.4.3.
Sposoby reprezentowania algorytmów
Lista kroków algorytmu
Schemat blokowy algorytmu
Drzewo algorytmu
Program w języku programowania wysokiego poziomu
Algorytmy liniowe i z warunkami
Algorytmy liniowe
Algorytmy z warunkami
Rozwiązywanie równania kwadratowego
1.5. Iteracja
1.6.
1.6.1.
1.6.2.
1.6.3.
Rekurencja
Obliczanie silni liczby naturalnej
Wyznaczanie elementów ciągu Fibonacciego
Wieże Hanoi
1.7. Metoda „dziel i zwyciężaj”
1.7.1. Przeszukiwanie binarne ciągu uporządkowanego
1.8. Programowanie zachłanne
1.8.1. Minimalizacja łączenia par
1.9. Kryptografia i kryptoanaliza. Metody szyfrowania
1.10.
1.10.1.
1.10.2.
1.10.3.
Własności algorytmów
Złożoność obliczeniowa i efektywność algorytmów
Poprawność i skończoność algorytmów
Optymalność algorytmów
R
 
ozdział 
2. 
Algorytmy i ich zastosowanie
 
 
2.1. Wyznaczanie największego wspólnego dzielnika
i najmniejszej wspólnej wielokrotności
dwóch liczb naturalnych
2.1.1. Algorytm Euklidesa
2.1.2. Obliczanie najmniejszej wspólnej wielokrotności
66
67
71
Część 1.
Informatyka Europejczyka. Informatyka
2.2. Wyznaczanie wartości wielomianu,
pozycyjne systemy liczbowe
i reprezentacja danych liczbowych w komputerze
2.2.1. Systemy liczbowe
2.2.2. Konwersje pozycyjnych systemów liczbowych
2.2.3. Operacje arytmetyczne wykonywane
w różnych systemach liczbowych
2.2.4. Wyznaczanie wartości wielomianu
za pomocą schematu Hornera
2.2.5. Zamiana liczb z dowolnego pozycyjnego
systemu liczbowego na system dziesiętny
z zastosowaniem schematu Hornera
2.2.6. Reprezentacja danych liczbowych w komputerze
2.3. Generowanie liczb pierwszych i badanie,
czy liczba jest pierwsza
2.3.1. Badanie, czy liczba jest pierwsza
2.3.2. Sito Eratostenesa
2.4. Przeszukiwanie ciągu liczbowego — metody liniowe
2.4.1. Liniowe przeszukiwanie ciągu liczbowego
2.4.2. Liniowe przeszukiwanie
ciągu liczbowego z wartownikiem
2.5. Znajdowanie najmniejszego
lub największego elementu w ciągu liczbowym
2.6. Znajdowanie lidera w zbiorze
2.7. Sprawdzanie monotoniczności ciągu liczbowego
2.8. Sortowanie ciągu liczbowego
2.8.1. Metody sortowania przez porównania
2.8.2. Sortowanie w czasie liniowym
2.9. Zastosowanie metody „dziel i zwyciężaj”
2.9.1. Jednoczesne znajdowanie najmniejszego
i największego elementu
2.9.2. Sortowanie przez scalanie
2.9.3. Sortowanie szybkie
2.10. Metody numeryczne i obliczenia przybliżone
2.10.1. Obliczanie wartości pierwiastka kwadratowego
z liczby nieujemnej — algorytm Newtona-Raphsona
2.10.2. Obliczanie pola obszaru
ograniczonego wykresem funkcji
2.10.3. Znajdowanie przybliżonej wartości miejsca zerowego
funkcji — metoda połowienia przedziałów
2.11. Wyznaczanie wartości wyrażenia zapisanego
w odwrotnej notacji polskiej ONP
72
72
75
81
85
89
91
97
97
100
103
103
108
110
113
117
119
121
130
136
136
140
146
150
150
154
162
166
Spis treści
2.12. Zastosowanie programowania zachłannego
2.12.1. Problem plecakowy
2.12.2. Algorytm wydawania reszty
2.13. Wybrane algorytmy kryptograficzne
2.13.1. Szyfrowanie symetryczne
2.13.2. Szyfrowanie asymetryczne
169
169
179
182
182
194
197
198
200
201
204
209
213
221
222
223
223
223
224
224
227
230
235
236
238
238
240
241
248
254
254
262
268
272
273
275
276
279
R
 
ozdział 
3. 
Programowanie w języku C++
 
 
3.1. Języki programowania — pojęcia, klasyfikacja, przykłady
3.2.
3.2.1.
3.2.2.
3.2.3.
3.2.4.
3.2.5.
3.2.6.
3.3.
3.3.1.
3.3.2.
3.3.3.
3.3.4.
3.3.5.
3.3.6.
3.3.7.
Wprowadzenie do programowania
Struktura programu
Operacje wejścia-wyjścia
Zmienne, stałe, wskaźniki i referencje
Wyrażenia arytmetyczne, relacje i operatory logiczne
Liczby losowe
Komentarze
Podstawowe konstrukcje algorytmiczne
Instrukcja pusta
Instrukcja przypisania
Instrukcja złożona
Instrukcje warunkowe
Instrukcja wyboru
Instrukcje iteracyjne
Instrukcje sterujące
3.4. Proste typy danych
3.5. Strukturalizacja programu
3.5.1.
3.5.2.
3.5.3.
3.5.4.
3.6.
3.6.1.
3.6.2.
3.6.3.
3.7.
3.7.1.
3.7.2.
3.7.3.
Struktura funkcji
Zmienne lokalne i globalne
Przekazywanie parametrów w funkcjach
Przeładowanie funkcji
Strukturalne typy danych
Tablice
Łańcuchy
Struktury
Dynamiczne struktury danych
Stos
Kolejka
Lista
3.8. Plikowe operacje wejścia-wyjścia
3.8  77
2
Rozdział 2.
Algorytmy i ich zastosowanie
Funkcja w języku Pascal (prog2_5.pas):
function
nww (a, b: integer): integer;
begin
nww:=a*b
div
nwd(a,b)
end;
Zadanie 2.1.
Podaj specyfikację zadania i skonstruuj algorytm w postaci schematu bloko-
wego i programu wykonujący skracanie ułamków zwykłych. Licznik i mia-
nownik ułamka wprowadź z klawiatury.
Zadanie 2.2.
Podaj specyfikację zadania i skonstruuj algorytm w postaci programu wy-
konujący podstawowe operacje arytmetyczne na ułamkach zwykłych, w tym
dodawanie, odejmowanie, mnożenie, dzielenie. Wynik wykonanej opera-
cji powinien być przedstawiony w postaci skróconej, z wyłączeniem części
całkowitej.
2.2.
Wyznaczanie
 
wartości wielomianu,
 
pozycyjne systemy liczbowe
 
i reprezentacja danych
 
liczbowych w komputerze
2.2.1.
Systemy liczbowe
Systemem liczbowym
nazywamy zbiór zasad określających sposób zapi-
sywania i nazywania liczb.
Pozycyjny system liczbowy
to system, w którym wartość cyfry zależy od
miejsca, w jakim znajduje się ona w danej liczbie. Miejsce to nazywa-
my pozycją.
2

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin