Wojewódzki Konkurs Przedmiotowy z Informatyki (śląskie) - algorytmy i dane

1.Algorytm

Algorytm to skończony, uporządkowany ciąg jednoznacznych kroków, który prowadzi od danych do wyniku. Dobry algorytm jest poprawny (daje dobry wynik dla wszystkich poprawnych danych), skończony (kończy się po skończonej liczbie kroków) i jednoznaczny (każdy krok można wykonać tylko w jeden sposób). Przykłady z życia: przepis kulinarny, instrukcja montażu mebli, opis drogi do szkoły.

2.Specyfikacja problemu

Specyfikacja to dokładny opis problemu przed napisaniem algorytmu: DANE (co algorytm dostaje i jakie warunki muszą one spełniać) oraz WYNIK (co ma zostać obliczone). Przykład: Dane: dwie liczby naturalne a i b większe od 0. Wynik: największy wspólny dzielnik liczb a i b. Specyfikacja nie mówi, JAK liczyć - tylko CO wchodzi i CO wychodzi.

3.Etapy rozwiązywania problemu

1) Sformułowanie problemu i specyfikacja (dane, wynik). 2) Analiza problemu i wybór metody. 3) Zapis algorytmu: lista kroków albo schemat blokowy. 4) Zapis algorytmu w języku programowania, czyli program. 5) Testowanie programu na różnych danych i poprawianie błędów. Testuje się też przypadki szczególne, np. dwie równe liczby albo zero.

4.Lista kroków

Lista kroków to zapis algorytmu w języku naturalnym w postaci ponumerowanych poleceń. Przykład - średnia trzech ocen: Krok 1. Wczytaj oceny a, b, c. Krok 2. Oblicz sumę $s = a + b + c$. Krok 3. Oblicz średnią $sr = s : 3$. Krok 4. Wypisz sr. Koniec. W liście kroków można zapisywać też skoki, np. „Jeśli warunek jest spełniony, wróć do kroku 2”.

5.Schemat blokowy - rodzaje bloków

Schemat blokowy to graficzny zapis algorytmu: bloki połączone strzałkami pokazującymi kolejność działań. Owal (zaokrąglony prostokąt) - początek i koniec (START, STOP). Równoległobok - wejście i wyjście (wczytaj, wypisz). Prostokąt - blok operacyjny, czyli obliczenie lub przypisanie, np. $s \leftarrow a + b$. Romb - blok decyzyjny z warunkiem.

6.Blok decyzyjny i pętla w schemacie blokowym

Blok decyzyjny (romb) zawiera warunek, np. $a > b$, i ma dwa wyjścia: TAK i NIE - tak zapisuje się rozgałęzienie, czyli instrukcję warunkową. Gdy strzałka wraca do bloku, który był już wykonany, powstaje pętla (iteracja): kroki powtarzają się, dopóki warunek w rombie tego wymaga. Każda pętla musi się kiedyś zakończyć, inaczej algorytm nie byłby skończony.

7.Podzielność liczb

Liczba a jest podzielna przez b, gdy reszta z dzielenia a przez b wynosi 0. W Pythonie resztę daje operator %, więc warunek podzielności to a % b == 0. Przykład: 84 % 7 daje 0, więc 84 dzieli się przez 7; 85 % 7 daje 1, więc 85 nie dzieli się przez 7. Liczba n jest parzysta, gdy n % 2 == 0.

8.Dzielenie całkowite i reszta (div i mod)

Dzielenie całkowite daje część całkowitą wyniku, a reszta to to, co zostaje. W Pythonie 17 // 5 daje 3, a 17 % 5 daje 2, bo $17 = 3 \cdot 5 + 2$. W listach kroków i schematach te działania często nazywa się div i mod. Reszta z dzielenia przez b jest zawsze mniejsza od b, a zwykłe dzielenie 17 / 5 daje 3.4.

9.Wyodrębnianie cyfr liczby

