Zapisz się na listę

Teoretyczne podstawy informatyki: co naprawdę sprawdza to zadanie

Logika, zapis wyrażeń, kryptografia i koszt algorytmu. Odpowiedź jest tu zwykle krótka, powstaje na kartce i opiera się na rozumowaniu, a nie na działającym programie.

26
zadań w tym dziale

Dział obejmuje logikę i algebrę Boole’a: tablice prawdy, prawa de Morgana i bramki logiczne. Należą do niego też zapis wyrażeń w notacji infiksowej, prefiksowej i w odwrotnej notacji polskiej, kryptografia razem z podpisem elektronicznym i funkcją skrótu, porównywanie efektywności algorytmów oraz myślenie komputacyjne, w tym modelowanie problemu grafem. Zadania są zamknięte albo wymagają krótkiej odpowiedzi. Polecenie każe uzupełnić tablicę prawdy lub uprościć wyrażenie logiczne, obliczyć wartość wyrażenia w odwrotnej notacji polskiej, zaszyfrować tekst szyfrem przesuwającym albo wskazać, którym kluczem się podpisuje, a którym weryfikuje podpis.

Ze złożoności obliczeniowej w zakresie jest notacja O, czyli opis tego, jak liczba operacji rośnie wraz z rozmiarem danych, oraz porównywanie efektywności algorytmów. Tylko poglądowo pojawiają się klasy problemów łatwych i trudnych oraz problemy nierozstrzygalne, jak problem stopu: nie da się napisać algorytmu, który dla każdego programu rozstrzygnie, czy ten się zatrzyma. Poza zakresem egzaminu leżą dowody formalne i analiza złożoności wykraczająca poza porównanie efektywności.

W pytaniach o koszt algorytmu pułapka polega na tym, że uczeń zna właściwą odpowiedź i podaje ją jako hasło, zamiast uzasadnić. Samo nazwanie klasy kosztu bez pokazania, skąd się bierze, zwykle nie niesie tego, czego wymaga rubryka. Odwrotnie bywa równie kosztownie: rozbudowany opis, który ani razu nie odnosi się do rozmiaru danych.

Zadania maturalne z informatyki: teoria i złożoność — co sprawdzamy w Twoim rozwiązaniu

  • Czy uzasadnienie odwołuje się do rozmiaru danych, a nie do wrażenia o szybkości.
  • Czy w zadaniu z kryptografii klucz prywatny i publiczny mają właściwe role przy podpisie i przy szyfrowaniu.
  • Czy odpowiedź porównuje to, o co prosi polecenie, a nie dwie dowolne rzeczy.
Czego tu nie ma: treści zadań z arkuszy CKE, rozwiązań wzorcowych ani kluczy odpowiedzi. Ta strona opisuje własnymi słowami, czego dotyczy materiał i co sprawdzamy w Twoim rozwiązaniu. Zadania z arkuszy rozwiązuje się w aplikacji, po zalogowaniu.

Najczęstsze pytania

Co z logiki obejmuje dział teoretycznych podstaw informatyki?
Operatory negacji, koniunkcji, alternatywy i alternatywy wykluczającej, tablice prawdy i prawa de Morgana: zaprzeczenie koniunkcji jest alternatywą zaprzeczeń, a zaprzeczenie alternatywy koniunkcją zaprzeczeń. Do tego bramki logiczne NOT, AND, OR, NAND, NOR i XOR, z których buduje się układy cyfrowe. Typowe polecenie każe uzupełnić tablicę prawdy albo uprościć wyrażenie logiczne. Częste pomyłki dotyczą wypełniania tablic prawdy i stosowania praw de Morgana.
Czym odwrotna notacja polska różni się od zwykłego zapisu wyrażeń?
W zwykłym zapisie, czyli w notacji infiksowej, operator stoi między argumentami. W notacji prefiksowej, inaczej przedrostkowej, stoi przed nimi, a w odwrotnej notacji polskiej, czyli w zapisie przyrostkowym, po nich. Dzięki temu zapis w odwrotnej notacji polskiej nie potrzebuje nawiasów ani priorytetów działań, a wartość wyrażenia oblicza się na stosie. Częsty błąd w zadaniach z tą notacją to zła kolejność.
Którym kluczem podpisuje się dokument, a którym szyfruje wiadomość?
Podpis elektroniczny tworzy się kluczem prywatnym, a weryfikuje kluczem publicznym. Taki podpis potwierdza autentyczność i integralność dokumentu. Przy szyfrowaniu asymetrycznym jest odwrotnie: kluczem publicznym się szyfruje, a prywatnym odszyfrowuje. Pomylenie tych ról to typowy błąd w zadaniach z kryptografii. W szyfrze symetrycznym, na przykład w szyfrze Cezara przesuwającym litery alfabetu o stałą liczbę pozycji, ten sam klucz służy do szyfrowania i odszyfrowania. Funkcja skrótu jest jednokierunkowa i daje wynik stałej długości, dlatego używa się jej przy hasłach i do sprawdzania integralności danych.

Zobacz też

Matura z informatyki 2027: wymagania i arkusz

Z bloga

SQL na maturze z informatyki: zadanie z bazami danychJak przygotować się do matury z informatyki