Računanje enodimenzionalne vztrajne homologije v geodezični metriki

magistrsko delo

Matija Čufar (Avtor), Žiga Virk (Mentor)

Povzetek

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.

Ključne besede

matematika;računska topologija;topološka analiza podatkov;algoritmi;homologija;vztrajna homologija;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[M. Čufar]
UDK:	515.16
COBISS:	18913881
Št. ogledov:	39702
Št. prenosov:	279
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Computing one-dimensional persistent homology in a geodesic metric
Sekundarni povzetek:	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.
Sekundarne ključne besede:	computational topology;topological data analysis;algorithms;homology;persistent homology;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Študijski program:	0
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Strani:	53 str.
ID:	11406156