Računanje enodimenzionalne vztrajne homologije v geodezični metriki : magistrsko delo

Čufar, Matija (avtor), Virk, Žiga (mentor)

V nalogi je predstavljen algoritem za računanje enodimenzionalne vztrajne homologije v geodezični metriki. Uporaba geodezične metrike nam omogoča, da iz točkastih podatkov ocenimo najkrajšo bazo prve homološke grupe prostora iz katerega smo točke vzorčili. V nalogi najprej predstavimo teoretično ozadje enodimenzionalne vztrajne homologije na geodezičnih prostorih. Izkaže se, da so kritične vrednosti vztrajne homologije povezane s sklenjenimi geodetkami, ki predstavljajo najkrajšo bazo prve homološke grupe geodezičnega prostora. V drugem delu naloge z uporabe predstavljene teorije predstavimo lasten algoritem in ga analiziramo. Na koncu predstavimo še rezultate, ki smo jih dobimi z implementacijo algoritma v programskem jeziku Julia. Za izdelavo rezultatov smo uporabili nekaj sintetičnih množic podatkov in eno, večjo, množico podatkov iz realnega sveta.

• Jezik: Slovenski jezik
• Ključne besede: Računska topologija, topološka analiza podatkov, algoritmi, homologija, vztrajna homologija.
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko ; FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2020
• PID: 20.500.12556/RUL-114071
• UDK: 515.1
• COBISS.SI-ID: 18913881
• Datum objave v RUL: 12.02.2020

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Computing one-dimensional persistent homology in a geodesic metric

Izvleček

In this thesis, we present an algorithm that computes the one-dimensional persistent homology in a geodesic metric. The use of a geodesic metric allows us to approximate the shortest homology basis of the underlying space. First, we present the theoretical background of one-dimensional persistent homology of geodesic spaces. The main result of this section is the connection between the critical points of persistent homology and geodesic loops in the space, which form the shortest basis of the first homology group. Next, we present a new algorithm based on the theory. This algorithm approximates the shortest basis of the first homology group. Finally, we present some results that were computed using our implementation of the algorithm in the Julia programming language. We test the algorithm on a few synthetic data set and one, larger, more realistic data set.

• Ključne besede: Computational toplogy, topological data analysis, algorithms, homology, persistent homology.