Název:
Bezestrojová charakterizace polynomiálně počitatelných funkcí
Překlad názvu:
Machine-Free Characterization of Polynomially Computable Functions
Autoři:
Profeld, Michal ; Švejdar, Vítězslav (vedoucí práce) ; Verner, Jonathan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2017
Jazyk:
cze
Abstrakt: [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
Klíčová slova:
Cobham; Polynomiální čas; rekurze; Cobham; Polynomial time; recursion