Topološka analiza podatkov

Uspešno opravljene domače naloge in seminarsko-projektne naloge so pogoj za opravljanje izpita.

Topologija je področje matematike, ki se ukvarja z analizo oblik in več dimenzionalnih objektov. Topološka analiza podatkov pa je področje med topologijo in računalništvom, ki obravnava in analizira lastnosti oblik zajetih iz podatkov, slik in več dimenzionalnih podatkovnih množic. Ob množici podatkov, ki se neprestano zajemajo, na eni strani in pa vse bolj zmogljivimi računalnškimi sistemi na drugi se razvija tudi vrsta novih algoritmov za analizo in predstavitev, ki uporabljajo čedalje več topoloških pojmov in modelov. Za predstavitev podatkov se uporabljajo grafi in ploskve, triangulacije, simplicialni in celični kompleksi ter mnogoterosti. Za analizo podatkov pa se uporabljajo topološke invariante teh objektov kot so število komponent, fundamentalna grupa, homološke grupe in kohomološki kolobar, Morsova teorija, filtracije in vztrajnost. Takšne invariante se tipično lepo izračunajo in dajejo odgovore na vprašanja kot so, ali je objekt sestavljen iz enega li več kosov, ali ima kakšne luknje in tunele, kakšne značilnosti ima pri različnih resolucijah, kako so posamezni kosi zlepljeni skupaj v celoto... Na drugi strani je na voljo tudi čedalje več hitrih in učinkovitih algoritmov za njihovo računanje.
Pri predmetu bodo predstavljeni osnovni topološki pojmi in modeli, ki se uporabljajo za predstavitev večdimenzionalnih objektov in prostorov, nekaj njihovih osnovnih številskih in algebraičnih invariant. Poudarek pa bo na uporabi teh modelov in invariant pri analizi in rekonstrukciji objektov iz zajetih podatkov, konfiguracijskih prostorov robotov in mehaničnih sistemov, pri analizi omrežij in v drugih povsem uporabnih domenah. Posamezna teme, ki jih bomo obravnavali, so
Osnovni pojmi topoloških in metričnih prostorov;
Grafi in ploskve;
Triangulacije, simplicialni in celični kompleksi;
Homološke grupe in Bettijeva števila, njihova interpretacija in osnovni algoritmi za njihovo računanje;
Diskretne Morsove funkcije in njihova uporaba pri analizi podatkov;
Filtracije in vztrajnost za analizo podatkov pri različnih resolucijah.
Pri predmetu bo poudarek predvsem na uporabi opisanih topoloških pojmov in algoritmov pri analizi konkretnih podatkovnih množic, problemov in modelov.

Herbert Edelsbrunner, John Harer: Computational Topology, American Mathematical Society, 2010
Afra J. Zomorodian: Topology for Computing, Cambridge University Press, 2005
Hjelle, Øyvind, Dæhlen, Morten: Triangulations and applications, Springer, 2006
Kevin Knudson: Morse theory, smooth and discrete, World Scientific, 2015

Cilj predmeta je študentom na razumljiv način predstaviti osnovne pojme algebraične topologije, ki se uporabljajo v računalniških algoritmih pri analizi velikih množic večdimenzionalnih podatkov, pri rekonstrukciji objektov in konfiguracijskih prostorov robotov in mehaničnih sistemov in pri drugih realnih problmemih. Matematični pojmi bodo predstavljni predvsem z uporabnega zornega kota, poudarek bo na konkretnih primerih in računalniških algoritmih.

Po uspešno opravljenem predmetu bo študent:
razumel pojem topološke invariante in njenega pomena pri analizi oblike in drugih lastnosti podatkov;
razumel pojem simplicialnega kompleksa in poznal osnovne algoritme za konstrukcijo simplicialnih
kompleksov na danih podatkih;
poznal osnovne računske prijeme in algoritme za računanje Eulerjeve karakteristike, homoloških grup in Bettijevih števil;
razumel pojem filtracije in vztrajnosti;
znal pridobljeno znanje uporabiti za konstrukcijo preprostih topoloških algoritmov za analizo podatkovnih množic in rezultate interpretirati.

Predavanja s podporo avdio-vizualne opreme,
predstavitev teoretičnih pojmov in prikaz pomena na konkretnih primerih,
laboratorijske vaje v računalniški učilnici z ustrezno programsko opremo. Delo posamezno in v skupinah. Velik poudarek na praktičnem delu in na skupinskem reševanju praktičnih problemov.

Način (pisni izpit, ustno izpraševanje, naloge, projekt):
Sprotno preverjanje (domače naloge, kolokviji in projektno delo)
Končno preverjanje (pisni in ustni izpit)
Ocene: 6-10 pozitivno, 5 negativno
(v skladu s Statutom UL)

VIRK, Žiga. Small loop spaces. Topology and its Applications, ISSN 0166-8641, 2010, vol. 157, no. 2, str. 451-455.

VIRK, Žiga. Realizations of countable groups as fundamental groups of compacta. Mediterranean journal of mathematics, 2013, vol. 10, no. 3, str. 1573-1589.

DYDAK, Jerzy, VIRK, Žiga. Preserving coarse properties. Revista matemática complutense, 2016, vol. 29, iss. 1, str. 191-206.

EDELSBRUNNER, Herbert, VIRK, Žiga, WAGNER, Hubert. Smallest enclosing spheres and Chernoff points in Bregman geometry. V: SPECKMANN, Bettina (ur.), TÓTH, Csaba D. (ur.). 34th International Symposium on Computational Geometry : SoCG 2018, June 11-14, 2018, Budapest, Hungary,

VIRK, Žiga. Approximations of 1-dimensional intrinsic persistence of geodesic spaces and their stability. Revista matemática complutense, Jan. 2019, vol. 32, iss. 1, str. 195-213.