Kiwiki - Príspevky používateľa [sk]

Problém batoha

2010-04-08T16:45:44Z

Jumanji:

== Formulácia problému ==

Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

== Riešenie problému ==

Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.

Vytvoríme tabuľku, kde stĺpce budú popisovať cieľovú nosnosť (kapacitu) batohu, posledný stĺpec bude maximálna nosnosť.
Riadky budú označovať jednotlivé veci, ktoré môžeme do batohu vložiť.
Budeme potrebovať n + 1 riadkov, kde n je počet predmetov. Riadok navyše máme pre žiadny vložený predmet. Ďalej budeme potrebovať k + 1 stĺpcov, jeden stĺpec navyše je pre kapacitu batoha o veľkosti 0.

Prvý stĺpec naplníme samými nulami, pretože to zodpovedá batohu s nulovou kapacitou.
Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.

[[Súbor:Batoh1.jpg]]

- V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
- Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.
Konkrétne, keď sa pozrieme na prvý predmet a nosnosť batohu 6. Váha prvého predmetu je 5 a jeho cena 10. Zistíme, akú cenu mal batoh s rovnakou kapacitou, ale bez tohto predmetu a akú cenu by mal s kapacitou batohu nižšou o hmotnosť prvého predmetu s nultým predmetom a k tejto hodnote prirátame cenu prvého predmetu.
- Vidíme, že druhá hodnota je väčšia, tým pádom napíšeme do bunky číslo 24.
Takto postupne vypĺňame celú tabuľku. Výsledná hodnota je v pravom dolnom stĺpci.

Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:

----

[[Súbor:Vzorec.jpg]] a [[Súbor:Vzorec1.jpg]]

----

T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.

Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.

== Iné prístupy k riešeniu ==

Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.

Brute force: iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.

== Zložitosť algoritmu ==

Časová zložitosť algoritmu závisí od veľkosti tabuľky.
Máme tu 2 faktory:
n + 1 riadkov, kde n je počet predmetov a
k + 1 stĺpcov, kde k je maximálna kapacita batohu.
Čiže časová zložitosť tohto algoritmu je O(k*n).
Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.

== Využitie ==

Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.

== Program v jazyku C++ ==

const n=3;
void greedy(double M,double W[n],double C[n],double X[n])
{ double Z=M;
int i;
for (i=0; i<n; i++) {
if(W[i]>Z)a
break;
X[i]=1;
Z=Z-W[i];
}
if ((i<n))
X[i]=Z/W[i];
}

int main()
{
double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
greedy(20,W,C,X);
double p=0;
for (int i=0 ;i<n; p+=X[i]*C[i],i++)
cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
cout<<"celkom:"<<p<<endl;
system("pause"); }

Problém batoha

2010-04-08T16:45:01Z

Jumanji:

== Formulácia problému: ==

Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

== Riešenie problému: ==

Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.

Vytvoríme tabuľku, kde stĺpce budú popisovať cieľovú nosnosť (kapacitu) batohu, posledný stĺpec bude maximálna nosnosť.
Riadky budú označovať jednotlivé veci, ktoré môžeme do batohu vložiť.
Budeme potrebovať n + 1 riadkov, kde n je počet predmetov. Riadok navyše máme pre žiadny vložený predmet. Ďalej budeme potrebovať k + 1 stĺpcov, jeden stĺpec navyše je pre kapacitu batoha o veľkosti 0.

Prvý stĺpec naplníme samými nulami, pretože to zodpovedá batohu s nulovou kapacitou.
Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.

[[Súbor:Batoh1.jpg]]

- V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
- Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.
Konkrétne, keď sa pozrieme na prvý predmet a nosnosť batohu 6. Váha prvého predmetu je 5 a jeho cena 10. Zistíme, akú cenu mal batoh s rovnakou kapacitou, ale bez tohto predmetu a akú cenu by mal s kapacitou batohu nižšou o hmotnosť prvého predmetu s nultým predmetom a k tejto hodnote prirátame cenu prvého predmetu.
- Vidíme, že druhá hodnota je väčšia, tým pádom napíšeme do bunky číslo 24.
Takto postupne vypĺňame celú tabuľku. Výsledná hodnota je v pravom dolnom stĺpci.

Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:

----

[[Súbor:Vzorec.jpg]] a [[Súbor:Vzorec1.jpg]]

----

T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.

Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.

== Iné prístupy k riešeniu: ==

Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.

Brute force: iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.

== Zložitosť algoritmu: ==

Časová zložitosť algoritmu závisí od veľkosti tabuľky.
Máme tu 2 faktory:
n + 1 riadkov, kde n je počet predmetov a
k + 1 stĺpcov, kde k je maximálna kapacita batohu.
Čiže časová zložitosť tohto algoritmu je O(k*n).
Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.

== Využitie: ==

Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.

== Program v jazyku C++: ==

const n=3;
void greedy(double M,double W[n],double C[n],double X[n])
{ double Z=M;
int i;
for (i=0; i<n; i++) {
if(W[i]>Z)a
break;
X[i]=1;
Z=Z-W[i];
}
if ((i<n))
X[i]=Z/W[i];
}

int main()
{
double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
greedy(20,W,C,X);
double p=0;
for (int i=0 ;i<n; p+=X[i]*C[i],i++)
cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
cout<<"celkom:"<<p<<endl;
system("pause"); }

Problém batoha

2010-04-08T16:44:13Z

Jumanji:

Problém batoha

2010-04-08T16:38:21Z

Jumanji:

Obsah:
#REDIRECT [[-Formulácia problému]]
-Návrh riešenia problému
-Riešenie
-Zložitosť
-Využitie
-Iné prístupy k riešeniu
-Riešenie v jazyku C++

Formulácia problému:
Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

Riešenie problému:
Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.

Vytvoríme tabuľku, kde stĺpce budú popisovať cieľovú nosnosť (kapacitu) batohu, posledný stĺpec bude maximálna nosnosť.
Riadky budú označovať jednotlivé veci, ktoré môžeme do batohu vložiť.
Budeme potrebovať n + 1 riadkov, kde n je počet predmetov. Riadok navyše máme pre žiadny vložený predmet. Ďalej budeme potrebovať k + 1 stĺpcov, jeden stĺpec navyše je pre kapacitu batoha o veľkosti 0.

Prvý stĺpec naplníme samými nulami, pretože to zodpovedá batohu s nulovou kapacitou.
Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.

[[Súbor:Batoh1.jpg]]

