Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Algebraické struktury v teoretické informatice

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01ALTI ZK 3 1+1 česky
Přednášející:
Severin Pošta (gar.), Milena Svobodová
Cvičící:
Severin Pošta (gar.), 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 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 17. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3947206.html