Binarni RAM--strojevi

master's thesis

• Title (english): Binary RAM-machines
• Author: Jurica Miletić
• Mentor: Vedran Čačić (mentor)
• Committee member: Vedran Čačić (predsjednik povjerenstva)
• Committee member: Filip Najman (član povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Josip Tambača (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-12-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U početku rada smo definirali binarni RAM-stroj i svojstvo binarne BRAM-izračunljivosti za totalne brojevne funkcije. Zatim smo definirali pojam vremenske složenosti za totalne BRAM-algoritme i za funkcije koje oni računaju. Zatim smo radi pojednostavljenja računanja definirali pojmove binmakro-stroj i vanjsku vremensku složenost kako bismo lakše dokazali polinomnu BRAM-izračunljivost totalnih brojevnih funkcija. Zatim smo pomoću postupka spljoštenja pokazali vezu između izračunavanja s binmakro-programima i BRAM-programima. Definiranjem makroa izgradili dovoljno složene programske cjeline kako bismo na kraju izgradili makro-algoritme polinomne vremenske složenosti čija spljoštenja računaju totalne brojevne funkcije zbrajanja i množenja za mjesnosti k >_ 2 iz čega slijedi zbog dokazanih tvrdnji da su one polinomno BRAM-izračunljive.

Abstract (english)

In the beginning of this thesis we defined binary RAM-machine and the property of binary RAM-computability for total natural number functions. Then we defined the term time complexity for total BRAM-algorithms and also for the functions they compute. Then, for the sake of simplifying computation, we defined terms binmacro-machine and outer time complexity so we could more easily prove polynomial BRAM-computability of total natural number functions. Then with the help of flattening procedure we showed the connection between the computation with binmacro-programs and BRAM-programs. By defining macros, we built fairly complex programming units so we could build macro-algorithms of polynomial time complexity whose flattenings compute total number functions of addition and multiplication of arities k >_ 2 from which follows, with proven statements, that they are polynomially BRAM-computable.

• Keywords: binarni RAM-stroj; BRAM-program; totalni BRAM-algoritmi
• Keywords (english): binary RAM-machine; BRAM-program; total BRAM-algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:217:370882
• 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: 2021-02-23 10:45:31