Izračunljivost na skupovima Z, Q, R i C

diplomski rad

• Autor: Ivan Posavčević
• Mentor: Vedran Čačić (mentor)
• Član povjerenstva: Vedran Čačić (predsjednik povjerenstva)
• Član povjerenstva: Goranka Nogo (član povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Marko Vrdoljak (č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: 2016-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Rad je logički podijeljen u dva poglavlja. Prvo poglavlje "Prebrojiva izračunljivost" počinje osnovnim konceptima i pojmovima vezanima uz izračunljivost na \(\mathbb{N}\). Koristeći te pojmove i koncepte, uvode se analogni pojmovi za prebrojive nadskupove od \(\mathbb{N}\) i detaljno dokazuje izračunljivost određenih funkcija. Govori se o pojmu dimenzije skupa i prikazu nadskupova od \(\mathbb{N}\) pomoću prirodnih brojeva. Glavni rezultat poglavlja predstavlja dokaz izračunljivoga analogona teorema o dijeljenju s ostatkom. Drugo poglavlje "Neprebrojiva izračunljivost" detaljno pokriva temelje izračunljivosti na \(\mathbb{R}\) i jedan primjer izračunljivosti na \(\mathbb{C}\). Značajna razlika u odnosu na prethodno poglavlje leži u prikazu realnoga broja, što donosi velik zaokret u pristupu problemu izračunljivosti. Međutim, obilato se koriste pojmovi iz prethodnoga poglavlja i time se ova dva različito motivirana pristupa stapaju u koherentnu cjelinu. Glavni rezultat cijeloga rada dokaz je izračunljivosti rješenja kvadratne jednadžbe. Budući da je rad napisan u formi skripte, mogao bi poslužiti u slučaju pojave (izbornih) kolegija vezanih uz ovu temu.

Sažetak (engleski)

This thesis is logically divided into two chapters. The first chapter ”Countable computability” starts with basic concepts and terms associated with computability on \(\mathbb{N}\). Using these concepts and terms, there are introduced analogous terms for countable supersets of \(\mathbb{N}\) and detail proven the computability of certain functions. It is spoken about the term of set dimension and the representation of supersets of \(\mathbb{N}\) using the natural numbers. The main result of the chapter is the proof of computable analogue of the reminder theorem. The second chapter ”Uncountable computability” covers the foundations of computability on \(\mathbb{R}\) and one example of computability on \(\mathbb{C}\) in detail. The significant difference in comparison to the previous chapter lies in representation of the real number, which brings a big turnaround in the approach to the problem of computability. However, terms from discrete case are used profusely and in that way these two differently motivated approaches are merged into a coherent unit. The main result of the whole thesis is the proof of computability of quadratic equation’s solutions. Since the thesis is written in the form of scripts, it could be used in the case of appearance of (elective) courses associated with this topic.

• Ključne riječi: prebrojiva izračunljivost; dokaz izračunljivoga analogona teorema o dijeljenju s ostatkom; neprebrojiva izračunljivost; dokaz izračunljivosti rješenja kvadratne jednadžbe
• Ključne riječi (engleski): countable computability; proof of computable analogue of the reminder theorem; uncountable computability; proof of computability of quadratic equation’s solutions
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:822190
• 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-01-30 10:43:41