« poprzedni punkt   następny punkt »


Ćwiczenia do wykładu 04
 

  1. Udowodnij, że permutacja n liczb  ma co najwyżej n(n-1)/2 inwersji.
     
  2. Rozważmy następujący algorytm sortowania Alg1:
    1. Wyznacz największy i najmniejszy element ciągu stosując algorytm optymalny.
    2. Umieść znalezione elementy na ostatniej i pierwszej pozycji ciągu wykonując operację swap.
    3. Powtarzaj postępowanie dla ciągu, w którym pominięto pierwszy i ostatni element, tak długo aż cały ciąg zostanie uporządkowany.

     Ile porównań wykona ten algorytm? Narysuj graf algorytmu Alg1 i uzasadnij jego poprawność.
     

  3. Rozważmy następujący algorytm sortowania Alg2:
    1. Znajdź największy i drugi co do wielkości element ciągu metodą Turniej (por. wykład III, p. 5).
    2. Zamień miejscami znaleziony element największy z ostatnią pozycją ciągu.
    3. Zamień miejscami przedostatni element ze znalezionym elementem drugim co do wielkości.
    4. Powtarzaj postępowanie  (od punktu a) dla ciągu zmniejszonego o dwa ostatnie elementy dopóki cały ciąg nie będzie uporządkowany niemalejąco.

    Ile porównań wykona ten algorytm w przypadku, gdy ciąg jest już posortowany? Oszacuj koszt algorytmu w przypadku najgorszym.  Narysuj graf algorytmu Alg2 i uzasadnij jego poprawność.
     

  4. Zmodyfikuj algorytmy SelectionSort i InsertionSort, tak by dla dowolnego n elementowego ciągu e, wyznaczały one permutację  i1,...,in  liczb naturalnych od 1 do n taką, że  e[i1] £e[i2] ... £ e[in].
     
  5. Napisz algorytm QuickSort bez użycia rekursji. Jaka pomocnicza struktura danych będzie potrzebna?
     
  6. Zapisz iteracyjną wersję algorytmu MergeSort. (b) Zaproponuj realizację tego algorytmu na listach. Zbadaj, czy takie modyfikacje zmieniają koszt czasowy algorytmu. Zwróć uwagę na różnice w rozwiązaniu zadań 6 i 7.
     
  7. Udowodnij, że każdy algorytm scalania dwóch posortowanych ciągów n elementowych, przez porównywanie elementów, musi wykonać w najgorszym przypadku co najmniej 2n-1 porównań.
     
  8. Dane są dwa zbiory skończone. Skonstruuj i zaimplementuj algorytmy znajdowania sumy i przecięcia teoriomnogościowego tych zbiorów. Oszacuj koszt zaproponowanych algorytmów.
     
  9. Dana jest kwadratowa układanka o wymiarach n´n, której wszystkie pozycje są wypełnione liczbami od 1 do n2. Jaka jest najmniejsza liczba ruchów typu "swap" (zamiana pozycji dwóch elementów), aby ułożyć wszystkie liczby w porządku rosnącym zarówno wierszami jak i kolumnami? Zaproponuj ogólną metodę postępowania.

 

« poprzedni punkt   następny punkt »