Bakalářská práce

Algoritmy pro výpočet Smithova normálního tvaru

Algorithms for computing the Smith normal form

Jan Plhák
Anotace

V této bakalářské práci se věnujeme algoritmům pro výpočet Smithova normálního tvaru celočíselných matic, který nalézá uplatnění například při řešení soustav celočíselných rovnic nebo při počítání simpliciálních homologií. Protože v průběhu výpočtu Smithova normálního tvaru můžeme už pro malé matice narazit na problémy s bitovou délkou mezivýsledků, uvádíme zde algoritmus, pro nějž odvozujeme odhad …více

Abstract

In this thesis we study algorithms for computing the Smith normal form of integer matrices which can be used to solve systems of linear Diophantine equations or in the process of computing simplicial homology groups. In the computation of the Smith normal form, even for small matrices, one can easily run into problems with the bit length of intermediate results. For that reason we introduce a refined …více

Klíčová slova
Smithův normální tvar Redukovaný schodovitý tvar Algoritmus Bachovo lemma Čínská zbytková věta Paralelizace Smith normal form Row reduced echelon form Algorithm Bach's lemma Chinese remainder theorem Parallelization
Zadání práce
Náplní práce bude výklad vybraných algoritmů pro výpočet Smithova normálního tvaru celočíselných matic, ideálně efektivního náhodnostního algoritmu nebo deterministického algoritmu běžícího v polynomiálním čase.
Administrativní informace
Práce zkontrolována:
1. 6. 2015 10:37, doc. Lukáš Vokřínek, PhD., učo 43588
Plný text práce
1,6 MB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
22. 6. 2015
Práce byla úspěšně obhájena

Vedoucí

doc. Lukáš Vokřínek, PhD., učo 43588
ÚMS Ústavy PřF MU

Oponent

Mgr. Jaroslav Šeděnka, Ph.D., učo 143135
abs FI MU, PřF MU

Literatura

  • DUMMIT, David Steven a Richard M. FOOTE. Abstract algebra. 3rd ed. Hoboken, N.J.: John Wiley & Sons, 2004, xii, 932 s. ISBN 0-471-43334-9.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Matematika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.