Ściągi i notacje
Systemy liczbowe, złożoność, składnia Pythona i SQL — najczęściej potrzebne na maturze z informatyki.
Algorytmy
| klasa | nazwa | przykład |
|---|---|---|
| O(1) | stała | dostęp do elementu tablicy |
| O(log n) | logarytmiczna | wyszukiwanie binarne, NWD |
| O(n) | liniowa | maksimum, zliczanie |
| O(n log n) | quasi-liniowa | sortowanie przez scalanie |
| O(n²) | kwadratowa | sortowanie bąbelkowe |
| O(2ⁿ) | wykładnicza | Fibonacci rekurencyjny bez memoizacji |
Rząd wzrostu liczby operacji w zależności od rozmiaru danych n.
Zastosowanie: Uzasadnianie wyboru algorytmu; zagnieżdżone pętle ⇒ mnożenie złożoności.
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
Największy wspólny dzielnik w O(log min(a,b)).
Zastosowanie: Skracanie ułamków, NWW(a,b) = a·b / NWD(a,b).
ostatnia = n % 10 # cyfra jedności
reszta = n // 10 # bez ostatniej cyfry
while n > 0:
cyfra = n % 10
n //= 10
Rozbijanie liczby na cyfry wyłącznie operacjami arytmetycznymi.
Zastosowanie: Zadania z zakazem używania napisów, tablic i funkcji wbudowanych (np. przeniesienia w dodawaniu pisemnym).
Arkusz kalkulacyjny
| cel | funkcja |
|---|---|
| warunek | JEŻELI(warunek; wtedy; inaczej) |
| liczenie | LICZ.JEŻELI, LICZ.WARUNKI |
| suma / średnia | SUMA.JEŻELI, ŚREDNIA.JEŻELI |
| wyszukiwanie | WYSZUKAJ.PIONOWO, INDEKS+PODAJ.POZYCJĘ |
| daty | MIESIĄC, ROK, DZIEŃ.TYG |
| zaokrąglenie | ZAOKR(liczba; cyfry) |
Adresowanie bezwzględne parametrów: $B$1.
Zastosowanie: Średnie miesięczne: tabela przestawna lub ŚREDNIA.JEŻELI po numerze miesiąca.
Python
licznik = {}
with open("dane.txt") as f:
f.readline() # nagłówek
for linia in f:
pola = linia.strip().split("\t")
klucz = pola[2]
licznik[klucz] = licznik.get(klucz, 0) + 1
najczestszy = max(licznik, key=licznik.get)
Wzorzec dla zadań „który klient / sklep / słowo występuje najczęściej”.
Zastosowanie: Pliki rozdzielane tabulatorem; przecinek dziesiętny zamień na kropkę przed float().
ord("a") # 97
chr(97) # "a"
s[:k] # pierwsze k znaków (prefiks)
s[-k:] # ostatnie k znaków (sufiks)
s[::-1] # odwrócony napis
s == s[::-1] # palindrom
sum(ord(c) for c in s) # suma kodów ASCII
Podstawowe operacje w zadaniach tekstowych.
Zastosowanie: Prefiksosufiks: porównaj s1[:k] z s2[-k:] oraz s2[:k] z s1[-k:].
SQL
SELECT DISTINCT p.IdProduktu, p.Nazwa
FROM Produkty p
JOIN Kategorie k ON p.IdKategorii = k.IdKategorii
WHERE k.NazwaKategorii = 'spozywcze'
AND p.Opis LIKE '%fragment%'
GROUP BY ... HAVING ... ORDER BY ... DESC;
Kolejność klauzul: SELECT → FROM → JOIN → WHERE → GROUP BY → HAVING → ORDER BY.
Zastosowanie: WHERE filtruje wiersze, HAVING — grupy po agregacji; LIKE '%tekst%' — zawiera fragment.
SELECT k.IdKlienta, k.Imie, k.Nazwisko
FROM klienci k
LEFT JOIN transakcje t ON t.IdKlienta = k.IdKlienta
WHERE t.IdTransakcji IS NULL;
LEFT JOIN zachowuje wszystkie wiersze z lewej tabeli; brak dopasowania daje NULL.
Zastosowanie: Zadania „którzy klienci niczego nie kupili”.
Sieci
| wersja | długość | zapis |
|---|---|---|
| IPv4 | 32 bity | 4 oktety dziesiętnie, np. 192.168.0.1 |
| IPv6 | 128 bitów | 8 grup szesnastkowych, np. 2001:db8::1 |
Adres sieci = adres AND maska. Maska /k ⇒ 2^(32−k) − 2 adresów hostów.
Zastosowanie: Zadania o liczbie bitów, podsieciach i maskach.
| typ | klucz | przykład |
|---|---|---|
| symetryczne | jeden wspólny | AES |
| asymetryczne | publiczny + prywatny | RSA |
| skrót (hash) | brak, jednokierunkowy | SHA-256 |
Publiczny klucz szyfruje, prywatny deszyfruje; podpis cyfrowy — odwrotnie.
Zastosowanie: Zadania testowe o bezpieczeństwie i certyfikatach.
Systemy liczbowe
| n | 2ⁿ | n | 2ⁿ |
|---|---|---|---|
| 0 | 1 | 6 | 64 |
| 1 | 2 | 7 | 128 |
| 2 | 4 | 8 | 256 |
| 3 | 8 | 10 | 1024 |
| 4 | 16 | 16 | 65 536 |
| 5 | 32 | 32 | 4 294 967 296 |
Do zamiany 2 ↔ 16 grupuj po 4 bity, 2 ↔ 8 — po 3 bity.
Zastosowanie: Szacowanie zakresów, liczba wartości na k bitach = 2ᵏ.
Na n bitach: zakres −2ⁿ⁻¹ … 2ⁿ⁻¹−1.
−x: zaneguj bity x i dodaj 1.
+5 = 00000101
~5 = 11111010
−5 = 11111011
Najstarszy bit informuje o znaku (1 = liczba ujemna).
Zastosowanie: Dodawanie liczb ze znakiem tym samym układem sumującym.