|
|
Test Rabina-Millera a volba báze
Franců, Martin ; Simon, Petr (vedoucí práce) ; Čunát, Vladimír (oponent)
Práce se zabývá různými způsoby volby báze v Rabinově-Millerově testu. V teoretické části je učiněn krátký přehled prvočíselných testů podobných Rabinovu-Millerovu testu a je dokázáno několik tvrzení o struktuře množiny sil- ných lhářů v multiplikativní grupě. Vybrané netradiční volby báze jsou otestovány na množině lichých složených čísel od 100 do 200 000 000 a výsledky jsou porov- nány s výsledky při obvyklé volbě báze. Je vyslovena domněnka o vylepšení testu prostřednictvím používání bází určitého tvaru vzhledem k testovanému číslu. Sou- částí práce je také program, který implementuje posuzované způsoby volby báze. Tento program umožňuje uživateli pohodlné srovnávání výsledků testů s různými způsoby volby báze. V druhé části práce je dokumentace programu. 1 Seznam tabulek 2.1 Výsledky testů s různými volbami báze na testovací množině. . . . 19 2.2 Výsledky testů s různými volbami báze na spsp(2,3,5) < 101 2 z článku [7]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Typy zpráv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1 Třídy hledačů bází. . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Názvy a funkce reportérů. . . . . . . . . . . . . . . . . . . . . . . 33 2 Seznam obrázků 2.1 Hustota lhářů v závislosti na poměru lháře ku testovanému...
|
|
|
Datové struktury pro různá rozdělení dat
Čunát, Vladimír ; Koubek, Václav (vedoucí práce) ; Mareš, Martin (oponent)
Práce se zabývá studiem problému predchudce, kde datová struktura udržuje dynamickou usporádanou množinu klícu. Krome prehledu nejduležitejších publikovaných výsledku ukazujeme podrobný popis konkrétní možnosti, jak lze docílit pravdepodobnostní úpravy van Emde Boasovy struktury. Tato úprava snižuje pametovou nárocnost na optimum, akorát stejné casové složitosti (log logN) již není dosahováno v nejhorším prípade, ale v amortizovaném ocekávaném prípade. Nejlepší ocekávaná amortizovaná složitost dosahovaná na tríde (s ; s1-d)-hladkých distribucí je rovna O(log log n). Kombinací známých technik dostáváme novou datovou strukturu, která dosahuje stejné složitosti, ale na širší tríde distribucí než bylo doposud možné. Navíc lze jako podstrukturu využít optimální amortizované rešení problému navržené Beamem a Fichem, což zarucí omezení amortizované složitosti nové struktury na asymptoticky optimální hodnotu rovnou p(log n/ log log n).
|
|
|
Test Rabina-Millera a volba báze
Franců, Martin ; Simon, Petr (vedoucí práce) ; Čunát, Vladimír (oponent)
Práce se zabývá různými způsoby volby báze v Rabinově-Millerově testu. V teoretické části je učiněn krátký přehled prvočíselných testů podobných Rabinovu-Millerovu testu a je dokázáno několik tvrzení o struktuře množiny sil- ných lhářů v multiplikativní grupě. Vybrané netradiční volby báze jsou otestovány na množině lichých složených čísel od 100 do 200 000 000 a výsledky jsou porov- nány s výsledky při obvyklé volbě báze. Je vyslovena domněnka o vylepšení testu prostřednictvím používání bází určitého tvaru vzhledem k testovanému číslu. Sou- částí práce je také program, který implementuje posuzované způsoby volby báze. Tento program umožňuje uživateli pohodlné srovnávání výsledků testů s různými způsoby volby báze. V druhé části práce je dokumentace programu. 1 Seznam tabulek 2.1 Výsledky testů s různými volbami báze na testovací množině. . . . 19 2.2 Výsledky testů s různými volbami báze na spsp(2,3,5) < 101 2 z článku [7]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Typy zpráv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1 Třídy hledačů bází. . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Názvy a funkce reportérů. . . . . . . . . . . . . . . . . . . . . . . 33 2 Seznam obrázků 2.1 Hustota lhářů v závislosti na poměru lháře ku testovanému...
|
|
|
Datové struktury pro různá rozdělení dat
Čunát, Vladimír ; Koubek, Václav (vedoucí práce) ; Mareš, Martin (oponent)
Práce se zabývá studiem problému predchudce, kde datová struktura udržuje dynamickou usporádanou množinu klícu. Krome prehledu nejduležitejších publikovaných výsledku ukazujeme podrobný popis konkrétní možnosti, jak lze docílit pravdepodobnostní úpravy van Emde Boasovy struktury. Tato úprava snižuje pametovou nárocnost na optimum, akorát stejné casové složitosti (log logN) již není dosahováno v nejhorším prípade, ale v amortizovaném ocekávaném prípade. Nejlepší ocekávaná amortizovaná složitost dosahovaná na tríde (s ; s1-d)-hladkých distribucí je rovna O(log log n). Kombinací známých technik dostáváme novou datovou strukturu, která dosahuje stejné složitosti, ale na širší tríde distribucí než bylo doposud možné. Navíc lze jako podstrukturu využít optimální amortizované rešení problému navržené Beamem a Fichem, což zarucí omezení amortizované složitosti nové struktury na asymptoticky optimální hodnotu rovnou p(log n/ log log n).
|
|
|
Moderní metody fraktální komprese obrazu
Čunát, Vladimír ; Senft, Martin (oponent) ; Dvořák, Tomáš (vedoucí práce)
V předložené práci studujeme metody fraktální komprese obrazu. Jsou zde rozebrány základní používané techniky, publikovaná rozšíření a jsou navržena a implementována drobná vylepšení stávajících metod. Dále je představen modulární systém umožňující vyměřování různých variant jednotlivých částí kompresního procesu a zjednodušující tak porovnání účinnosti různých algoritm. Nově navržená vylepšení jsou vyhodnocena na testovacích obrázcích. Pedstavená penalizační metoda dosahuje vyšších kvalit dekomprimovaných obrázků. Diferenční kódování v kombinaci s přeuspořádáním cílových blok snižuje nároky na prostor okolo 5%. Predikce implementovaná pomocí KD-stromů se naopak ukázala jako nepříliš účinná v porovnání s článkem používajícím jinou datovou strukturu.
|
host ::
RSS.