izpis_h1_title_alt

Iskanje najnižjega skupnega prednika vozlišč v drevesu
ID Jerše, Jakob (Avtor), ID Hočevar, Tomaž (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (1,87 MB)
MD5: A593CDC8828284A5FAF18AC679D4AF98

Izvleček
Iskanje najnižjega skupnega prednika (angl. lowest common ancestor) vozlišč v drevesu je klasičen problem na področju algoritmov in podatkovnih struktur. Cilj naloge je bil raziskati, implementirati in opisati različne pristope, ki se uporabljajo za reševanje tega problema. Najboljša rešitev, ki je predstavljena, ima linearno časovno zahtevnost predprocesiranja O(N) in konstantno časovno zahtevnost odgovarjanja na poizvedbe O(1). To doseže s prevedbo problema iskanja najnižjega skupnega prednika na problem iskanja najmanjše vrednosti na intervalu. Vsi implementirani algoritmi so eksperimentalno ovrednoteni na izbranih testnih podatkih. Prav tako so podane primerjave časovnih in prostorskih zahtevnosti teh algoritmov.

Jezik:Slovenski jezik
Ključne besede:najnižji skupni prednik, drevesni algoritmi, podatkovne strukture, časovna zahtevnost, predprocesiranje, poizvedba, iskanje najmanjše vrednosti na intervalu.
Vrsta gradiva:Diplomsko delo/naloga
Tipologija:2.11 - Diplomsko delo
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2024
PID:20.500.12556/RUL-155813 Povezava se odpre v novem oknu
COBISS.SI-ID:189012483 Povezava se odpre v novem oknu
Datum objave v RUL:19.04.2024
Število ogledov:129
Število prenosov:98
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Finding the lowest common ancestor of nodes in a tree
Izvleček:
Finding the lowest common ancestor (LCA) of nodes in a tree is a classic problem in the field of algorithms and data structures. The goal of the thesis was to explore, implement, and describe various approaches used to solve this problem. The best solution that is presented has linear preprocessing time complexity O(N) and constant query answering time complexity O(1) achieved by reducing the lowest common ancestor problem to finding the minimum value in an interval. All implemented algorithms are experimentally evaluated on selected test data. Additionally, comparisons of the time and space complexities of these algorithms are provided.

Ključne besede:lowest common ancestor, tree algorithms, data structures, time complexity, preprocessing, query, range minimum query.

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj