Original title:
Bezestrojová charakterizace polynomiálně počitatelných funkcí
Translated title:
Machine-Free Characterization of Polynomially Computable Functions
Authors:
Profeld, Michal ; Švejdar, Vítězslav (advisor) ; Verner, Jonathan (referee) Document type: Bachelor's theses
Year:
2017
Language:
cze Abstract:
[cze][eng] Práce se zabývá bezestrojou definicí polynomiálních funkcí. Hlavním cílem je čtenáře obeznámit nejen s touto definicí, ale i s ostatními důležitými pojmy této práce. Nejdůležitějšími pojmy je myšleno: základní funkcem, schéma skládání funkcí, rekuzivní schémata a polynomiální podmínky. Během práce bude čtenář mimo jiné svědkem odvození nejznámějších polynomiálně ome- zených funkcí, jako jsou násobení, sčítání, nebo jiné aritmetické funkce. Od- vozeny však budou i zajímavější a netradiční funkce, jako je funkce smash, nebo mocnění v prostoru Zn. 1This thesis focuses on machine-free definition of polynomial functions. The main goal is to not only make the readers familiar with this de- finition, but also to introduce them to the other pivotal terms of this thesis. The other pivotal terms are: basic functions, function composi- tion, recursive schemes a polynomial conditions. Throughout the thesis the readers will be introduced, among other things, to derivation of the most used polynomially bounded functions, like multiplication, addi- tion, or other arithmetic functions. 1
Keywords:
Cobham; Polynomial time; recursion; Cobham; Polynomiální čas; rekurze
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/86061