- V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
- Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.
Konkrétne, keď sa pozrieme na prvý predmet a nosnosť batohu 6. Váha prvého predmetu je 5 a jeho cena 10. Zistíme, akú cenu mal batoh s rovnakou kapacitou, ale bez tohto predmetu a akú cenu by mal s kapacitou batohu nižšou o hmotnosť prvého predmetu s nultým predmetom a k tejto hodnote prirátame cenu prvého predmetu.
- Vidíme, že druhá hodnota je väčšia, tým pádom napíšeme do bunky číslo 24.
Takto postupne vypĺňame celú tabuľku. Výsledná hodnota je v pravom dolnom stĺpci.

Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:

----

[[Súbor:Vzorec.jpg]] a [[Súbor:Vzorec1.jpg]]

----

T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.

Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.

Iné prístupy k riešeniu:
Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.

Brute force: iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.

Zložitosť algoritmu:
Časová zložitosť algoritmu závisí od veľkosti tabuľky.
Máme tu 2 faktory:
n + 1 riadkov, kde n je počet predmetov a
k + 1 stĺpcov, kde k je maximálna kapacita batohu.
Čiže časová zložitosť tohto algoritmu je O(k*n).
Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.

Využitie:
Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.

Program v jazyku C++:

const n=3;
void greedy(double M,double W[n],double C[n],double X[n])
{ double Z=M;
int i;
for (i=0; i<n; i++) {
if(W[i]>Z)a
break;
X[i]=1;
Z=Z-W[i];
}
if ((i<n))
X[i]=Z/W[i];
}

int main()
{
double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
greedy(20,W,C,X);
double p=0;
for (int i=0 ;i<n; p+=X[i]*C[i],i++)
cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
cout<<"celkom:"<<p<<endl;
system("pause"); }
#REDIRECT [[#REDIRECT [[]]]]

Problém batoha

2010-04-08T16:32:53Z

Jumanji:

Formulácia problému:
Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

Riešenie problému:
Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.

Vytvoríme tabuľku, kde stĺpce budú popisovať cieľovú nosnosť (kapacitu) batohu, posledný stĺpec bude maximálna nosnosť.
Riadky budú označovať jednotlivé veci, ktoré môžeme do batohu vložiť.
Budeme potrebovať n + 1 riadkov, kde n je počet predmetov. Riadok navyše máme pre žiadny vložený predmet. Ďalej budeme potrebovať k + 1 stĺpcov, jeden stĺpec navyše je pre kapacitu batoha o veľkosti 0.

Prvý stĺpec naplníme samými nulami, pretože to zodpovedá batohu s nulovou kapacitou.
Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.

[[Súbor:Batoh1.jpg]]

- V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
- Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.
Konkrétne, keď sa pozrieme na prvý predmet a nosnosť batohu 6. Váha prvého predmetu je 5 a jeho cena 10. Zistíme, akú cenu mal batoh s rovnakou kapacitou, ale bez tohto predmetu a akú cenu by mal s kapacitou batohu nižšou o hmotnosť prvého predmetu s nultým predmetom a k tejto hodnote prirátame cenu prvého predmetu.
- Vidíme, že druhá hodnota je väčšia, tým pádom napíšeme do bunky číslo 24.
Takto postupne vypĺňame celú tabuľku. Výsledná hodnota je v pravom dolnom stĺpci.

Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:

----

[[Súbor:Vzorec.jpg]] a [[Súbor:Vzorec1.jpg]]

----

T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.

Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.

Iné prístupy k riešeniu:
Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.

Brute force: iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.

Zložitosť algoritmu:
Časová zložitosť algoritmu závisí od veľkosti tabuľky.
Máme tu 2 faktory:
n + 1 riadkov, kde n je počet predmetov a
k + 1 stĺpcov, kde k je maximálna kapacita batohu.
Čiže časová zložitosť tohto algoritmu je O(k*n).
Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.

Využitie:
Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.

Program v jazyku C++:

const n=3;
void greedy(double M,double W[n],double C[n],double X[n])
{ double Z=M;
int i;
for (i=0; i<n; i++) {
if(W[i]>Z)a
break;
X[i]=1;
Z=Z-W[i];
}
if ((i<n))
X[i]=Z/W[i];
}

int main()
{
double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
greedy(20,W,C,X);
double p=0;
for (int i=0 ;i<n; p+=X[i]*C[i],i++)
cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
cout<<"celkom:"<<p<<endl;
system("pause"); }

Problém batoha

2010-04-08T16:32:23Z

Jumanji:

Problém batoha

2010-04-08T16:31:13Z

Jumanji:

Problém batoha

2010-04-08T16:28:11Z

Jumanji:

Problém batoha

2010-04-08T16:26:56Z

Jumanji:

Formulácia problému:
Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

Riešenie problému:
Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.

Vytvoríme tabuľku, kde stĺpce budú popisovať cieľovú nosnosť (kapacitu) batohu, posledný stĺpec bude maximálna nosnosť.
Riadky budú označovať jednotlivé veci, ktoré môžeme do batohu vložiť.
Budeme potrebovať n + 1 riadkov, kde n je počet predmetov. Riadok navyše máme pre žiadny vložený predmet. Ďalej budeme potrebovať k + 1 stĺpcov, jeden stĺpec navyše je pre kapacitu batoha o veľkosti 0.

Prvý stĺpec naplníme samými nulami, pretože to zodpovedá batohu s nulovou kapacitou.
Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.

[[Súbor:Batoh1.jpg]]

- V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
- Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.
Konkrétne, keď sa pozrieme na prvý predmet a nosnosť batohu 6. Váha prvého predmetu je 5 a jeho cena 10. Zistíme, akú cenu mal batoh s rovnakou kapacitou, ale bez tohto predmetu a akú cenu by mal s kapacitou batohu nižšou o hmotnosť prvého predmetu s nultým predmetom a k tejto hodnote prirátame cenu prvého predmetu.
- Vidíme, že druhá hodnota je väčšia, tým pádom napíšeme do bunky číslo 24.
Takto postupne vypĺňame celú tabuľku. Výsledná hodnota je v pravom dolnom stĺpci.

Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:

[[Súbor:Vzorec.jpg]] a [[Súbor:Vzorec1.jpg]]

T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.

Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.

Iné prístupy k riešeniu:
Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.

Brute force: iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.