Ostatnia cyfra liczby n to n % 10, a liczba bez ostatniej cyfry to n // 10. Powtarzamy te dwa kroki, dopóki n > 0. Przykład dla 472: 472 % 10 = 2 i 472 // 10 = 47; 47 % 10 = 7 i 47 // 10 = 4; 4 % 10 = 4 i 4 // 10 = 0 - koniec. Cyfry poznajemy od końca: 2, 7, 4. Tak liczy się np. sumę cyfr (tu 13) albo liczbę cyfr.

10.Wyszukiwanie dzielników liczby

Najprostszy algorytm: sprawdź po kolei każdą liczbę d od 1 do n; jeśli n % d == 0, to d jest dzielnikiem n. W Pythonie robi się to pętlą for d in range(1, n + 1) z warunkiem if n % d == 0 w środku. Przykład: dzielniki liczby 12 to 1, 2, 3, 4, 6, 12. Każda liczba dzieli się przez 1 i przez samą siebie; liczba, która ma dokładnie te dwa dzielniki, to liczba pierwsza.

11.NWD - największy wspólny dzielnik

NWD(a, b) to największa liczba, przez którą dzielą się bez reszty obie liczby a i b. Przykład: dzielniki 12 to 1, 2, 3, 4, 6, 12, a dzielniki 18 to 1, 2, 3, 6, 9, 18; wspólne są 1, 2, 3, 6, więc $\mathrm{NWD}(12, 18) = 6$. Gdy NWD wynosi 1, liczby są względnie pierwsze, np. 8 i 15. NWD służy m.in. do skracania ułamków.

12.Algorytm Euklidesa z odejmowaniem

Dopóki liczby a i b są różne, od większej odejmij mniejszą i wynikiem zastąp większą. Gdy a = b, ta wspólna wartość to NWD. Przykład dla 12 i 18: $(12, 18) \to (12, 6) \to (6, 6)$, więc $\mathrm{NWD}(12, 18) = 6$. Metoda działa, bo dla a > b liczby a i b mają te same wspólne dzielniki co liczby a - b i b.

13.Algorytm Euklidesa z resztą z dzielenia

Dopóki b jest różne od 0: oblicz resztę r = a % b, potem przyjmij a = b oraz b = r. Gdy b = 0, wynikiem jest a. Przykład dla 48 i 18: 48 % 18 = 12, para (18, 12); 18 % 12 = 6, para (12, 6); 12 % 6 = 0, para (6, 0), więc NWD = 6. W Pythonie: while b != 0: a, b = b, a % b - po pętli w a jest NWD.

14.Porównanie dwóch wersji algorytmu Euklidesa

Obie wersje dają ten sam wynik, ale wersja z resztą zwykle wykonuje dużo mniej kroków, bo jedno dzielenie z resztą zastępuje wiele odejmowań tej samej liczby. Przykład dla 100 i 2: wersja z odejmowaniem potrzebuje 49 odejmowań (100, 98, 96, … aż do 2), a wersja z resztą - jednego kroku, bo 100 % 2 = 0.

15.NWW - najmniejsza wspólna wielokrotność

NWW(a, b) to najmniejsza liczba dodatnia, która dzieli się zarówno przez a, jak i przez b. Łatwo ją obliczyć z NWD: $\mathrm{NWW}(a, b) = a \cdot b : \mathrm{NWD}(a, b)$. Przykład: $\mathrm{NWD}(4, 6) = 2$, więc $\mathrm{NWW}(4, 6) = 24 : 2 = 12$. NWW przydaje się np. przy sprowadzaniu ułamków do wspólnego mianownika.

16.Wyszukiwanie liniowe (sekwencyjne)

Służy do szukania elementu w zbiorze nieuporządkowanym. Przeglądamy elementy po kolei od pierwszego i każdy porównujemy z szukanym. Kończymy, gdy go znajdziemy (podajemy jego pozycję), albo gdy sprawdzimy wszystkie (elementu nie ma). Dla n elementów w najgorszym razie potrzeba n porównań. Przykład: szukając 5 w [8, 3, 5, 1], porównujemy z 8, 3 i 5 - znaleziony po 3 porównaniach.

17.Wyszukiwanie największego i najmniejszego elementu

