Ćwiczenia | Informatyka MIMUW

Zadanie 1

Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi \( \lceil \log 4! \rceil \).

Wskazówka

Przedstaw za pomocą drzewa decyzyjnego algorytm sortowania przez scalanie z pominięciem zbędnych porównań.

Zadanie 2

Zaproponuje algorytm sortujący 4 elementy za pomocą co 5 porównań.

Wskazówka

Narysuj drzewo decyzyjne implementujące sortowanie przez scalanie. Unikaj redundantnych porównań.

Zadanie 3

Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.

Wskazówka

Załóżmy, że sortujemy ciąg \( x_1, x_2, x_3, x_4, x_5 \). Oto trzy pierwsze porównania:
1) \( x_1 \) z \( x_2 \)
2) \( x_3 \) z \( x_4 \)
3) porównanie mniejszych elementów z każdej z par.

Zadanie 4

Udowodnij, że każdy algorytm wyznaczający element minimalny w zbiorze \( n \)-elementowym wykonuje w pesymistycznym przypadku co najmniej \( n-1 \) porównań.

Wskazówka

Wykorzystaj fakt, że każdy \( n \)-wierzchołkowy graf spójny zawiera co najmniej \( n-1 \) krawędzi.

Zadanie 5

Zaproponuj algorytm, który w ciągu długości \( n \) wyznacza elementy maksymalmy i minimalny wykonując co najwyżej \( 3n/2 - 2 \) porównania, gdy \( n \) jest parzyste, a co najwyżej \( 3\lfloor n/2\rfloor \), gdy \( n \) jest nieparzyste.

Wskazówka

W pierwsze fazie porównuj elementy w rozłącznych parach.