Izračunljivost u euklidskom prostoru

master's thesis

• Author: Renato Babojelić
• Mentor: Zvonko Iljazović (mentor)
• Committee member: Zvonko Iljazović (predsjednik povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Filip Najman (član povjerenstva)
• Committee member: Matija Kazalicki (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-03-03, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U radu se proučava izračunljivost metričkih prostora i skupova u metričkim prostorima. Uvode se pojmovi izračunljive točke i izračunljivog niza. Pokazuje se da je euklidski prostor izračunljiv metrički prostor. Definiramo izračunljiv skup izračunljivog metričkog prostora i rekruzivno prebrojiv skup u takvom prostoru. Dolazimo do rezultata kako je svaki izračunljiv skup rekurzivno prebrojiv, te kako svaki rekurzivno prebrojiv, neprazan i potpun skup sadrži gust izračunljiv niz. Promatramo prostor kompaktnih skupova \((\mathscr{K}, d_{H})\) nekog izračunljivog metričkog prostora \((X, d, \alpha)\) uz Hausdorffovu metriku. Pokazujemo kako je \((\mathscr{K}, d_{H}, \Lambda)\) jedan izračunljiv metrički prostor, te kako su svi izračunljivi skupovi u prostoru \((X, d, \alpha)\) upravo izračunljive točke prostora \((\mathscr{K}, d_{H}, \Lambda)\) i obratno.

Abstract (english)

The thesis examines the computability of metric spaces and sets in metric spaces. We introduce the terms of computable point and computable sequence. We prove the Euclidean space is a computable metric space. Furthermore, we define a computable set in a computable metric space and recursively computable set in such a space. We go to prove that every computable set is recursively enumerable and every recursively enumerable, non-empty and complete set contains a dense computable sequence. Further we go to examine a space of compact sets \((\mathscr{K}, d_{H})\) of a computable metric space \((X, d, \alpha)\) considering Hausdorff metric. We show \((\mathscr{K}, d_{H}, \Lambda)\) is a computable metric space, and that all computable metric sets of \((X, d, \alpha)\) space are exactly the computable points of \((\mathscr{K}, d_{H}, \Lambda)\), and that the converse also holds.

• Keywords: metrički prostori; izračunljiva točka; izračunljivi niz; euklidski prostor; rekurzivno prebrojiv skup; Hausdorffova metrika
• Keywords (english): metric spaces; computable point; computable sequence; Eucledean space; recursively enumerable set; Hausdorff metric
• Language: croatian
• URN:NBN: urn:nbn:hr:217:775307
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-03-01 13:16:33