Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:vyhledavani_razeni

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revize Předchozí verze
pitel:isz:vyhledavani_razeni [16. 09. 2013, 09.34:50]
pitel [Knuth-Morris-Pratt] obrazky
pitel:isz:vyhledavani_razeni [16. 09. 2013, 09.35:33] (aktuální)
pitel [Řazení] link
Řádek 1: Řádek 1:
 +====== Vyhledávání a řazení ======
 +====== Vyhledávání ======
 +Nejdůležitějším parametrem je **přístupová doba**, tedy doba potřebná k nalezení požadované informace. Přesněji je možné uvádět: "​[Minimální|Maximální|Průměrná] doba (ne)úspěšného vyhledání."​
  
 +===== Sekvenční vyhledávání v poli =====
 +Po jednom prvku procházíme pole((neseřazené)) a kontrolujeme jestli se aktuální prvek shoduje s hledaným. Pokud je index prvku roven délce pole a ani tak jsme nenašli, je vyhledání neúspěšné.
 +
 +  * Minimální čas úspěšného vyhledání = 1 (hledaný byl hned první prvek)
 +  * Maximální čas úspěšného vyhledání = N((délka pole)) (hledný prvek byl až na posledním místě)
 +  * Průměrný čas úspěšného vyhledání = N/2
 +  * Čas neúspěšného vyhledání = N
 +
 +Algoritmus je možné vylepšit tzv. zarážkou, která se přidá na konec pole. Pak samozřejmě vždy najdeme požadovaný prvek, a úspěch se pozná podle indexu prvku.
 +
 +Dobrým vylepšením je v případě nalezení prvku tento prvek prohodit s jeho sousedem. Takto se často hledané prvky dostanou na začátek pole a budou tak nalézány dříve.
 +
 +Pokud pole seřadíme, můžeme dříve detekovat nenalezení prvku.
 +
 +===== Binární vyhledávání =====
 +[[wp>​Binary search algorithm]]
 +
 +Pracuje nad seřazeným polem a funguje na principu půlení intervalu.
 +
 +<code pascal>
 +{Nastavení zarážek}
 +min := 1; {Pascal indexuje pole od 1}
 +max := N; {N je velikost pole A}
 +
 +repeat
 +  mid := (min + max) div 2;        {Najdi prostřední prvek}
 +  if x > A[mid] then               ​{Pokud je hledaný prvek větší než prostřední}
 +    min := mid + 1                 ​{Zpracujeme dále část pole která je větší než prostřední}
 +  else 
 +    max := mid - 1;                {V opačném případě zpracujeme část menší než prostřední}
 +until (A[mid] = x) or (min > max); {Tohle opakujeme dokud prostřední prvek není tím hledaným nebo dokud není jak rozsah zmenšovat}
 +</​code>​
 +
 +Tato metoda má **logaritmickou složitost**.
 +==== Binární vyhledávací strom ====
 +[[wp>​Binary search tree]]
 +
 +Je to stromová datová struktura, kde každý uzel má nejvíce 2 potomky((proto binární)) a přitom levý potomek je menší a pravý je větší než rodičovský.
 +
 +Vše potřebné je na výše uvedené Wikipedii.
 +
 +===== Hashovací tabulky =====
 +[[wp>​Hash table]]
 +
 +FIXME
 +
 +==== Mapovací funkce ====
 +[[wp>​Hash function]]
 +
 +Je to funkce, která se provede nad daty která chceme do tabulky přidat, nebo vyhledat, a podle ní se rozhodne ke kterému řádku tabulky přistoupíme.
 +
 +Funkce musí být:
 +  * Rychlá
 +  * Způsobovat co nejméně kolizí (jinými slovy, musí vytvářet co možná nejunikátnější hashe)
 +
 +===== Prohledávání textu =====
 +[[wp>​String searching algorithm]]
 +
 +==== Knuth-Morris-Pratt ====
 +[[wp>​Knuth–Morris–Pratt algorithm]]
 +
 +Ke své práci využívá konečný automat. Následující ukázka demonstruje automat pro hledaný vzorek //AABC// při použití abecedy {A,B,C}.
 +
 +{{pitel:​isz:​kmp_alg.png|}}
 +
 +Nevýhodou takového řešení je skutečnost,​ že z každého uzlu vychází tolik hran, kolik je znaků abecedy. Lze vyjádřit i pomocí dvou hran - ANO(souhlas,​ Y), NE (nesouhlas, N). Vzorek ABABCB pro libolovolnou abeceny obsahující alespoň znaky A a B. 
 +
 +{{pitel:​isz:​kmp_2hrany.png|}} ​
 +
 +==== Boyer-Moor ====
 +[[wp>​Boyer–Moore string search algorithm]]
 +
 +Viz opora IAL strana 174
 +
 +====== Řazení ======
 +  * [[wp>​Sorting algorithm]]
 +  * [[http://​www.sorting-algorithms.com|Sorting Algorithm Animations]]
 +  * [[pitel:​ial:​tahak#​razeni|Tabulka s vlastnostmi]]
 +====== Shrnutí ======
 +  * vyhledávání:​ sekvenční v poli, v binárním vyhledávacím stromu, přes hash funkci a tabulku (tabulka rozptýlených hodnot)
 +  * prohledávání textu: naivní metoda, knuth-morris-pratt (konečný automat), boyer-moore (2 tabulky, porovnává se hledané slovo odzadu)
 +  * řazení: bubble, insertion, select, merge, heap, quick
 +  * Znát složitosti algoritmů
/var/www/wiki/data/pages/pitel/isz/vyhledavani_razeni.txt · Poslední úprava: 16. 09. 2013, 09.35:33 autor: pitel