Przyjmij, że pierwszy element jest największy (max). Przeglądaj kolejne elementy: jeśli któryś jest większy od max, zapamiętaj go jako nowy max. Po przejrzeniu całego ciągu max to największy element. Najmniejszy (min) szuka się tak samo, sprawdzając, czy element jest mniejszy. Dla n elementów potrzeba n - 1 porównań. Przykład: w [7, 3, 9, 2] max = 9, a min = 2.

18.Sortowanie przez wybieranie - zasada

Sortowanie (porządkowanie) to ustawienie elementów w kolejności, np. rosnąco. W sortowaniu przez wybieranie znajdujemy najmniejszy element w nieposortowanej części i zamieniamy go z pierwszym elementem tej części. Część posortowana rośnie o jeden element, a nieposortowana maleje. Dla n elementów wystarczy n - 1 takich przebiegów.

19.Sortowanie przez wybieranie - przykład

Ciąg [5, 3, 8, 1]. Przebieg 1: najmniejszy jest 1, zamiana z 5 daje [1, 3, 8, 5]. Przebieg 2: w części [3, 8, 5] najmniejszy jest 3 - stoi już na miejscu, więc [1, 3, 8, 5]. Przebieg 3: w części [8, 5] najmniejszy jest 5, zamiana z 8 daje [1, 3, 5, 8]. Ostatni element jest już na swoim miejscu, więc 4 elementy wymagają 3 przebiegów.

20.Sortowanie przez zliczanie - zasada

Stosuje się je, gdy sortujemy liczby całkowite z małego zakresu, np. oceny od 1 do 6. Tworzymy tablicę liczników - po jednym dla każdej możliwej wartości - i przeglądając dane, zwiększamy licznik odpowiedniej wartości o 1. Potem wypisujemy każdą wartość, od najmniejszej, tyle razy, ile wskazuje jej licznik. Ten algorytm w ogóle nie porównuje elementów ze sobą.

21.Sortowanie przez zliczanie - przykład

Dane: [3, 1, 2, 3, 1], możliwe wartości od 0 do 3. Liczniki: 0 występuje 0 razy, 1 - 2 razy, 2 - 1 raz, 3 - 2 razy, czyli tablica liczników [0, 2, 1, 2]. Wypisujemy: 1, 1, 2, 3, 3. W Pythonie liczniki to lista, np. licz = [0] * 4, a dla każdej liczby x z danych wykonujemy licz[x] += 1.

22.Wartości logiczne

Wartość logiczna to prawda albo fałsz. W komputerze zapisuje się je jako 1 (prawda) i 0 (fałsz), a w Pythonie jako True i False (typ bool). Wartość logiczną ma każdy warunek, np. 7 > 3 daje True, a 2 == 5 daje False. Od wartości warunku zależy, którą drogą pójdzie algorytm w bloku decyzyjnym albo w instrukcji if.

23.Operatory logiczne: i, lub, nie

Koniunkcja (i, AND, w Pythonie and) jest prawdziwa tylko wtedy, gdy oba warunki są prawdziwe. Alternatywa (lub, OR, w Pythonie or) jest prawdziwa, gdy prawdziwy jest choć jeden warunek. Negacja (nie, NOT, w Pythonie not) odwraca wartość: not True daje False. Przykład: dla x = 5 warunek x > 0 and x < 10 jest prawdziwy, a x > 7 or x < 2 - fałszywy.

24.Bit i bajt

Bit to najmniejsza jednostka informacji: ma wartość 0 albo 1. Bajt (B) to 8 bitów. Na n bitach można zapisać $2^n$ różnych układów, więc jeden bajt ma $2^8 = 256$ możliwości - np. liczby od 0 do 255. Większe jednostki to kilobajt, megabajt i gigabajt; w informatyce 1 KiB (kibibajt) to 1024 bajty, a 1 kB w zapisie dziesiętnym to 1000 bajtów.

25.System binarny (dwójkowy)

System pozycyjny o podstawie 2: używa tylko cyfr 0 i 1. Wartość cyfry zależy od jej pozycji - licząc od prawej, kolejne pozycje mają wagi 1, 2, 4, 8, 16, 32, 64, 128… (potęgi dwójki). Komputer zapisuje w nim wszystkie dane, bo układy elektroniczne łatwo rozróżniają dwa stany, np. jest napięcie albo go nie ma. Zapis z podstawą: $1011_{(2)}$.

