Izračunljivost u euklidskom prostoru

diplomski rad

• Autor: Renato Babojelić
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Zvonko Iljazović (predsjednik povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Član povjerenstva: Filip Najman (član povjerenstva)
• Član povjerenstva: Matija Kazalicki (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2017-03-03, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: metrički prostori; izračunljiva točka; izračunljivi niz; euklidski prostor; rekurzivno prebrojiv skup; Hausdorffova metrika
• Ključne riječi (engleski): metric spaces; computable point; computable sequence; Eucledean space; recursively enumerable set; Hausdorff metric
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:775307
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-03-01 13:16:33