Binarni RAM--strojevi

diplomski rad

• Naslov (engleski): Binary RAM-machines
• Autor: Jurica Miletić
• Mentor: Vedran Čačić (mentor)
• Član povjerenstva: Vedran Čačić (predsjednik povjerenstva)
• Član povjerenstva: Filip Najman (član povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Član povjerenstva: Josip Tambača (č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: 2020-12-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: binarni RAM-stroj; BRAM-program; totalni BRAM-algoritmi
• Ključne riječi (engleski): binary RAM-machine; BRAM-program; total BRAM-algorithms
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:370882
• 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: 2021-02-23 10:45:31