hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
|
mgr-szz:in-gra:11-gra [2016/06/05 10:13] haf [Zadání] |
mgr-szz:in-gra:11-gra [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Zadání | + | ====== Zadání ====== |
| - | ====== | + | |
| Datové struktury pro prostorové vyhledávání. Vyhledávání podle rozsahů, multidimenzionální binární stromy, stromy úseček. | Datové struktury pro prostorové vyhledávání. Vyhledávání podle rozsahů, multidimenzionální binární stromy, stromy úseček. | ||
| Řádek 8: | Řádek 7: | ||
| Pozn.: některé matematické základy poskytují poznámky z předmětu Geometrické algoritmy (viz Použité zdroje). | Pozn.: některé matematické základy poskytují poznámky z předmětu Geometrické algoritmy (viz Použité zdroje). | ||
| - | ====== | + | ====== Datové struktury pro prostorové vyhledávání ====== |
| - | uktury pro prostorové vyhledávání ====== | + | |
| ===== Příklady elementárních úloh ===== | ===== Příklady elementárních úloh ===== | ||
| * Lokalizace bodu v 2-3D prostoru - hledání objektu, kterému patří daný bod | * Lokalizace bodu v 2-3D prostoru - hledání objektu, kterému patří daný bod | ||
| Řádek 81: | Řádek 79: | ||
| {{:mgr-szz:in-gra:11_html_m4c5acfe4.jpg|}} | {{:mgr-szz:in-gra:11_html_m4c5acfe4.jpg|}} | ||
| Vyhledávání rozsahů (regionů) probíhá nejprve podle první souřadnice, při nalezení správného rozsahu (který obsahuje list v), pokračuje postupně podle dalších souřadnic, jejichž stromy jsou uloženy asociovaně k uzlu v. | Vyhledávání rozsahů (regionů) probíhá nejprve podle první souřadnice, při nalezení správného rozsahu (který obsahuje list v), pokračuje postupně podle dalších souřadnic, jejichž stromy jsou uloženy asociovaně k uzlu v. | ||
| - | |||
| - | ====== Metoda přímého přístupu ====== | ||
| - | //Není mi zřejmé, co přesně je zde myšleno. Vzhledem k tomu, že tato část otázky byla vypuštěna pro státnice od r. 2014, snad to ani není moc důležité. V knize Moderní počítačová grafika ani ve slajdech k předmětu Počítačová grafika není k tomuto tématu nic uvedeno. Snad toto. Popisuje obecná data, ale lze si představit i jako strukturu pro popis scény objektů.// | ||
| - | |||
| - | ===== Přímý přístup k datům ===== | ||
| - | Pod přímým přístupem k datům se rozumí přímé čtení záznamu ze známé adresy. V těchto metodách se každý požadovaný záznam se přečte hned napoprvé. Metody přímého přístupu k datům evidentně vyžadují znalost adresy pro každý záznam. To neznamená, že v každém okamžiku jsou známy adresy všech záznamů najednou. Znamená to, že v okamžiku potřeby daného záznamu existuje možnost adresu zjistit. U těchto metod se obdobně jako u metod sériového hledání předpokládá existence klíče a vzestupné nebo sestupné uspořádání jeho hodnot. | ||
| - | |||
| - | ==== Přímé adresování ==== | ||
| - | Při metodě přímého adresování je adresou přímo klíč nebo jeho lineární transformace. Metoda přímého adresování je vhodná v případě, že | ||
| - | |||
| - | * klíč je numerický | ||
| - | * ke každé hodnotě klíče z nějakého uzavřeného intervalu existuje záznam | ||
| - | * délka záznamu je u všech záznamů stejná | ||
| - | |||
| - | **Příklad**: Nechť každý z 13 vrtů v terénu má číselný kód od 1 do 13 (vrty jsou tedy "očíslovány"). Nechť délka záznamu obsahující údaje o každém vrtu je 67. Klíčem vrtu je jeho číslo -v- a z něj lze odvodit adresu záznamu výrazem A = (v-1) * 67. | ||
| - | |||
| - | ==== Nepřímé adresování ==== | ||
| - | Nejčastěji však data v souborech nesplňují ani přibližně požadavky odůvodňující přímé adresování. Je to např. tehdy, když | ||
| - | |||
| - | * posloupnost klíčů ani teoreticky neobsahuje všechny hodnoty jediného uzavřeného intervalu, ale mezi hodnotami jsou "velké mezery". | ||
| - | * klíč je koncipován tak, že teoreticky umožňuje použít všechny hodnoty z nějakého uzavřeného intervalu, ale je známo, že všech skutečných záznamů bude mnohem méně. | ||
| - | * klíčem je výraz jiného typu než numerického a nemůže tedy být přímo použit k adresování. | ||
| - | |||
| - | V uvedených a podobných případech je nutno mít k disposici funkci, která transformuje hodnotu klíče na adresu. Adresa není tedy určena přímo, ale zprostředkovaně klíčem; proto se tyto metody nazývají metody nepřímého adresování, a protože používají (již při výkladu metod zápisu zmíněnou) Hash - funkci, nazývají se také Hash - metodami. | ||
| - | |||
| - | Zpravidla není možno sestrojit funkci A = A (k) tak, aby to bylo prosté zobrazení (celé) množiny klíčů na rovnoměrně rozložené adresy v množině použitelných adres. Na druhé straně by funkce A neměla být (z časových důvodů při jejím vyhodnocování) příliš složitá. Proto se užívají takové funkce, které některé adresy ponechávají neobsazené a jiné adresy jsou obrazem většího počtu klíčů. | ||
| ===== Hledání v datech s indexy ===== | ===== Hledání v datech s indexy ===== | ||
