Základy algoritmizace a programování

Petr Sváček, Luděk Beneš, Olga Majlingová
Ústav technické matematiky

Cviceni č. 11


Zde obsah cvičení jen v provizorní textové podobě, podrobněji viz MOODLE.
I. Algoritmy třídění. Stejný program je často možné zapsat různými způsoby s odlišnou efektivitou. Při použití počítačů používáme pokud je to možné rychlé algoritmy (lze definovat přesný význam pojmu). Vyzkoušejte si následující algoritmy třídění aplikované např. na náhodná data.
Náhodná data vygenerujte například takto

n = 1024;
SEZNAM = randi(10000, n, 1);

Čas běhu algoritmu zjistíte například následovně (čas může být ovlivněn úlohami běžícími na pozadí):

zac = time; sorted = bsort(SEZNAM); kon = time; kon - zac

Úkoly:

    Vyzkoušejte jednotlivé algoritmy (bsort - bublinkové třídění, dsort - třídění přímým výběrem, qsort - algoritmus quick sort) a jejich časovou náročnost (Algoritmy jsou uvedeny na konci této stránky)
    Algoritmy si projděte, zejména bublinkové třídění a třídění přímým výběrem. Algoritmus QuickSort užívá takzvané rekurze. Nahládněte do kódu a vysvětlete tento pojem.
    Upravte algoritmy tak aby prvky byly seřazeny od nejmenšího, od největšího, nebo např. vzhledem k velikosti absolutní hodnoty.
    Upravte algoritmy např. tak aby bylo řazeno pole struktur dle vybrané hodnoty.

II. Rychlá diskrétní Fourierova transformace: Jedním z důležitých rychlých algoritmů je výpočet diskrétní Fourierovy transformace diskrétních (komplexních) hodnot 𝑥𝑛

dle vzorce

𝑋𝑘=∑𝑁−1𝑛=0𝑥𝑛𝑒−𝑖2𝜋𝑘𝑛/𝑁 pro 𝑘∈{0,…,𝑁−1}



Výpočet odpovídá násobení matice vektorem, tedy odpovídá provedení 𝑁2
operací (složitost je 𝑂(𝑛2)). Algoritmus lze ale při vhodném zápisu a pro volbu 𝑁=2𝑚 realizovat se složitostí 𝑚𝑁 operací nebo-li se složitostí 𝑂(𝑁log2𝑁).
a) Vyzkoušejte složitost algoritmu
Algoritmus je realizován přímo v Matlabu funkce fft, vyzkoušejte jeho rychlost/efektivitu pro 𝑁=2𝑚 , a napr. 𝑁=2𝑚−1, volte m dle vykonu a pameti Vaseho pocitace: zkuste nejprve 𝑚=18

a postupne zvysujte, nejvyse vsak na m = 27 (obsazena pamet vektorem bude cca 1 GB!!!) .

N = (2^15), h = 200 * randn(N, 1); zac = time; a = fft(h); kon = time; kon - zac

b) Vyzkousejte pouziti FFT pro analyzu signalu h a signalu hsum (signal zatizen sumem s normalnim nahodnym rozdelenim).

T = 5; % 
N = 65536; 
n1 = N - 1; t = T * (0:n1)' / n1;
f1 = 50; f2 = 120; 

h    = 0.7 * sin(2 * pi * f1 * t) + sin(2 * pi * f2 * t);
hsum = h + 2 * randn(size(t)); % signal zasumnen nahodnym sumem o amplitude 2, normalni rozdeleni

plot(t, hsum, 'k.'), axis([0.2 0.8])

plot(t, h, t, hsum, 'k.'), axis([0.2 0.3])

Fh = 2 * abs(fft(h)) / length(h);
FREQ = 200; % maximal frequency to be shown
idx = 1:((FREQ + T) * T); plot((idx - 1 ) / T, Fh(idx));

plot((idx - 1) / T, Fh(idx),'bo-');

c) Vyzkoušejte použití FFT pro získaní frekvence a amplitudy signálu h, pokud víte, že se skládá ze 2 neznámých základních frekvencí. Vygenerujte náhodný signál dle následujícího řádku a užijte FFT pro detekci frekvencí signálu. Zkuste přidat šum.

T = 5; N = 65536;  t = T * (0:(N-1))' / (N-1);
h    = randi(400,1)/100 * sin(2 * pi * randi(200,1) * t) + randi(300,1)/100 *sin(2 * pi * randi(200,1) * t);

Vyzkoušejte použití FFT při zjišťování frekvence a amplitudy netlumeného i tlumeného signálu h o jedné frekvenci

f1 = 105; d1 = -0.2; d2 = -0.5;
h1    = 0.7 * exp(d1 * t) .* sin(2 * pi * f1 * t);
h2    = 0.7 * exp(d2 * t) .* sin(2 * pi * f1 * t);
h     = 0.7 * sin(2 * pi * f1 * t);

d) Vyzkoušejte použití FFT při zjišťování frekvence a amplitudy tlumeného signálu h o dvou různě tlumených frekvencích

f1 = 105; f2 = 45; d1 = -0.5; d2 = -2; A1 = 0.9; A2 = 3;
hn    = A1 * sin(2 * pi * f1 * t) + A2 * sin(2 * pi * f2 * t);
h     = A1 * exp(d1 * t) .* sin(2 * pi * f1 * t) + A2 * exp(d1 * t) .*  sin(2 * pi * f2 * t);

Bublinkové třídění:

function  sorted = bsort(vector)
%
% 

n = length(vector);
sorted = vector;
do
  poczmen = 0;
  for i = 1:(n-1)
    if (sorted(i) < sorted(i+1))
      tmp = sorted(i);
      sorted(i) = sorted(i + 1);
      sorted(i + 1) = tmp;
      poczmen = poczmen + 1;
    end
  end
until poczmen == 0;

Třídění přímým výběrem:

function  sorted = dsort(vector)
%
% 
%
n = length(vector);
sorted = vector;

for i = 1:n-1,
  for j = (i + 1):n
     if (sorted(i) > sorted(j))
	 tmp = sorted(i);
         sorted(i) = sorted(j);
         sorted(j) = tmp;
     end
  end
end

Rychlé třídění (quicksort, ...):

function  sorted = qsort(vector)

m = length(vector);
sorted = vector;
sort_r(1, m);

function sort_r(low, high)
  i = low;
  j = high;
  if (high > low)
      idx = floor((low + high) / 2);
      pivot = sorted(idx);
      while (i <= j)
         while(sorted(i) < pivot)
	    i = i + 1;
         end
         while(sorted(j) > pivot)
            j = j - 1;
         end
        if(i <= j) 
          tmp1 = sorted(i);
          sorted(i) = sorted(j);
          sorted(j) = tmp1;
          i = i + 1; j = j - 1;
        end
      end
      if (low < j) 
         sort_r(low, j);
      end
      if (i < high) 
         sort_r(i, high);
      end
    end
  end
end