CKE Egzamin Zawodowy INF.04 & Matura Rozszerzona z Informatyki — Algorytmika, złożoność obliczeniowa, OOP (C++/C#/Python) i testowanie

32 zaawansowane zagadnienia z kwalifikacji zawodowej INF.04 (Projektowanie, programowanie i testowanie aplikacji) oraz matury rozszerzonej z informatyki CKE: algorytmy sortowania i wyszukiwania (z wartownikiem, binarne), złożoność obliczeniowa, algorytm Euklidesa, Sito Eratostenesa, schemat Hornera, ONP, programowanie dynamiczne i zachłanne, struktury danych (stos, kolejka, BST, grafy BFS/DFS), programowanie obiektowe OOP w C++/C#/Python, wzorce projektowe GoF, zasady SOLID, testy jednostkowe AAA, diagramy UML, Scrum, Git oraz aplikacje desktopowe (WPF/WinForms) i webowe (React/Angular).

Level
advanced
Languages
pl → pl
Cards
32
Markdown
CKE Egzamin Zawodowy INF.04 & Matura Rozszerzona z Informatyki — Algorytmika, złożoność obliczeniowa, OOP (C++/C#/Python) i testowanie (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Jak przebiega część praktyczna egzaminu zawodowego CKE w kwalifikacji INF.04 (Projektowanie, programowanie i testowanie aplikacji) oraz egzamin maturalny z informatyki na poziomie rozszerzonym?W części praktycznej **INF.04** (czas **180 minut**, próg zdawalności **minimum 75%**) zdający tworzy: (1) aplikację konsolową (implementującą zadany algorytm lub strukturę obiektową w C++, C#, Java lub Python), (2) aplikację desktopową (WPF, WinForms, Qt), mobilną (Android/Xamarin/.NET MAUI) lub webową (React/Angular) oraz (3) dokumentację techniczną i testy. **Matura rozszerzona z informatyki CKE** trwa **210 minut** przy komputerze (50 punktów, z czego większość to zadania algorytmiczne w C++/Python/Java, analiza baz danych SQL oraz arkusz kalkulacyjny).Dokumentacja egzaminacyjna w INF.04 (zrzuty ekranu z działania aplikacji konsolowej i okienkowej/webowej/mobilnej, opis wykorzystanego systemu operacyjnego, IDE, języków i bibliotek) jest punktowana osobno i stanowi łatwe punkty do przekroczenia progu 75%.
  • Egzamin praktyczny INF.04 trwa 90 minut z progiem 50%, a matura z informatyki pisana jest wyłącznie na kartce papieru bez komputera
  • W części praktycznej **INF.04** (czas **180 minut**, próg zdawalności **minimum 75%**) zdający tworzy: (1) aplikację konsolową (implementującą zadany algorytm lub strukturę obiektową w C++, C#, Java lub Python), (2) aplikację desktopową (WPF, WinForms, Qt), mobilną (Android/Xamarin/.NET MAUI) lub webową (React/Angular) oraz (3) dokumentację techniczną i testy. **Matura rozszerzona z informatyki CKE** trwa **210 minut** przy komputerze (50 punktów, z czego większość to zadania algorytmiczne w C++/Python/Java, analiza baz danych SQL oraz arkusz kalkulacyjny).
  • W kwalifikacji INF.04 jedynym dopuszczalnym językiem programowania jest język PHP
  • Na maturze rozszerzonej z informatyki obowiązuje minimalny próg zdawalności 50%
2Czym różni się konstruktor domyślny, parametrowy i kopiujący oraz destruktor w C++/C#/Python i kiedy wywoływany jest konstruktor kopiujący?**Konstruktor** to metoda specjalna wywoływana automatycznie podczas tworzenia obiektu (w C++/C#/Java ma nazwę identyczną z nazwą klasy i brak typu zwracanego; w Pythonie to metoda `__init__(self, ...)`). **Konstruktor kopiujący** w C++ (`Klasa(const Klasa& wzorzec)`) tworzy nowy obiekt jako kopię istniejącego obiektu tej samej klasy (wywoływany np. przy przekazywaniu obiektu przez wartość lub inicjalizacji `Klasa b = a;`). **Destruktor** (`~Klasa()` w C++) jest wywoływany przed zniszczeniem obiektu i służy do zwalniania zasobów (np. dynamicznie zaalokowanej pamięci `delete` lub otwartych plików).Ważny szczegół z C++: parametr konstruktora kopiującego MUSI być przekazany przez **referencję** (`const Klasa& wzorzec`), ponieważ przekazanie przez wartość wymagałoby wywołania konstruktora kopiującego do skopiowania samego argumentu, prowadząc do nieskończonej rekurencji!
  • **Konstruktor** to metoda specjalna wywoływana automatycznie podczas tworzenia obiektu (w C++/C#/Java ma nazwę identyczną z nazwą klasy i brak typu zwracanego; w Pythonie to metoda `__init__(self, ...)`). **Konstruktor kopiujący** w C++ (`Klasa(const Klasa& wzorzec)`) tworzy nowy obiekt jako kopię istniejącego obiektu tej samej klasy (wywoływany np. przy przekazywaniu obiektu przez wartość lub inicjalizacji `Klasa b = a;`). **Destruktor** (`~Klasa()` w C++) jest wywoływany przed zniszczeniem obiektu i służy do zwalniania zasobów (np. dynamicznie zaalokowanej pamięci `delete` lub otwartych plików).
  • Konstruktor w C++ i C# musi mieć zadeklarowany typ zwracany void, a w Pythonie nazywa się __construct__()
  • W jednej klasie może istnieć wiele przeciążonych destruktorów przyjmujących różne parametry
  • Konstruktor kopiujący w C++ przyjmuje parametr przekazywany przez wartość Klasa(Klasa wzorzec) bez referencji
3Jak działają podstawowe struktury danych: Stos (Stack — LIFO), Kolejka (Queue — FIFO), Lista jednokierunkowa/dwukierunkowa oraz Drzewo binarne poszukiwań (BST)?**Stos (Stack)** działa według zasady **LIFO (Last In, First Out — ostatni na wejściu, pierwszy na wyjściu)** z operacjami `push` (włóż na szczyt) i `pop` (zdejmij ze szczytu) w czasie O(1) — używany np. do wywołań rekurencyjnych, cofania operacji Undo i notacji ONP. **Kolejka (Queue)** działa według zasady **FIFO (First In, First Out — pierwszy na wejściu, pierwszy na wyjściu)** z operacjami `enqueue` (dodaj na koniec) i `dequeue` (pobierz z początku) w czasie O(1). **Drzewo BST**: dla każdego węzła wszystkie klucze w lewym poddrzewie są mniejsze, a w prawym poddrzewie większe (wyszukiwanie średnio O(log n), przejście **In-order** wypisuje elementy posortowane rosnąco!).Trzy klasyczne porządki przechodzenia drzewa binarnego (DFS): **Pre-order** (Korzeń -> Lewe -> Prawe), **In-order** (Lewe -> Korzeń -> Prawe), **Post-order** (Lewe -> Prawe -> Korzeń), a przechodzenie poziomami (BFS) wykorzystuje kolejkę FIFO.
  • Stos działa w trybie FIFO (pierwszy wchodzi, pierwszy wychodzi), a kolejka w trybie LIFO
  • Dostęp do i-tego elementu listy jednokierunkowej po indeksie ma złożoność czasową O(1) tak samo jak w tablicy
  • Przejście Pre-order w drzewie BST odwiedza najpierw lewe poddrzewo, potem prawe, a na końcu korzeń
  • **Stos (Stack)** działa według zasady **LIFO (Last In, First Out — ostatni na wejściu, pierwszy na wyjściu)** z operacjami `push` (włóż na szczyt) i `pop` (zdejmij ze szczytu) w czasie O(1) — używany np. do wywołań rekurencyjnych, cofania operacji Undo i notacji ONP. **Kolejka (Queue)** działa według zasady **FIFO (First In, First Out — pierwszy na wejściu, pierwszy na wyjściu)** z operacjami `enqueue` (dodaj na koniec) i `dequeue` (pobierz z początku) w czasie O(1). **Drzewo BST**: dla każdego węzła wszystkie klucze w lewym poddrzewie są mniejsze, a w prawym poddrzewie większe (wyszukiwanie średnio O(log n), przejście **In-order** wypisuje elementy posortowane rosnąco!).
4Jak działa reprezentacja liczb całkowitych ze znakiem w kodzie U2 (uzupełnieniowym do dwóch — Two's Complement) oraz dlaczego w arytmetyce zmiennoprzecinkowej IEEE 754 wyrażenie `0.1 + 0.2 == 0.3` daje `false`?W **n-bitowym kodzie U2** najstarszy bit (MSB) ma wagę ujemną **-2^{n-1}**, a pozostałe bity mają standardowe wagi dodatnie $2^{n-2}, ..., 2^0$ (zakres 8-bitowego U2 to **-128 ... +127**; aby zmienić znak liczby w U2, negujemy wszystkie bity — kod U1 — i dodajemy `1`). W standardzie zmiennoprzecinkowym **IEEE 754** (`float` 32-bit, `double` 64-bit: bit znaku, cecha/wykładnik z obciążeniem bias, mantysa) ułamki dziesiętne takie jak `0.1` i `0.2` mają **nieskończone rozwinięcie okresowe w systemie dwójkowym**, co powoduje zaokrąglenie mantysy (`0.1 + 0.2 = 0.30000000000000004`); dlatego liczby zmiennoprzecinkowe porównuje się zawsze z dokładnością epsilon: **`abs(a - b) < 1e-9`**!W 8-bitowym kodzie **U2** liczba `-1` ma postać `11111111_U2` (`-128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1`), a `-128` ma postać `10000000_U2` (natomiast `10000001` to `-1` w kodzie znak-moduł ZM, a w U2 jest to `-127`!).
  • W **n-bitowym kodzie U2** najstarszy bit (MSB) ma wagę ujemną **-2^{n-1}**, a pozostałe bity mają standardowe wagi dodatnie $2^{n-2}, ..., 2^0$ (zakres 8-bitowego U2 to **-128 ... +127**; aby zmienić znak liczby w U2, negujemy wszystkie bity — kod U1 — i dodajemy `1`). W standardzie zmiennoprzecinkowym **IEEE 754** (`float` 32-bit, `double` 64-bit: bit znaku, cecha/wykładnik z obciążeniem bias, mantysa) ułamki dziesiętne takie jak `0.1` i `0.2` mają **nieskończone rozwinięcie okresowe w systemie dwójkowym**, co powoduje zaokrąglenie mantysy (`0.1 + 0.2 = 0.30000000000000004`); dlatego liczby zmiennoprzecinkowe porównuje się zawsze z dokładnością epsilon: **`abs(a - b) < 1e-9`**!
  • W 8-bitowym kodzie U2 zakres liczb wynosi od -127 do +128 i występują dwie różne reprezentacje zera (+0 oraz -0)
  • Typ double w standardzie IEEE 754 przechowuje ułamki dziesiętne bez żadnych błędów zaokrągleń
  • Liczba -1 w 8-bitowym kodzie uzupełnieniowym U2 ma postać binarną 10000001
5Czym różnią się modyfikatory dostępu `public`, `private` oraz `protected` w językach C++, C# i Java i jaki jest domyślny modyfikator w `class` vs `struct` w języku C++?**`public`**: składnik dostępny z dowolnego miejsca w programie. **`private`**: składnik dostępny wyłącznie wewnątrz danej klasy (oraz dla funkcji/klas zaprzyjaźnionych `friend` w C++) — klasy pochodne NIE mają do niego bezpośredniego dostępu! **`protected`**: składnik niedostępny z zewnątrz klasy, ale **dostępny w klasach pochodnych (dziedziczących)**. W języku C++ domyślnym modyfikatorem dostępu w **`class`** jest **`private`**, natomiast w **`struct`** domyślnym modyfikatorem jest **`public`**.Jeśli arkusz INF.04 brzmi: „Pola klasy powinny być dostępne w klasie bazowej oraz w klasach potomnych, ale niedostępne dla innych klas”, należy użyć modyfikatora **`protected`**!
  • Składniki private są bezpośrednio dostępne w klasach dziedziczących, a składniki protected są dostępne tylko w tej samej klasie
  • W języku C++ w słowie kluczowym class wszystkie pola są domyślnie publiczne
  • **`public`**: składnik dostępny z dowolnego miejsca w programie. **`private`**: składnik dostępny wyłącznie wewnątrz danej klasy (oraz dla funkcji/klas zaprzyjaźnionych `friend` w C++) — klasy pochodne NIE mają do niego bezpośredniego dostępu! **`protected`**: składnik niedostępny z zewnątrz klasy, ale **dostępny w klasach pochodnych (dziedziczących)**. W języku C++ domyślnym modyfikatorem dostępu w **`class`** jest **`private`**, natomiast w **`struct`** domyślnym modyfikatorem jest **`public`**.
  • Modyfikator protected pozwala na odczyt pola z funkcji main() na dowolnym obiekcie klasy
6Czym różni się przekazywanie argumentów do funkcji przez wartość (pass by value) od przekazywania przez referencję (`&` w C++, `ref` / `out` w C#) lub wskaźnik (`*`)?Przy przekazywaniu **przez wartość** (`void f(int x)`) funkcja pracuje na lokalnej **kopii** argumentu, więc zmiana parametru `x` wewnątrz funkcji NIE zmienia zmiennej oryginalnej w miejscu wywołania. Przy przekazywaniu **przez referencję** (`void f(int &x)` w C++ lub `void f(ref int x)` w C#) parametr jest aliasem oryginalnej zmiennej, więc każda jego modyfikacja wewnątrz funkcji zmienia bezpośrednio zmienną przekazaną przez wywołującego (i unika kosztownego kopiowania dużych struktur/wektorów, np. `const vector<int>& v`).W Pythonie zmienne przechowują referencje do obiektów: modyfikacja zawartości obiektu mutowalnego (np. `lista.append(5)` lub `tab[0] = 9` wewnątrz funkcji) zmienia oryginalną listę, natomiast przypisanie nowej wartości do zmiennej niemutowalnej (`int`, `str`, `tuple`) tworzy nowy obiekt lokalny.
  • W języku C++ zapis void zamien(int a, int b) zamienia miejscami wartości zmiennych w funkcji main()
  • W języku Python typy mutowalne takie jak lista (list) lub słownik (dict) przekazane do funkcji nie mogą zostać zmodyfikowane wewnątrz tej funkcji
  • Przekazanie dużego obiektu przez wartość const Klasa v jest zawsze szybsze niż przekazanie przez stałą referencję const Klasa& v
  • Przy przekazywaniu **przez wartość** (`void f(int x)`) funkcja pracuje na lokalnej **kopii** argumentu, więc zmiana parametru `x` wewnątrz funkcji NIE zmienia zmiennej oryginalnej w miejscu wywołania. Przy przekazywaniu **przez referencję** (`void f(int &x)` w C++ lub `void f(ref int x)` w C#) parametr jest aliasem oryginalnej zmiennej, więc każda jego modyfikacja wewnątrz funkcji zmienia bezpośrednio zmienną przekazaną przez wywołującego (i unika kosztownego kopiowania dużych struktur/wektorów, np. `const vector<int>& v`).
7Jak działa przeszukiwanie grafu wszerz (BFS — Breadth-First Search) oraz w głąb (DFS — Depth-First Search) i jaka jest ich złożoność obliczeniowa dla listy sąsiedztwa?**BFS (przeszukiwanie wszerz)** używa **kolejki FIFO**: odwiedza wierzchołki warstwami (najpierw sąsiadów w odległości 1 krawędzi, potem 2 krawędzi itd.), dzięki czemu w grafie nieważonym **znajduje najkrótsze ścieżki** od źródła do wszystkich osiągalnych wierzchołków. **DFS (przeszukiwanie w głąb)** używa **rekurencji lub stosu LIFO**: podąża wzdłuż ścieżki tak głęboko, jak to możliwe, zanim się cofnie (backtracking) — służy m.in. do wykrywania cykli, sortowania topologicznego i spójnych składowych. Dla reprezentacji przez **listę sąsiedztwa** oba algorytmy mają złożoność czasową **O(V + E)** (a dla macierzy sąsiedztwa O(V²)).Gdy krawędzie grafu mają nieujemne wagi liczbowe, do wyznaczania najkrótszych ścieżek zamiast BFS stosuje się **algorytm Dijkstry** z kolejką priorytetową (kopcem binarnym) o złożoności **O((V + E) log V)**.
  • Algorytm BFS wykorzystuje stos LIFO, a algorytm DFS wykorzystuje kolejkę FIFO
  • **BFS (przeszukiwanie wszerz)** używa **kolejki FIFO**: odwiedza wierzchołki warstwami (najpierw sąsiadów w odległości 1 krawędzi, potem 2 krawędzi itd.), dzięki czemu w grafie nieważonym **znajduje najkrótsze ścieżki** od źródła do wszystkich osiągalnych wierzchołków. **DFS (przeszukiwanie w głąb)** używa **rekurencji lub stosu LIFO**: podąża wzdłuż ścieżki tak głęboko, jak to możliwe, zanim się cofnie (backtracking) — służy m.in. do wykrywania cykli, sortowania topologicznego i spójnych składowych. Dla reprezentacji przez **listę sąsiedztwa** oba algorytmy mają złożoność czasową **O(V + E)** (a dla macierzy sąsiedztwa O(V²)).
  • Do wyznaczenia najkrótszych ścieżek w grafie ważonym z dodatnimi wagami krawędzi służy zwykły algorytm DFS
  • Macierz sąsiedztwa dla rzadkiego grafu o 100 000 wierzchołków zajmuje mniej pamięci niż lista sąsiedztwa
8Na czym polega wyszukiwanie binarne (połówkowe — Binary Search) oraz wyszukiwanie liniowe z wartownikiem (Linear Search with Sentinel) i jakie mają złożoności obliczeniowe?**Wyszukiwanie liniowe z wartownikiem** działa na dowolnej (także nieposortowanej) tablicy o rozmiarze n: poszukiwany element x dopisuje się na końcu tablicy jako wartownika na indeksie n, dzięki czemu w pli `while (tab[i] != x)` unika się sprawdzania warunku końca tablicy `i < n` w każdym kroku (złożoność czasowa **O(n)**). **Wyszukiwanie binarne** wymaga **tablicy posortowanej** i w każdym kroku odrzuca połowę przedziału poszukiwań (`srodek = (lewy + prawy) // 2`), osiągając złożoność czasową **O(log n)** (np. dla 1 000 000 elementów maksymalnie 20 porównań).Zarówno wyszukiwanie liniowe z wartownikiem (np. w tablicy 50 pseudolosowych liczb z przedziału 1..100), jak i wyszukiwanie binarne należą do kanonu jawnych zadań egzaminacyjnych CKE INF.04.
  • Wyszukiwanie binarne działa na nieposortowanej tablicy w czasie O(1), a wyszukiwanie z wartownikiem wymaga tablicy posortowanej
  • Dla tablicy 1024-elementowej wyszukiwanie binarne w przypadku pesymistycznym wykonuje 512 porównań
  • Wartownika w wyszukiwaniu liniowym wstawia się zawsze na środkowy indeks tablicy
  • **Wyszukiwanie liniowe z wartownikiem** działa na dowolnej (także nieposortowanej) tablicy o rozmiarze n: poszukiwany element x dopisuje się na końcu tablicy jako wartownika na indeksie n, dzięki czemu w pli `while (tab[i] != x)` unika się sprawdzania warunku końca tablicy `i < n` w każdym kroku (złożoność czasowa **O(n)**). **Wyszukiwanie binarne** wymaga **tablicy posortowanej** i w każdym kroku odrzuca połowę przedziału poszukiwań (`srodek = (lewy + prawy) // 2`), osiągając złożoność czasową **O(log n)** (np. dla 1 000 000 elementów maksymalnie 20 porównań).
9Jak zamienić liczbę naturalną z systemu dziesiętnego na system pozycyjny o podstawie `p` (np. binarny `p=2`, ósemkowy `p=8`, szesnastkowy `p=16`) oraz jak działa schemat Hornera przy zamianie odwrotnej i obliczaniu wartości wielomianu?**Z dziesiętnego na system o podstawie `p`**: wielokrotnie dzielimy liczbę całkowicie przez `p` (`n // p`), zapisując reszty z dzielenia (`n % p`), aż iloraz osiągnie `0`; zapis w systemie o podstawie `p` tworzą reszty odczytane **od końca (od ostatniej do pierwszej)**. **Schemat Hornera** (złożoność liniowa **O(n)** — tylko `n` mnożeń i `n` dodawań zamiast potęgowania): wartość liczby o cyfrach `c_0, c_1, ..., c_k` przy podstawie `p` (lub wielomianu w punkcie `p`) obliczamy iteracyjnie: `wynik = 0; dla każdej kolejnej cyfry c od lewej: wynik = wynik * p + c`.Przykład często występujący na maturze z informatyki i w INF.02/INF.04: `255_10 = 11111111_2 = 377_8 = FF_16`, a zastosowanie schematu Hornera dla `1011_2` daje: `(((1 * 2 + 0) * 2 + 1) * 2 + 1) = 11_10`.
  • Przy zamianie z systemu dziesiętnego na binarny reszty z dzielenia przez 2 odczytuje się od pierwszej do ostatniej
  • Schemat Hornera dla wielomianu stopnia n wymaga wykonania n*(n+1)/2 operacji mnożenia
  • Liczba dziesiętna 255 zapisana w systemie szesnastkowym to 100_16, a w binarnym 10000000_2
  • **Z dziesiętnego na system o podstawie `p`**: wielokrotnie dzielimy liczbę całkowicie przez `p` (`n // p`), zapisując reszty z dzielenia (`n % p`), aż iloraz osiągnie `0`; zapis w systemie o podstawie `p` tworzą reszty odczytane **od końca (od ostatniej do pierwszej)**. **Schemat Hornera** (złożoność liniowa **O(n)** — tylko `n` mnożeń i `n` dodawań zamiast potęgowania): wartość liczby o cyfrach `c_0, c_1, ..., c_k` przy podstawie `p` (lub wielomianu w punkcie `p`) obliczamy iteracyjnie: `wynik = 0; dla każdej kolejnej cyfry c od lewej: wynik = wynik * p + c`.
10Jak oblicza się wartość wyrażenia zapisanego w Odwrotnej Notacji Polskiej (ONP / RPN — notacja postfiksowa) za pomocą stosu, np. dla wyrażenia `2 3 + 5 * 4 -`?Czytamy wyrażenie ONP od lewej do prawej: (1) napotykając liczbę, odkładamy ją na stos (`push`); (2) napotykając operator binarny (`+`, `-`, `*`, `/`), zdejmujemy ze stosu dwa elementy: pierwszy zdjęty to **prawy operand `b`**, drugi zdjęty to **lewy operand `a`**, wykonujemy działanie `a op b` i wynik odkładamy z powrotem na stos. Dla `2 3 + 5 * 4 -`: `2, 3 -> +` daje `5`; `5, 5 -> *` daje `25`; `25, 4 -> -` daje `25 - 4 = 21`.Uwaga na operatory nieprzemienne (`-`, `/`, `^`) w ONP: dla wyrażenia `10 3 -` na stos trafia najpierw `10`, potem `3`; zdejmując ze szczytu otrzymujemy najpierw `b = 3`, a potem `a = 10`, więc obliczamy `a - b = 10 - 3 = 7`!
  • Czytamy wyrażenie ONP od lewej do prawej: (1) napotykając liczbę, odkładamy ją na stos (`push`); (2) napotykając operator binarny (`+`, `-`, `*`, `/`), zdejmujemy ze stosu dwa elementy: pierwszy zdjęty to **prawy operand `b`**, drugi zdjęty to **lewy operand `a`**, wykonujemy działanie `a op b` i wynik odkładamy z powrotem na stos. Dla `2 3 + 5 * 4 -`: `2, 3 -> +` daje `5`; `5, 5 -> *` daje `25`; `25, 4 -> -` daje `25 - 4 = 21`.
  • Wyrażenie ONP wymaga nawiasów do określenia kolejności wykonywania działań, a dla 2 3 + 5 * 4 - wynik wynosi 13
  • Przy odejmowaniu w ONP zawsze odejmujemy drugi zdjęty ze stosu element od pierwszego zdjętego ze stosu
  • Do ewaluacji wyrażenia w Odwrotnej Notacji Polskiej używa się kolejki FIFO zamiast stosu LIFO
11Jakie wzorce projektowe (Design Patterns) i architektoniczne: `Singleton`, `Factory Method`, `Observer`, `Strategy`, `MVC` (Model-View-Controller) oraz `MVVM` (Model-View-ViewModel) występują na egzaminie INF.04?Klasyfikacja GoF (Gang of Four): (1) **Kreacyjne**: **Singleton** (gwarantuje istnienie dokładnie jednej instancji klasy z prywatnym konstruktorem i statyczną metodą dostępową `getInstance()`), **Factory Method / Abstract Factory**, **Builder**; (2) **Strukturalne**: **Adapter**, **Decorator**, **Facade**; (3) **Behawioralne (Czynnościowe)**: **Observer (Obserwator)** (automatyczne powiadamianie subskrybentów o zmianie stanu obiektu), **Strategy (Strategia)** (wymienne algorytmy w czasie działania). Architektoniczne: **MVC** (Model – dane i logika biznesowa, View – widok UI, Controller – obsługa żądań) oraz **MVVM** (stosowany w WPF / .NET MAUI / Angular z dwukierunkowym wiązaniem danych **Data Binding** między View a ViewModel).Pytania o rozpoznanie wzorca projektowego (zwłaszcza **Singleton**, **Obserwator**, **Dekorator**, **Fasada** oraz architektury **MVC** i **MVVM**) pojawiają się w niemal każdym arkuszu części pisemnej INF.04.
  • Wzorzec Singleton pozwala na tworzenie nieograniczonej liczby instancji klasy za pomocą publicznego konstruktora
  • Wzorzec Observer należy do wzorców kreacyjnych, a Factory Method do wzorców behawioralnych
  • Klasyfikacja GoF (Gang of Four): (1) **Kreacyjne**: **Singleton** (gwarantuje istnienie dokładnie jednej instancji klasy z prywatnym konstruktorem i statyczną metodą dostępową `getInstance()`), **Factory Method / Abstract Factory**, **Builder**; (2) **Strukturalne**: **Adapter**, **Decorator**, **Facade**; (3) **Behawioralne (Czynnościowe)**: **Observer (Obserwator)** (automatyczne powiadamianie subskrybentów o zmianie stanu obiektu), **Strategy (Strategia)** (wymienne algorytmy w czasie działania). Architektoniczne: **MVC** (Model – dane i logika biznesowa, View – widok UI, Controller – obsługa żądań) oraz **MVVM** (stosowany w WPF / .NET MAUI / Angular z dwukierunkowym wiązaniem danych **Data Binding** między View a ViewModel).
  • W architekturze MVC warstwa View odpowiada za bezpośrednie wykonywanie zapytań SQL do bazy danych
12Czym różni się przeciążanie metod (Method Overloading — polimorfizm statyczny) od przesłaniania metod (Method Overriding — polimorfizm dynamiczny) w C++, C# i Java?**Przeciążanie (Overloading)** występuje w obrębie tej samej klasy: wiele metod ma tę samą nazwę, ale **różną listę parametrów** (liczba, typy lub kolejność argumentów — sam typ zwracany nie wystarczy do przeciążenia!). **Przesłanianie (Overriding)** występuje między klasą bazową a klasą pochodną: klasa pochodna dostarcza nową implementację metody o **dokładnie takiej samej sygnaturze** (w C++ i C# metoda bazowa musi być oznaczona jako `virtual`, a w klasie pochodnej `override`; w Javie metody nieprywatne i niestatyczne są domyślnie wirtualne, oznaczane adnotacją `@Override`).Konstruktory w klasie również mogą być **przeciążane** (np. konstruktor bezparametrowy oraz konstruktor z 3 parametrami), ale konstruktor nie może być wirtualny.
  • Przeciążanie (Overloading) polega na zmianie samego typu zwracanego funkcji przy identycznej liście parametrów
  • Przesłanianie (Overriding) nie wymaga dziedziczenia i odbywa się wewnątrz jednej pojedynczej klasy
  • Metody statyczne (static) mogą być polimorficznie przesłaniane za pomocą słowa kluczowego virtual
  • **Przeciążanie (Overloading)** występuje w obrębie tej samej klasy: wiele metod ma tę samą nazwę, ale **różną listę parametrów** (liczba, typy lub kolejność argumentów — sam typ zwracany nie wystarczy do przeciążenia!). **Przesłanianie (Overriding)** występuje między klasą bazową a klasą pochodną: klasa pochodna dostarcza nową implementację metody o **dokładnie takiej samej sygnaturze** (w C++ i C# metoda bazowa musi być oznaczona jako `virtual`, a w klasie pochodnej `override`; w Javie metody nieprywatne i niestatyczne są domyślnie wirtualne, oznaczane adnotacją `@Override`).
13Jak metodą „dziel i zwyciężaj” znaleźć jednocześnie minimum i maksimum w tablicy `n`-elementowej wykonując tylko `~1,5 n` porównań zamiast `2n - 2` porównań?Naiwne osobne szukanie minimum i maksimum wymaga `2n - 2` porównań. W metodzie optymalnej (jednoczesnego wyszukiwania min i max) bierzemy elementy z tablicy **parami** `(tab[i], tab[i+1])`: najpierw porównujemy oba elementy ze sobą (**1 porównanie**), a następnie mniejszy z nich porównujemy z dotychczasowym `min` (**1 porównanie**), a większy z dotychczasowym `max` (**1 porównanie**). Dzięki temu dla każdej pary elementów wykonujemy tylko **3 porównania na 2 elementy**, co daje łącznie **`3/2 n - 2` (`1,5 n - 2`) porównań**!Optymalne jednoczesne wyszukiwanie minimum i maksimum (`1,5n - 2` porównań) to klasyczne zagadnienie zarówno na maturze rozszerzonej z informatyki CKE, jak i w części pisemnej INF.04.
  • Najpierw sortujemy tablicę algorytmem bąbelkowym i bierzemy pierwszy oraz ostatni element, co daje 1,5 n porównań
  • Nie da się wyznaczyć jednocześnie minimum i maksimum w tablicy nieposortowanej w mniej niż 2n - 2 porównaniach
  • Algorytm jednoczesnego szukania min i max ma złożoność czasową O(log n)
  • Naiwne osobne szukanie minimum i maksimum wymaga `2n - 2` porównań. W metodzie optymalnej (jednoczesnego wyszukiwania min i max) bierzemy elementy z tablicy **parami** `(tab[i], tab[i+1])`: najpierw porównujemy oba elementy ze sobą (**1 porównanie**), a następnie mniejszy z nich porównujemy z dotychczasowym `min` (**1 porównanie**), a większy z dotychczasowym `max` (**1 porównanie**). Dzięki temu dla każdej pary elementów wykonujemy tylko **3 porównania na 2 elementy**, co daje łącznie **`3/2 n - 2` (`1,5 n - 2`) porównań**!
14Jak w aplikacjach desktopowych C# (WPF / Windows Forms) oraz C++ (Qt) tworzy się obsługę zdarzeń kontrolek (przycisk, lista rozwijana, suwak, pole wyboru) wymaganych na egzaminie praktycznym INF.04?W **WPF (XAML + C#)** układ interfejsu buduje się kontenerami `Grid`, `StackPanel`, `WrapPanel`, a kontrolki to m.in. `TextBox`, `Button` (zdarzenie `Click`), `ComboBox` (`SelectionChanged`), `RadioButton` / `CheckBox` (`IsChecked == true`), `Slider` (`ValueChanged`), `Image` (zmiana obrazu przez `new BitmapImage(new Uri(...))`), a okno komunikatu wyświetla się przez **`MessageBox.Show("Tekst", "Tytuł", MessageBoxButton.OK, MessageBoxImage.Information)`**. W **WinForms** okno komunikatu i kontrolki działają analogicznie (`textBox1.Text`, `checkBox1.Checked`).Drobna, ale bardzo ważna różnica między Windows Forms a WPF na egzaminie INF.04: w **WinForms** napis na etykiecie `Label` lub przycisku `Button` to właściwość **`.Text`**, natomiast w **WPF** to właściwość **`.Content`** (choć pole tekstowe `TextBox` w obu technologiach używa właściwości **`.Text`**!).
  • W WPF i Windows Forms stan zaznaczenia kontrolki CheckBox sprawdza się właściwością .Text == "true"
  • W technologii WPF układ okna definiuje się w języku SQL zamiast w języku znaczników XAML
  • W **WPF (XAML + C#)** układ interfejsu buduje się kontenerami `Grid`, `StackPanel`, `WrapPanel`, a kontrolki to m.in. `TextBox`, `Button` (zdarzenie `Click`), `ComboBox` (`SelectionChanged`), `RadioButton` / `CheckBox` (`IsChecked == true`), `Slider` (`ValueChanged`), `Image` (zmiana obrazu przez `new BitmapImage(new Uri(...))`), a okno komunikatu wyświetla się przez **`MessageBox.Show("Tekst", "Tytuł", MessageBoxButton.OK, MessageBoxImage.Information)`**. W **WinForms** okno komunikatu i kontrolki działają analogicznie (`textBox1.Text`, `checkBox1.Checked`).
  • Aby zmienić tekst etykiety Label w WPF, należy użyć właściwości label1.Value zamiast label1.Content
15Jakie są podstawowe polecenia systemu kontroli wersji Git (`git init`, `clone`, `status`, `add`, `commit`, `branch`, `checkout`/`switch`, `merge`, `pull`, `push`) wymagane w kwalifikacji INF.04?`git init` tworzy nowe lokalne repozytorium; `git clone <url>` pobiera kopię zdalnego repozytorium; `git status` pokazuje stan plików; `git add <plik>` (lub `git add .`) przenosi zmiany ze katalogu roboczego do poczekalni (**Staging Area / Index**); `git commit -m "opis"` trwale zapisuje migawkę z poczekalni w lokalnym repozytorium; `git branch <nazwa>` tworzy gałąź, a `git switch <nazwa>` (lub `git checkout -b <nazwa>`) przełącza gałąź; `git merge <gałąź>` scala zmiany z innej gałęzi do bieżącej; `git push` wysyła commity na zdalny serwer (np. GitHub/GitLab), a `git pull` (`fetch` + `merge`) pobiera i scala zmiany ze zdalnego repozytorium.Plik **`.gitignore`** zawiera listę wzorców plików i katalogów (np. `node_modules/`, `bin/`, `obj/`, `.env`), które Git ma celowo ignorować i nie śledzić w repozytorium.
  • Polecenie git commit natychmiast wysyła kod na zdalny serwer GitHub bez użycia polecenia git push
  • Polecenie git clone służy do zatwierdzania lokalnych zmian w bieżącej gałęzi
  • Plik .gitignore służy do zapisywania haseł dostępowych do serwera Git
  • `git init` tworzy nowe lokalne repozytorium; `git clone <url>` pobiera kopię zdalnego repozytorium; `git status` pokazuje stan plików; `git add <plik>` (lub `git add .`) przenosi zmiany ze katalogu roboczego do poczekalni (**Staging Area / Index**); `git commit -m "opis"` trwale zapisuje migawkę z poczekalni w lokalnym repozytorium; `git branch <nazwa>` tworzy gałąź, a `git switch <nazwa>` (lub `git checkout -b <nazwa>`) przełącza gałąź; `git merge <gałąź>` scala zmiany z innej gałęzi do bieżącej; `git push` wysyła commity na zdalny serwer (np. GitHub/GitLab), a `git pull` (`fetch` + `merge`) pobiera i scala zmiany ze zdalnego repozytorium.
16Jak działa algorytm Euklidesa wyznaczania największego wspólnego dzielnika `NWD(a, b)` w wersji z odejmowaniem oraz w zoptymalizowanej wersji z dzieleniem modulo i jak na jego podstawie oblicza się `NWW(a, b)`?Wersja z odejmowaniem: dopóki `a != b`, od większej liczby odejmujemy mniejszą (`if a > b: a -= b else: b -= a`). Zoptymalizowana wersja z resztą z dzielenia (modulo, złożoność logarytmiczna): dopóki `b != 0`, wykonujemy przypisanie `a, b = b, a % b`, a wynikiem jest `a`. Najmniejszą wspólną wielokrotność obliczamy ze wzoru **`NWW(a, b) = (a * b) / NWD(a, b)`** (w kodzie lepiej zapisać `(a / NWD(a, b)) * b`, aby uniknąć przepełnienia typu całkowitego!).Dla pary liczb `(1000000000, 1)` wersja z odejmowaniem wykona miliard iteracji, podczas gdy wersja z operatorem modulo (`%`) zakończy działanie w **jednym kroku**!
  • W wersji modulo algorytmu Euklidesa pętla wykonuje się dopóki a % b == 0, a NWW(a, b) = (a + b) / NWD(a, b)
  • Wersja z odejmowaniem jest zawsze szybsza od wersji z operatorem modulo dla bardzo odległych liczb (np. 10^9 i 2)
  • Wersja z odejmowaniem: dopóki `a != b`, od większej liczby odejmujemy mniejszą (`if a > b: a -= b else: b -= a`). Zoptymalizowana wersja z resztą z dzielenia (modulo, złożoność logarytmiczna): dopóki `b != 0`, wykonujemy przypisanie `a, b = b, a % b`, a wynikiem jest `a`. Najmniejszą wspólną wielokrotność obliczamy ze wzoru **`NWW(a, b) = (a * b) / NWD(a, b)`** (w kodzie lepiej zapisać `(a / NWD(a, b)) * b`, aby uniknąć przepełnienia typu całkowitego!).
  • Algorytm Euklidesa można zapisać wyłącznie w postaci rekurencyjnej, a nie iteracyjnej
17Czym różnią się metodyki wytwarzania oprogramowania: kaskadowa (Waterfall) oraz zwinna Scrum (role, artefakty, wydarzenia)?**Model kaskadowy (Waterfall)**: liniowa sekwencja faz (Wymagania -> Projekt -> Implementacja -> Testowanie -> Wdrożenie -> Utrzymanie), gdzie kolejna faza zaczyna się po zakończeniu poprzedniej (trudne wprowadzanie zmian w trakcie projektu). **Scrum (framework Agile)**: praca w krótkich iteracjach zwanych **Sprintami** (1–4 tygodnie). **3 role (Accountabilities) w Scrum**: **Product Owner** (odpowiada za wartość produktu i kolejność w Product Backlogu), **Scrum Master** (dba o proces Scrum i usuwa przeszkody), **Developers** (zespół wytwarzający przyrost). **3 artefakty**: Product Backlog, Sprint Backlog, Increment (Przyrost, spełniający *Definition of Done*). **Wydarzenia**: Sprint, Sprint Planning, Daily Scrum (15 min), Sprint Review, Sprint Retrospective.W Scrumie NIE istnieje rola „Project Managera” ani „Team Leadera” — zespół Scrum jest samoorganizujący się (self-managing), a spotkanie **Daily Scrum** ma stały limit czasowy (timebox) wynoszący maksymalnie **15 minut**.
  • W metodyce Scrum kierownik projektu (Project Manager) przydziela zadania programistom podczas 2-godzinnego spotkania Daily Scrum
  • Za priorytetyzację Product Backlogu w Scrum odpowiada wyłącznie Scrum Master
  • W modelu Waterfall działająca wersja oprogramowania dostarczana jest klientowi co dwa tygodnie od pierwszego dnia projektu
  • **Model kaskadowy (Waterfall)**: liniowa sekwencja faz (Wymagania -> Projekt -> Implementacja -> Testowanie -> Wdrożenie -> Utrzymanie), gdzie kolejna faza zaczyna się po zakończeniu poprzedniej (trudne wprowadzanie zmian w trakcie projektu). **Scrum (framework Agile)**: praca w krótkich iteracjach zwanych **Sprintami** (1–4 tygodnie). **3 role (Accountabilities) w Scrum**: **Product Owner** (odpowiada za wartość produktu i kolejność w Product Backlogu), **Scrum Master** (dba o proces Scrum i usuwa przeszkody), **Developers** (zespół wytwarzający przyrost). **3 artefakty**: Product Backlog, Sprint Backlog, Increment (Przyrost, spełniający *Definition of Done*). **Wydarzenia**: Sprint, Sprint Planning, Daily Scrum (15 min), Sprint Review, Sprint Retrospective.
18Jakie rodzaje diagramów języka UML (Unified Modeling Language) dzielą się na diagramy strukturalne i behawioralne oraz co oznaczają relacje na diagramie klas: dziedziczenie (generalizacja), realizacja, asocjacja, agregacja i kompozycja?**Diagramy strukturalne UML**: diagram klas (Class Diagram), obiektów, komponentów, wdrożenia (Deployment). **Diagramy behawioralne (czynnościowe) UML**: diagram przypadków użycia (Use Case — aktorzy, relacje `<<include>>` wykonywana zawsze oraz `<<extend>>` wykonywana warunkowo), diagram sekwencji, aktywności, maszyn stanowych. Na **diagramie klas**: linia ciągła z pustym trójkątnym grotem to **dziedziczenie (generalizacja)**; linia przerywana z pustym trójkątnym grotem to **realizacja interfejsu**; linia z **pustym rombem** to **agregacja** (część może istnieć bez całości); linia z **zamalowanym (pełnym) rombem** to **kompozycja** (silna relacja „część-całość” — usunięcie całości niszczy też jej części).Pamiętaj: na diagramie klas UML romb (zarówno pusty dla agregacji, jak i zamalowany dla kompozycji) rysuje się zawsze przy klasie reprezentującej **CAŁOŚĆ (kontener)**, a nie przy klasie reprezentującej część!
  • **Diagramy strukturalne UML**: diagram klas (Class Diagram), obiektów, komponentów, wdrożenia (Deployment). **Diagramy behawioralne (czynnościowe) UML**: diagram przypadków użycia (Use Case — aktorzy, relacje `<<include>>` wykonywana zawsze oraz `<<extend>>` wykonywana warunkowo), diagram sekwencji, aktywności, maszyn stanowych. Na **diagramie klas**: linia ciągła z pustym trójkątnym grotem to **dziedziczenie (generalizacja)**; linia przerywana z pustym trójkątnym grotem to **realizacja interfejsu**; linia z **pustym rombem** to **agregacja** (część może istnieć bez całości); linia z **zamalowanym (pełnym) rombem** to **kompozycja** (silna relacja „część-całość” — usunięcie całości niszczy też jej części).
  • Na diagramie przypadków użycia relacja <<include>> oznacza zachowanie opcjonalne, a <<extend>> zachowanie obowiązkowe
  • Diagram sekwencji i diagram przypadków użycia należą do strukturalnych diagramów UML
  • Zamalowany romb w relacji kompozycji umieszcza się po stronie klasy będącej częścią podrzędną, a nie po stronie klasy-całości
19Jak działa Szyfr Cezara oraz Szyfr Przestawieniowy / Vigenère’a dla wielkich liter alfabetu łacińskiego (`'A'..'Z'`, kody ASCII `65..90`) i jak zapisać przesunięcie cykliczne o klucz `k`?Dla wielkich liter alfabetu angielskiego (`'A'` ma kod ASCII **65**, `'Z'` ma **90**, a małe `'a'` ma **97**): szyfrowanie Cezara o dowolny klucz całkowity `k >= 0` ze zawijaniem cyklicznym wokół alfabetu 26-literowego opisuje wzór **`nowy_znak = char((kod_znaku - 'A' + k) % 26 + 'A')`**, a odszyfrowywanie: `char((kod_znaku - 'A' - (k % 26) + 26) % 26 + 'A')`. W szyfrze Vigenère’a każda kolejna litera tekstu jawnego jest przesuwana o klucz wynikający z odpowiadającej jej litery słowa-klucza.Ponieważ alfabet łaciński ma 26 liter, klucz `k` działa modulo 26 (np. klucz `k = 29` daje dokładnie takie samo przesunięcie jak `29 % 26 = 3`). Zadanie z szyfrem Cezara wielokrotnie pojawiało się na egzaminie praktycznym INF.04 (wraz z testami jednostkowymi!).
  • Dla wielkich liter alfabetu angielskiego (`'A'` ma kod ASCII **65**, `'Z'` ma **90**, a małe `'a'` ma **97**): szyfrowanie Cezara o dowolny klucz całkowity `k >= 0` ze zawijaniem cyklicznym wokół alfabetu 26-literowego opisuje wzór **`nowy_znak = char((kod_znaku - 'A' + k) % 26 + 'A')`**, a odszyfrowywanie: `char((kod_znaku - 'A' - (k % 26) + 26) % 26 + 'A')`. W szyfrze Vigenère’a każda kolejna litera tekstu jawnego jest przesuwana o klucz wynikający z odpowiadającej jej litery słowa-klucza.
  • Wzór na szyfr Cezara to char((kod_znaku + k) % 26), a kod ASCII wielkiej litery 'A' wynosi 97
  • Dla klucza k = 29 szyfr Cezara daje inny kryptogram niż dla klucza k = 3
  • Szyfr Cezara jest przykładem współczesnego szyfru asymetrycznego z kluczem publicznym i prywatnym
20Jak działa algorytm szybkiego potęgowania (potęgowania binarnego — Exponentiation by Squaring) obliczający `a^n` (lub `a^n mod m`) w czasie `O(log n)`?Zamiast mnożyć podstawę `a` przez siebie `n` razy (czas O(n)), wykorzystujemy własność: dla parzystego wykładnika `a^n = (a^(n/2))^2`, a dla nieparzystego `a^n = a * a^(n-1)`. W wersji iteracyjnej: inicjujemy `wynik = 1`; dopóki `n > 0`: jeśli `n % 2 == 1` (najmłodszy bit wykładnika wynosi 1), mnożymy `wynik = wynik * a`; następnie w każdym kroku podnosimy podstawę do kwadratu `a = a * a` i dzielimy wykładnik całkowicie przez 2: `n = n // 2`. Pętla wykonuje dokładnie tyle kroków, ile bitów ma zapis binarny liczby `n`, czyli **O(log n)**.Dla `n = 1000` (ponieważ `2^9 < 1000 < 2^10 = 1024`) pętla szybkiego potęgowania wykona zaledwie **10 iteracji** zamiast 1000 mnożeń!
  • Szybkie potęgowanie oblicza a^n w czasie O(n) poprzez wielokrotne dodawanie liczby a w pętli
  • Zamiast mnożyć podstawę `a` przez siebie `n` razy (czas O(n)), wykorzystujemy własność: dla parzystego wykładnika `a^n = (a^(n/2))^2`, a dla nieparzystego `a^n = a * a^(n-1)`. W wersji iteracyjnej: inicjujemy `wynik = 1`; dopóki `n > 0`: jeśli `n % 2 == 1` (najmłodszy bit wykładnika wynosi 1), mnożymy `wynik = wynik * a`; następnie w każdym kroku podnosimy podstawę do kwadratu `a = a * a` i dzielimy wykładnik całkowicie przez 2: `n = n // 2`. Pętla wykonuje dokładnie tyle kroków, ile bitów ma zapis binarny liczby `n`, czyli **O(log n)**.
  • Algorytm szybkiego potęgowania działa wyłącznie wtedy, gdy wykładnik n jest potęgą dwójki
  • Dla n = 1000 algorytm szybkiego potęgowania wykonuje dokładnie 500 iteracji pętli
21Czym różni się klasa abstrakcyjna (`abstract class`) od interfejsu (`interface`) w językach obiektowych (C#, Java, C++)?**Klasa abstrakcyjna** nie może mieć własnych instancji (`new`), może zawierać zarówno metody abstrakcyjne (w C++ czysto wirtualne `virtual void oblicz() = 0;`), jak i zwykłe metody z pełną implementacją, pola stanu oraz konstruktory; klasa pochodna może dziedziczyć tylko po **jednej** klasie abstrakcyjnej (w C# i Javie — jednokrotne dziedziczenie klas). **Interfejs** definiuje kontrakt zachowania (zestaw sygnatur metod i właściwości), nie posiada pól instancyjnych ani konstruktorów, a jedna klasa może implementować **wiele interfejsów jednocześnie**.W języku C++ nie ma osobnego słowa kluczowego `interface` ani `abstract` przed klasą — klasa staje się abstrakcyjna, gdy posiada co najmniej jedną **metodę czysto wirtualną** zdeklarowaną z przypisaniem `= 0` (np. `virtual double pole() const = 0;`).
  • **Klasa abstrakcyjna** nie może mieć własnych instancji (`new`), może zawierać zarówno metody abstrakcyjne (w C++ czysto wirtualne `virtual void oblicz() = 0;`), jak i zwykłe metody z pełną implementacją, pola stanu oraz konstruktory; klasa pochodna może dziedziczyć tylko po **jednej** klasie abstrakcyjnej (w C# i Javie — jednokrotne dziedziczenie klas). **Interfejs** definiuje kontrakt zachowania (zestaw sygnatur metod i właściwości), nie posiada pól instancyjnych ani konstruktorów, a jedna klasa może implementować **wiele interfejsów jednocześnie**.
  • W językach C# i Java jedna klasa może dziedziczyć po wielu klasach abstrakcyjnych jednocześnie, ale implementować tylko jeden interfejs
  • W C++ klasę abstrakcyjną tworzy się za pomocą słowa kluczowego interface przed nazwą klasy
  • Klasa abstrakcyjna nie może posiadać żadnego konstruktora wywoływanego przez klasy pochodne
22Jak działa algorytm zachłanny (Greedy) na przykładzie problemu wydawania reszty dla polskiego systemu monetarnego `[500, 200, 100, 50, 20, 10, 5, 2, 1]` vs kiedy algorytm zachłanny NIE daje rozwiązania optymalnego (i wymagane jest programowanie dynamiczne)?Algorytm zachłanny w każdym kroku podejmuje decyzję lokalnie optymalną (np. przy wydawaniu reszty wybiera największy możliwy nominał nieprzekraczający pozostałej kwoty: `liczba = kwota // nominal; kwota = kwota % nominal`). Dla kanonicznego zestawu polskich nominałów (1, 2, 5, 10, 20, 50...) zachłanne wydawanie reszty zawsze daje minimalną liczbę monet/banknotów, ale dla zestawu niekanonicznego — np. nominałów `{1, 3, 4}` i kwoty `6` — algorytm zachłanny wybierze `4 + 1 + 1` (3 monety), podczas gdy optimum z **programowania dynamicznego** to `3 + 3` (**2 monety**!).Na maturze rozszerzonej z informatyki CKE rozróżnienie między strategią zachłanną (np. na kracie z maksymalną sumą, gdzie ruch w prawo/dół zależy od całej ścieżki) a programowaniem dynamicznym (`dp[i][j] = plansza[i][j] + max(dp[i-1][j], dp[i][j-1])`) jest jednym z klasycznych zadań teoretycznych i praktycznych.
  • Algorytm zachłanny zawsze gwarantuje znalezienie globalnie minimalnej liczby monet dla dowolnego zestawu nominałów
  • Algorytm zachłanny w każdym kroku podejmuje decyzję lokalnie optymalną (np. przy wydawaniu reszty wybiera największy możliwy nominał nieprzekraczający pozostałej kwoty: `liczba = kwota // nominal; kwota = kwota % nominal`). Dla kanonicznego zestawu polskich nominałów (1, 2, 5, 10, 20, 50...) zachłanne wydawanie reszty zawsze daje minimalną liczbę monet/banknotów, ale dla zestawu niekanonicznego — np. nominałów `{1, 3, 4}` i kwoty `6` — algorytm zachłanny wybierze `4 + 1 + 1` (3 monety), podczas gdy optimum z **programowania dynamicznego** to `3 + 3` (**2 monety**!).
  • Programowanie dynamiczne polega na losowym sprawdzaniu wszystkich możliwych permutacji monet bez zapamiętywania podproblemów
  • W problemie plecakowym dyskretnym (0-1 Knapsack) algorytm zachłanny zawsze daje wynik optymalny
23Jaka jest czasowa i pamięciowa złożoność obliczeniowa algorytmów sortowania: bąbelkowego (Bubble Sort), przez wstawianie (Insertion Sort), przez wybieranie (Selection Sort), przez scalanie (Merge Sort), szybkiego (Quick Sort) oraz przez zliczanie (Counting Sort)?Sortowania kwadratowe w przypadku średnim i pesymistycznym **O(n²)** (w miejscu, pamięć O(1)): **Bubble Sort** (optymistycznie z flagą O(n)), **Insertion Sort** (optymistycznie dla tablicy prawie posortowanej O(n), stabilny), **Selection Sort** (zawsze O(n²) porównań, niestabilny). Sortowania metodą „dziel i zwyciężaj”: **Merge Sort** — zawsze **O(n log n)** (stabilny, wymaga dodatkowej pamięci O(n)); **Quick Sort** — średnio i optymistycznie **O(n log n)**, pesymistycznie **O(n²)** (gdy pivotem jest skrajny element w posortowanej tablicy). **Counting Sort**: **O(n + k)**, gdzie k to rozpiętość przedziału wartości całkowitych.Sortowanie bąbelkowe, przez wstawianie lub przez wybieranie jest jednym z najczęściej spotykanych zadań dla aplikacji konsolowej w części praktycznej egzaminu INF.04!
  • Sortowania kwadratowe w przypadku średnim i pesymistycznym **O(n²)** (w miejscu, pamięć O(1)): **Bubble Sort** (optymistycznie z flagą O(n)), **Insertion Sort** (optymistycznie dla tablicy prawie posortowanej O(n), stabilny), **Selection Sort** (zawsze O(n²) porównań, niestabilny). Sortowania metodą „dziel i zwyciężaj”: **Merge Sort** — zawsze **O(n log n)** (stabilny, wymaga dodatkowej pamięci O(n)); **Quick Sort** — średnio i optymistycznie **O(n log n)**, pesymistycznie **O(n²)** (gdy pivotem jest skrajny element w posortowanej tablicy). **Counting Sort**: **O(n + k)**, gdzie k to rozpiętość przedziału wartości całkowitych.
  • Sortowanie bąbelkowe i przez wybieranie mają złożoność O(n log n), a sortowanie przez scalanie ma złożoność O(n²)
  • Sortowanie przez wybieranie (Selection Sort) dla tablicy posortowanej wykonuje tylko O(n) porównań
  • Algorytm Quick Sort jest domyślnie stabilnym algorytmem sortowania o złożoności pamięciowej O(n²)
24Jak obliczyć pierwiastek kwadratowy `√S` z zadaną dokładnością `ε` za pomocą iteracyjnej metody Newtona-Raphsona (Herona) oraz znaleźć miejsce zerowe funkcji ciągłej metodą bisekcji (połowienia przedziału)?**Metoda Newtona-Raphsona (Herona) dla `√S`**: przyjmujemy przybliżenie początkowe `x = S` (lub `S/2`) i powtarzamy w pętli `while abs(x - S / x) > epsilon:` podstawienie średniej arytmetycznej boków prostokąta o polu S: **`x = 0.5 * (x + S / x)`** (zbieżność kwadratowa). **Metoda bisekcji** dla funkcji ciągłej `f(x)` na przedziale `[a, b]`, na którego końcach funkcja ma przeciwne znaki (`f(a) * f(b) < 0`): w pętli `while (b - a) > epsilon:` wyznaczamy środek `s = (a + b) / 2`; jeśli `f(a) * f(s) <= 0`, to `b = s`, w przeciwnym razie `a = s`.Zarówno metoda Herona obliczania pierwiastka kwadratowego, jak i metoda bisekcji oraz obliczanie pola pod wykresem funkcji metodą prostokątów/trapezów należą do klasycznych metod numerycznych sprawdzanych na maturze rozszerzonej z informatyki i na egzaminie INF.04.
  • **Metoda Newtona-Raphsona (Herona) dla `√S`**: przyjmujemy przybliżenie początkowe `x = S` (lub `S/2`) i powtarzamy w pętli `while abs(x - S / x) > epsilon:` podstawienie średniej arytmetycznej boków prostokąta o polu S: **`x = 0.5 * (x + S / x)`** (zbieżność kwadratowa). **Metoda bisekcji** dla funkcji ciągłej `f(x)` na przedziale `[a, b]`, na którego końcach funkcja ma przeciwne znaki (`f(a) * f(b) < 0`): w pętli `while (b - a) > epsilon:` wyznaczamy środek `s = (a + b) / 2`; jeśli `f(a) * f(s) <= 0`, to `b = s`, w przeciwnym razie `a = s`.
  • Metoda bisekcji działa dla dowolnego przedziału [a, b], w którym f(a) * f(b) > 0, a we wzorze Herona x = (x - S/x) * 2
  • Metoda bisekcji ma zbieżność kwadratową i jest zawsze szybsza od metody stycznych Newtona
  • Wzór Herona wymaga obliczania pochodnej funkcji trygonometrycznej w każdej iteracji
25Jak w arkuszu kalkulacyjnym (Microsoft Excel / LibreOffice Calc) na maturze rozszerzonej z informatyki CKE działają funkcje `LICZ.JEŻELI`, `LICZ.WARUNKI`, `SUMA.JEŻELI`, `SUMA.WARUNKÓW`, `WYSZUKAJ.PIONOWO` (`VLOOKUP`) / `X.WYSZUKAJ` oraz adresowanie względne, bezwzględne (`$A$1`) i mieszane (`$A1`, `A$1`)?Adresowanie: `A1` (względne — zmienia wiersz i kolumnę przy kopiowaniu), **`$A$1`** (bezwzględne — blokuje zarówno kolumnę, jak i wiersz), **`$A1`** (mieszane — blokuje kolumnę A), **`A$1`** (mieszane — blokuje wiersz 1). `LICZ.WARUNKI(zakres1; kryterium1; zakres2; kryterium2)` oraz `SUMA.WARUNKÓW(zakres_sumowania; zakres_kryt1; kryt1; ...)` obsługują wiele warunków jednocześnie. W **`WYSZUKAJ.PIONOWO(szukana; tabela; nr_kolumny; 0)`** czwarty argument równy **`0` (`FAŁSZ`)** jest kluczowy na maturze, bo wymusza **dokładne dopasowanie** klucza w nieposortowanej tabeli!Uwaga na różnicę w kolejności argumentów w Excelu/Calcu: w pojedynczej `SUMA.JEŻELI(zakres_kryterium; kryterium; zakres_sumowania)` zakres sumowania jest **na końcu**, natomiast w wielowarunkowej `SUMA.WARUNKÓW(zakres_sumowania; zakres_kryt1; kryt1; ...)` zakres sumowania jest **pierwszym argumentem**!
  • W funkcji WYSZUKAJ.PIONOWO czwarty argument równy 1 (PRAWDA) wymusza dokładne dopasowanie w nieposortowanej tabeli
  • Adresowanie: `A1` (względne — zmienia wiersz i kolumnę przy kopiowaniu), **`$A$1`** (bezwzględne — blokuje zarówno kolumnę, jak i wiersz), **`$A1`** (mieszane — blokuje kolumnę A), **`A$1`** (mieszane — blokuje wiersz 1). `LICZ.WARUNKI(zakres1; kryterium1; zakres2; kryterium2)` oraz `SUMA.WARUNKÓW(zakres_sumowania; zakres_kryt1; kryt1; ...)` obsługują wiele warunków jednocześnie. W **`WYSZUKAJ.PIONOWO(szukana; tabela; nr_kolumny; 0)`** czwarty argument równy **`0` (`FAŁSZ`)** jest kluczowy na maturze, bo wymusza **dokładne dopasowanie** klucza w nieposortowanej tabeli!
  • W funkcji SUMA.WARUNKÓW zakres sumowania podaje się jako ostatni argument na samym końcu formuły
  • Zapis $A1 blokuje numer wiersza 1 podczas kopiowania formuły w dół, ale pozwala na zmianę kolumny A
26Jakie są cztery fundamentalne filary programowania obiektowego (OOP): Hermetyzacja (Enkapsulacja), Dziedziczenie, Polimorfizm oraz Abstrakcja?(1) **Hermetyzacja (Enkapsulacja)**: ukrywanie wewnętrznego stanu obiektu (pola `private` / `protected`) i udostępnianie kontrolowanego dostępu przez metody publiczne (gettery, settery, właściwości). (2) **Dziedziczenie (Inheritance, relacja „jest / is-a”)**: przejmowanie pól i metod klasy bazowej (nadrzędnej) przez klasę pochodną (podrzędną). (3) **Polimorfizm (Wielopostaciowość)**: zdolność wywołania właściwej implementacji metody w zależności od rzeczywistego typu obiektu w czasie wykonania (przesłanianie metod wirtualnych `virtual` / `override`) oraz przeciążanie metod (overloading). (4) **Abstrakcja**: wyodrębnienie istotnych cech obiektu za pomocą klas abstrakcyjnych i interfejsów.W części praktycznej INF.04 arkusz bardzo często wymaga zdefiniowania pól klasy jako prywatnych (`private`) lub chronionych (`protected`), napisania konstruktorów (bezparametrowego, parametrowego, kopiującego) oraz metod dostępowych (getterów/setterów).
  • Hermetyzacja polega na oznaczaniu wszystkich pól klasy jako public, aby przyspieszyć dostęp z zewnątrz
  • (1) **Hermetyzacja (Enkapsulacja)**: ukrywanie wewnętrznego stanu obiektu (pola `private` / `protected`) i udostępnianie kontrolowanego dostępu przez metody publiczne (gettery, settery, właściwości). (2) **Dziedziczenie (Inheritance, relacja „jest / is-a”)**: przejmowanie pól i metod klasy bazowej (nadrzędnej) przez klasę pochodną (podrzędną). (3) **Polimorfizm (Wielopostaciowość)**: zdolność wywołania właściwej implementacji metody w zależności od rzeczywistego typu obiektu w czasie wykonania (przesłanianie metod wirtualnych `virtual` / `override`) oraz przeciążanie metod (overloading). (4) **Abstrakcja**: wyodrębnienie istotnych cech obiektu za pomocą klas abstrakcyjnych i interfejsów.
  • Polimorfizm oznacza możliwość dziedziczenia przez jedną klasę wyłącznie po typach prostych int i float
  • Z klasy abstrakcyjnej można bezpośrednio utworzyć instancję obiektu operatorem new
27Jak w aplikacjach internetowych (React / Angular / JavaScript) działa stan komponentu (`useState`), właściwości (`props`) oraz komunikacja z usługami REST API (`fetch`, `JSON`, metody HTTP)?W bibliotece **React**: **`props`** to niemodyfikowalne (read-only) dane przekazywane z komponentu nadrzędnego (rodzica) do potomnego (dziecka); **`state`** (tworzony hookiem `const [licznik, setLicznik] = useState(0);`) to wewnętrzny, zmienny stan komponentu, którego aktualizacja przez funkcję `setLicznik(...)` powoduje ponowne wyrenderowanie widoku. W architekturze **REST API** komunikacja odbywa się najczęściej w formacie **JSON** (`JSON.stringify()` / `JSON.parse()`) przy użyciu metod HTTP: **`GET`** (pobierz zasób), **`POST`** (utwórz nowy zasób), **`PUT` / `PATCH`** (zaktualizuj zasób), **`DELETE`** (usuń zasób).W zadaniach praktycznych INF.04 z Reactem lub Angularem: w **React** listę elementów renderuje się metodą `.map()` z unikalnym atrybutem `key`, a formularze obsługuje przez `value` i `onChange={(e) => setPole(e.target.value)}`; w **Angularze** iterację w szablonie wykonuje dyrektywa `*ngFor="let el of lista"` (lub `@for`), warunek `*ngIf` (`@if`), a dwukierunkowe wiązanie z kontrolką formularza — **`[(ngModel)]="zmienna"`** (po zaimportowaniu `FormsModule`).
  • W bibliotece **React**: **`props`** to niemodyfikowalne (read-only) dane przekazywane z komponentu nadrzędnego (rodzica) do potomnego (dziecka); **`state`** (tworzony hookiem `const [licznik, setLicznik] = useState(0);`) to wewnętrzny, zmienny stan komponentu, którego aktualizacja przez funkcję `setLicznik(...)` powoduje ponowne wyrenderowanie widoku. W architekturze **REST API** komunikacja odbywa się najczęściej w formacie **JSON** (`JSON.stringify()` / `JSON.parse()`) przy użyciu metod HTTP: **`GET`** (pobierz zasób), **`POST`** (utwórz nowy zasób), **`PUT` / `PATCH`** (zaktualizuj zasób), **`DELETE`** (usuń zasób).
  • W bibliotece React komponent potomny może bezpośrednio modyfikować obiekt props otrzymany od rodzica, a bezpośrednie przypisanie licznik = 5 odświeża ekran
  • W Angularze do dwukierunkowego wiązania danych w formularzach używa się dyrektywy *ngFor zamiast [(ngModel)]
  • Format JSON pozwala na bezpośrednie przesyłanie skomplikowanych metod klasy zdefiniowanych w języku C++
28Czym różnią się testy jednostkowe (Unit Tests), testy integracyjne, testy systemowe (End-to-End) oraz testy akceptacyjne i jak zbudowany jest test jednostkowy według wzorca AAA (Arrange – Act – Assert)?**Testy jednostkowe (Unit Tests)**: weryfikują w izolacji najmniejsze fragmenty kodu (pojedyncze funkcje lub metody klasy, np. we frameworkach **xUnit, NUnit, MSTest, JUnit, pytest, unittest**). **Testy integracyjne**: sprawdzają współpracę połączonych modułów (np. serwisu z bazą danych lub API). **Testy systemowe / E2E**: weryfikują działanie całego zintegrowanego systemu. **Testy akceptacyjne (UAT)**: potwierdzają zgodność z wymaganiami klienta. Struktura **AAA** testu jednostkowego: **Arrange** (przygotowanie danych wejściowych i obiektu), **Act** (wywołanie testowanej metody), **Assert** (sprawdzenie asercją czy wynik rzeczywisty zgadza się z oczekiwanym, np. `Assert.AreEqual(oczekiwany, rzeczywisty)`).W metodyce **TDD (Test-Driven Development)** obowiązuje cykl **Red – Green – Refactor**: (1) napisz test, który nie przechodzi (Red), (2) napisz minimalny kod spełniający test (Green), (3) zrefaktoryzuj kod utrzymując zielone testy (Refactor).
  • **Testy jednostkowe (Unit Tests)**: weryfikują w izolacji najmniejsze fragmenty kodu (pojedyncze funkcje lub metody klasy, np. we frameworkach **xUnit, NUnit, MSTest, JUnit, pytest, unittest**). **Testy integracyjne**: sprawdzają współpracę połączonych modułów (np. serwisu z bazą danych lub API). **Testy systemowe / E2E**: weryfikują działanie całego zintegrowanego systemu. **Testy akceptacyjne (UAT)**: potwierdzają zgodność z wymaganiami klienta. Struktura **AAA** testu jednostkowego: **Arrange** (przygotowanie danych wejściowych i obiektu), **Act** (wywołanie testowanej metody), **Assert** (sprawdzenie asercją czy wynik rzeczywisty zgadza się z oczekiwanym, np. `Assert.AreEqual(oczekiwany, rzeczywisty)`).
  • Testy jednostkowe polegają na ręcznym klikaniu przez klienta końcowego w interfejs graficzny gotowej aplikacji
  • W metodyce TDD (Test-Driven Development) testy jednostkowe pisze się dopiero po wdrożeniu aplikacji na serwer produkcyjny
  • Metoda Assert.AreEqual() służy do kompilowania aplikacji okienkowej WPF do pliku wykonywalnego .exe
29Czym różni się testowanie metodą białej skrzynki (White-Box Testing) od testowania metodą czarnej skrzynki (Black-Box Testing) oraz testowanie statyczne od dynamicznego?**Czarna skrzynka (Black-Box)**: tester nie zna (lub nie bada) wewnętrznej struktury kodu źródłowego, lecz weryfikuje odpowiedzi programu dla zadanych danych wejściowych na podstawie specyfikacji wymagań (techniki: klasy równoważności, analiza wartości brzegowych). **Biała skrzynka (White-Box)**: testy projektowane są na podstawie znajomości wewnętrznej struktury kodu źródłowego (pokrycie instrukcji, pokrycie rozgałęzień `if/else`, ścieżek wykonania). **Testowanie statyczne** odbywa się bez uruchamiania programu (przegląd kodu Code Review, analiza statyczna linterami), a **dynamiczne** wymaga uruchomienia kodu.Przykład analizy wartości brzegowych (Boundary Value Analysis) dla pola przyjmującego wiek całkowity z przedziału `[18, 65]`: testujemy wartości tuż poza granicą i na granicy, czyli **`17, 18, 65, 66`**!
  • **Czarna skrzynka (Black-Box)**: tester nie zna (lub nie bada) wewnętrznej struktury kodu źródłowego, lecz weryfikuje odpowiedzi programu dla zadanych danych wejściowych na podstawie specyfikacji wymagań (techniki: klasy równoważności, analiza wartości brzegowych). **Biała skrzynka (White-Box)**: testy projektowane są na podstawie znajomości wewnętrznej struktury kodu źródłowego (pokrycie instrukcji, pokrycie rozgałęzień `if/else`, ścieżek wykonania). **Testowanie statyczne** odbywa się bez uruchamiania programu (przegląd kodu Code Review, analiza statyczna linterami), a **dynamiczne** wymaga uruchomienia kodu.
  • Testowanie metodą czarnej skrzynki wymaga pełnej analizy wszystkich gałęzi instrukcji warunkowych w kodzie źródłowym
  • Przegląd kodu (Code Review) jest przykładem testowania dynamicznego metodą czarnej skrzynki
  • Analiza wartości brzegowych polega na testowaniu wyłącznie wartości losowych ze środka przedziału
30Jak wyznaczyć długość i wartość najdłuższego spójnego podciągu rosnącego (lub podciągu o maksymalnej sumie — algorytm Kadane’a) w tablicy jednowymiarowej w czasie liniowym `O(n)`?(1) **Najdłuższy spójny podciąg rosnący** (bardzo częste zadanie na maturze z informatyki w Excelu i w C++/Pythonie): przechodzimy tablicę raz (`i` od 1 do `n-1`): jeśli `tab[i] > tab[i-1]`, zwiększamy `aktualna_dlugosc += 1` (i aktualizujemy `max_dlugosc`), w przeciwnym razie resetujemy `aktualna_dlugosc = 1`. (2) **Maksymalna suma spójnego podciągu (algorytm Kadane’a, O(n))**: w każdym kroku `aktualna_suma = max(tab[i], aktualna_suma + tab[i])` oraz `max_suma = max(max_suma, aktualna_suma)`.Uwaga na terminologię CKE na maturze z informatyki: **podciąg spójny (segment / podtablica)** składa się z elementów stojących bezpośrednio obok siebie na sąsiednich indeksach, natomiast **podciąg niespójny** powstaje przez wykreślenie dowolnych elementów bez zmiany kolejności pozostałych!
  • Znalezienie najdłuższego spójnego podciągu rosnącego wymaga zawsze trzech zagnieżdżonych pętli o złożoności O(n³)
  • (1) **Najdłuższy spójny podciąg rosnący** (bardzo częste zadanie na maturze z informatyki w Excelu i w C++/Pythonie): przechodzimy tablicę raz (`i` od 1 do `n-1`): jeśli `tab[i] > tab[i-1]`, zwiększamy `aktualna_dlugosc += 1` (i aktualizujemy `max_dlugosc`), w przeciwnym razie resetujemy `aktualna_dlugosc = 1`. (2) **Maksymalna suma spójnego podciągu (algorytm Kadane’a, O(n))**: w każdym kroku `aktualna_suma = max(tab[i], aktualna_suma + tab[i])` oraz `max_suma = max(max_suma, aktualna_suma)`.
  • Podciąg spójny pozwala na dowolne pomijanie elementów znajdujących się wewnątrz wybranego fragmentu tablicy
  • Algorytm Kadane'a działa poprawnie tylko wtedy, gdy wszystkie liczby w tablicy są dodatnie
31Co oznaczają pięć zasad obiektowego projektowania oprogramowania określanych akronimem SOLID?**S — Single Responsibility Principle (Zasada pojedynczej odpowiedzialności)**: klasa powinna mieć tylko jedno zadanie (jeden powód do zmiany). **O — Open/Closed Principle (Zasada otwarte-zamknięte)**: encje programistyczne powinny być otwarte na rozszerzanie, ale zamknięte na modyfikację istniejącego kodu. **L — Liskov Substitution Principle (Zasada podstawienia Liskov)**: obiekty klasy pochodnej muszą móc bezpiecznie zastępować obiekty klasy bazowej bez psucia poprawności programu. **I — Interface Segregation Principle (Zasada segregacji interfejsów)**: lepiej tworzyć wiele małych, wyspecjalizowanych interfejsów niż jeden ogólny. **D — Dependency Inversion Principle (Zasada odwrócenia zależności)**: moduły wysokiego poziomu nie powinny zależeć od modułów niskiego poziomu — oba powinny zależeć od abstrakcji (interfejsów).Zasady **SOLID** wraz z zasadami **DRY** (*Don't Repeat Yourself* — nie powtarzaj kodu), **KISS** (*Keep It Simple, Stupid*) oraz **YAGNI** (*You Aren't Gonna Need It*) stanowią fundament inżynierii oprogramowania na egzaminie INF.04.
  • **S — Single Responsibility Principle (Zasada pojedynczej odpowiedzialności)**: klasa powinna mieć tylko jedno zadanie (jeden powód do zmiany). **O — Open/Closed Principle (Zasada otwarte-zamknięte)**: encje programistyczne powinny być otwarte na rozszerzanie, ale zamknięte na modyfikację istniejącego kodu. **L — Liskov Substitution Principle (Zasada podstawienia Liskov)**: obiekty klasy pochodnej muszą móc bezpiecznie zastępować obiekty klasy bazowej bez psucia poprawności programu. **I — Interface Segregation Principle (Zasada segregacji interfejsów)**: lepiej tworzyć wiele małych, wyspecjalizowanych interfejsów niż jeden ogólny. **D — Dependency Inversion Principle (Zasada odwrócenia zależności)**: moduły wysokiego poziomu nie powinny zależeć od modułów niskiego poziomu — oba powinny zależeć od abstrakcji (interfejsów).
  • Litera S w SOLID oznacza stosowanie wzorca Singleton w każdej klasie programu
  • Zasada Open/Closed nakazuje, aby wszystkie pola klasy były otwarte (publiczne), a metody zamknięte (prywatne)
  • Zasada segregacji interfejsów (I) wymaga, aby cały projekt posiadał dokładnie jeden wspólny interfejs dla wszystkich klas
32Jak działa Sito Eratostenesa do wyznaczania liczb pierwszych z przedziału `[2..n]` i dlaczego wykreślanie wielokrotności wystarczy prowadzić dla dzielników `i` do `√n` (`i * i <= n`), zaczynając od `i * i`?Tworzymy tablicę logiczną `pierwsza[0..n]` zainicjowaną wartością `true` (poza indeksami 0 i 1 ustawionymi na `false`). Dla kolejnych liczb `i` od `2` do `√n` (`i * i <= n`): jeżeli `pierwsza[i]` jest `true`, to zamieniamy na `false` wszystkie jej wielokrotności zaczynając od **`j = i * i`** z krokiem `i` (`j += i`). Zaczynamy od `i * i`, ponieważ wszystkie mniejsze wielokrotności postaci `k * i` (gdzie `k < i`) zostały już wykreślone wcześniej jako wielokrotności mniejszych liczb pierwszych.Przy sprawdzaniu pierwszości pojedynczej liczby `n` (test pierwszości) również wystarczy sprawdzać dzielniki od `2` do `⌊√n⌋` (`d * d <= n`), bo jeśli liczba złożona `n = a * b` ma dzielnik właściwy, to co najmniej jeden z czynników nie przekracza `√n`.
  • W Sicie Eratostenesa zewnętrzna pętla musi zawsze dochodzić do n, a wewnętrzna zaczyna wykreślanie od 2 * n
  • Aby sprawdzić pierwszość pojedynczej dużej liczby n bez tablicy, należy sprawdzać dzielniki aż do n - 1
  • Liczba 1 jest traktowana w Sicie Eratostenesa jako najmniejsza liczba pierwsza
  • Tworzymy tablicę logiczną `pierwsza[0..n]` zainicjowaną wartością `true` (poza indeksami 0 i 1 ustawionymi na `false`). Dla kolejnych liczb `i` od `2` do `√n` (`i * i <= n`): jeżeli `pierwsza[i]` jest `true`, to zamieniamy na `false` wszystkie jej wielokrotności zaczynając od **`j = i * i`** z krokiem `i` (`j += i`). Zaczynamy od `i * i`, ponieważ wszystkie mniejsze wielokrotności postaci `k * i` (gdzie `k < i`) zostały już wykreślone wcześniej jako wielokrotności mniejszych liczb pierwszych.