ASD Ćwiczenia 5: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Zastępowanie tekstu – „ </math>” na „</math>” |
|||
| (Nie pokazano 4 wersji utworzonych przez 2 użytkowników) | |||
| Linia 1: | Linia 1: | ||
=='''Zadanie 1'''== | =='''Zadanie 1'''== | ||
Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi <math>\lceil \log 4! \rceil </math>. | Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi <math>\lceil \log 4! \rceil</math>. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
| Linia 13: | Linia 13: | ||
=='''Zadanie 2'''== | =='''Zadanie 2'''== | ||
Zaproponuje algorytm sortujący 4 | Zaproponuje algorytm sortujący 4 elementy za pomocą co 5 porównań. | ||
| Linia 27: | Linia 27: | ||
=='''Zadanie 3'''== | =='''Zadanie 3'''== | ||
Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań. | |||
| Linia 40: | Linia 40: | ||
2) <math>x_3</math> z <math>x_4</math> | 2) <math>x_3</math> z <math>x_4</math> | ||
3) porównanie mniejszych elementów z każdej z par | 3) porównanie mniejszych elementów z każdej z par. | ||
</div> | </div> | ||
</div> | </div> | ||
=='''Zadanie | =='''Zadanie 4'''== | ||
Udowodnij, że | Udowodnij, że każdy algorytm wyznaczający element minimalny w zbiorze <math>n</math>-elementowym wykonuje w pesymistycznym przypadku co najmniej <math>n-1</math> porównań. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
| Linia 53: | Linia 53: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Wykorzystaj fakt, | Wykorzystaj fakt, że każdy <math>n</math>-wierzchołkowy graf spójny zawiera co najmniej <math>n-1</math> krawędzi. | ||
</div> | |||
</div> | |||
=='''Zadanie 5'''== | |||
Zaproponuj algorytm, który w ciągu długości <math>n</math> wyznacza elementy maksymalmy i minimalny wykonując co najwyżej <math>3n/2 - 2</math> porównania, gdy <math>n</math> jest parzyste, a co najwyżej <math>3\lfloor n/2\rfloor</math>, gdy <math>n</math> jest nieparzyste. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
Wskazówka | |||
<div class="mw-collapsible-content" style="display:none"> | |||
W pierwsze fazie porównuj elementy w rozłącznych parach. | |||
</div> | |||
</div> | </div> | ||
Aktualna wersja na dzień 10:08, 5 wrz 2023
Zadanie 1
Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi .
Wskazówka
Zadanie 2
Zaproponuje algorytm sortujący 4 elementy za pomocą co 5 porównań.
Wskazówka
Zadanie 3
Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.
Wskazówka
Zadanie 4
Udowodnij, że każdy algorytm wyznaczający element minimalny w zbiorze -elementowym wykonuje w pesymistycznym przypadku co najmniej porównań.
Wskazówka
Zadanie 5
Zaproponuj algorytm, który w ciągu długości wyznacza elementy maksymalmy i minimalny wykonując co najwyżej porównania, gdy jest parzyste, a co najwyżej , gdy jest nieparzyste.
Wskazówka
