dc.contributor.advisor | Švejdar, Vítězslav | |
dc.creator | Tejkalová, Natálie | |
dc.date.accessioned | 2017-05-15T14:17:18Z | |
dc.date.available | 2017-05-15T14:17:18Z | |
dc.date.issued | 2013 | |
dc.identifier.uri | http://hdl.handle.net/20.500.11956/51943 | |
dc.description.abstract | Ačkoli v poslední době byla pozornost upřena především na nový deterministický algoritmus pro testování prvočíselnosti AKS, pravděpodobnostní algoritmy zůstávají efektivním nástrojem pro testování prvočíselnosti. Naše práce se věnuje převážně dvěma nejznámějším probabilistickým algoritmům pro testování prvočíselnosti. Podrobně popisuje princip a důkaz správnosti Solovay- Strassenova a Rabin-Millerova algoritmu. Kromě toho se také pokouší dívat na problematiku pravděpodobnostních testů obecněji. Je představena definice probabilistického algoritmu a různé třídy složitosti odpovídající Monte Carlo či Las Vegas algoritmům. Kromě čistě matematické teorie naznačíme i filosofické aspekty, nad kterými je třeba se při používání pravděpodobnostní metody zamýšlet. Powered by TCPDF (www.tcpdf.org) | cs_CZ |
dc.description.abstract | Attention has been paid mostly to the new deterministic algorithm for primality testing AKS recently. However, probabilistic algorithms remain an efficient tool for primality testing. Our thesis focuses mostly on two most well-known probabilistic algorithms for primality testing. It describes the main idea and gives proofs of correctness of Solovay-Strassen and Rabin-Miller algorithms. Apart from that, it also tries to look at the subject of probabilistic algorithms from a wider perspective. It presents a definition of a probabilistic algorithm and various complexity classes that correspond to Monte Carlo or Las Vegas algorithms. Besides pure mathematical theory, we mention also some philosophical aspects that need to be considered when we decide to use the probabilistic method. Powered by TCPDF (www.tcpdf.org) | en_US |
dc.language | Čeština | cs_CZ |
dc.language.iso | cs_CZ | |
dc.publisher | Univerzita Karlova, Filozofická fakulta | cs_CZ |
dc.subject | Probabilistický algoritmus | cs_CZ |
dc.subject | polynomiální algoritmus | cs_CZ |
dc.subject | prvočíslo | cs_CZ |
dc.subject | Probabilistic algorithm | en_US |
dc.subject | polynomial algorithm | en_US |
dc.subject | prime number | en_US |
dc.title | Probabilistické algoritmy pro prvočíselnost | cs_CZ |
dc.type | bakalářská práce | cs_CZ |
dcterms.created | 2013 | |
dcterms.dateAccepted | 2013-09-19 | |
dc.description.department | Department of Logic | en_US |
dc.description.department | Katedra logiky | cs_CZ |
dc.description.faculty | Faculty of Arts | en_US |
dc.description.faculty | Filozofická fakulta | cs_CZ |
dc.identifier.repId | 124237 | |
dc.title.translated | Probabilistic algorithms for testing primality | en_US |
dc.contributor.referee | Glivický, Petr | |
dc.identifier.aleph | 001626590 | |
thesis.degree.name | Bc. | |
thesis.degree.level | bakalářské | cs_CZ |
thesis.degree.discipline | Logic | en_US |
thesis.degree.discipline | Logika | cs_CZ |
thesis.degree.program | Logika | cs_CZ |
thesis.degree.program | Logic | en_US |
uk.thesis.type | bakalářská práce | cs_CZ |
uk.taxonomy.organization-cs | Filozofická fakulta::Katedra logiky | cs_CZ |
uk.taxonomy.organization-en | Faculty of Arts::Department of Logic | en_US |
uk.faculty-name.cs | Filozofická fakulta | cs_CZ |
uk.faculty-name.en | Faculty of Arts | en_US |
uk.faculty-abbr.cs | FF | cs_CZ |
uk.degree-discipline.cs | Logika | cs_CZ |
uk.degree-discipline.en | Logic | en_US |
uk.degree-program.cs | Logika | cs_CZ |
uk.degree-program.en | Logic | en_US |
thesis.grade.cs | Velmi dobře | cs_CZ |
thesis.grade.en | Very good | en_US |
uk.abstract.cs | Ačkoli v poslední době byla pozornost upřena především na nový deterministický algoritmus pro testování prvočíselnosti AKS, pravděpodobnostní algoritmy zůstávají efektivním nástrojem pro testování prvočíselnosti. Naše práce se věnuje převážně dvěma nejznámějším probabilistickým algoritmům pro testování prvočíselnosti. Podrobně popisuje princip a důkaz správnosti Solovay- Strassenova a Rabin-Millerova algoritmu. Kromě toho se také pokouší dívat na problematiku pravděpodobnostních testů obecněji. Je představena definice probabilistického algoritmu a různé třídy složitosti odpovídající Monte Carlo či Las Vegas algoritmům. Kromě čistě matematické teorie naznačíme i filosofické aspekty, nad kterými je třeba se při používání pravděpodobnostní metody zamýšlet. Powered by TCPDF (www.tcpdf.org) | cs_CZ |
uk.abstract.en | Attention has been paid mostly to the new deterministic algorithm for primality testing AKS recently. However, probabilistic algorithms remain an efficient tool for primality testing. Our thesis focuses mostly on two most well-known probabilistic algorithms for primality testing. It describes the main idea and gives proofs of correctness of Solovay-Strassen and Rabin-Miller algorithms. Apart from that, it also tries to look at the subject of probabilistic algorithms from a wider perspective. It presents a definition of a probabilistic algorithm and various complexity classes that correspond to Monte Carlo or Las Vegas algorithms. Besides pure mathematical theory, we mention also some philosophical aspects that need to be considered when we decide to use the probabilistic method. Powered by TCPDF (www.tcpdf.org) | en_US |
uk.file-availability | V | |
uk.publication.place | Praha | cs_CZ |
uk.grantor | Univerzita Karlova, Filozofická fakulta, Katedra logiky | cs_CZ |
dc.identifier.lisID | 990016265900106986 | |