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 [2014/10/27 09:07] 127.0.0.1 upraveno mimo DokuWiki |
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. | ||
+ | (Staré znenie:) | ||
Datové struktury pro prostorové vyhledávání. Vyhledávání podle rozsahů, multidimenzionální binární stromy,metoda přímého přístupu, stromy úseček. Sjednocení a průniky obdélníků. | Datové struktury pro prostorové vyhledávání. Vyhledávání podle rozsahů, multidimenzionální binární stromy,metoda přímého přístupu, stromy úseček. Sjednocení a průniky obdélníků. | ||
Řádek 77: | Řá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 ===== |