26.Zamiana liczby binarnej na dziesiętną

Każdą cyfrę mnożymy przez wagę jej pozycji i dodajemy wyniki - wystarczy dodać wagi pozycji, na których stoi 1. Przykład: $1011_{(2)} = 1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 1 \cdot 1 = 11$. Drugi przykład: $110010_{(2)} = 32 + 16 + 2 = 50$. Największa liczba zapisana na n bitach to same jedynki, np. $1111_{(2)} = 15$.

27.Zamiana liczby dziesiętnej na binarną

Dzielimy liczbę przez 2 i zapisujemy resztę; wynik dzielenia całkowitego znowu dzielimy przez 2 - aż dojdziemy do 0. Reszty czytamy od ostatniej do pierwszej. Przykład dla 13: 13 : 2 = 6 reszta 1; 6 : 2 = 3 reszta 0; 3 : 2 = 1 reszta 1; 1 : 2 = 0 reszta 1. Czytamy od dołu: $13 = 1101_{(2)}$. Sprawdzenie: 8 + 4 + 1 = 13.

28.Dodawanie liczb binarnych

Dodajemy pisemnie od prawej, jak w systemie dziesiętnym, ale w dwójkowym: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 10 (piszemy 0, 1 przenosimy), 1 + 1 + 1 = 11 (piszemy 1, 1 przenosimy). Przykład: $1011_{(2)} + 110_{(2)} = 10001_{(2)}$, czyli 11 + 6 = 17. Wynik łatwo sprawdzić, zamieniając liczby na dziesiętne.

29.System szesnastkowy (heksadecymalny)

