KWALIFIKACJA INF2 + INF3 - CZERWIEC 2006

PYTANIE NR 28.
Technika rozwiązywania problemów dziel i zwyciężaj jest stosowana przy
A.
B.
C.
D.
Wyjaśnienie poprawnej odpowiedzi:
"Dziel i zwyciężaj" polega na rozbijaniu problemu na mniejsze części i rozwiązywaniu ich niezależnie.
Wyszukiwanie binarne (połowienie przedziału) w uporządkowanym zbiorze wielokrotnie dzieli zakres na połowy. Scalanie dwóch ciągów, wyszukiwanie w nieuporządkowanym zbiorze i sortowanie bąbelkowe nie realizują tego schematu.

Pełne wyjaśnienie:

Technika dziel i zwyciężaj (divide and conquer) polega na tym, że problem jest dzielony na mniejsze podproblemy tego samego typu, następnie podproblemy są rozwiązywane (często rekurencyjnie), a na końcu wyniki są ewentualnie łączone w rozwiązanie całości.

Odpowiedź "znajdowaniu elementu w zbiorze uporządkowanym metodą połowienia przedziału." pasuje do tej definicji, ponieważ wyszukiwanie binarne na każdym kroku dzieli rozważany przedział na dwie połowy i wybiera tę, w której element może się znajdować. To jest klasyczny przykład dzielenia problemu na mniejszy (o połowę) podproblem, aż do osiągnięcia przypadku bazowego.

Odpowiedź "scalaniu dwóch ciągów uporządkowanych." sama w sobie opisuje operację łączenia (merge) dwóch posortowanych sekwencji. Jest ona elementem sortowania przez scalanie, ale pojedyncze "scalanie" nie jest etapem dzielenia problemu na podproblemy; to raczej krok liniowego łączenia wyników. Bez kontekstu całego algorytmu nie jest to typowy przykład "dziel i zwyciężaj".

Odpowiedź "znajdowaniu elementu w zbiorze nieuporządkowanym." zwykle oznacza wyszukiwanie liniowe, gdzie sprawdza się kolejne elementy. Nie występuje tu podział problemu na mniejsze niezależne części o tej samej strukturze (brak systematycznego "dzielenia przedziału" jak w binarnym).

Odpowiedź "sortowaniu zbioru metodą bąbelkową." jest niepoprawna, bo sortowanie bąbelkowe działa iteracyjnie przez lokalne zamiany sąsiednich elementów i wielokrotne przejścia po całej tablicy, bez mechanizmu dzielenia na podproblemy i rekurencyjnego rozwiązywania.

Wskazówka egzaminacyjna: w pytaniach o "dziel i zwyciężaj" szukaj algorytmów, w których wprost pojawia się podział na części (np. połowy, partycje) oraz często rekurencja i charakterystyczne złożoności typu O(log n) lub O(n log n).

Dodatkowe pytania

Dodatkowe pytania (FAQ):
To paradygmat projektowania algorytmów, w którym problem dzieli się na mniejsze podproblemy tego samego typu, rozwiązuje je (często rekurencyjnie), a następnie łączy wyniki. Typowe są tu powtarzające się podziały (np. na połowy) i dobre własności złożoności.
Wyszukiwanie binarne działa na danych uporządkowanych. Porównuje szukaną wartość z elementem środkowym, a potem odrzuca połowę przedziału, w której na pewno jej nie ma. Powtarza to aż do znalezienia elementu lub wyczerpania zakresu.
Bo w każdym kroku dzieli problem na mniejszy podproblem (pozostaje jedna połowa zakresu), a następnie zwycięża, rozwiązując ten podproblem analogicznie. Struktura jest powtarzalna i naturalnie opisywalna rekurencyjnie.
Zwykle nie. Typowe wyszukiwanie w nieuporządkowanych danych to skanowanie liniowe, czyli sprawdzanie elementów po kolei. Brakuje tu systematycznego podziału na mniejsze podproblemy o tej samej strukturze, jak w wyszukiwaniu binarnym.
Samo scalanie dwóch posortowanych ciągów jest operacją łączenia wyników. W paradygmacie "dziel i zwyciężaj" pojawia się jako etap w sortowaniu przez scalanie: najpierw dzielenie danych na części, potem sortowanie części, na końcu scalanie.
Sortowanie bąbelkowe wykonuje wielokrotne przejścia po tablicy i zamienia sąsiadujące elementy, "wypychając" największe na koniec. Nie dzieli problemu na mniejsze niezależne podproblemy ani nie korzysta z rekurencji typowej dla "dziel i zwyciężaj".
Najczęściej podaje się sortowanie szybkie i sortowanie przez scalanie. W obu przypadkach występuje podział danych na części, rozwiązanie części (rekurencyjnie) oraz połączenie/ustawienie wyniku. W praktyce to bardzo ważna rodzina algorytmów.
Gdy dane nie są uporządkowane zgodnie z relacją, której używasz do porównań. Wtedy "odrzucanie połowy" nie jest logicznie uzasadnione i można pominąć szukany element. Błędy powodują też złe granice przedziału i przepełnienia przy liczeniu środka.
Częsty błąd to utożsamienie każdego algorytmu z "dzieleniem" danych (np. iteracyjne sortowania) z paradygmatem "dziel i zwyciężaj". Drugi błąd to pominięcie warunku uporządkowania w wyszukiwaniu binarnym lub mylenie "scalania" z "dzieleniem".
Warto zrobić tabelę: paradygmat → cechy (rekurencja, podział, łączenie) → przykłady algorytmów. Następnie przećwiczyć rozpoznawanie po opisie słownym: czy algorytm realnie zmniejsza problem (np. o połowę), czy tylko iteruje po całości.
info

Około 60% zdających odpowiada poprawnie na to pytanie. średnie

Specjaliści zwracają uwagę: "Scalanie dwóch ciągów, wyszukiwanie w nieuporządkowanym zbiorze i sortowanie bąbelkowe nie realizują tego schematu."

Źródła:

  • Wikipedia: "Dziel i zwyciężaj" (hasło: Divide and conquer algorithm) https://pl.wikipedia.org/wiki/Dziel_i_zwyci%C4%99%C5%BCaj - dostęp: 2026-03-02
  • Wikipedia: "Wyszukiwanie binarne" https://pl.wikipedia.org/wiki/Wyszukiwanie_binarne - dostęp: 2026-03-02
  • Wikipedia: "Sortowanie bąbelkowe" https://pl.wikipedia.org/wiki/Sortowanie_b%C4%85belkowe - dostęp: 2026-03-02

Materiały:

  • Rozdziały z algorytmiki: paradygmaty projektowania algorytmów (divide and conquer)
  • Materiały o wyszukiwaniu binarnym i warunkach jego poprawności (uporządkowanie danych, warianty graniczne)
  • Ćwiczenia implementacyjne: porównanie iteracyjnej i rekurencyjnej wersji wyszukiwania binarnego

Aktualizacja pytania: 31.03.2026



Aktualizacja pytania: 31.03.2026
📡 Brak połączenia internetowego