Bezestrojová charakterizace polynomiálně počitatelných funkcí
Machine-Free Characterization of Polynomially Computable Functions
bakalářská práce (NEOBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/86061Identifikátory
SIS: 184421
Kolekce
- Kvalifikační práce [23727]
Autor
Vedoucí práce
Oponent práce
Verner, Jonathan
Fakulta / součást
Filozofická fakulta
Obor
Logika
Katedra / ústav / klinika
Katedra logiky
Datum obhajoby
19. 6. 2017
Nakladatel
Univerzita Karlova, Filozofická fakultaJazyk
Čeština
Známka
Neprospěl
Klíčová slova (česky)
Polynomiální čas, rekurze, CobhamKlíčová slova (anglicky)
Polynomial time, recursion, CobhamPrá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. 1
This 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