Zložitosť algoritmu:
Časová zložitosť algoritmu závisí od veľkosti tabuľky.
Máme tu 2 faktory:
n + 1 riadkov, kde n je počet predmetov a
k + 1 stĺpcov, kde k je maximálna kapacita batohu.
Čiže časová zložitosť tohto algoritmu je O(k*n).
Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.

Využitie:
Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.

Program v jazyku C++:
''
const n=3;
void greedy(double M,double W[n],double C[n],double X[n])
{ double Z=M;
int i;
for (i=0; i<n; i++) {
if(W[i]>Z)a
break;
X[i]=1;
Z=Z-W[i];
}
if ((i<n))
X[i]=Z/W[i];
}

int main()
{
double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
greedy(20,W,C,X);
double p=0;
for (int i=0 ;i<n; p+=X[i]*C[i],i++)
cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
cout<<"celkom:"<<p<<endl;
system("pause"); }
''

Problém batoha

2010-04-08T16:23:05Z

Jumanji:

Formulácia problému:
Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

Riešenie problému:
Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.

Vytvoríme tabuľku, kde stĺpce budú popisovať cieľovú nosnosť (kapacitu) batohu, posledný stĺpec bude maximálna nosnosť.
Riadky budú označovať jednotlivé veci, ktoré môžeme do batohu vložiť.
Budeme potrebovať n + 1 riadkov, kde n je počet predmetov. Riadok navyše máme pre žiadny vložený predmet. Ďalej budeme potrebovať k + 1 stĺpcov, jeden stĺpec navyše je pre kapacitu batoha o veľkosti 0.

Prvý stĺpec naplníme samými nulami, pretože to zodpovedá batohu s nulovou kapacitou.
Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.

[[Súbor:Batoh1.jpg]]

- V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
- Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.
Konkrétne, keď sa pozrieme na prvý predmet a nosnosť batohu 6. Váha prvého predmetu je 5 a jeho cena 10. Zistíme, akú cenu mal batoh s rovnakou kapacitou, ale bez tohto predmetu a akú cenu by mal s kapacitou batohu nižšou o hmotnosť prvého predmetu s nultým predmetom a k tejto hodnote prirátame cenu prvého predmetu.
- Vidíme, že druhá hodnota je väčšia, tým pádom napíšeme do bunky číslo 24.
Takto postupne vypĺňame celú tabuľku. Výsledná hodnota je v pravom dolnom stĺpci.

Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:

[[Súbor:Vzorec.jpg]] a [[Súbor:Vzorec1.jpg]]

T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.

Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.

Iné prístupy k riešeniu:
Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.

Brute force: iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.

Zložitosť algoritmu:
Časová zložitosť algoritmu závisí od veľkosti tabuľky.
Máme tu 2 faktory:
n + 1 riadkov, kde n je počet predmetov a
k + 1 stĺpcov, kde k je maximálna kapacita batohu.
Čiže časová zložitosť tohto algoritmu je O(k*n).
Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.

Využitie:
Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.

Program v jazyku C++:

const n=3;
void greedy(double M,double W[n],double C[n],double X[n])
{ double Z=M;
int i;
for (i=0; i<n; i++) {
if(W[i]>Z)a
break;
X[i]=1;
Z=Z-W[i];
}
if ((i<n))
X[i]=Z/W[i];
}

int main()
{
double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
greedy(20,W,C,X);
double p=0;
for (int i=0 ;i<n; p+=X[i]*C[i],i++)
cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
cout<<"celkom:"<<p<<endl;
system("pause"); }

Problém batoha

2010-04-08T16:14:10Z

Jumanji: Vytvorená stránka „<gallery>Batoh1.jpg</gallery>“

<gallery>Batoh1.jpg</gallery>

Súbor:Batoh1.jpg

2010-04-08T16:13:26Z

Jumanji:

Algoritmy triedenia

2010-03-21T21:01:13Z

Jumanji:

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}
__TOC__
{{Cvicenie|Triedenie(riešené príklady)}}
'''Triedenie'''

Triedaci algoritmus je v informatike algoritmus, ktorý zoraďuje prvky zoznamu v určenom poradí. Najpoužívanejšie sú numerické a lexikografické poradie.
Efektívne triedenie je dôležité pre optimalizáciu použitia iných algoritmov (ako je napr. vyhľadávanie), ktoré vyžadujú pre svoju správnu funkčnosť utriedené zoznamy. Formálne povedané, výstupné utriedené údaje musia spĺňať dve podmienky:
#Prvky vo výstupnom zozname majú neklesajúci trend (každý prvok je väčší alebo rovný ako predchádzajúci prvok)
#Výstupom je permutácia vstupných resp. preusporiadanie týchto údajov.

==Klasifikácia==
Triediace algoritmy môžeme klasifikovať podľa:
;Výpočtová zložitosť: (najhoršia, priemerná a najlepšia) pre zoznam s veľkosťou n položiek. Pre typické triediace algoritmy je prijateľná výpočtová zložitosť aspoň O(n.log n) a zlá O(n2). Ideálna zložitosť je O(n). Triediace algoritmy, ktoré používajú iba abstraktnú operáciu porovnania vždy majú priemernú zložitosť aspoň O(n.log n) porovnaní.
;Využitie pamäte:(a využívanie ďalších počítačových zdrojov). Niektoré triediace algoritmy sú typu "in-place". To znamená, že im stačí O(1) alebo O(log n) pamäte na triedené položky.
;Rekurzia: Niektoré algoritmy sú buď rekurzívne alebo nerekurzívne, niektoré môžu byť implementovateľné oboma spôsobmi (napr. Merge sort).
;Stabilita: Stabilné triediace algoritmy - súvis s triedením dvojíc kľúč-hodnota, pričom existujú 2 také záznamy, že kľúče sú rovnaké. Stabilný algoritmus nezmení poradie týchto dvojíc vo výsledku.
;Metóda triedenia: vkladanie, výmena, výber, zlúčenie, a pod.

==Typy triediacich algoritmov==
===Vnútorné triedenie===
Vnútorný triedenie je akýkoľvek triediaci proces, ktorý prebieha v hlavnej pamäti počítača. To je možné ak údaje, ktoré majú byť triedené majú takú veľkosť, že sa dokážu nahrať do hlavnej pamäti. Akékoľvek čítanie alebo zápis dát do/z externej pamäte môže značne spomaliť proces triedenia.

Uvažujem algoritmus Bubblesort, kde sa vymieňajú priľahlé záznamy s cieľom dostať ich do správneho poradia. V prípade, že časť triedeného súboru by bola b hlavnej pamäti a časť na externej pamäti, neustále by sa musel nahrávať do pamäti ten blok spboru, v ktorom sa vykonáva "prebulávanie".

