Pytania pomocnicze - INF.04

LIFO oznacza Last In, First Out, czyli ostatni dodany element jest usuwany lub przetwarzany jako pierwszy. Jest to podstawowa zasada działania stosu.

Lista pozwala zwykle na dostęp do elementów według indeksu i operacje w różnych miejscach kolekcji. Stos ogranicza operacje głównie do szczytu, czyli ostatnio dodanego elementu.

Stos warto użyć, gdy dane muszą być obsługiwane w odwrotnej kolejności niż zostały dodane. Przykładem jest cofanie operacji lub odwracanie kolejności elementów.

Najważniejsze operacje to push, czyli dodanie elementu, pop, czyli zdjęcie elementu, oraz peek, czyli podejrzenie elementu ze szczytu bez jego usuwania.

Stos nie służy do wyszukiwania dowolnych elementów, ponieważ dostępny jest przede wszystkim element znajdujący się na szczycie. Do szybkiego wyszukiwania lepsze są inne struktury, np. mapa lub tablica z odpowiednim indeksem.

Stos działa według zasady LIFO, czyli ostatni element wychodzi pierwszy. Kolejka działa według zasady FIFO, czyli pierwszy dodany element wychodzi pierwszy.

Ponieważ używa prostych, opisowych instrukcji zamiast ścisłej składni języka programowania. Dzięki temu skupia się na logice algorytmu, a nie na technicznych szczegółach kodu.

Kod źródłowy musi być zapisany zgodnie ze składnią konkretnego języka i może zostać wykonany po kompilacji lub interpretacji. Pseudokod jest tylko opisem algorytmu przeznaczonym dla człowieka.

Najczęściej używa się go przed rozpoczęciem właściwego programowania. Pomaga zaplanować rozwiązanie i uporządkować logikę działania programu.

Nie. Pseudokod nie jest formalnym językiem programowania, więc komputer nie wykona go bez przepisania na konkretny język, np. Python, Java lub C++.

Pozwala przeanalizować kolejne kroki algorytmu bez rozpraszania się składnią języka. Dzięki temu łatwiej zauważyć błędne warunki, brakujące kroki lub niepoprawną kolejność działań.

Pseudokod zapisuje algorytm tekstowo, a schemat blokowy przedstawia go graficznie za pomocą bloków i strzałek. Oba sposoby służą do opisu logiki algorytmu.

Algorytm iteracyjny używa pętli do powtarzania instrukcji. Algorytm rekurencyjny rozwiązuje problem przez wywoływanie samego siebie.

BubbleSort wykonuje kolejne porównania i zamiany elementów w pętlach. Nie wymaga wywoływania samego siebie.

Ponieważ w treści podano, że Fibonacci jest liczony rekurencyjnie. Oznacza to użycie funkcji wywołującej samą siebie, a nie pętli.

Tak. QuickSort jest klasycznym przykładem algorytmu dziel i zwyciężaj, często implementowanym rekurencyjnie przez sortowanie podtablic.

Nie. DFS można zapisać rekurencyjnie albo iteracyjnie z użyciem stosu. W pytaniach egzaminacyjnych DFS często kojarzy się jednak z rekurencją.

Najczęściej po obecności pętli, takich jak `for`, `while` lub powtarzanych instrukcji wykonywanych do spełnienia warunku.

Przykładami są BubbleSort, liniowe wyszukiwanie elementu, sumowanie elementów tablicy oraz obliczanie silni za pomocą pętli.

Polega na użyciu tego samego tajnego klucza do zaszyfrowania i odszyfrowania danych. Klucz muszą znać obie strony komunikacji.

Ponieważ każdy, kto pozna klucz, może odszyfrować zabezpieczone dane. Ujawnienie klucza oznacza utratę poufności informacji.

W szyfrowaniu symetrycznym używa się jednego wspólnego klucza. W asymetrycznym stosuje się parę kluczy: publiczny i prywatny.

Przykładami są AES, DES, 3DES i Blowfish. Obecnie najczęściej zalecany jest AES.

Jest szybkie i dobrze nadaje się do szyfrowania dużych ilości danych. Dlatego często stosuje się je w praktycznych systemach bezpieczeństwa.

Największym problemem jest bezpieczne przekazanie tajnego klucza drugiej stronie. Jeśli klucz zostanie przechwycony, dane mogą zostać odczytane.

To algorytm, w którym funkcja lub procedura wywołuje samą siebie. Każde wywołanie powinno przybliżać rozwiązanie do warunku zakończenia.

Przypadek bazowy zatrzymuje dalsze wywołania rekurencyjne. Bez niego program może doprowadzić do nieskończonej rekurencji i przepełnienia stosu.

Rekurencja polega na wywoływaniu funkcji przez samą siebie, a iteracja na wielokrotnym wykonywaniu instrukcji w pętli. Obie techniki często mogą rozwiązywać te same problemy.

Oznacza to, że wewnątrz definicji funkcji znajduje się instrukcja uruchamiająca tę samą funkcję, zwykle z innymi argumentami.

Rekurencja jest często używana przy obliczaniu silni, ciągu Fibonacciego, przeszukiwaniu drzew, sortowaniu szybkim i algorytmach typu dziel i zwyciężaj.

Największym problemem jest brak skutecznego warunku zakończenia. Może to spowodować zbyt wiele wywołań funkcji i błąd przepełnienia stosu.

