Računanje enodimenzionalne vztrajne homologije v geodezični metriki

magistrsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.09 - Master's Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[M. Čufar]
UDC:	515.16
COBISS:	18913881
Views:	39702
Downloads:	279
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Computing one-dimensional persistent homology in a geodesic metric
Secondary abstract:	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.
Secondary keywords:	computational topology;topological data analysis;algorithms;homology;persistent homology;
Type (COBISS):	Master's thesis/paper
Study programme:	0
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Pages:	53 str.
ID:	11406156