Rozdíly

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

--- pitel:isz:vyhledavani_razeni [16. 09. 2013, 07.35:33] – [Řazení] link pitel
+++ pitel:isz:vyhledavani_razeni [30. 12. 2022, 13.43:01] (aktuální) – upraveno mimo DokuWiki 127.0.0.1
@@ Řá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ů

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku