ASD Ćwiczenia 5

From Studia Informatyczne

Spis treści

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.