===Vonkajšie triedenie===
Vonkajšie triedenie<ref>External_sorting - http://en.wikipedia.org/wiki/External_sorting</ref> je termín pre triedu triediacich algoritmov, ktoré môžu spracovať obrovské množstvo dát. Vonkajšie triedenie sa vyžaduje, ak sa triedené údaje nezmestia do hlavnej pamäte počítača (zvyčajne RAM) a namiesto toho musia byť umiestnené v pomalšej vonkajšej pamäti (zvyčajne pevný disk). Vonkajšie triedenie zvyčajne používa princíp zlučovania. Vo fáze triedenia sú dáta rozdelené do malých objemov ktoré sa zmestia do hlavnej pamäte. Pri fáze zlúčenia sú tieto bloky spojené do jedného väčšieho súboru.
====Externý Mergesort====
Príklad externého triedenia je algoristmus externého mergesortu.<ref>Donald Knuth, ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998, ISBN 0-201-89685-0, Section 5.4: External Sorting, pp.248–379.</ref><ref>Ellis Horowitzand Sartaj Sahni, ''Fundamentals of Data Structures'', H. Freeman & Co., ISBN 0-716-78042-9.</ref>. Ako príklad uvádzame triedenie 900MB súboru ktorý rozdelíme na 100MB bloky, ktoré sú nahraté do pamäte.
# Načítaj 100MB dát do hlavnej pamäti a utrieď ich ľubovoľným triediacim algoritmom.
# Zapíš utriedený súbor na disk.
# Opakuj kroky 1. a 2. pokiaľ nie sú utriedené všetky 100MB bloky dát. Potom budeme tieto bloky spájať.
# Načítaj do pamäti prvých 10MB z každého utriedeného súboru. Alokuj zvyšných 10MB pre výstupný buffer.
# Vykonaj 9-násobný algoritmus merge (spájanie) zapíš výsledok do výstupného bufferu. Ak je výstupný buffer zaplnený, zapíš tieto údaje do výsledného utriedeného súboru. Ak je ľubovoľný z 9-tich vstupných bufferov prázdny, naplň ho ďalšími 10MB z jeho 100MB utriedeného súboru.

==Porovnanie algoritmov==
V nasledujúcej tabuľke je n počet záznamov, ktoré majú byť utriedené. Stĺpce "Priemerne" a "najhoršie" hovoria o časovej zložitosti, za predpokladu, že dĺžka všetkých kľúčov je konštantná, a preto všetky porovnania, výmeny a ďalšie potrebné operácie môže vykonať v konštantnom čase. "Pamäť" označuje množstvo pomocnej potrebnej okrem tej, ktorá je potrebná na samotné uloženie poľa ktoré sa bude triediť.

