Naslov Izračunljivost poopćenih grafova Naslov (engleski) Computability of generalized graphs Autor Matea Jelić Mentor Zvonko Iljazović (mentor)Član povjerenstva Marko Horvat (predsjednik povjerenstva)Član povjerenstva Goran Erceg (član povjerenstva)Član povjerenstva Zvonko Iljazović (član povjerenstva)Član povjerenstva Vedran Čačić (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2023-12-07, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Univerzalna decimalna klasifikacijaUDC ) 51 - Matematika Sažetak U izračunljivom topološkom prostoru, svaki izračunljiv skup je ujedno i poluizračunljiv, ali obrat općenito ne vrijedi. Zato u ovom radu prvo proučavamo uvjete uz koje je spomenuti obrat istinit. Pri tome će topološka svojstva skupa biti od izrazite važnosti, što znači da ova disertacija spada u područje izračunljive analize, ali i topologije. Kasnije, proučavamo i uvjete uz koje se poluizračunljiv skup, budući da općenito nije izračunljiv, može aproksimirati nekim svojim izračunljivim podskupom do na zadanu točnost. Prvo se bavimo lančastim i cirkularno lančastim kontinuumima i njihovim utjecajem na izračunljive skupove. Točnije, pokazujemo da je poluizračunljiv skup T u nekom izračunljivom topološkom prostoru i izračunljiv ako je \(T = S \cup K_0 \cup \dots \cup K_n\), gdje je \(S\) izračunljiv skup, a \(K_0,...,K_n\) konačan niz lančastih ili cirkularno lančastih kontinuuma koji se sijeku, međusobno ili s \(S\), samo u krajnjim točkama (u slučaju lančastih kontinuuma) ili u jednoj fiksiranoj točki (u slučaju barem jednog cirkularno lančastog kontinuuma). Rezultat primijenjen na lukove i topološke kružnice alternativno iskazujemo koristeći terminologiju adjunkcijskih prostora. Nadalje, definiramo lančasti graf kao topološki prostor koji se može prikazati kao unija konačno mnogo izoliranih točaka i konačno mnogo lančastih kontinuuma takvih da se svaka dva različita kontinuuma sijeku u najviše konačno mnogo točaka. Pokazujemo da pojam lančastog grafa poopćuje pojam topološkog grafa i da je izračunljiv, uvjetno govoreći, svaki onaj lančasti graf koji je poluizračunljiv i čije su krajnje točke izračunljive (što je također vrijedilo i za topološke grafove). Taj se dokaz oslanja na činjenicu da za kontinuum \(K\) lančast od \(a\) do \(b\) i za neki \(c \in K\) te za proizvoljni \(\varepsilon > 0\) postoji netrivijalni kontinuum \(L \subseteq K\) takav da je \(c \in L\) i \(L \subseteq B(c,\varepsilon)\), koju također dokazujemo. Na kraju, tražimo uvjete uz koje se poluizračunljiv skup S može, do na zadanu točnost, aproksimirati nekim svojim izračunljivim podskupom \(\hat{S}\). Dokazujemo da se svaki poluizračunljiv kontinuum \(S\) lančast od \(a\) do \(b\), gdje je \(a\) izračunljiva točka, može po volji dobro aproksimirati nekim svojim izračunljivim potkontinuumom \(\hat{S}\) lančastim od \(a\) do \(c\), gdje je \(c\) izračunljiva točka. U tu svrhu koristimo niz relacija definiranih na skupu \(\mathbb{N}\), a rezultat iskazujemo i u izračunljivom metričkom prostoru koristeći Hausdorffovu metriku.
Sažetak (engleski) Every computable set in an arbitrary computable topological space is also semicomputable, but reverse does not hold in general. Therefore, in this thesis we examine conditions which force a semicomputable set to be a computable one. Topological properties of a set are of a great importance, which means that this thesis belongs to the field of computable analysis, as well as topology. Later, we study the conditions under which every semicomputable set, since it is not computable in general, can be approximated by its computable subset for any given precision. Firstly, we examine chainable and circularly chainable continua and how can they impact computable sets. Actually, we show that a semicomputable set T in an arbitrary topological space is also computable if \(T = S \cup K_0 \cup \dots \cup K_n\), where \(S\) is a computable set and \(K_0,...,K_n\) a finite sequence of chainable or circularly chainable continua which intersect, one another or S, in endpoints (in case of chainable continua) or in one fixed point (in case of at least one circularly chainable continuum). The result applied to arcs and topological circles is also stated using terminology of adjunction spaces. Furthermore, we define the notion of a chainable graph as a topological space that can be expressed as the union of finitely many isolated points and finitely many chainable continua such that every two of them intersect in at most finitely many points. We show that a chainable graph generalizes a topological graph. Also, we prove that every semicomputable chainable graph with computable endpoints is computable (which is also true for topological graphs). The proof relies on a fact that for given continuum \(K\) chainable from \(a\) to \(b\) and arbitrary \(c \in K\) and \(\varepsilon > 0\), there exists a nontrivial continuum \(L \subseteq K\) such that \(c \in L\) and \(L \subseteq B(c,\varepsilon)\). We also prove the aforementioned statement. Finally, we examine the conditions under which a semicomputable set \(S\) can be, up to an arbitrary precision, approximated by some computable subset \(\hat{S}\). We prove that every semicomputable continuum \(S\) chainable from \(a\) to \(b\), where \(a\) is a computable point, can by approximated good enough with some computable subcontinuum \(\hat{S}\) chainable from \(a\) to \(c\), where \(c\) is a computable point. For that purpose we use relations defined on \(\mathbb{N}\), and we state the previous result using Hausdorff metric, as well.
Ključne riječi
izračunljiv topološki prostor
lančasti kontinuum
cirkularno lančasti kontinuum
adjunkcijski prostor
izračunljiv tip
lančasti graf
\(\mathscr{U}\)–blizu
Ključne riječi (engleski)
computable topological space
chainable continuum
circularly chainable continuum
adjunction space
computable type
chainable graph
\(\mathscr{U}\)–close
Jezik hrvatski URN:NBN urn:nbn:hr:217:528268 Datum promocije 2023 Studijski program Naziv: Matematika Vrsta resursa Tekst Opseg viii, 94 str. Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2023-12-20 12:24:09
