Název: | Některé algoritmy pro prvočíselné rozklady |
Další názvy: | Some methods for integer factorization |
Autoři: | Šuster, Zdeněk |
Vedoucí práce/školitel: | Honzík Lukáš, PhDr. Ph.D. |
Datum vydání: | 2019 |
Nakladatel: | Západočeská univerzita v Plzni |
Typ dokumentu: | diplomová práce |
URI: | http://hdl.handle.net/11025/39197 |
Klíčová slova: | prvočíslo;prvočíselný rozklad;faktorizace dělením;pollardův rho algoritmus;pollardův p-1 algoritmus;eulerova metoda |
Klíčová slova v dalším jazyce: | prime number;integer factorization;trial factorization;pollard´s rho algorithm;pollard´s p-1 algorithm;euler´s method |
Abstrakt: | Jedním z cílů této práce je seznámení s prvočíselností a faktorizačních metod. Nejprve je vysvětlen důležitý pojem pro tuto práci, tj. prvočíslo, a také prvočíselný rozklad. Tyto pojmy hrají důležitou roli u faktorizačních metod pro nalezení prvočíselného rozkladu u celých čísel. V druhé kapitole jsou mezi popsanými faktorizačními metodami faktorizace dělením ("hrubá" síla), Pollardův rho algoritmus, Pollardův p - 1 algoritmus a Eulerova metoda. Některé z algoritmů lze využít i pro zvídavé žáky v učitelské praxi. K těmto metodám bylo v následující kapitole vypočteno několik ilustračních příkladů, které se snažili ukázat početní i časovou náročnost těchto algoritmů, ale také jejich možnosti pro zrychlení výpočtu i jejich úskalí. Během výpočtů byla použita řada sofistikovanějších zařízeních pro rychlejší výpočet příkladů, a to stolní kalkulátor TI - 92 Plus či webové prostředí WolframAlpha. Právě časová náročnost je podstatou poslední kapitoly, kde se zabývám pojmy jako složitost algoritmu a třídy složitosti, pomocí kterých můžeme porovnávat algoritmy právě z hlediska času jejich výpočtu. |
Abstrakt v dalším jazyce: | One of the aims of this thesis is to get acquainted with prime numbers and factorization methods. First, an important concept for this thesis, i.e. a prime number, is also explained, as well as a prime quote. These terms play an important role in factorization methods for finding prime numbers in integers. In the second chapter, there are described the following factoring methods: Trial Factorization, Pollard rho algorithm, Pollard p - 1 algorithm and Euler's method. Some of the algorithms can also be used for inquisitive pupils in teaching practice. Several illustrative examples have been computed in these chapters, which have attempted to show both the numerical and time demands of these algorithms, but also their possibilities for speeding up the calculations and their obstacles. During the calculations, a number of more sophisticated devices were used to quickly compute examples, such as the TI - 92 Plus Desktop Calculator and the WolframAlpha Web Environment. Time-consuming is the essence of the last chapter where I deal with concepts such as the complexity of the algorithm and the complexity class, by which we can compare the algorithms precisely in terms of the time of their calculation. |
Práva: | Plný text práce je přístupný bez omezení. |
Vyskytuje se v kolekcích: | Diplomové práce / Theses (KMT) |
Soubory připojené k záznamu:
Soubor | Popis | Velikost | Formát | |
---|---|---|---|---|
Nektere metody pro prvociselne rozklady.pdf | Plný text práce | 1,24 MB | Adobe PDF | Zobrazit/otevřít |
hodnoceni vedouciho DP - Suster.pdf | Posudek vedoucího práce | 27,45 kB | Adobe PDF | Zobrazit/otevřít |
Posudek diplomove prace Suster.pdf | Posudek oponenta práce | 131,17 kB | Adobe PDF | Zobrazit/otevřít |
Suster protokol762.pdf | Průběh obhajoby práce | 306,62 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/39197
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.