Złożoność liniowa oznacza, że liczba operacji rośnie proporcjonalnie do rozmiaru danych wejściowych. Jej oznaczenie to O(n).

O(1) oznacza stałą liczbę operacji niezależną od liczby danych. O(n) oznacza, że liczba operacji rośnie wraz z liczbą elementów.

Pojedyncza pętla przechodząca przez wszystkie elementy tablicy lub listy ma zwykle złożoność O(n).

O(n²) oznacza złożoność kwadratową, w której liczba operacji rośnie znacznie szybciej niż liczba danych. Często występuje przy dwóch zagnieżdżonych pętlach.

Litera n oznacza rozmiar danych wejściowych, np. liczbę elementów w tablicy, liście lub zbiorze.

Nie. Big O opisuje tempo wzrostu liczby operacji, a nie dokładny czas w sekundach, który zależy też od sprzętu i implementacji.

Oznacza złożoność kwadratową. Liczba operacji rośnie proporcjonalnie do kwadratu liczby danych wejściowych.

Ponieważ wykonuje wiele przejść po tablicy i porównuje sąsiednie elementy. Dla n elementów liczba porównań jest rzędu n razy n.

Wyszukiwanie binarne ma złożoność O(log n), ponieważ w każdym kroku odrzuca połowę pozostałych danych.

Merge Sort ma złożoność O(n log n). Jest szybszy od Bubble Sort dla dużych zbiorów danych.

O(n) rośnie liniowo wraz z liczbą danych, a O(n²) rośnie kwadratowo. Algorytm O(n²) staje się dużo wolniejszy przy dużych danych.

Nie zawsze. Złożoność algorytmu Dijkstry zależy od implementacji i użytych struktur danych, np. macierzy sąsiedztwa albo kolejki priorytetowej.

Oznacza, że czas działania algorytmu rośnie trochę szybciej niż liniowo, ale znacznie wolniej niż kwadratowo. Jest to typowa złożoność efektywnych algorytmów sortowania porównawczego.

Średnio tablica jest dzielona na w miarę równe części, a każdy poziom podziału wymaga przejrzenia elementów. Daje to około log n poziomów i n operacji na poziom.

Gdy pivot jest wybierany bardzo niekorzystnie, np. zawsze jako najmniejszy lub największy element. Wtedy podział tablicy jest skrajnie nierówny.

Pivot to element wybrany jako punkt odniesienia podczas podziału tablicy. Elementy mniejsze i większe od niego są rozmieszczane po przeciwnych stronach.

Te algorytmy mają średnią złożoność O(n²). Dlatego są zwykle wolniejsze od QuickSort dla dużych zbiorów danych.

Polega na podzieleniu problemu na mniejsze podproblemy, rozwiązaniu ich osobno i połączeniu wyników. QuickSort dzieli tablicę względem pivota i sortuje części rekurencyjnie.

Ponieważ w pytaniach egzaminacyjnych QuickSort jest często zestawiany z prostymi algorytmami O(n²). Jego średnia złożoność O(n log n) jest najważniejszą cechą do zapamiętania.

QuickSort ma średnią złożoność O(n log n), a sortowanie bąbelkowe O(n²). Przy dużej liczbie elementów różnica w czasie działania staje się bardzo duża.

Problem sortowania jest dzielony na mniejsze podproblemy przez wybór pivota i podział tablicy. Następnie każda część jest sortowana osobno.

Pivot to element odniesienia, względem którego dzieli się dane na mniejsze i większe. Dobry wybór pivota wpływa na szybkość działania algorytmu.

W najgorszym przypadku QuickSort ma złożoność O(n²), np. gdy pivot jest wybierany bardzo niekorzystnie i podział danych jest skrajnie nierówny.

Sortowanie przez zliczanie jest bardzo szybkie tylko dla liczb całkowitych z niewielkiego, znanego zakresu. Nie jest uniwersalne dla dowolnych danych.

Sortowanie przez wstawianie ma zwykle złożoność O(n²), więc dla dużych danych wykonuje bardzo dużo porównań i przesunięć. Sprawdza się raczej przy małych lub prawie posortowanych zbiorach.

Oznacza, że liczba operacji rośnie szybciej niż liniowo, ale znacznie wolniej niż kwadratowo. Jest to dobra złożoność dla algorytmów sortowania porównawczego.

Polega na podzieleniu problemu na mniejsze podproblemy, rozwiązaniu ich osobno i połączeniu wyników. QuickSort dzieli tablicę względem pivota i sortuje części rekurencyjnie.

Ponieważ wywołuje sam siebie dla mniejszych fragmentów tablicy. Rekurencja kończy się, gdy fragment ma zero lub jeden element.

Pivot to element odniesienia, względem którego dzielona jest tablica. Elementy mniejsze trafiają na jedną stronę, a większe na drugą.

Średnia złożoność QuickSort wynosi O(n log n). Dlatego algorytm jest zwykle bardzo szybki w praktyce.

QuickSort może osiągnąć złożoność O(n²), gdy pivot jest wybierany niekorzystnie. Przykładem jest sytuacja, gdy za każdym razem dzieli tablicę bardzo nierówno.

Nie. Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je miejscami, ale nie dzieli problemu na mniejsze części.

Sortowanie przez wybór wielokrotnie wyszukuje najmniejszy element i przenosi go na właściwe miejsce. QuickSort dzieli tablicę względem pivota i sortuje powstałe części.