Ściągi i notacje

Systemy liczbowe, złożoność, składnia Pythona i SQL — najczęściej potrzebne na maturze z informatyki.

Algorytmy

Złożoność obliczeniowa
klasanazwaprzykład
O(1)staładostęp do elementu tablicy
O(log n)logarytmicznawyszukiwanie binarne, NWD
O(n)liniowamaksimum, zliczanie
O(n log n)quasi-liniowasortowanie przez scalanie
O(n²)kwadratowasortowanie bąbelkowe
O(2ⁿ)wykładniczaFibonacci 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.

Przykład: Dwie zagnieżdżone pętle po n ⇒ O(n²)
Algorytm Euklidesa (NWD)
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).

Przykład: nwd(48, 18) = 6
Cyfry liczby bez napisów
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).

Przykład: 12345 → 5, 4, 3, 2, 1

Arkusz kalkulacyjny

Funkcje arkusza (Excel / LibreOffice)
celfunkcja
warunekJEŻELI(warunek; wtedy; inaczej)
liczenieLICZ.JEŻELI, LICZ.WARUNKI
suma / średniaSUMA.JEŻELI, ŚREDNIA.JEŻELI
wyszukiwanieWYSZUKAJ.PIONOWO, INDEKS+PODAJ.POZYCJĘ
datyMIESIĄC, ROK, DZIEŃ.TYG
zaokrąglenieZAOKR(liczba; cyfry)

Adresowanie bezwzględne parametrów: $B$1.

Zastosowanie: Średnie miesięczne: tabela przestawna lub ŚREDNIA.JEŻELI po numerze miesiąca.

Przykład: =ZAOKR(ŚREDNIA(B2:B32);1)

Python

Czytanie pliku i zliczanie
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().

Przykład: licznik.get(k, 0) + 1
Kody znaków, napisy i wycinki
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:].

Przykład: sum(ord(c) for c in "oko") = 329

SQL

Składnia zapytania SELECT
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.

Przykład: COUNT(*), SUM(), AVG(), MIN(), MAX()
Klient bez zakupów (LEFT JOIN)
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”.

Przykład: IS NULL zamiast = NULL

Sieci

Długość adresów IP
wersjadługośćzapis
IPv432 bity4 oktety dziesiętnie, np. 192.168.0.1
IPv6128 bitów8 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.

Przykład: /24 ⇒ 254 hosty
Szyfrowanie: symetryczne i asymetryczne
typkluczprzykład
symetrycznejeden wspólnyAES
asymetrycznepubliczny + prywatnyRSA
skrót (hash)brak, jednokierunkowySHA-256

Publiczny klucz szyfruje, prywatny deszyfruje; podpis cyfrowy — odwrotnie.

Zastosowanie: Zadania testowe o bezpieczeństwie i certyfikatach.

Przykład: Szyfr Cezara: (litera + k) mod 26

Systemy liczbowe

Potęgi dwójki i konwersje
n2ⁿn2ⁿ
01664
127128
248256
38101024
4161665 536
532324 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ᵏ.

Przykład: A5₁₆ = 1010 0101₂ = 165₁₀
Kod uzupełnień do 2 (U2)

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.

Przykład: −5 na 8 bitach: 11111011