|
New algorithm for spectral factorization and its application in signal processing
Ježek, Jan ; Hromčík, Martin ; Šebek, Michael
In this report a new algorithm is presented for the spectral factorization of a two-sided symmetric polynomial. The method is based on the discrete Fourier transform theory (DFT) and its relationship to the Z-transform. Involving DFT computational techniques, namely the famous fast Fourier transform routine (FFT), brings high computational efficiency and reliability. The power of the proposed procedure is employed in a particular practical signal processing application.
|
|
Výpočet triangulace s minimální váhou (MWT)
Charvát, Pavel ; Kolingerová, Ivana (vedoucí práce) ; Ferko, Andrej (oponent)
Pro výpočet MWT už dlouhou dobu není znám žádný polynomiální algoritmus a ani se neví, zda je NP. Tento stav zůstává podle našich zdrojů stále neznámý. V práci uvádíme přehled možných přístupů k problému, jako jsou modifikace zadání se známou složitostí nebo hledání nejrůznějších heuristik a aproximací, umožňujících v rozumném čase najít přesné nebo alespoň přibližné řešení, a porovnáváme jejich kvalitu v konkrétních situacích. Hlavní částí je popis a implementace efektivní heuristiky s (téměř?) lineární očekávanou složitostí pro rovnoměrně rozložené body v konvexní oblasti. Algoritmus modifikuje Drysdalův algoritmus hledání kandidátních hran GT a Beuroutiho výpočet modifikovaného LMT-skeletonu, u kterého navíc doplňujeme důkazy správnosti. MWT dokončíme z grafu kandidátních hran v O(n · d3 + n · d2+k), kde d je maximální stupeň vrcholu a k je největší počet vnitřních komponent nějaké stěny skeletonu. Dále navrhujeme novou aproximaci s polynomiální složitostí a (téměř?) lineární očekávanou složitostí, která se jen zřídka liší od optimální triangulace, a lze dokázat její nejhorší možný aproximační faktor O(1). Aproximace kombinuje heuristiku modifikovaného LMT-skeletonu s omezenou quasi-greedy triangulací a s triangulací minimální kostry. Minimální triangulace nakonec aplikujeme v praktickém problému výpočtu...
|
| |
|
Testování perfektních mocnin
Straková, Hana ; Jedlička, Přemysl (oponent) ; Stanovský, David (vedoucí práce)
Perfektní mocnina je takové přirozené číslo, které lze zapsat jako netriviální mocninu jiného přirozeného čísla. Přirozené číslo n tedy nazveme perfektní mocninou, pokud existují přirozená čísla x a k, obě větší než 2, taková, že n = x^k. Testy, zda je číslo perfektní mocnina, jsou důležité pro faktorizaci čísel nebo testy prvočíselnosti, které samy neumějí rozlišit, zda je vstupní číslo mocnina jiného čísla. Tato práce pojednává o dvou algoritmech na testování perfektních mocnin, prvním od E.Bacha & J. Sorensona a druhém od Daniela J. Bernsteina. Cílem práce je implementace algoritmů v jazyce C s pomocí knihovny GMP, srovnání teoretických výsledků pro jednotlivé algoritmy s praktickými měřeními a porovnání algoritmů mezi sebou z hlediska teoretického přístupu a rychlosti.
|
| |
| |
|
Gröbnerovy báze
Petržilková, Lenka ; Žemlička, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
V této práci si nejprve připomeneme základní Buchbergerův algoritmus pro výpočet Gröbnerovy báze nad komutativními polynomiálními okruhy. Zabýváme se také jednoznačností Gröbnerovy báze pro daný ideál. Dále zkoumáme méně známý, ale pro některé případy efektivnější Faugèreův F4 algoritmus. V závěru první kapitoly tyto dva algoritmy porovnáme. V druhé kapitole rozebereme zobecnění Buchbergerova algoritmu pro nekomutativní okruhy a to jak pro volné tak pro faktorové algebry. Na rozdíl od komu- tativního případu zde mohou mít i konečně generované ideály nekonečné Gröbnerovy báze. Mimo jiné zde zkoumáme tzv. kvazi-nuly, tj. prvky, ze kte- rých přenásobením libovolným termem vznikne nula, a jejich roli při redukci polynomu množinou. 1
|
|
Kvadraturní a kubaturní formule pro funkce s vysokou oscilací
Gregor, Luděk ; Najzar, Karel (oponent) ; Kofroň, Josef (vedoucí práce)
V předložené práci studujeme metody aproximující hodnotu určitého integrálu funkcí s vysokou oscilací. Využíváme v praxi obvyklého tvaru zkoumaných funkcí, vyskytující se například u Fourierovových řad a Fourierova integrálu, kde je integrována funkce součinem rychle oscilující a obecně neoscilující funkce. Přirozenou cestou je aprosimace neoscilující funkce tak, abychom dostali součin funkcí, jež je snadno analyticky integrovatelný. Typickou volbou jsou funkce, které jsou spojité a po částech polynomiální. Dále je možné aplikovat Möbiův inverzní vzorec na Poissonovu sumační formuli. Zmiňujeme metody využívající teorii ortogonálních polynomů. Pro dvojný integrál s jedním nedegenerovaným stacionárním bodem využíváme asymptotického rozvoje.
|
| |
|
Softwarová podpora výuky kryptosystémů založených na problému faktorizace velkých čísel
Vychodil, Petr ; Martinásek, Zdeněk (oponent) ; Burda, Karel (vedoucí práce)
Tato diplomová práce se zabývá softwarovou podporou výuky asymetrických šifrovacích algoritmů, založených na problematice faktorizace velkých čísel. Byl vytvořen vzorový program, který umožňuje provádět operace spojené se šifrováním a dešifrováním s interaktivním ovládáním, s jehož pomocí lze jednoduchým způsobem pochopit princip šifrovací metody RSA. V kapitolách 1 a 2 je rozebrána problematika šifrovacích algoritmů všeobecně. Kapitoly 3 - 5 se již podrobně věnují problematice šifrovacího algoritmu RSA, principům získání, správy a použití šifrovacích klíčů. Kapitola 5 popisuje možnosti zvolení vhodné technologie pro vytvoření konečného softwarového produktu, která by umožňovala vhodným způsobem prezentovat vlastnosti tohoto rozšířeného šifrovacího algoritmu RSA. Konečným softwarovým produktem je java aplet, popsán v kapitole 6 a 7, který je rozdělen na teoretickou a praktickou část. Teoretická sekce prezentuje všeobecné informace o šifrovacím algoritmu RSA. V praktické části si uživatelé programu vyzkouší vlastní výpočetní úkony spojené s algoritmem RSA. Informace získané uživatelem v různých sekcích programu jsou dostačující k pochopení principu fungování tohoto algoritmu.
|
host ::