System pozycyjny o podstawie 16. Ma 16 cyfr: 0-9 oraz litery A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. Wagi pozycji od prawej to 1, 16, 256… Służy jako krótszy zapis liczb binarnych - np. w kodach kolorów (#FF8800) i adresach pamięci. Liczbę szesnastkową oznacza się np. $\mathrm{2F}_{(16)}$ albo przedrostkiem 0x, np. 0x2F.

30.Zamiana między systemem szesnastkowym a binarnym

Jedna cyfra szesnastkowa odpowiada dokładnie 4 bitom, bo $2^4 = 16$. Z szesnastkowego na binarny: każdą cyfrę zamieniamy na 4 bity, np. $\mathrm{2F}_{(16)}$: 2 = 0010, F = 1111, więc $101111_{(2)}$. Z binarnego na szesnastkowy: dzielimy bity na czwórki od prawej, np. 1101 0110 to D i 6, czyli $\mathrm{D6}_{(16)}$.

31.Zamiana między systemem szesnastkowym a dziesiętnym

Z szesnastkowego na dziesiętny: cyfry mnożymy przez wagi 1, 16, 256… i dodajemy, np. $\mathrm{2F}_{(16)} = 2 \cdot 16 + 15 = 47$. Z dziesiętnego na szesnastkowy: dzielimy przez 16 i zapisujemy reszty (10-15 jako A-F), czytając od dołu, np. 200 : 16 = 12 reszta 8, 12 : 16 = 0 reszta 12, czyli C, więc $200 = \mathrm{C8}_{(16)}$. Liczba FF to 255.

32.Kod ASCII

ASCII to standard, który każdemu znakowi przypisuje liczbę (kod). Podstawowy ASCII ma 128 kodów (od 0 do 127) i używa 7 bitów; obejmuje cyfry, litery łacińskie, znaki interpunkcyjne i znaki sterujące. Warto pamiętać: spacja = 32, '0' = 48, 'A' = 65, 'a' = 97. Kolejne litery mają kolejne kody ('B' = 66), a mała litera ma kod o 32 większy od wielkiej.

33.Tekst w komputerze i Unicode

Tekst zapisuje się jako ciąg kodów kolejnych znaków, np. słowo „Ala” to kody 65, 108, 97. ASCII nie zawiera polskich liter (ą, ę, ł…), dlatego dziś stosuje się Unicode - standard obejmujący znaki niemal wszystkich języków świata, zwykle zapisywany w kodowaniu UTF-8. W Pythonie ord('A') daje 65, a chr(66) daje 'B'.

34.Grafika rastrowa (bitmapowa)

Obraz rastrowy to siatka pikseli (punktów), z których każdy ma jeden kolor zapisany liczbami. Dobrze nadaje się do zdjęć i obrazów z płynnymi przejściami barw. Przy dużym powiększeniu widać pojedyncze piksele i „schodki” na krawędziach (pikselizacja), więc jakość spada. Przykładowe formaty: BMP, PNG, JPG, GIF. Grafikę rastrową tworzą m.in. aparat cyfrowy, skaner i programy do rysowania, czyli edytory grafiki rastrowej.

35.Rozdzielczość i głębia kolorów

Rozdzielczość obrazu to liczba pikseli w poziomie i w pionie, np. $1920 \times 1080$. Głębia kolorów to liczba bitów przypadających na jeden piksel: 1 bit daje 2 kolory (czarny i biały), 8 bitów - 256 kolorów, 24 bity - $2^{24}$, czyli ok. 16,7 mln kolorów. Im większa rozdzielczość i głębia kolorów, tym obraz dokładniejszy, ale plik większy.

36.Model barw RGB

W modelu RGB każdy kolor powstaje z mieszania światła czerwonego (Red), zielonego (Green) i niebieskiego (Blue). Przy 24 bitach każda składowa ma 8 bitów, czyli wartość od 0 do 255: (0, 0, 0) to czerń, (255, 255, 255) biel, (255, 0, 0) czerwień. W stronach WWW kolor zapisuje się szesnastkowo jako #RRGGBB, np. #FF0000 to czerwony, a #FFFFFF biały. RGB stosują ekrany; drukarki używają modelu CMYK.

37.Rozmiar obrazu rastrowego

Rozmiar obrazu bez kompresji w bitach to liczba pikseli w poziomie razy liczba pikseli w pionie razy głębia kolorów (bity na piksel). Aby otrzymać bajty, dzielimy przez 8. Przykład: obraz 100 na 50 pikseli, 24 bity na piksel: $100 \cdot 50 \cdot 24 = 120\,000$ bitów, czyli $120\,000 : 8 = 15\,000$ bajtów. Dwukrotnie większa szerokość i wysokość dają czterokrotnie większy plik.

38.Grafika wektorowa

Obraz wektorowy składa się z obiektów opisanych matematycznie: odcinków, krzywych, wielokątów i okręgów - zapisuje się ich współrzędne, grubość linii i kolor wypełnienia. Taki obraz można dowolnie powiększać bez utraty jakości, bo program za każdym razem rysuje go na nowo. Nadaje się do logo, ikon, schematów, map i krojów pisma, ale nie do zdjęć. Przykładowy format: SVG.

39.Zapis dźwięku - próbkowanie

Dźwięk to fala, a komputer zapisuje go jako ciąg liczb. Próbkowanie to mierzenie wychylenia fali w równych odstępach czasu. Częstotliwość próbkowania to liczba próbek na sekundę (w hercach, Hz), np. 44 100 Hz w jakości płyty CD. Rozdzielczość bitowa (np. 16 bitów) mówi, jak dokładnie zapisuje się każdą próbkę. Dźwięk stereo ma 2 kanały. Formaty: WAV (zwykle bez kompresji), MP3 (z kompresją, mniejszy plik).

40.Zapis wideo

Film cyfrowy to szybko wyświetlana sekwencja obrazów rastrowych (klatek) razem ze ścieżką dźwiękową. Płynność ruchu zależy od liczby klatek na sekundę (fps), np. 25 lub 30; jakość obrazu - od rozdzielczości klatki, np. Full HD to $1920 \times 1080$ pikseli. Nieskompresowany film zajmowałby ogromnie dużo miejsca, dlatego używa się kodeków, które go kompresują. Popularne formaty plików wideo: MP4, AVI, MKV.