Bezestrojová charakterizace polynomiálně počitatelných funkcí
Název práce v češtině: | Bezestrojová charakterizace polynomiálně počitatelných funkcí |
---|---|
Název v anglickém jazyce: | Machine-Free Characterization of Polynomially Computable Functions |
Klíčová slova: | Polynomiální čas, rekurze, Cobham |
Klíčová slova anglicky: | Polynomial time, recursion, Cobham |
Akademický rok vypsání: | 2013/2014 |
Typ práce: | bakalářská práce |
Jazyk práce: | čeština |
Ústav: | Katedra logiky (21-KLOG) |
Vedoucí / školitel: | doc. RNDr. Vítězslav Švejdar, CSc. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 09.06.2014 |
Datum zadání: | 09.06.2014 |
Schválení administrátorem: | zatím neschvalováno |
Datum potvrzení stud. oddělením: | 16.06.2014 |
Datum a čas obhajoby: | 14.09.2016 09:00 |
Datum odevzdání elektronické podoby: | 15.08.2016 |
Datum proběhlé obhajoby: | 14.09.2016 |
Odevzdaná/finalizovaná: | odevzdaná studentem a finalizovaná |
Oponenti: | Mgr. Jonathan Verner, Ph.D. |
Zásady pro vypracování |
Pojem polynomiálně počitatelné funkce je intuitivně poměrně jasný: funkce je polynomiálně počitatelná, jestliže ji počítá algoritmus, který pro zpracování libovolného vstupu vystačí s počtem kroků, který je omezen polynomem v délce onoho vstupu. Exaktní definice je ale ne tak jasná, neboť pro explikaci toho, jak se počítají ony kroky a čeho kroky to jsou, je nutný nějaký výpočtový model, například Turingovy stroje. Je ale zajímavé, že existuje i "bezestrojová" charakterizace tohoto pojmu, která je podobná definici primitivně rekurzívních funkcí. Tomuto tématu jsou věnovány články [1] a [2].
Vypracujte vlastní verzi výkladu této problematiky. Rozmyslete si obsah článku [1], doplňte všechny vynechané detaily a udělejte si vlastní názor na to, zda a jaký účel onen článek splnil. Podle vlastní úvahy případně porovnejte články [1] a [2]. Použijte, ovšem s korektní citací, cokoliv z [3]. Vypracujte teorii polynomiálně počitatelných funkcí ve stylu teorie primitivně rekurzívních funkcí. K [3] případně přidejte důkaz nebo náznak důkazu, že bezestrojová definice je ekvivalentní definici založené například na Turingových strojích. |
Seznam odborné literatury |
[1] S. Bellantoni, S. Cook. A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2:297-110, 1992.
[2] A. Cobham. The Intrinsic Computational Difficulty of Functions, in: Proc. Logic, Methodology, and Philosophy of Science II, Y. Bar-Hillel ed., pp. 24-30. North Holland, 1965. [3] P. Mach. Bezestrojová charakterizace funkcí počitatelných v polynomiálním čase. Předběžná verze nefinalizované ročníkové práce. Katedra logiky FF UK, 1998. |