{| class="wikitable sortable" border=1 cellpadding=5
|-
! Názov
! Najlepšie
! Priemerne
! Najhoršie
! Pamäť
! Metóda triedenia
|-
| Bubble sort
| <math>\mathcal{O} (n)</math>
| <math>\mathcal{O} (n^2)</math>
| <math>\mathcal{O} (n^2)</math>
| <math>\mathcal{O}(1)</math>
| Výmena
|-
| Gnome sort
| <math>\mathcal{O} (n)</math>
| ---
| <math>\mathcal{O} (n^2)</math>
| <math>\mathcal{O}(1)</math>
| Výmena
|-
| Shake sort
| ---
| ---
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(1)</math>
| Výmena
|-
| Selection sort
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(1)</math>
| Výber
|-
| Shell sort
| <math>O(n^{1 + \frac{c}{\sqrt m}})</math><ref name="sedgewick96">Robert Sedgewick: [http://www.cs.princeton.edu/~rs/shell/ ''Analysis of Shellsort and Related Algorithms''], Fourth Annual European Symposium on Algorithms, Barcelona, 1996</ref>
| ---
| <math>\mathcal{O}(n \cdot \log^2 n)</math>
| <math>\mathcal{O}(1)</math>
| Vkladanie
|-
| Insert sort
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(1)</math>
| Vkladanie
|-
| Merge sort
| <math>\mathcal{O} (n \cdot \log n)</math>
| <math>\mathcal{O} (n \cdot \log n)</math>
| <math>\mathcal{O} (n \cdot \log n)</math>
| <math>\mathcal{O}(n)</math>
| Zlučovanie
|-
| Heap sort
| <math>\mathcal{O} (n \cdot \log n)</math>
| <math>\mathcal{O} (n \cdot \log n)</math>
| <math>\mathcal{O} (n \cdot \log n)</math>
| <math>\mathcal{O}(1)</math>
| Výber
|-
| Quick sort
| <math>\mathcal{O}(n \cdot \log n)</math>
| <math>\mathcal{O}(n \cdot \log n)</math>
| <math>\mathcal{O}(n^2)</math>
| <math>\mathcal{O}(\log n)</math>
| Delenie
|}

===Popis metód tiedenia===
Existuje niekoľko základných druhov algoritmov univerzálneho vnútorného triedenia. Niektoré z pokročilejšách algoritmov využívajú viacero postupov.

;Triedenie výberom:V súbore sa vždy nájde najmenší zo zostávajúcich položiek a uloží na koniec postupne vytváraného utriedeného súboru.
;Triedenie vkladaním:Zo súboru neusporiadaných dát sa postupne berie položka po položke a vkladá sa na správne miesto v usporiadanom súbore (na začiatku je prázdny).
;Triedenie výmenou:V súbore sa vždy nájde (nejakou metódou závislou na konkrétnom algoritme) nejaká dvojica prvkov, ktorá je v zlom poradí, a tieto prvky sa navzájom zamenia.
;Triedenie zlučovaním:Vstupný súbor sa rozdelí na časti, ktoré sa (typicky rekurzívne) zoradia. Výsledné časti sa potom zlúčia takým spôsobom, aby aj výsledok bol zoradený.

Neexistuje žiaden "dokonalý" triediaci algoritmus, ktorý by bol ideálny pre všetky použitia. Rôzne algoritmy majú rôzne vlastnosti čo sa týka ich očakávané časovej a pamäťovej zložitosti, náročnosti implementácie a ďalších vlastností. Pre konkrétne podmienky sa tak často navrhujú špecifické varianty.

==Princíp známych triediacich algoritmov==

===Bubble sort===
Bubble sort predstavuje jednoduchý spôsob triedenia dát. Algoritmus začína na začiatku súboru údajov. Porovnáva prvé dva prvky, a ak je prvý väčší ako druhý, tak ich zamení. Toto robí pre každú dvojicu susedných prvkov až po koniec dátového súboru. Potom začína odznova s prvými dvoma prvkami, až pokiaľ nie je čo zameniť. Tento algoritmus je veľmi neefektívny, a málo použiteľný. Napríklad, ak budeme mať utriediť 100 prvkov, potom celkový počet porovnaní bude 10 000. Mierne lepšia varianta je Shake sort (Coctail sort), ktorý pracuje na princípe Buublesort ale prebublávanie sa deje striedavo smerom zľava doprava (a opačne). Modifikovaný Bubblesort zmenšuje počet porovnaní na 4950 (pri 100 prvkoch)
===Selection sort===
Princíp fungovania je, že sa vyberie z nezotriedenej časti postupnosti prvok s minimálnou hodnotou a vloží sa na koniec zotriedenej časti postupnosti. Na začiatku má zotriedená postupnosť 0 prvkov a nezotriedená má toľko prvokv, koľko je veľkosť poľa.
===Shell sort===
Pracuje podobne ako Selectionsort na princípe výberu. Shellsort vylepšuje vkladanie prvkov zadefinovaním kroku pri porovnávaní prvkov. Viacnásobným prechodom triedeným poľom a zmenšovaním kroku dosahuje lepšie výsledku ako InsertSort. Tento algoritmus je vhodné na zoznamy, ktoré sú skoro utriedené.
===Merge sort===
Merge sort využíva spájanie už zotriedených zoznamov do nového zoznamu, ktorý bude tiež zotriedený. Začína porovnávaním každých dvoch prvkov (tj 1 s 2,potom s 3, potom s 4, ...) a ich vzájomnou zámenou, aby boli zotriedené. Potom sa spojí každý z výsledných zoznamov (zatiaľ dvojprvkových) na štvrprvkový zoznam, a tak ďalej, až pokiaľ nie sú posledné dva zoznamy zlúčené do finálneho usporiadaného zoznamu.
===Heap sort===
Heapsort je efektívnejšia verzia Selectionsort-u. Funguje na výbere najmenšieho/najväčšieho prvku a umiestnením na začiatok/koniec zoznamu. Podobným spôsobom sa pokračuje zo zvyškom zoznamu. Pracuje sa s dátovou štruktúrou [[halda]], čo je špeciálny prípad binárneho stromu.
===Quick sort===
Quicksort je algoritmus typu "rozdeľuj a panuj". Funguje na princípe rozdelenia triedeného poľa vzhľadom na vzťažný prvok (pivot) tak že prvky menšie ako pivot sú naľavo od pivota a prvky väčšie ako pivot sú napravo od pivota. Potom sa algoritmus rekurzívne aplikuje na tieto rozdelenia.

==Odkazy==
* Donald E. Knuth: ''The Art of Computer Programming, Volume 3: Sorting and Searching.'' Second Edition. Reading, Massachusetts: Addison-Wesley, 1998. ISBN 0-201-89685-0
* [http://www.nist.gov/dads/HTML/sort.html Algoritmy řazení ve slovníku algoritmů a datových struktur NIST]
* [http://tjn.fjfi.cvut.cz/~virius/jera/binary/trideni.htm ''Třídění'' ve výukových materiálech k předmětu Základy algoritmizace]
* David R. Martin: Sorting Algorithm Animations - http://www.sorting-algorithms.com
* [http://www.informit.com/store/product.aspx?isbn=0201361205 Algorithms in Java], Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.
<references />

Algoritmy vyhľadávania

2010-03-21T20:39:54Z

Jumanji:

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Cvicenie|Vyhľadávanie (riešené príklady)}}
{{Skripta programovanie}}
__TOC__

'''Vyhľadávanie'''

Vyhľadávanie je základnou úlohou pri práci s väčším objemom dát. Podľa povahy dát (zložitosti, usporiadania, veľkosti) volíme vhodný algoritmus vyhľadávania. Algortimy vyhľadávanie môžeme rozdeliť do niekoľko skupín:
#Sekvenčné vyhľadávanie
#Vyhľadávanie v usporiadaných zoznamoch (resp. poliach)
#Vyhľadávanie v rekurzívnych štruktúrach

=Sekvenčné vyhľadávanie=
==Jednoduché sekvenčné vyhľadávanie==
Princíp tohto vyhľadávania je jednoduchý. Majme pole údajov o dĺžke ''n'', v ktorých budeme hľadať údaj ''x''. Pod pojmom údaj si môžeme ptredstaviť ľubovoľný dátový typ (celé číslo, reálne číslo, štruktúru, smerník na nejaký dátový typ).
Princíp: postupne prechádzame pole od indexu ''0'' až po index ''n-1''. V prípade, ak zistíme zhodu hľadaného prvku s prvkom v poli, tak funkciu ukončíme s úspechom, v opačnom prípade skončíme s výsledkom "prvok sa nenašiel"

'''Dohodnuté návratové hodnoty funkcie:'''

Vyhľadávacia funkcia bude vracať index prvku, ktorý je zhodný s hľadaným prvkom. V prípade neúspechu (hľadaný prvok sa v poli nevyskytuje) vráti funkcia hodnotu -1.

<properties>
Názov funkcie=hladajSekvencne
Návratová hodnota=index nájdeného prvku (-1 pri neúspechu)
Parametre=pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu=O(n)
</properties>

<source lang="c" line>
int hladajSekvencne(int *pole,int dlzka,int x)
{ int i=0;
while( (i<dlzka) && (pole[i]!=x) )
i++;
if(i<dlzka) return i;
else return -1;
}
</source>

Analýza riešenia:
Algoritmus je vhodný pre vyhľadávanie údajov v dátovej štruktúre jednorozmerné pole. Údaje v tomto poli môžu byť neusporiadané.
Podmienka i<dlzka zaručí, že sa bude prehľadávať len v rozsahu poľa ''pole''. Vždy sa začína na indexe i=0; tento index sa postupne zvyšuje (i++), pokiaľ nenarazíme na hľadaný prvok (pole[i]!=x). Podmienka na riadku 5 je tam pre kontrolu prípadu, keď sme prešli celé pole a hľadaný prvok sme nenašli.

Nevýhoda: každý cyklus sa vykonávajú 2 porovnania: i<dlzka a pole[i]!=x

==Jednoduché sekvenčné vyhľadávanie s nárazníkom==
V predchádzajúcom prípade sa v každom cykle robili 2 porovnania. Určitými úpravami dokážeme tieto porovnania znížiť len na 1 porovnanie. Bude to však chcieť drobnú úpravu poľa, v ktorom budeme vyhľadávať. Pole si upravíme tak, že hľadaný prvok sa tam bude vždy vyskytovať. Skutočná veľkosť poľa ''pole'' musí byť teda o jednu položku väčšia ako je počet prvkov v poli. Iba po splnení tejto podmienky môžeme urobiť priradenie, ako je ukázané v riadku 3.
Toto priradenie nazveme '''nárazník'''.

<properties>
Názov funkcie=hladajSekvencneN
Návratová hodnota=index nájdeného prvku (-1 pri neúspechu)
Parametre=pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu=O(n)
</properties>

<source lang="c" line>
int hladajSekvencneN(int *pole, int n, int x)
{
pole[n] = x; // musi byt na to vyhradene miesto!
int i = 0;
while (pole[i] != x)
i++;
if (i < n)
return i;
else
return -1;
}
</source>
Analýza riešenia:
Algoritmus je vhodný pre vyhľadávanie údajov v dátovej štruktúre jednorozmerné pole. Údaje v tomto poli môžu byť neusporiadané.
Priradenie pole[n] = x dovoľuje vynechať kontrolu i<dlzka (funkcia hladajSekvencne). Vieme, že prvok v poli vždy nájdeme, preto stačí na konci urobiť porovnanie (riadok 7), či sme prvok x našli na pozícii menšej ako n (v rozsahu poľa). Ak áno, vrátime hodnotu premennej i, čo je index nájdeného prvku, ak sme hľadaný prvok našli na pozícii n, vrátime hodnotu -1, pretože na pozícii n je náš nárazník.

Poznámka: Touto úpravou sme vylepšili čas, vyhľadávania, ale nie zložitosť algoritmu.

Nasledujúci obrázok ukazuje porovanie časov vyhľadávania doteraz spomínaných algorimnov pri opakovanom vyhľadávaní vo veľkých (cca 1 000 000 položiek) poliach.
<pLines ymin=0 axiscolor=888888 cubic angle=90 plots legend xtitle=pocet_cisel ytitle=cas>
,hladajSekvencne,hladajSekvencneN
10 000, 0.016, 0.015
100 000, 0.235, 0.125
200 000, 0.859, 0.813
300 000, 1.281, 1.234
500 000, 2.156, 2.063
700 000, 3.031, 2.891
1 000 000, 4.328, 4.141
2 000 000, 8.656, 8.375
5 000 000, 21.531, 20.657
10 000 000, 42.422, 41.235
</pLines>

=Vyhľadávanie v usporiadaných zoznamoch=
Zložitosť O(n) pre algorimy lineárneho, resp. sekvenčného vyhľadávania dokážeme znížiť, ak sú údaje v ktorých budeme vyhľadávať usporiadané. V tomto prípade nemusíme pole prvkov v ktorom hľadáme prechádzať celé (od indexu 0 až po n-1), ale stačí si skontrolovať položky len na určitých miestach.

==Binárne vyhľadávanie==
Predpoklad správneho vyhľadávania je, že prvku sú v poli usporiadané. Postup vyhľadávania:
;Použité premenné:
*''pole'' - jednorozmerné pole, v ktorom budeme vyhľadávať
*''x'' - prvok, ktorý hľadáme
*''n'' - veľkosť pola ''pole''.
*''lavy'', ''pravy'' - rozsah poľa, (začiatok , koniec) kde budeme hľadať.

#Rozdeľ pole na 2 polovice. Index stredného prvku vypočítaš ako:
#* stred=(lavy+pravy)/2
#Ak platí lavy>pravy, tak koniec, prvok sa nenašiel.
#Zober prvok v strede poľa (na indexe stred) a porovnaj ho s hľadaným prvkom ''x''
#Ak sa ''x'' zhoduje so stredným prvkom - koniec. Výsledok je index tohto prvku
#V opačnom prípade
#*Ak je ''x'' väčšie ako stredný prvok, tak hľadaj v pravej časti poľa
#**lavy=stred+1, pravy zostava nezmenený (choď na krok 1)
#*Ak je ''x'' menšie ako stredný prvok, tak hľadaj v ľavej časti poľa
#**lavy=zostava nezmenený, pravy = stred-1 (choď na krok 1)

Ukážme si konkrétny príklad (šedé políčka predstavujú indexy poľa, biele sú prvky poľa):
<source lang="c">
x=18
n=10
</source>
{| class="wikitable" border=1 cellpadding=5
|+pole=
|- style="color:green;background-color:#DADADA"
|0 ||1 ||2 ||3 ||4 ||5 ||6 ||7 ||8 ||9 ||10
|-
|1 ||2 ||6 ||18 ||20 ||23 ||29 ||32 ||34 ||39 ||43
|}
Pre implementáciu algoritmu binárneho vyhľadávania si musíme vypočítať hodnoty ľavého a pravého indexu poľa, v ktorom hľadáme. Na začiatok je to jednoduché:
<source lang="c">
lavy=0
pravy=n-1
</source>
*Porovnajme hľadaný prvok x=18 so stredným prvkom:
<source lang="c">
stred=(lavy+pravy)/2
stred=5
</source>
{| class="wikitable" border=1 cellpadding=5
|+pole=
|- style="color:green;background-color:#DADADA"
|0 ||1 ||2 ||3 ||4 ||5 ||6 ||7 ||8 ||9 ||10
|-
|style="background-color:yellow" |1
|style="background-color:yellow" |2
|style="background-color:yellow" |6
|style="background-color:yellow" |18
|style="background-color:yellow" |20
|style="font-weight:800" | 23
|style="background-color:gray" |29
|style="background-color:gray"|32
|style="background-color:gray"|34
|style="background-color:gray"|39
|style="background-color:gray"|43
|}
* pole[5] != x (23 != 18 )
** platí že x<23 (resp. x<pole[stred])
** budeme vyhľadávať vľavo (žltá časť)
*** lavy zostane nezmeneny (0)
*** pravy=stred - 1 (4)

*Porovnajme hľadaný prvok x=18 so stredným prvkom:
<source lang="c">
stred=(lavy+pravy)/2 = (0+4)/2=2
stred=2
</source>
{| class="wikitable" border=1 cellpadding=5
|+pole=
|- style="color:green;background-color:#DADADA"
|0 ||1 ||2 ||3 ||4 ||5 ||6 ||7 ||8 ||9 ||10
|-
|style="background-color:gray" |1
|style="background-color:gray" |2
|style="font-weight:800" |6
|style="background-color:yellow" |18
|style="background-color:yellow" |20
|style="background-color:gray" | 23
|style="background-color:gray" |29
|style="background-color:gray"|32
|style="background-color:gray"|34
|style="background-color:gray"|39
|style="background-color:gray"|43
|}
* pole[2] != x (6 != 18 )
** platí že x>6 (resp. x>pole[stred])
** budeme vyhľadávať vpravo (žltá časť)
*** lavy = stred + 1 (3)
*** pravy zostane nezmeneny (4)

*Porovnajme hľadaný prvok x=18 so stredným prvkom:
<source lang="c">
stred=(lavy+pravy)/2 = (3+4)/2=3
stred=3
</source>
* pole[3] == x (18 = 18 )
*Stredný prvok je zhodný s hľadaným
*Algoritmus končí
**Výsledok je index nájdeného prvku, teda ''stred''. V našom príklade je to 3.

===Binárne vyhľadávanie - zdrojový kód v jazyku C===
<properties>
Názov funkcie=hladajBinarne hladajBinarneR
Návratová hodnota=index nájdeného prvku (-1 pri neúspechu)
Parametre=pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu=O(Log(n))
</properties>

Keďže samotné definícia binárneho vyhľadávania je rekurzívna, uvádzame aj rekurzívnu verziu funkcie.

{| class=wikitable border=1 cellpadding=5
|+ Binárne vyhľadávanie - jazyk C
|-
! Iteračná verzia
! Rekurzívna verzia
|-
|
<source lang="c">
int hladajBinarne(int *pole,int dlzka, int x)
{ int najdene=0;
int lavy = 0, pravy = dlzka - 1, stred;
while ( (lavy <= pravy) && (najdene==0) )
{
stred = (lavy + pravy) / 2;
if (pole[stred] == x)
najdene=1;
else
if (pole[stred] < x)
lavy = stred + 1;
else
pravy=stred - 1;
}
if(najdene==1)
return stred;
else
return -1;
}

</source>
|
<source lang="c">
int hladajBinarneR(int *pole,int lavy, int pravy, int x)
{ if(lavy>pravy)
return -1;
else
{
int stred=(lavy+pravy)/2;
if(pole[stred]==x)
return stred;
else
{ if( x<pole[stred] )
return hladajB(pole,lavy,stred-1,x);
else
return hladajB(pole,stred+1,pravy,x);
}
}
}

</source>
|}

==Ternárne vyhľadávanie==
Predpoklad správneho vyhľadávania je, že prvku sú v poli usporiadané. Postup vyhľadávania je podobný ako pri binárnom vyhľadávaním abšak pole nerozdelíme na polovicu ale na tretiny.

;Použité premenné:
*''pole'' - jednorozmerné pole, v ktorom budeme vyhľadávať
*''x'' - prvok, ktorý hľadáme
*''n'' - veľkosť pola ''pole''.
*''i'', ''j'' - rozsah poľa, (začiatok , koniec) kde budeme hľadať.
*''m1'' - index prvku v prvej tretine
*''m2'' - index prvku v druhej tretine

#Rozdeľ pole na tretiny
##m1=( i*2 + j ) / 3;
##m2=( i + j*2 ) / 3;
#Porovnaj, či sa hľadaný prvok zhoduje z prvkom na indexe m1, ak áno, tak koniec. Výsledok je index m1
#Porovnaj, či sa hľadaný prvok zhoduje z prvkom na indexe m2, ak áno, tak koniec. Výsledok je index m2
#Ak platí i>j, skonči, prvok x sa v poli nenachádza.
#Ak je hľadaný prvok menší ako prvok pole[m1], tak hľadaj v prvej tretine poľa
#* i zostáva nezmenené , j=m1-1. Choď na krok 1.
#Ak je hľadaný prvok väčší ako prvok pole[m2], tak hľadaj v tretej tretine poľa
#* i = m2+1 , j zostáva nezmenené. Choď na krok 1.
#inak hľadaj v druhej tretine poľa
#* i = m1+1 , j=m2-+. Choď na krok 1.

Uveďme príklad: V prechádzajúcom príklade hľadajme číslo x=39

Na začiatku máme:
<source lang="c">
i=0
j=10
</source>
Vypočítame m1, m2
<source lang="c">
m1=( i*2 + j ) / 3 = (0+10)/3 = 3
m2=( i + j*2 ) / 3 = (0+20)/3 = 6
</source>
{| class="wikitable" border=1 cellpadding=5
|+pole=
|- style="color:green;background-color:#DADADA"
|0 ||1 ||2 ||m1=3 ||4 ||5 ||m2=6 ||7 ||8 ||9 ||10
|-
|style="background-color:gray" |1
|style="background-color:gray" |2
|style="background-color:gray" |6
|style="font-weight:800" |18
|style="background-color:gray" |20
|style="background-color:gray"| 23
|style="font-weight:800" |29
|style="background-color:yellow"|32
|style="background-color:yellow"|34
|style="background-color:yellow"|39
|style="background-color:yellow"|43
|}

Teraz hľadáme v tretej tretine poľa:
<source lang="c">
i=m2+1=7
j=10
</source>
Vypočítame m1, m2
<source lang="c">
m1=( i*2 + j ) / 3 = (14+10)/3 =8
m2=( i + j*2 ) / 3 = (7+20)/3 = 9
</source>

{| class="wikitable" border=1 cellpadding=5
|+pole=
|- style="color:green;background-color:#DADADA"
|0 ||1 ||2 ||3 ||4 ||5 ||6 ||7 ||m1=8 ||m2=9 ||10
|-
|style="background-color:gray" |1
|style="background-color:gray" |2
|style="background-color:gray" |6
|style="background-color:gray" |18
|style="background-color:gray" |20
|style="background-color:gray"| 23
|style="background-color:gray" |29
|style="background-color:gray"|32
|style="font-weight:800"|34
|style="font-weight:800"|39
|style="background-color:gray"|43
|}

Platí, že x=pole[m2]. Výsledkom bude teda hodnota m2 (index nájdeného prvku v poli)
===Ternárne vyhľadávanie - zdrojový kód v C===
<properties>
Názov funkcie=hladajTernarne
Návratová hodnota=index nájdeného prvku (-1 pri neúspechu)
Parametre=pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu=O(Log n)
</properties>

<source lang="c">
int hladajTernarne(int pole[],int i,int j,int x) {
int m1,m2;
m1=( i*2 + j ) / 3;
m2=( i + j*2 ) / 3;
if(x==pole[m1])
return m1;
if(x==pole[m2])
return m2;
if(i>j) return -1; // prvok sa nenašiel
if(x<pole[m1]) // hľadaj v prvej tretine
return(hladajTernarne(pole, i,m1-1,x));
if(x>pole[m2]) // hľadaj v druhej tretine
return(hladajTernarne(pole, m2+1,j,x));
else // hľadaj v tretej tretine
return(hladajTernarne(pole, m1+1,m2-1,x));
}
</source>

===Porovnanie binárneho a ternárneho vyhľadávania===
;Provnávané varianty:rekurzívne verzie funkcií
;Spôsov porovnávania: Veľkosť poľa v ktorom hľadáme - n (os x grafu) 
:Počet hľadaných čísel - 1000 
:Počet opakovaní každého hľadania - 1000

<pLines ymin=0 axiscolor=888888 cubic angle=90 plots legend xtitle=pocet_cisel ytitle=cas_[s]>
,binarne,ternarne
1 000, 2.115, 2.094
5 000, 2.537, 2.513
10 000, 2.674, 2.622
50 000, 3.028, 3.005
100 000, 3.252, 3.032
500 000, 3.642, 3.358
1 000 000, 3.719, 3.471
5 000 000, 4.129, 3.771
10 000 000, 4.410, 3.963
50 000 000, 5.679, 4.304
100 000 000, 5.806, 5.248
</pLines>

=Vyhľadávanie v rekurzívnych štruktúrach=
Ďalším špeciálnym typom vyhľadávania je vyhľadávanie v rekurzívne definovaných štruktúrach. Medzi tieto štruktúry patria [[Strom_Dátová štruktúra|stromy]], konkrétne [[Binárny strom]] alebo [[B-strom]]. V týchto štruktúrach sa nedá implementovať lineárne vyhľadávanie ani binárne (resp. ternárane) vyhľadávanie, pretože samotná štruktúra takéhoto dátového typu to nedovoľuje.
==Vyhľadávanie v binárnych stromoch==
Najjednoduchšia forma stromu je binárny strom. Binárny strom je stromová dátová štruktúra, v ktorej každý uzol má najviac dvoch potomkov. Binárny strom sa skladá z
# koreňového uzla
# ľavý a pravý podstrom.
#*Oba podstromy sú taktiež binárne stromy.
[[Súbor:binStrom.png|frame|right|Binárny strom]]
Uzly na najnižšej úrovni stromu (2, 5, 11, 4) sa nazývajú ''listy''.
Vlastnosťou binárneho stromu je to, že údaje v ňom sú vždy usporiadané nasledovným spôsobom:
* naľavo od uzla sú tie prvky, ktoré majú hodnotu menšiu ako tohoto uzla
* napravo od uzla sú tie prvky, ktoré majú hodnotu väčšiu ako tohoto uzla

Pri tomto predpoklade môžeme sformulovať vyhľadávací algoritmus pre binárne stromy:

Budeme hľadať v binárnom strome, ktorý si označme ''bstrom''. Tento každý uzol stromu môže mať žiadneho, jedného alebo dvoch potomkov. Potomkov budeme značiť ''ľavý'' a ''pravý''. V strome ''bstrom'' budeme hľadať prvok ''x''.

#Označ si koreň stromu v ktorom budeme hľadať ako ''uzol''.
#Porovnaj hodnotu uzla ''uzol'' s hľadaným prvkom ''x''.
#Ak sa tieto hodnoty zhodujú - koniec. Našli sme prvok ''x''.
#Ak aktuálny ''uzol'' nemá potomkov, tak koniec - Nenašli sme prvok ''x''.
#Ak je hodnota ''x'' menšia ako hodnota uzla ''uzol'', tak označ si ako ''uzol'' potomka ''ľavý''. Choď na krok 1.
#Ak je hodnota ''x'' menšia ako hodnota uzla ''uzol'', tak označ si ako ''uzol'' potomka ''pravý''. Choď na krok 1.

Pseudokód algoritmu vyhľadávania:
<source lang="text">
hľadaj(strom, x)
uzol <- vrhol stromu strom
ak je uzol list
koniec - x sme nenašli
ak je hodnota uzla == x tak
koniec - vráť hodnotu x
ak je hodnota uzla < x tak
hľadaj(uzol->lavy,x)
ak je hodnota uzla > x tak
hľadaj(uzol->pravy,x)
</source>
značenie uzol->lavy, resp. uzol->pravy má význam, že ďalej budeme pracovať len s ľavou, resp. pravou časťou binárneho stromu.

===Implementácia v jazyku C===
Definícia binárneho stromu je v kapitole [[Binárny strom]]. Pre správne pochopenie nasledujúcej časti je potrebné vedieť pracovať s binárnym stromom.

Definujme dátovú štruktúru binárny strom:
<source lang="c">
struct TUzol
{ int data;
TUzol *lavy,*pravy;
};
</source>

<properties>
Názov funkcie=hladajRekurzivneStrom
Návratová hodnota=smerník na nájdený prvok (v prípade neúspechu NULL)
Parametre=binárny strom - strom hľadaný prvok - x
Zložitosť algoritmu=O(n)
</properties>

<source lang="c">
TUzol* hladajRekurzivneStrom(TUzol *s, int x)
{
if(s==NULL) return NULL;
if(s->data == x ) return s;
if(x < s->data) return hladajRekurzivneStrom(s->lavy);
if(x > s->data) return hladajRekurzivneStrom(s->pravy);

}
</source>
http://www.cs.auckland.ac.nz/software/AlgAnim/trees.html

=HASH funkcie=

=Odkazy=
* http://en.wikipedia.org/wiki/Linear_search
* http://en.wikipedia.org/wiki/Binary_search
* http://en.wikipedia.org/wiki/Ternary_search
* http://www.dcc.uchile.cl/~rbaeza/handbook/search_a.html
* http://www.cs.auckland.ac.nz/software/AlgAnim/searching.html