Algebraické struktury v teoretické informatice

Garant předmětu:

Edita Pelantová, Severin Pošta

Přednášející:

Severin Pošta, Milena Svobodová

Cvičící:

Severin Pošta, Milena Svobodová

Předmět zajišťuje:

katedra matematiky

Anotace:

Předmět je věnován některým algebraickým strukturám. Zaměřuje se na Gröbnerovy báze ideálů okruhů polynomů a na jejich použití při řešení soustav algebraických rovnic a jejich další praktické aplikace a na celočíselné okruhy v algebraických tělesech, které se využívají k různým reprezentacím čísel s cílem návrhu efektivních algoritmů pro aritmetické operace a evaluaci elementárních funkcí.

Požadavky:

Znalosti základů obecné algebry (01ALGE) a algebraické teorie čísel (01TC).

Osnova přednášek:

1) Gröbnerovy báze v okruzích polynomů více proměnných

2) Ideály v okruzích polynomů více proměnných, báze ideálu

3) Uspořádání monomů, přepisování

4) Buchbergerův algoritmus

5) Řešení soustav polynomiálních rovnic, barvení grafů, automatické dokazování

6) Jednoznačné poziční reprezentace s celočíselnými bázemi v okruhu celých čísel Z a v okruhu gaussovských celých čísel, NAF reprezentace, aritmetické operace v těchto soustavách a konečné automaty.

7) Redundantní reprezentace v reálném a komplexním oboru, paralelní algoritmy pro sčítání a odčítání a vztah k míře redundance, on-line algoritmy pro násobení a dělení.

8) Reprezentace čísel pro „posuň a sečti“ algoritmy k výpočtu hodnot elementárních funkcí.

Osnova cvičení:

V oblasti okruhů polynomů je cvičení zaměřeno na konstrukci Gröbnerových bází konkrétně zadaných ideálů.

V oblasti číslených soustav je cvičení zaměřeno zejména na hledání reprezentace čísel v různých soustavách, algorimty pro aritmetické operace v redundantní soustavě a na optimalizaci parametrů pro zadanou bázi. Studenti také prezentují řešení teoretických i praktických úloh, které jim byly zadány individuálně.

Cíle studia:

Naučit se manipulovat s ideály okruhů polynomů několika proměnných, konstruovat Gröbnerovy báze těchto ideálů. Naučit se pracovat s různými číselnými reprezentacemi a využívat je ke konstrukci algoritmů pro rychlé počítání aritmetických operací a vyčíslování elementárních funkcí.

Studijní materiály:

[1] Jean-Michel Muller, Elementary Functions: Algorithms and Implementation, 3rd ed., Birkhauser 2016

[2] Michel Rigo, Formal languages, Automata and Numeration systems, Wiley, 2014

[3] David Stanovský, Libor Barto: Počítačová algebra, Matfyzpress 2017

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Matematická informatika (volitelný předmět)